org.jgrapht.alg.color

Class ColorRefinementAlgorithm<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

VertexColoringAlgorithm<V>

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

Color refinement algorithm that finds the coarsest stable coloring of a graph based on a given alpha 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 and 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

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

Methods inherited from class java.lang.Object

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

Constructor Detail

ColorRefinementAlgorithm

public ColorRefinementAlgorithm(Graph<V,E> graph,
                                VertexColoringAlgorithm.Coloring<V> alpha)

Construct a new coloring algorithm.

Parameters:

graph - the input graph

alpha - the coloring on the graph to be refined

ColorRefinementAlgorithm

public ColorRefinementAlgorithm(Graph<V,E> graph)

Construct a new coloring algorithm.

Parameters:

graph - the input graph

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 interface VertexColoringAlgorithm<V>

Returns:

the calculated coloring