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

Nested Class Summary

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

VertexColoringAlgorithm.Coloring<V>, VertexColoringAlgorithm.ColoringImpl<V>

Field Summary

Fields inherited from class org.jgrapht.alg.color.GreedyColoring

graph, SELF_LOOPS_NOT_ALLOWED

Constructor Summary

Constructors

Constructor	Description
LargestDegreeFirstColoring(Graph<V,E> graph)	Construct a new coloring algorithm.

Method Summary

Modifier and Type	Method	Description
protected Iterable<V>	getVertexOrdering()	Get the ordering of the vertices used by the algorithm.

Methods inherited from class org.jgrapht.alg.color.GreedyColoring

getColoring

Methods inherited from class java.lang.Object

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

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