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

    • 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

      • 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 refine
        rep - 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 >= 1
        rep - 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 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​(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