public class Graph
extends java.lang.Object
implements java.lang.Cloneable
Each node or edge may have a weight associated with it
(see Edge
and Node
).
The nodes (edges) in a graph are always distinct, but their weights
need not be.
Each node (edge) has a unique, integer label associated with it.
These labels can be used, for example, to index arrays and matrixes
whose rows/columns correspond to nodes (edges). See nodeLabel(Node)
(edgeLabel(Edge)
) for details.
Both directed and undirected graphs can be implemented using this
class. In directed graphs, the order of nodes specified to the
addEdge
method is relevant, whereas in undirected graphs, the
order is unimportant. Support for both undirected and directed graphs
follows from the combined support for these in the underlying Node
and Edge
classes. For more thorough support for directed
graphs, see DirectedGraph
.
The same node can exist in multiple graphs, but any given graph can contain only one instance of the node. Node labels, however, are local to individual graphs. Thus, the same node may have different labels in different graphs. Furthermore, the label assigned in a given graph to a node may change over time (if the set of nodes in the graph changes). If a node is contained in multiple graphs, it has the same weight in all of the graphs. All of this holds for edges as well. The same weight may be shared among multiple nodes and edges.
Multiple edges in a graph can connect the same pair of nodes. Thus, multigraphs are supported.
Once assigned, node and edge weights should not be changed in ways that
affect comparison under the equals
method.
Otherwise, unpredictable behavior may result.
In discussions of complexity, n and e refers to the number of graph nodes and edges, respectively.
In derived classes, the following methods need special
attention regarding whether or not they should be overridden:
validEdgeWeight(Object)
validNodeWeight(Object)
Constructor and Description 

Graph()
Construct an empty graph.

Graph(int nodeCount)
Construct an empty graph with enough storage allocated for the
specified number of nodes.

Graph(int nodeCount,
int edgeCount)
Construct an empty graph with enough storage allocated for the
specified number of edges, and number of nodes.

Modifier and Type  Method and Description 

protected Edge 
_addEdge(Node node1,
Node node2,
boolean weighted,
java.lang.Object weight)
Create and add an edge with a specified source node, sink node,
and optional weight.

protected void 
_connect(Edge edge,
Node node)
Connect an edge to a node by appropriately modifying
the adjacency information associated with the node.

protected void 
_connectEdge(Edge edge)
Connect a given edge in this graph.

protected void 
_disconnect(Edge edge,
Node node)
Disconnect an edge from a node that it is incident to.

protected void 
_disconnectEdge(Edge edge)
Disconnect a given edge in this graph.

protected Graph 
_emptyGraph()
Return an empty graph that has the same runtime type as this graph.

protected void 
_initializeAnalyses()
Initialize the list of analyses that are associated with this graph,
and initialize the change counter of the graph.

protected void 
_registerChange()
Register a change to the graph by updating the change counter.

protected void 
_registerEdge(Edge edge)
Register a new edge in the graph.

protected void 
_registerNode(Node node)
Register a new node in the graph.

void 
addAnalysis(Analysis analysis)
Add an analysis to the list of analyses that this graph is associated
with.

Edge 
addEdge(Edge edge)
Add a preconstructed edge (unweighted or weighted).

Edge 
addEdge(Node node1,
Node node2)
Add an unweighted edge between two nodes.

Edge 
addEdge(Node node1,
Node node2,
java.lang.Object weight)
Add a weighted edge between two nodes.

java.util.Collection 
addEdge(java.lang.Object weight1,
java.lang.Object weight2)
Given two node weights w1 and w2, add all unweighted
edges of the form (x1, x2), where
(x1.getWeight() == w1) && (x2.getWeight() == w2) . 
java.util.Collection 
addEdge(java.lang.Object weight1,
java.lang.Object weight2,
java.lang.Object newEdgeWeight)
Given two node weights w1 and w2, add weighted
edges of the form (x1, x2), where
(x1.getWeight() == w1) && (x2.getWeight() == w2) . 
void 
addEdges(java.util.Collection edgeCollection)
Add a collection of edges to the graph.

