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.

## Nested Class Summary

Nested Classes
Modifier and Type
Class
Description
`static class`
`GraphColoring.Color`
`static class`
`GraphColoring.GreedyGraphColoring<N,E>`
Greedily assign nodes with high degree unique colors.

## Field Summary

Fields
Modifier and Type
Field
Description
`protected N[]`
`colorToNodeMap`
`protected final AdjacencyGraph<N,E>`
`graph`

## Constructor Summary

Constructors
Constructor
Description
`GraphColoring(AdjacencyGraph<N,E> graph)`

## Method Summary

Modifier and Type
Method
Description
`abstract int`
`color()`
Annotates the graph with `GraphColoring.Color` objects using `Annotatable.setAnnotation(Annotation)`.
`AdjacencyGraph<N,E>`
`getGraph()`
`N`
`getPartitionSuperNode(N node)`
Using the coloring as partitions, finds the node that represents that partition as the super node.

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

## Field Details

### colorToNodeMap

protected N[] colorToNodeMap

### graph

protected final AdjacencyGraph<N,E> graph

## Constructor Details

### GraphColoring

public GraphColoring(AdjacencyGraph<N,E> graph)

## 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()