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>
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|)$.
-
Nested Class Summary
Nested ClassesNested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm
VertexColoringAlgorithm.Coloring<V>, VertexColoringAlgorithm.ColoringImpl<V>
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionColorRefinementAlgorithm
(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 TypeMethodDescriptioncalculateColorDegrees
(int refiningColor, ColorRefinementAlgorithm<V, E>.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
(Set<Integer> adjacentColors, ColorRefinementAlgorithm<V, E>.ColoringRepresentation rep) Helper method that cleanups the internal representation of color degrees for a new iteration.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
(Set<V> vertices) Returns a coloring such that all vertices have the same (zero) color.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
(Integer color, Deque<Integer> refineStack, ColorRefinementAlgorithm<V, E>.ColoringRepresentation rep) Helper method for splitting up a color.
-
Field Details
-
graph
-
alpha
-
-
Constructor Details
-
ColorRefinementAlgorithm
Construct a new coloring algorithm.- Parameters:
graph
- the input graphalpha
- the coloring on the graph to be refined
-
ColorRefinementAlgorithm
Construct a new coloring algorithm.- Parameters:
graph
- the input graph
-
-
Method Details
-
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 Set<Integer> calculateColorDegrees(int refiningColor, ColorRefinementAlgorithm<V, E>.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(Set<Integer> adjacentColors, ColorRefinementAlgorithm<V, E>.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(Integer color, Deque<Integer> refineStack, ColorRefinementAlgorithm<V, E>.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
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
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
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
-