boolean 
addGraph(Graph graph)
Add a given graph to this graph.

Node 
addNode()
Add an unweighted node to this graph.

Node 
addNode(Node node)
Add a preconstructed node (unweighted or weighted).

void 
addNodes(java.util.Collection nodeCollection)
Add a collection of nodes to the graph.

Node 
addNodeWeight(java.lang.Object weight)
Add a new weighted node to this graph given the node weight.

java.util.Collection 
addNodeWeights(java.util.Collection weightCollection)
Add a collection of nodes to the graph.

long 
changeCount()
Return the present value of a counter that keeps track
of changes to the graph.

java.lang.Object 
clone()
Return a clone of this graph.

Graph 
cloneAs(Graph graph)
Return a clone of this graph in the form of the argument graph type
(i.e., the runtime type of the returned graph is that of the
argument graph).

java.util.Collection 
connectedComponents()
Return the connected components of the graph.

boolean 
containsEdge(Edge edge)
Return true if the specified edge exists in the graph, and the
edge is not hidden in the graph.

boolean 
containsEdgeWeight(java.lang.Object weight)
Test if the specified object is an edge weight in this
graph.

boolean 
containsNode(Node node)
Return True if the specified node exists in the
graph.

boolean 
containsNodeWeight(java.lang.Object weight)
Test if the specified object is a node weight in this
graph.

Edge 
edge(int label)
Return an edge in this graph given the edge label;
the returned edge may be hidden see
hideEdge(Edge) . 
Edge 
edge(java.lang.Object weight)
Return an edge in this graph that has a specified weight.

int 
edgeCount()
Return the total number of edges in this graph.

int 
edgeLabel(Edge edge)
Return the edge label of the specified edge.

int 
edgeLabel(java.lang.Object weight)
Return the edge label of the specified edge given the edge weight.

java.util.Collection 
edges()
Return all the edges in this graph in the form of a collection.

java.util.Collection 
edges(java.util.Collection collection)
Return all the edges in this graph whose weights are contained
in a specified collection.

java.util.Collection 
edges(java.lang.Object weight)
Return all the edges in this graph that have a specified weight.

java.lang.Object 
edgeWeight(int label)
Return the weight of a given edge in the graph given the edge label.

boolean 
equals(java.lang.Object graph)
Test if a graph is equal to this one.

int 
hashCode()
Returns the hash code for this graph.

boolean 
hidden(Edge edge)
Return true if a given edge is hidden in this graph.

int 
hiddenEdgeCount()
Return the number of hidden edges in the graph.

java.util.Collection 
hiddenEdges()
Return all the hidden edges in this graph in the form of a collection.

boolean 
hideEdge(Edge edge)
Hide an edge if the edge exists in the graph and is not already hidden.

int 
incidentEdgeCount(Node node)
Return the number of edges that are incident to a specified node.

java.util.Collection 
incidentEdges(Node node)
Return the set of incident edges for a specified node.

java.util.Collection 
neighborEdges(Node node1,
Node node2)
Return the collection of edges that make a node node2 a neighbor of a
node node1.

java.util.Collection 
neighbors(Node node)
Return all of the neighbors of a given node in the form of a
a collection.

Node 
node(int label)
Return a node in this graph given the node label.

Node 
node(java.lang.Object weight)
Return a node in this graph that has a specified weight.

int 
nodeCount()
Return the total number of nodes in this graph.

int 
nodeLabel(Node node)
Return the node label of the specified node.

int 
nodeLabel(java.lang.Object weight)
Return the node label of the specified node given the node weight.

java.util.Collection 
nodes()
Return all the nodes in this graph in the form of a collection.

java.util.Collection 
nodes(java.util.Collection collection)
Return the collection of nodes in this graph whose weights are
contained in a specified collection.

java.util.Collection 
nodes(java.lang.Object weight)
Return all the nodes in this graph that have a specified weight.

java.lang.Object 
nodeWeight(int label)
Return the weight of a given node in the graph given the node label.

boolean 
removeEdge(Edge edge)
Remove an edge from this graph if it exists in the graph.

