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

Class 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 Detail

      • LargestDegreeFirstColoring

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

    • Method Detail

      • 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