Module org.jgrapht.core
Package org.jgrapht.alg.color

Class LargestDegreeFirstColoring<V,E>

java.lang.Object
org.jgrapht.alg.color.GreedyColoring<V,E>
org.jgrapht.alg.color.LargestDegreeFirstColoring<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
VertexColoringAlgorithm<V>
public class LargestDegreeFirstColoring<V,E> extends GreedyColoring<V,E>
The largest degree first greedy coloring algorithm.

This is the greedy coloring algorithm which orders the vertices by non-increasing degree. See the following paper for details.

  • D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85--86, 1967.
Author:
Dimitrios Michail

  • Constructor Details

    • LargestDegreeFirstColoring

      public LargestDegreeFirstColoring(Graph<V,E> graph)
      Construct a new coloring algorithm.
      Parameters:
      graph - the input graph

  • Method Details

    • getVertexOrdering

      protected Iterable<V> getVertexOrdering()
      Get the ordering of the vertices used by the algorithm.
      Overrides:
      getVertexOrdering in class GreedyColoring<V,E>
      Returns:
      the ordering of the vertices used by the algorithm