boolean 
removeNode(Node node)
Remove a node from this graph if it exists in the graph.

boolean 
restoreEdge(Edge edge)
Restore an edge if the edge exists in the graph and is presently
hidden.

int 
selfLoopEdgeCount()
Return the number of self loop edges in this graph.

int 
selfLoopEdgeCount(Node node)
Return the number of self loop edges of a specified node.

java.util.Collection 
selfLoopEdges()
Return the collection of all selfloop edges in this graph.

java.util.Collection 
selfLoopEdges(Node node)
Return the collection of all selfloop edges that are incident to
a specified node.

Graph 
subgraph(java.util.Collection collection)
Return the subgraph induced by a collection of nodes.

Graph 
subgraph(java.util.Collection nodeCollection,
java.util.Collection edgeCollection)
Return the subgraph formed by a subset of nodes and a subset of
edges.

java.lang.String 
toString()
Return a string representation of this graph.

boolean 
validateWeight(Edge edge)
Validate the weight of an edge.

boolean 
validateWeight(Edge edge,
java.lang.Object oldWeight)
Validate the weight of an edge given the edge and its previous weight.

boolean 
validateWeight(Node node)
Validate the weight of a node.

boolean 
validateWeight(Node node,
java.lang.Object oldWeight)
Validate the weight of a node given the node and its previous weight.

boolean 
validEdgeWeight(java.lang.Object object)
Return true if the given object is a valid edge weight for this graph.

boolean 
validNodeWeight(java.lang.Object object)
Return true if the given object is a valid node weight for this graph.

static java.lang.Object[] 
weightArray(java.util.Collection elementCollection)
Given a collection of graph elements (nodes and edges), return an array
of weights associated with these elements.

public Graph()
public Graph(int nodeCount)
nodeCount
 The number of nodes.public Graph(int nodeCount, int edgeCount)
nodeCount
 The number of nodes.edgeCount
 The number of edges.public void addAnalysis(Analysis analysis)
Analysis
when an analysis is created, and normally should not be called
elsewhere.analysis
 The analysis.java.lang.IllegalArgumentException
 If the graph associated with the
analysis is not equal to this graph, or if the graph already contains
the analysis in its list of analyses.public Edge addEdge(Node node1, Node node2, java.lang.Object weight)
node1
) node
to the second (node2
) node. Multiple edges
between the same nodes are allowed, and are considered
different edges. Selfloops are also allowed.node1
 The first node.node2
 The second node.weight
 The weight.GraphElementException
 If the first node or second
node is not already in the graph.java.lang.NullPointerException
 If the weight is null
.public Edge addEdge(Node node1, Node node2)
addEdge(Node, Node, Object)
, except that no
weight is assigned to the edge.node1
 The first node.node2
 The second node.GraphElementException
 If the first node or second
node is not already in the graph.public java.util.Collection addEdge(java.lang.Object weight1, java.lang.Object weight2, java.lang.Object newEdgeWeight)
(x1.getWeight() == w1) && (x2.getWeight() == w2)
.weight1
 The first node weight.weight2
 The second node weight.newEdgeWeight
 The weight to assign to each new edge.Edge
.GraphElementException
 If no edge is
added (i.e., if no nodes x1, x2 satisfy the above condition).public java.util.Collection addEdge(java.lang.Object weight1, java.lang.Object weight2)
(x1.getWeight() == w1) && (x2.getWeight() == w2)
.weight1
 The first node weight.weight2
 The second node weight.Edge
.GraphElementException
 If no edge is
added (i.e., if no nodes x1, x2 satisfy the above condition).public Edge addEdge(Edge edge)
edge
 The edge.GraphElementException
 If the source or sink node
of the edge is not already in the graph.GraphConstructionException
 If the edge is already in
the graph, or if the edge is hidden in the graph.hideEdge(Edge)
public void addEdges(java.util.Collection edgeCollection)
Edge
.edgeCollection
 The collection of edges to add.public boolean addGraph(Graph graph)
graph
 The graph to add.public Node addNode()
public Node addNode(Node node)
node
 The node.GraphConstructionException
 If the node is already
