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 typeE
- the graph edge type
- All Implemented Interfaces:
VertexColoringAlgorithm<V>
- Direct Known Subclasses:
LargestDegreeFirstColoring
,RandomGreedyColoring
,SmallestDegreeLastColoring
public class GreedyColoring<V,E> extends java.lang.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 Graph<V,E>
graph
The input graphprotected static java.lang.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
All Methods Instance Methods Concrete Methods Modifier and Type Method Description VertexColoringAlgorithm.Coloring<V>
getColoring()
Computes a vertex coloring.protected java.lang.Iterable<V>
getVertexOrdering()
Get the ordering of the vertices used by the algorithm.
-
-
-
Field Detail
-
SELF_LOOPS_NOT_ALLOWED
protected static final java.lang.String SELF_LOOPS_NOT_ALLOWED
Error message if the input graph contains self-loops.- See Also:
- Constant Field Values
-
-
Method Detail
-
getVertexOrdering
protected java.lang.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 interfaceVertexColoringAlgorithm<V>
- Returns:
- a vertex coloring
-
-