N
- Value type that the graph node stores.E
- Value type that the graph edge stores.public abstract class Graph<N,E> extends java.lang.Object implements AdjacencyGraph<N,E>
Nodes and edges in the graph can store a piece of data that this graph is
used to represent. For example, a variable interference graph might store a
variable in the node. This piece of data can be accessed with
GraphNode.getValue()
and Graph.GraphEdge.getValue()
.
Algorithms and analysis can annotate information on the nodes and edges
using GraphNode.getValue()
and Graph.GraphEdge.getValue()
. For example,
a graph coloring algorithm can store the color as an annotation. If multiple
analyses are required, it is up to the user of the analysis to save the
annotated solution between passes.
We implemented our own graph data structure (as opposed to using
com.google.common.graph
) for two reasons. First, aside from
the node's label value, we would like to annotate information on the nodes
and edges. Using a map to annotate would introduce too much overhead during
fix point analysis. Also, com.google.common.graph
does not
support labeling of edges. Secondly, not using another external package would
limit our dependencies.
TODO(user): All functionality for removing nodes and edges.
Modifier and Type | Class and Description |
---|---|
private static class |
Graph.AnnotationState
Pseudo typedef for a pair of annotations.
|
private static class |
Graph.GraphAnnotationState
Pseudo typedef for
ArrayList<AnnotationState> . |
static interface |
Graph.GraphEdge<N,E>
A generic edge.
|
(package private) class |
Graph.SimpleSubGraph<N,E>
A simple implementation of SubGraph that calculates adjacency by iterating
over a node's neighbors.
|
Modifier and Type | Field and Description |
---|---|
private java.util.Deque<Graph.GraphAnnotationState> |
edgeAnnotationStack
Used by
pushEdgeAnnotations() and popEdgeAnnotations() . |
private java.util.Deque<Graph.GraphAnnotationState> |
nodeAnnotationStack
Used by
pushNodeAnnotations() and popNodeAnnotations() . |
Constructor and Description |
---|
Graph() |
Modifier and Type | Method and Description |
---|---|
void |
clearEdgeAnnotations()
Makes each edge's annotation null.
|
void |
clearNodeAnnotations()
Makes each node's annotation null.
|
abstract void |
connect(N n1,
E edge,
N n2)
Connects two nodes in the graph with an edge.
|
void |
connectIfNotFound(N n1,
E edge,
N n2)
Connects two nodes in the graph with an edge if such edge does not already
exists between the nodes.
|
abstract GraphNode<N,E> |
createNode(N value)
Gets a node from the graph given a value.
|
abstract void |
disconnect(N n1,
N n2)
Disconnects two nodes in the graph by removing all edges between them.
|
abstract java.util.List<? extends Graph.GraphEdge<N,E>> |
getEdges()
Gets an immutable list of all edges.
|
abstract java.util.List<? extends Graph.GraphEdge<N,E>> |
getEdges(N n1,
N n2)
Retrieves an edge from the graph.
|
abstract Graph.GraphEdge<N,E> |
getFirstEdge(N n1,
N n2)
Retrieves any edge from the graph.
|
abstract java.util.List<GraphNode<N,E>> |
getNeighborNodes(N value)
Gets the neighboring nodes.
|
abstract int |
getNodeDegree(N value)
Gets the degree of a node.
|
(package private) <T extends GraphNode<N,E>> |
getNodeOrFail(N val)
Gets the node of the specified type, or throws an
IllegalArgumentException.
|
abstract java.util.Collection<? extends GraphNode<N,E>> |
getNodes()
Gets an immutable list of all nodes.
|
int |
getWeight(N value)
Returns a weight for the given value to be used in ordering nodes, e.g.
|
boolean |
hasNode(N n)
Checks whether the node exists in the graph (
createNode(Object)
has been called with that value). |
abstract boolean |
isConnected(N n1,
E e,
N n2)
Checks whether two nodes in the graph are connected by the given
edge type.
|
abstract boolean |
isConnected(N n1,
N n2)
Checks whether two nodes in the graph are connected.
|
private static void |
popAnnotations(java.util.Deque<Graph.GraphAnnotationState> stack)
Restores the node annotations on the top of stack and pops stack.
|
void |
popEdgeAnnotations()
Restores edges' annotation values to state before last
pushEdgeAnnotations() . |
void |
popNodeAnnotations()
Restores nodes' annotation values to state before last
pushNodeAnnotations() . |
private static void |
pushAnnotations(java.util.Deque<Graph.GraphAnnotationState> stack,
java.util.Collection<? extends Annotatable> haveAnnotations)
Pushes a new list on stack and stores nodes annotations in the new list.
|
void |
pushEdgeAnnotations()
Pushes edges' annotation values.
|
void |
pushNodeAnnotations()
Pushes nodes' annotation values.
|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getNode, newSubGraph
private java.util.Deque<Graph.GraphAnnotationState> nodeAnnotationStack
pushNodeAnnotations()
and popNodeAnnotations()
.private java.util.Deque<Graph.GraphAnnotationState> edgeAnnotationStack
pushEdgeAnnotations()
and popEdgeAnnotations()
.public abstract void connect(N n1, E edge, N n2)
n1
- First node.edge
- The edge.n2
- Second node.public abstract void disconnect(N n1, N n2)
n1
- First node.n2
- Second node.public final void connectIfNotFound(N n1, E edge, N n2)
n1
- First node.edge
- The edge.n2
- Second node.public abstract GraphNode<N,E> createNode(N value)
Object.equals
.value
- The node's value.public abstract java.util.Collection<? extends GraphNode<N,E>> getNodes()
getNodes
in interface AdjacencyGraph<N,E>
public abstract java.util.List<? extends Graph.GraphEdge<N,E>> getEdges()
public abstract int getNodeDegree(N value)
value
- The node's value.public int getWeight(N value)
AdjacencyGraph
GraphColoring
.getWeight
in interface AdjacencyGraph<N,E>
public abstract java.util.List<GraphNode<N,E>> getNeighborNodes(N value)
value
- The node's value.public abstract java.util.List<? extends Graph.GraphEdge<N,E>> getEdges(N n1, N n2)
n1
- Node one.n2
- Node two.public abstract Graph.GraphEdge<N,E> getFirstEdge(N n1, N n2)
n1
- Node one.n2
- Node two.public final boolean hasNode(N n)
createNode(Object)
has been called with that value).n
- Node.true
if it exist.public abstract boolean isConnected(N n1, N n2)
n1
- Node 1.n2
- Node 2.true
if the two nodes are connected.public abstract boolean isConnected(N n1, E e, N n2)
n1
- Node 1.e
- The edge type.n2
- Node 2.<T extends GraphNode<N,E>> T getNodeOrFail(N val)
public final void clearNodeAnnotations()
AdjacencyGraph
clearNodeAnnotations
in interface AdjacencyGraph<N,E>
public final void clearEdgeAnnotations()
public final void pushNodeAnnotations()
popNodeAnnotations()
. Nodes' annotation values are cleared.public final void popNodeAnnotations()
pushNodeAnnotations()
.public final void pushEdgeAnnotations()
popEdgeAnnotations()
. Edges' annotation values are cleared.public final void popEdgeAnnotations()
pushEdgeAnnotations()
.private static void pushAnnotations(java.util.Deque<Graph.GraphAnnotationState> stack, java.util.Collection<? extends Annotatable> haveAnnotations)
private static void popAnnotations(java.util.Deque<Graph.GraphAnnotationState> stack)