in the graph.GraphWeightException
 If the weight is invalid.public Node addNodeWeight(java.lang.Object weight)
weight
 The node weight.GraphWeightException
 If the specified weight is null.public java.util.Collection addNodeWeights(java.util.Collection weightCollection)
weightCollection
 The collection of node weights; each element
is an instance of Object
.Node
.public void addNodes(java.util.Collection nodeCollection)
Node
.nodeCollection
 The collection of nodes to add.public long changeCount()
Analysis
s to determine
if associated computations are obsolete. Upon overflow, the counter
resets to zero, broadcasts a change to all graph analyses, and
begins counting again.public java.lang.Object clone()
equals(Object)
)).clone
in class java.lang.Object
public Graph cloneAs(Graph graph)
equals(Object)
. However,
modifications to the graph topology
make the clone not equal to this graph.graph
 The graph that gives the runtime type of the clone.public java.util.Collection connectedComponents()
public boolean containsEdge(Edge edge)
edge
 The specified edge.hidden(Edge)
,
hideEdge(Edge)
public boolean containsEdgeWeight(java.lang.Object weight)
equals
method. If the specified
edge weight is null, return false.weight
 The edge weight to be tested.public boolean containsNode(Node node)
node
 The specified node.public boolean containsNodeWeight(java.lang.Object weight)
equals
method. If the specified
weight is null, return false.weight
 The node weight to be tested.public Edge edge(java.lang.Object weight)
weight
 The specified edge weight.GraphWeightException
 If the specified weight
is not an edge weight in this graph or if the specified weight
is null but the graph does not contain any unweighted edges.public Edge edge(int label)
hideEdge(Edge)
.label
 The edge label.GraphElementException
 If the label is not associated
with an edge in this graph.edgeLabel(Edge)
public int edgeCount()
public int edgeLabel(Edge edge)
edge
 A graph edge.GraphElementException
 If the specified edge is not
not an edge in this graph.public int edgeLabel(java.lang.Object weight)
weight
 The edge weight.GraphWeightException
 If the specified weight is not
an edge weight in this graph.edgeLabel(Edge)
public java.lang.Object edgeWeight(int label)
label
 The edge label.java.lang.IndexOutOfBoundsException
 If the label is
not valid.GraphWeightException
 If the edge corresponding
to the label is unweighted.edgeLabel(Edge)
public java.util.Collection edges()
Edge
.
Hidden edges are not included in the returned collection.
The returned collection cannot be modified.
This is an O(1) operation if there are no hidden edges;
otherwise, it is an O(e) operation.public java.util.Collection edges(java.lang.Object weight)
Node
.weight
 The specified weight.public java.util.Collection edges(java.util.Collection collection)
Edge
. A null element in the argument collection is interpreted
to mean that all unweighted edges are to be included in the result.
Duplicate weights or null elements in the specified collection result
in duplicate edges in the returned collection.
Nonnull elements in the argument collection that are not edge weights
are ignored.collection
 The specified collection of weights.edges(Object)
public boolean equals(java.lang.Object graph)
Derived graph classes may override this method if there is additional information in the graphs (beyond nodes and edges) that is relevant to equality.
equals
in class java.lang.Object
graph
 The graph with which to compare this graph.hashCode()
public int hashCode()
Derived graph classes may override this method if there is additional information in the graphs (beyond nodes and edges) that is relevant to equality between graphs.
hashCode
in class java.lang.Object
equals(Object)
public boolean hidden(Edge edge)
edge
 The given edge.public int hiddenEdgeCount()
public java.util.Collection hiddenEdges()
Edge
.
This is an O(1) operation.public boolean hideEdge(Edge edge)
removeEdge(Edge)
, and
allows the same label to be used if the edge is restored later.
This is an O(1) operation.edge
 The edge to hide.restoreEdge(Edge)
public int incidentEdgeCount(Node node)
node
 The node.GraphElementException
 If the specified node is not in
the graph.public java.util.Collection incidentEdges(Node node)
Edge
.node
 The specified node.GraphElementException
 If the specified node is not in
