N
- Value type that the graph node stores.E
- Value type that the graph edge stores.public abstract class GraphColoring<N,E> extends Object
Annotatable.setAnnotation(Annotation)
and provide
a node to super node mapping with getPartitionSuperNode(Object)
. The
given 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.
Modifier and Type | Class and Description |
---|---|
static class |
GraphColoring.Color
The color of a node
|
static class |
GraphColoring.GreedyGraphColoring<N,E>
Greedily assign nodes with high degree unique colors.
|
Modifier and Type | Field and Description |
---|---|
protected N[] |
colorToNodeMap |
protected AdjacencyGraph<N,E> |
graph |
Constructor and Description |
---|
GraphColoring(AdjacencyGraph<N,E> graph) |
Modifier and Type | Method and 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.
|
protected N[] colorToNodeMap
protected final AdjacencyGraph<N,E> graph
public GraphColoring(AdjacencyGraph<N,E> graph)
public abstract int color()
GraphColoring.Color
objects using
Annotatable.setAnnotation(Annotation)
.public N getPartitionSuperNode(N node)
public AdjacencyGraph<N,E> getGraph()
Copyright © 2009–2023 Google. All rights reserved.