Package com.google.javascript.jscomp.graph

Class GraphColoring<N,E>

java.lang.Object
com.google.javascript.jscomp.graph.GraphColoring<N,E>
Type Parameters:
N - Value type that the graph node stores.
E - Value type that the graph edge stores.
Direct Known Subclasses:
GraphColoring.GreedyGraphColoring
public abstract class GraphColoring<N,E> extends Object
Annotates the graph with a color in a way that no connected node will have the same color. Nodes of the same color cab then be partitioned together and be represented by a super node. This class will merely annotate the nodes with a color using Annotatable.setAnnotation(Annotation) and provide a node to super node mapping with getPartitionSuperNode(Object). The give graph itself will not be modified.

This algorithm is NOT deterministic by default. Passes that requires deterministic output should provide a Comparator in the constructor as a tie-breaker. This tie-break will be used when deciding which node should be colored first when multiple nodes have the same degree.

  • Field Details

    • colorToNodeMap

      protected N[] colorToNodeMap

    • graph

      protected final AdjacencyGraph<N,E> graph

  • Constructor Details

  • Method Details

    • color

      public abstract int color()
      Annotates the graph with GraphColoring.Color objects using Annotatable.setAnnotation(Annotation).
      Returns:
      The number of unique colors need.

    • getPartitionSuperNode

      public N getPartitionSuperNode(N node)
      Using the coloring as partitions, finds the node that represents that partition as the super node. The first to retrieve its partition will become the super node.

    • getGraph

      public AdjacencyGraph<N,E> getGraph()