the graph.public java.util.Collection neighborEdges(Node node1, Node node2)
Edge
.node1
 The node node1.node2
 The node node2.GraphElementException
 If node1 or node2 is not in this
graph.DirectedGraph.predecessorEdges(Node, Node)
,
DirectedGraph.successorEdges(Node, Node)
public java.util.Collection neighbors(Node node)
node
 The node whose neighbors are to be returned.public Node node(java.lang.Object weight)
weight
 The specified node weight.GraphWeightException
 If the specified weight
is not a node weight in this graph or if the specified weight
is null but the graph does not contain any unweighted nodes.public Node node(int label)
label
 The node label.java.lang.IndexOutOfBoundsException
 If the label is not
associated with a node in this graph.nodeLabel(Node)
public int nodeCount()
public int nodeLabel(Node node)
node
 A graph node.GraphElementException
 If the specified node is not
a node in this graph.public int nodeLabel(java.lang.Object weight)
weight
 The node weight.GraphWeightException
 If the specified weight is not
a node weight in this graph.nodeLabel(Node)
public java.lang.Object nodeWeight(int label)
label
 The node label.java.lang.IndexOutOfBoundsException
 If the label is
not valid.GraphWeightException
 If the node corresponding
to the label is unweighted.nodeLabel(Node)
public java.util.Collection nodes()
Node
.public java.util.Collection nodes(java.lang.Object weight)
Node
.weight
 The specified weight.public java.util.Collection nodes(java.util.Collection collection)
Node
.
A null element in the argument collection is interpreted
to mean that all unweighted nodes are to be included in the result.
Duplicate weights or null elements in the specified collection result
in duplicate nodes in the returned collection.
Nonnull elements in the argument collection that are not node weights
are ignored.collection
 The specified collection of weights.GraphWeightException
 If any specified weight
is not a node weight in this graph.public boolean removeEdge(Edge edge)
addEdge(Edge)
),
provided that the incident nodes are still in the graph.
This is an O(e) operation. A similar operation can be
performed in O(1) time using hideEdge(Edge)
.
edge
 The edge to be removed.hideEdge(Edge)
public boolean removeNode(Node node)
node
 The node to be removed.public boolean restoreEdge(Edge edge)
edge
 The edge to restore.GraphElementException
 If the source node and
sink node of the given edge are not both in the graph.hideEdge(Edge)
public int selfLoopEdgeCount()
public int selfLoopEdgeCount(Node node)
node
 The node.GraphElementException
 If the node is not in the graph.public java.util.Collection selfLoopEdges()
Edge
.
This operation takes O(E) time, where E is the number
of edges in the graph.public java.util.Collection selfLoopEdges(Node node)
Edge
.node
 The node.GraphElementException
 If the node is not in the graph.public Graph subgraph(java.util.Collection collection)
_emptyGraph()
.
Derived classes that do not have zeroargument constructors may
need to override this method to properly initialize the subgraph.collection
 The collection of nodes; each element
is a Node
.GraphElementException
 If the collection contains a node
that is not in this graph.public Graph subgraph(java.util.Collection nodeCollection, java.util.Collection edgeCollection)
_emptyGraph()
.nodeCollection
 The subset of nodes; each element is an instance
of Node
.edgeCollection
 The subset of edges. Each element is an instance
of Edge
.GraphElementException
 If the argument collections contain
a node or edge that is not in this graph.addEdges(Collection)
,
addNodes(Collection)
public java.lang.String toString()
toString
in class java.lang.Object
public boolean validEdgeWeight(java.lang.Object object)
object
 The given object.public boolean validNodeWeight(java.lang.Object object)
object
 The given object.public boolean validateWeight(Edge edge)
edge
 The edge whose weight is to be validated.GraphElementException
 If the specified edge is not in
the graph.GraphWeightException
 If the weight of the given edge
