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|)$.

  • Field Details

  • Constructor Details

    • 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 Details

    • 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
    • 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 refine
      rep - 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 >= 1
      rep - 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 for
      refineStack - the stack containing all colors that have to be refined
      rep - 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 checked
      graph - 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(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 Deque<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