org.jgrapht.alg.color

Class GreedyColoring<V,E>

java.lang.Object

org.jgrapht.alg.color.GreedyColoring<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

VertexColoringAlgorithm<V>

Direct Known Subclasses:

LargestDegreeFirstColoring, RandomGreedyColoring, SmallestDegreeLastColoring

public class GreedyColoring<V,E>
extends Object
implements VertexColoringAlgorithm<V>

The greedy coloring algorithm.

The algorithm iterates over all vertices and assigns the smallest possible color that is not used by any neighbors. Subclasses may provide a different vertex ordering.

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

Modifier and Type	Field and Description
protected Graph<V,E>	graph The input graph
protected static String	SELF_LOOPS_NOT_ALLOWED Error message if the input graph contains self-loops.

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
VertexColoringAlgorithm.Coloring<V>	getColoring() Computes a vertex coloring.
protected Iterable<V>	getVertexOrdering() Get the ordering of the vertices used by the algorithm.

Methods inherited from class java.lang.Object

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

Field Detail

SELF_LOOPS_NOT_ALLOWED

protected static final String SELF_LOOPS_NOT_ALLOWED

Error message if the input graph contains self-loops.

See Also:

Constant Field Values

graph

protected final Graph<V,E> graph

The input graph

Constructor Detail

GreedyColoring

public GreedyColoring(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.

Returns:

the ordering of the vertices used by the algorithm

getColoring

public VertexColoringAlgorithm.Coloring<V> getColoring()

Computes a vertex coloring.

Specified by:

getColoring in interface VertexColoringAlgorithm<V>

Returns:

a vertex coloring