Package micycle.pgs.commons

Class RLFColoring<V,E>

java.lang.Object
micycle.pgs.commons.RLFColoring<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
org.jgrapht.alg.interfaces.VertexColoringAlgorithm<V>
public class RLFColoring<V,E> extends Object implements org.jgrapht.alg.interfaces.VertexColoringAlgorithm<V>
The Recursive Largest First (RLF) algorithm for graph coloring.

The RLF algorithm was originally designed by F. Leighton (1979) in A Graph Coloring Algorithm for Large Scheduling Problems, in part for use in constructing solutions to large timetabling problems. It sequentially builds color classes on the basis of greedy choices. In particular, the first vertex placed in a color class C is one with a maximum number of uncolored neighbors, and the next vertices placed in C are chosen so that they have as many uncolored neighbors which cannot be placed in C.

This implementation is based on the original algorithm pseudocode provided in 'A new efficient RLF-like Algorithm for the Vertex Coloring Problem' : "for practical purposes, the RLF algorithm, if programmed properly, exhibits an O(n2) time dependence for many applications".

RLF exhibits similar chromatic performance compared to DSATUR. In 'A Performance Comparison of Graph Coloring Algorithms' RLF tended to produce the best colorings (as measured by color number), marginally ahead of DSATUR.

Improved drop-in replacement heuristics for RLF are explored in 'A new efficient RLF-like Algorithm for the Vertex Coloring Problem' (though most increase runtime complexity).

Author:
Michael Carleton

  • Nested Class Summary

    Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm

    org.jgrapht.alg.interfaces.VertexColoringAlgorithm.Coloring<V extends Object>, org.jgrapht.alg.interfaces.VertexColoringAlgorithm.ColoringImpl<V extends Object>

  • Constructor Summary

    Constructors
    Constructor
    Description
    RLFColoring(org.jgrapht.Graph<V,E> graph)
     
    RLFColoring(org.jgrapht.Graph<V,E> graph, long seed)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    org.jgrapht.alg.interfaces.VertexColoringAlgorithm.Coloring<V>
    getColoring()
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • RLFColoring

      public RLFColoring(org.jgrapht.Graph<V,E> graph)

    • RLFColoring

      public RLFColoring(org.jgrapht.Graph<V,E> graph, long seed)

  • Method Details

    • getColoring

      public org.jgrapht.alg.interfaces.VertexColoringAlgorithm.Coloring<V> getColoring()
      Specified by:
      getColoring in interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm<V>