Module org.jgrapht.core

Package 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	Description
protected final Graph<V,E>	graph	The input graph
protected static final String	SELF_LOOPS_NOT_ALLOWED	Error message if the input graph contains self-loops.

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	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 Details

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 Details

GreedyColoring

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

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