is not valid, as determined by validEdgeWeight(Object)
.validateWeight(Edge, Object)
,
validateWeight(Node)
public boolean validateWeight(Edge edge, java.lang.Object oldWeight)
edge
 The edge whose weight is to be validated.oldWeight
 The previous weight of the edge (null if the edge
was previously unweighted).validateWeight(Edge)
,
validateWeight(Node, Object)
public boolean validateWeight(Node node)
validNodeWeight(Object)
, and
updates, if necessary, the internal mapping of weights into
their associated nodes.
This updating operation is necessary for correct operation of
containsNodeWeight(Object)
,
node(Object)
,
nodes(Collection)
, and
nodes(Object)
,
if the node weight has changed in a way
that affects comparison under the equals method.
This method returns true if the node weight has changed (as determined
by the equals() method) since the last time the graph was notified
of the node's weight. Furthermore, if the node weight has changed in
this way, a graph change is registered.
This is an O(n) operation.node
 The node whose weight is to be validated.GraphElementException
 If the specified node is not in
the graph.GraphWeightException
 If the weight of the given node
is not valid, as determined by validNodeWeight(Object)
.validateWeight(Node, Object)
public boolean validateWeight(Node node, java.lang.Object oldWeight)
validateWeight(Node)
except that the additional argument is used to improve efficiency.
The previous node weight should be set to null to indicate that
the node was previously unweighted.
Consider an example in which a given Node node is contained in two graphs graph1 and graph2 , and suppose that we wish to change the weight of the node. Below is a sample code fragment that achieves such a weight change with proper notification to the containing graphs.
Object oldWeight = node.getWeight(); node.setWeight(newWeight); graph1.validateWeight(node, oldWeight); graph2.validateWeight(node, oldWeight);
In this example, #validateWeight(Node) could be used (e.g., if the previous weight oldWeight was not available) in place of #validateWeight(Node, Object), but the efficiency would be lower.
node
 The node whose weight is to be validated.oldWeight
 The previous weight of the node.validateWeight(Node)
public static java.lang.Object[] weightArray(java.util.Collection elementCollection)
elementCollection
 The collection of graph elements;
each element is a Node
or an Edge
.Object
.java.lang.NullPointerException
 If the specified collection contains
a null value.GraphElementException
 If the specified collection
contains a nonnull value that is neither a node nor an edge.protected Edge _addEdge(Node node1, Node node2, boolean weighted, java.lang.Object weight)
node1
 The source node of the edge.node2
 The sink node of the edge.weighted
 True if the edge is to be weighted.weight
 The weight that is to be applied if the edge is to
be weighted.GraphElementException
 If either of the specified
nodes is not in the graph.java.lang.NullPointerException
 If the edge is to be weighted, but
the specified weight is null.protected void _connect(Edge edge, Node node)
edge
 The edge.node
 The node.GraphConstructionException
 If the edge has already
been connected to the node.protected void _connectEdge(Edge edge)
_connect(Edge, Node)
,
the given edge to its source and sink nodes;
updates the mapping of weights into corresponding graph
edges; and registers a change in the graph. This method should be
overridden to perform additional operations that are necessary
to connect edges in derived graph classes.edge
 The edge to connect.hideEdge(Edge)
,
removeEdge(Edge)
,
_disconnectEdge(Edge)
,
_registerChange()
protected void _disconnect(Edge edge, Node node)
edge
 The edge.node
 The node.protected void _disconnectEdge(Edge edge)
_disconnect(Edge, Node)
, the given edge
from its source and sink nodes;
updates the mapping of weights into corresponding graph
edges; and registers a change in the graph. This method should be
overridden to perform additional operations that are necessary
to disconnect edges in derived graph classes.edge
 The edge to disconnect.hideEdge(Edge)
,
removeEdge(Edge)
,
_connectEdge(Edge)
,
_registerChange()
protected Graph _emptyGraph()
protected void _initializeAnalyses()
Analysis
protected void _registerChange()
Analysis
protected void _registerEdge(Edge edge)
edge
 The new edge.GraphWeightException
 If the weight of the given edge is
not valid, as determined by validEdgeWeight(Object)
._registerNode(Node)
protected void _registerNode(Node node)
node
 The new node.GraphWeightException
 If the weight of the given node is
not valid, as determined by validNodeWeight(Object)
._registerEdge(Edge)