Package org.jgrapht.alg.color
Class ColorRefinementAlgorithm<V,E>
- java.lang.Object
-
- org.jgrapht.alg.color.ColorRefinementAlgorithm<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
VertexColoringAlgorithm<V>
public class ColorRefinementAlgorithm<V,E> extends java.lang.Object implements VertexColoringAlgorithm<V>
Color refinement algorithm that finds the coarsest stable coloring of a graph based on a givenalpha
coloring as described in the following paper: C. Berkholz, P. Bonsma, and M. Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory of Computing Systems, 60(4), p581--614, 2017.The complexity of this algorithm is $O((|V| + |E|)log |V|)$.
- Author:
- Christoph GrĂ¼ne, Daniel Mock, Oliver Feith
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm
VertexColoringAlgorithm.Coloring<V>, VertexColoringAlgorithm.ColoringImpl<V>
-
-
Constructor Summary
Constructors Constructor Description ColorRefinementAlgorithm(Graph<V,E> graph)
Construct a new coloring algorithm.ColorRefinementAlgorithm(Graph<V,E> graph, VertexColoringAlgorithm.Coloring<V> alpha)
Construct a new coloring algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description VertexColoringAlgorithm.Coloring<V>
getColoring()
Calculates a canonical surjective k-coloring of the given graph such that the classes of the coloring form the coarsest stable partition that refines alpha.
-
-
-
Constructor Detail
-
ColorRefinementAlgorithm
public ColorRefinementAlgorithm(Graph<V,E> graph, VertexColoringAlgorithm.Coloring<V> alpha)
Construct a new coloring algorithm.- Parameters:
graph
- the input graphalpha
- the coloring on the graph to be refined
-
-
Method Detail
-
getColoring
public VertexColoringAlgorithm.Coloring<V> getColoring()
Calculates a canonical surjective k-coloring of the given graph such that the classes of the coloring form the coarsest stable partition that refines alpha.- Specified by:
getColoring
in interfaceVertexColoringAlgorithm<V>
- Returns:
- the calculated coloring
-
-