Package org.graph4j.coloring

Class RecursiveLargestFirstColoring

java.lang.Object
org.graph4j.SimpleGraphAlgorithm
org.graph4j.coloring.RecursiveLargestFirstColoring
All Implemented Interfaces:
ColoringAlgorithm
public class RecursiveLargestFirstColoring extends SimpleGraphAlgorithm implements ColoringAlgorithm

The RLF algorithm assigns colors to a graph’s vertices by constructing each color class one at a time. It does this by identifying a maximal independent set of vertices in the graph (using various heuristics), assigning these to the same color, and then removing these vertices from the graph. These actions are repeated on the remaining subgraph until no vertices remain. If using the heuristic described in (Lewis, R. (2021). A Guide to Graph Colouring: Algorithms and Applications.) RLF produces exact results for bipartite, cycle, and wheel graphs. RLF was shown to produce significantly better vertex colorings than alternative heuristics, such as DSatur, on random graphs. Having a complexity of O(nm), it is slower than the greedy or DSatur heuristics.

Author:
Cristian Frăsinaru

  • Constructor Details

    • RecursiveLargestFirstColoring

      public RecursiveLargestFirstColoring(Graph graph)

  • Method Details

    • findColoring

      public Coloring findColoring()
      Description copied from interface: ColoringAlgorithm
      In case of exact algorithms, this method should return the optimum coloring, if one can be computed within the alloted time. Otherwise, in case of heuristics or if the time limit is exceeded, it should return the best valid coloring that could be computed.
      Specified by:
      findColoring in interface ColoringAlgorithm
      Returns:
      a valid coloring of the graph.

    • findColoring

      public Coloring findColoring(int numColors)
      Specified by:
      findColoring in interface ColoringAlgorithm
      Parameters:
      numColors - maximum number of colors to be used.
      Returns:
      a coloring of the graph with the specified number of colors, or null if no coloring can be found by this algorithm.