ColorRefinementAlgorithm (JGraphT : a free Java graph library)

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 java.lang.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	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.

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