- 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|)$.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
ColorRefinementAlgorithm.ColoringRepresentation
-
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 Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private java.util.Set<java.lang.Integer>
calculateColorDegrees(int refiningColor, ColorRefinementAlgorithm.ColoringRepresentation rep)
Helper method that calculates the color degree for every vertex and the maximum and minimum color degree for every color.private void
cleanupColorDegrees(java.util.Set<java.lang.Integer> adjacentColors, ColorRefinementAlgorithm.ColoringRepresentation rep)
Helper method that cleanups the internal representation of color degrees for a new iteration.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.private static <V> VertexColoringAlgorithm.Coloring<V>
getDefaultAlpha(java.util.Set<V> vertices)
Returns a coloring such that all vertices have the same (zero) color.private java.util.Deque<java.lang.Integer>
getSortedStack(VertexColoringAlgorithm.Coloring<V> alpha)
Returns a canonically sorted stack of all colors of alpha.private boolean
isAlphaConsistent(VertexColoringAlgorithm.Coloring<V> alpha, Graph<V,E> graph)
Checks whether alpha is a valid surjective l-coloring for the given graphprivate void
splitUpColor(java.lang.Integer color, java.util.Deque<java.lang.Integer> refineStack, ColorRefinementAlgorithm.ColoringRepresentation rep)
Helper method for splitting up a color.
-
-
-
Field Detail
-
alpha
private final VertexColoringAlgorithm.Coloring<V> 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
-
calculateColorDegrees
private java.util.Set<java.lang.Integer> calculateColorDegrees(int refiningColor, ColorRefinementAlgorithm.ColoringRepresentation rep)
Helper method that calculates the color degree for every vertex and the maximum and minimum color degree for every color.- Parameters:
refiningColor
- color to refinerep
- the coloring representation- Returns:
- the list of all colors that have at least one vertex with colorDegree >= 1
-
cleanupColorDegrees
private void cleanupColorDegrees(java.util.Set<java.lang.Integer> adjacentColors, ColorRefinementAlgorithm.ColoringRepresentation rep)
Helper method that cleanups the internal representation of color degrees for a new iteration.- Parameters:
adjacentColors
- the list of all colors that have at least one vertex with colorDegree >= 1rep
- the coloring representation
-
splitUpColor
private void splitUpColor(java.lang.Integer color, java.util.Deque<java.lang.Integer> refineStack, ColorRefinementAlgorithm.ColoringRepresentation rep)
Helper method for splitting up a color.- Parameters:
color
- the color to split the color class forrefineStack
- the stack containing all colors that have to be refinedrep
- the coloring representation
-
isAlphaConsistent
private boolean isAlphaConsistent(VertexColoringAlgorithm.Coloring<V> alpha, Graph<V,E> graph)
Checks whether alpha is a valid surjective l-coloring for the given graph- Parameters:
alpha
- the surjective l-coloring to be checkedgraph
- the graph that is colored by alpha- Returns:
- whether alpha is a valid surjective l-coloring for the given graph
-
getDefaultAlpha
private static <V> VertexColoringAlgorithm.Coloring<V> getDefaultAlpha(java.util.Set<V> vertices)
Returns a coloring such that all vertices have the same (zero) color.- Parameters:
vertices
- the vertices that should be colored- Returns:
- the all-0 coloring
-
getSortedStack
private java.util.Deque<java.lang.Integer> getSortedStack(VertexColoringAlgorithm.Coloring<V> alpha)
Returns a canonically sorted stack of all colors of alpha. It is important that alpha is consistent.- Parameters:
alpha
- the surjective l-coloring- Returns:
- a canonically sorted stack of all colors of alpha
-
-