ptolemy.graph

Class Graph

java.lang.Object

ptolemy.graph.Graph

All Implemented Interfaces:

java.lang.Cloneable

Direct Known Subclasses:

DirectedGraph

public class Graph
extends java.lang.Object
implements java.lang.Cloneable

A graph with optionally-weighted nodes and edges.

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)

Since:

Ptolemy II 0.2

Version:

$Id$

Author:

Shuvra S. Bhattacharyya, Ming-Yung Ko, Fuat Keceli, Shahrooz Shahparnia, Yuhong Xiong, Jie Liu.

See Also:

Edge, Node

Pt.AcceptedRating:

Red (cxh)

Pt.ProposedRating:

Red (cxh)

Constructor Summary

Constructors

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.

Method Summary

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 run-time 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 pre-constructed 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 pre-constructed 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 run-time 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 self-loop edges in this graph.
java.util.Collection	selfLoopEdges(Node node) Return the collection of all self-loop 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.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

Graph

public Graph()

Construct an empty graph.

Graph

public Graph(int nodeCount)

Construct an empty graph with enough storage allocated for the specified number of nodes. Memory management is more efficient with this constructor if the number of nodes is known.

Parameters:

nodeCount - The number of nodes.

Graph

public Graph(int nodeCount,
             int edgeCount)

Construct an empty graph with enough storage allocated for the specified number of edges, and number of nodes. Memory management is more efficient with this constructor if the number of nodes and edges is known.

Parameters:

nodeCount - The number of nodes.

edgeCount - The number of edges.

Method Detail

addAnalysis

public void addAnalysis(Analysis analysis)

Add an analysis to the list of analyses that this graph is associated with. This method is called by Analysis when an analysis is created, and normally should not be called elsewhere.

Parameters:

analysis - The analysis.

Throws:

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.

addEdge

public Edge addEdge(Node node1,
                    Node node2,
                    java.lang.Object weight)

Add a weighted edge between two nodes. If the edge is subsequently operated on as a directed edge, its orientation will be taken to be directed from the first (node1) node to the second (node2) node. Multiple edges between the same nodes are allowed, and are considered different edges. Self-loops are also allowed.

Parameters:

node1 - The first node.

node2 - The second node.

weight - The weight.

Returns:

The edge.

Throws:

GraphElementException - If the first node or second node is not already in the graph.

java.lang.NullPointerException - If the weight is null.

addEdge

public Edge addEdge(Node node1,
                    Node node2)

Add an unweighted edge between two nodes. Operation is the same as in addEdge(Node, Node, Object), except that no weight is assigned to the edge.

Parameters:

node1 - The first node.

node2 - The second node.

Returns:

The edge.

Throws:

GraphElementException - If the first node or second node is not already in the graph.

addEdge

public 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).

Parameters:

weight1 - The first node weight.

weight2 - The second node weight.

newEdgeWeight - The weight to assign to each new edge.

Returns:

The set of edges that were added; each element of this set is an instance of Edge.

Throws:

GraphElementException - If no edge is added (i.e., if no nodes x1, x2 satisfy the above condition).

addEdge

public 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).

Parameters:

weight1 - The first node weight.

weight2 - The second node weight.

Returns:

The set of edges that were added; each element of this set is an instance of Edge.

Throws:

GraphElementException - If no edge is added (i.e., if no nodes x1, x2 satisfy the above condition).

addEdge

public Edge addEdge(Edge edge)

Add a pre-constructed edge (unweighted or weighted).

Parameters:

edge - The edge.

Returns:

The edge.

Throws:

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.

See Also:

hideEdge(Edge)

addEdges

public void addEdges(java.util.Collection edgeCollection)

Add a collection of edges to the graph. Each element in the argument collection must be a unique Edge.

Parameters:

edgeCollection - The collection of edges to add.

addGraph

public boolean addGraph(Graph graph)

Add a given graph to this graph. This base class method simply adds all nodes and edges in the given graph to this graph. If a derived class contains extra fields associated with edges, nodes and the graph itself, it can override this method to handle those fields. This method does not add hidden edges of the argument graph to this graph.

Parameters:

graph - The graph to add.

Returns:

True if this graph changed as a result of the call.

addNode

public Node addNode()

Add an unweighted node to this graph.

Returns:

The node.

addNode

public Node addNode(Node node)

Add a pre-constructed node (unweighted or weighted).

Parameters:

node - The node.

Returns:

The node.

Throws:

GraphConstructionException - If the node is already in the graph.

GraphWeightException - If the weight is invalid.

addNodeWeight

public Node addNodeWeight(java.lang.Object weight)

Add a new weighted node to this graph given the node weight.

Parameters:

weight - The node weight.

Returns:

The node.

Throws:

GraphWeightException - If the specified weight is null.

addNodeWeights

public java.util.Collection addNodeWeights(java.util.Collection weightCollection)

Add a collection of nodes to the graph. Each element of the collection is interpreted as a weight of a new node to add in the graph.

Parameters:

weightCollection - The collection of node weights; each element is an instance of Object.

Returns:

The set of nodes that that were added; each element is an instance of Node.

addNodes

public void addNodes(java.util.Collection nodeCollection)

Add a collection of nodes to the graph. Each element in the argument collection must be a unique Node.

Parameters:

nodeCollection - The collection of nodes to add.

changeCount

public long changeCount()

Return the present value of a counter that keeps track of changes to the graph. This counter is monitored by Analysiss 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.

Returns:

The present value of the counter.

clone

public java.lang.Object clone()

Return a clone of this graph. The clone has the same set of nodes and edges. Changes to the node or edge weights affect the clone simultaneously. However, modifications to the graph topology make the clone different from this graph (e.g., they are no longer equal (see equals(Object))).

Overrides:

clone in class java.lang.Object

Returns:

The clone graph.

cloneAs

public Graph cloneAs(Graph graph)

Return a clone of this graph in the form of the argument graph type (i.e., the run-time type of the returned graph is that of the argument graph). The clone has the same set of nodes and edges. Changes to the node or edge weights affect the clone simultaneously. If the run-time type of the argument graph is equal to that of this graph, then the clone is equal to this graph, as determined by equals(Object). However, modifications to the graph topology make the clone not equal to this graph.

Parameters:

graph - The graph that gives the run-time type of the clone.

Returns:

A clone of this graph.

connectedComponents

public java.util.Collection connectedComponents()

Return the connected components of the graph. The connected components are returned as a Collection, where each element of the Collection is a Collection of Nodes.

Returns:

The connected components.

containsEdge

public boolean containsEdge(Edge edge)

Return true if the specified edge exists in the graph, and the edge is not hidden in the graph.

Parameters:

edge - The specified edge.

Returns:

True if the specified edge exists in the graph and is not hidden.

See Also:

hidden(Edge), hideEdge(Edge)

containsEdgeWeight

public boolean containsEdgeWeight(java.lang.Object weight)

Test if the specified object is an edge weight in this graph. Equality is determined by the equals method. If the specified edge weight is null, return false.

Parameters:

weight - The edge weight to be tested.

Returns:

True if the specified object is an edge weight in this graph.

containsNode

public boolean containsNode(Node node)

Return True if the specified node exists in the graph.

Parameters:

node - The specified node.

Returns:

True if the specified node exists in the graph.

containsNodeWeight

public boolean containsNodeWeight(java.lang.Object weight)

Test if the specified object is a node weight in this graph. Equality is determined by the equals method. If the specified weight is null, return false.

Parameters:

weight - The node weight to be tested.

Returns:

True if the specified object is a node weight in this graph.

edge

public Edge edge(java.lang.Object weight)

Return an edge in this graph that has a specified weight. If multiple edges have the specified weight, then return one of them arbitrarily. If the specified weight is null, return an unweighted edge (again arbitrarily chosen if there are multiple unweighted edges).

Parameters:

weight - The specified edge weight.

Returns:

An edge that has this weight.

Throws:

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.

edge

public Edge edge(int label)

Return an edge in this graph given the edge label; the returned edge may be hidden see hideEdge(Edge).

Parameters:

label - The edge label.

Returns:

The edge.

Throws:

GraphElementException - If the label is not associated with an edge in this graph.

See Also:

edgeLabel(Edge)

edgeCount

public int edgeCount()

Return the total number of edges in this graph. Multiple connections between two nodes are counted multiple times. Hidden edges are not included in this count.

Returns:

The total number of edges in this graph.

edgeLabel

public int edgeLabel(Edge edge)

Return the edge label of the specified edge. The edge label is a unique integer from 0 through E-1, where E is the number of edges currently in the graph. Edge labels maintain their consistency (remain constant) during periods when no edges are removed from the graph. When edges are removed, the labels assigned to the remaining edges may change.

Parameters:

edge - A graph edge.

Returns:

The edge label.

Throws:

GraphElementException - If the specified edge is not not an edge in this graph.

edgeLabel

public int edgeLabel(java.lang.Object weight)

Return the edge label of the specified edge given the edge weight. If multiple edges have the specified weight, then return one of their labels arbitrarily.

Parameters:

weight - The edge weight.

Returns:

The edge label.

Throws:

GraphWeightException - If the specified weight is not an edge weight in this graph.

See Also:

edgeLabel(Edge)

edgeWeight

public java.lang.Object edgeWeight(int label)

Return the weight of a given edge in the graph given the edge label.

Parameters:

label - The edge label.

Returns:

The weight of the edge.

Throws:

java.lang.IndexOutOfBoundsException - If the label is not valid.

GraphWeightException - If the edge corresponding to the label is unweighted.

See Also:

edgeLabel(Edge)

edges

public java.util.Collection edges()

Return all the edges in this graph in the form of a collection. Each element in the returned collection is an instance of 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.

Returns:

All the edges in this graph.

edges

public java.util.Collection edges(java.lang.Object weight)

Return all the edges in this graph that have a specified weight. The edges are returned in the form of a collection. If the specified weight is null, return all the unweighted edges. If no edges have the specified weight (or if the argument is null and there are no unweighted edges), return an empty collection. Each element in the returned collection is an instance of Node.

Parameters:

weight - The specified weight.

Returns:

The edges in this graph that have the specified weight.

edges

public java.util.Collection edges(java.util.Collection collection)

Return all the edges in this graph whose weights are contained in a specified collection. The edges are returned in the form of a collection. Each element in the returned collection is an instance of 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. Non-null elements in the argument collection that are not edge weights are ignored.

Parameters:

collection - The specified collection of weights.

Returns:

The edges in this graph whose weights are contained in the specified collection.

See Also:

edges(Object)

equals

public boolean equals(java.lang.Object graph)

Test if a graph is equal to this one. It is equal if it is of the same class, and has the same sets of nodes and edges.

Derived graph classes may override this method if there is additional information in the graphs (beyond nodes and edges) that is relevant to equality.

Overrides:

equals in class java.lang.Object

Parameters:

graph - The graph with which to compare this graph.

Returns:

True if the graph is equal to this one.

See Also:

hashCode()

hashCode

public int hashCode()

Returns the hash code for this graph. The hash code is the sum of the hash codes of the nodes and edges.

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.

Overrides:

hashCode in class java.lang.Object

Returns:

The hash code for this graph.

See Also:

equals(Object)

hidden

public boolean hidden(Edge edge)

Return true if a given edge is hidden in this graph.

Parameters:

edge - The given edge.

Returns:

True if the edge is hidden in this graph.

hiddenEdgeCount

public int hiddenEdgeCount()

Return the number of hidden edges in the graph.

Returns:

The number of hidden edges.

hiddenEdges

public java.util.Collection hiddenEdges()

Return all the hidden edges in this graph in the form of a collection. Each element in the returned collection is an instance of Edge. This is an O(1) operation.

Returns:

All the hidden edges in this graph.

hideEdge

public boolean hideEdge(Edge edge)

Hide an edge if the edge exists in the graph and is not already hidden. This method removes an edge from the graph, including removal from the incidence lists of the source and sink nodes, but preserves the allocation of the edge label to the edge. This makes the operation more efficient than standard edge removal removeEdge(Edge), and allows the same label to be used if the edge is restored later. This is an O(1) operation.

Parameters:

edge - The edge to hide.

Returns:

True if the edge was in the graph and not already hidden.

See Also:

restoreEdge(Edge)

incidentEdgeCount

public int incidentEdgeCount(Node node)

Return the number of edges that are incident to a specified node.

Parameters:

node - The node.

Returns:

The number of incident edges.

Throws:

GraphElementException - If the specified node is not in the graph.

incidentEdges

public java.util.Collection incidentEdges(Node node)

Return the set of incident edges for a specified node. Each element in the returned set is an Edge.

Parameters:

node - The specified node.

Returns:

The set of incident edges.

Throws:

GraphElementException - If the specified node is not in the graph.

neighborEdges

public java.util.Collection neighborEdges(Node node1,
                                          Node node2)

Return the collection of edges that make a node node2 a neighbor of a node node1. In other words, return the set of edges that are incident to both node1 and node2. Each element of the returned collection is an instance of Edge.

Parameters:

node1 - The node node1.

node2 - The node node2.

Returns:

The collection of edges that make node2 a neighbor of node1.

Throws:

GraphElementException - If node1 or node2 is not in this graph.

See Also:

DirectedGraph.predecessorEdges(Node, Node), DirectedGraph.successorEdges(Node, Node)

neighbors

public java.util.Collection neighbors(Node node)

Return all of the neighbors of a given node in the form of a a collection. Each element of the collection is a Node. A neighbor of a node X is a node that is the sink of an edge whose source is X, or the source of a node whose sink is node X. In other words, a neighbor of X is a node that is adjacent to X. All elements in the returned collection are unique nodes.

Parameters:

node - The node whose neighbors are to be returned.

Returns:

The neighbors of the node as a collection.

node

public Node node(java.lang.Object weight)

Return a node in this graph that has a specified weight. If multiple nodes have the specified weight, then return one of them arbitrarily. If the specified weight is null, return an unweighted node (again arbitrarily chosen if there are multiple unweighted nodes).

Parameters:

weight - The specified node weight.

Returns:

A node that has this weight.

Throws:

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.

node

public Node node(int label)

Return a node in this graph given the node label.

Parameters:

label - The node label.

Returns:

The node.

Throws:

java.lang.IndexOutOfBoundsException - If the label is not associated with a node in this graph.

See Also:

nodeLabel(Node)

nodeCount

public int nodeCount()

Return the total number of nodes in this graph.

Returns:

The total number of nodes in this graph.

nodeLabel

public int nodeLabel(Node node)

Return the node label of the specified node. The node label is a unique integer from 0 through N-1, where N is the number of nodes currently in the graph. Node labels maintain their consistency (remain constant) during periods when no nodes are removed from the graph. When nodes are removed, the labels assigned to the remaining nodes may change.

Parameters:

node - A graph node.

Returns:

The node label.

Throws:

GraphElementException - If the specified node is not a node in this graph.

nodeLabel

public int nodeLabel(java.lang.Object weight)

Return the node label of the specified node given the node weight. If multiple nodes have the specified weight, then return one of their labels arbitrarily.

Parameters:

weight - The node weight.

Returns:

The node label.

Throws:

GraphWeightException - If the specified weight is not a node weight in this graph.

See Also:

nodeLabel(Node)

nodeWeight

public java.lang.Object nodeWeight(int label)

Return the weight of a given node in the graph given the node label.

Parameters:

label - The node label.

Returns:

The weight of the node.

Throws:

java.lang.IndexOutOfBoundsException - If the label is not valid.

GraphWeightException - If the node corresponding to the label is unweighted.

See Also:

nodeLabel(Node)

nodes

public java.util.Collection nodes()

Return all the nodes in this graph in the form of a collection. Each element in the returned collection is an instance of Node.

Returns:

All the nodes in this graph.

nodes

public java.util.Collection nodes(java.lang.Object weight)

Return all the nodes in this graph that have a specified weight. The nodes are returned in the form of a collection. If the specified weight is null, return all the unweighted nodes. If no nodes have the specified weight (or if the argument is null and there are no unweighted nodes), return an empty collection. Each element in the returned collection is an instance of Node.

Parameters:

weight - The specified weight.

Returns:

The nodes in this graph that have the specified weight.

nodes

public java.util.Collection nodes(java.util.Collection collection)

Return the collection of nodes in this graph whose weights are contained in a specified collection. Each element in the returned collection is an instance of 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. Non-null elements in the argument collection that are not node weights are ignored.

Parameters:

collection - The specified collection of weights.

Returns:

The nodes in this graph whose weights are contained in a specified collection.

Throws:

GraphWeightException - If any specified weight is not a node weight in this graph.

removeEdge

public boolean removeEdge(Edge edge)

Remove an edge from this graph if it exists in the graph. The edge may be hidden. An edge that is removed from a graph can be re-inserted into the graph at a later time (using 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).

Parameters:

edge - The edge to be removed.

Returns:

True if the edge was removed.

See Also:

hideEdge(Edge)

removeNode

public boolean removeNode(Node node)

Remove a node from this graph if it exists in the graph. All edges incident to the node (excluding hidden edges) are also removed. This is an O(n + ke) operation, where k is the number of incident edges.

Parameters:

node - The node to be removed.

Returns:

True if the node was removed.

restoreEdge

public boolean restoreEdge(Edge edge)

Restore an edge if the edge exists in the graph and is presently hidden. This is an O(1) operation.

Parameters:

edge - The edge to restore.

Returns:

True if the edge is in the graph and was hidden.

Throws:

GraphElementException - If the source node and sink node of the given edge are not both in the graph.

See Also:

hideEdge(Edge)

selfLoopEdgeCount

public int selfLoopEdgeCount()

Return the number of self loop edges in this graph.

Returns:

The number of self loop edges.

selfLoopEdgeCount

public int selfLoopEdgeCount(Node node)

Return the number of self loop edges of a specified node.

Parameters:

node - The node.

Returns:

The number of self loop edges.

Throws:

GraphElementException - If the node is not in the graph.

selfLoopEdges

public java.util.Collection selfLoopEdges()

Return the collection of all self-loop edges in this graph. Each element in the returned collection is an Edge. This operation takes O(E) time, where E is the number of edges in the graph.

Returns:

The self-loop edges in this graph.

selfLoopEdges

public java.util.Collection selfLoopEdges(Node node)

Return the collection of all self-loop edges that are incident to a specified node. Each element in the collection is an Edge.

Parameters:

node - The node.

Returns:

The self-loop edges that are incident to the node.

Throws:

GraphElementException - If the node is not in the graph.

subgraph

public Graph subgraph(java.util.Collection collection)

Return the subgraph induced by a collection of nodes. In other words, return the subgraph formed by the given collection N of nodes together with the set of edges of the form (x, y), where x and y are both in N. Node and edge weights are preserved. In derived classes, this method returns the same type of graph as is returned by _emptyGraph(). Derived classes that do not have zero-argument constructors may need to override this method to properly initialize the subgraph.

Parameters:

collection - The collection of nodes; each element is a Node.

Returns:

The induced subgraph.

Throws:

GraphElementException - If the collection contains a node that is not in this graph.

subgraph

public Graph subgraph(java.util.Collection nodeCollection,
                      java.util.Collection edgeCollection)

Return the subgraph formed by a subset of nodes and a subset of edges. Node and edge weights are preserved. In derived classes, this method returns the same type of graph as is returned by _emptyGraph().

Parameters:

nodeCollection - The subset of nodes; each element is an instance of Node.

edgeCollection - The subset of edges. Each element is an instance of Edge.

Returns:

The subgraph.

Throws:

GraphElementException - If the argument collections contain a node or edge that is not in this graph.

See Also:

addEdges(Collection), addNodes(Collection)

toString

public java.lang.String toString()

Return a string representation of this graph. The string representation lists the nodes, including their labels and their weights, followed by the edges, including their labels, source nodes, sink nodes, and weights.

Overrides:

toString in class java.lang.Object

Returns:

A string representation of this graph.

validEdgeWeight

public boolean validEdgeWeight(java.lang.Object object)

Return true if the given object is a valid edge weight for this graph. An object is a valid edge weight if it is meaningful to assign it as an edge weight in this type of graph. If the given object is null this method returns true if it is valid to have an unweighted edge in this type of graph. This base class method returns true unconditionally. In derived classes, the method should be overridden to take into account any restrictions on edge weights.

Parameters:

object - The given object.

Returns:

True if if the given object is a valid edge weight for this graph.

validNodeWeight

public boolean validNodeWeight(java.lang.Object object)

Return true if the given object is a valid node weight for this graph. An object is a valid node weight if it is meaningful to assign it as a node weight in this type of graph. If the given object is null this method returns true if it is valid to have an unweighted node in this type of graph. This base class method returns true unconditionally. In derived classes, the method should be overridden to take into account any restrictions on node weights.

Parameters:

object - The given object.

Returns:

True if if the given object is a valid node weight for this graph.

validateWeight

public boolean validateWeight(Edge edge)

Validate the weight of an edge. Operation parallels that of #validateWeight(Node).

Parameters:

edge - The edge whose weight is to be validated.

Returns:

True if the edge weight has changed, as determined by the equals method.

Throws:

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).

See Also:

validateWeight(Edge, Object), validateWeight(Node)

validateWeight

public boolean validateWeight(Edge edge,
                              java.lang.Object oldWeight)

Validate the weight of an edge given the edge and its previous weight. Operation parallels that of #validateWeight(Node, Object).

Parameters:

edge - The edge whose weight is to be validated.

oldWeight - The previous weight of the edge (null if the edge was previously unweighted).

Returns:

True if the edge weight has changed, as determined by the equals method.

See Also:

validateWeight(Edge), validateWeight(Node, Object)

validateWeight

public boolean validateWeight(Node node)

Validate the weight of a node. This method checks the validity of the node weight (using 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.

Parameters:

node - The node whose weight is to be validated.

Returns:

True if the node weight has changed, as determined by the equals method.

Throws:

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).

See Also:

validateWeight(Node, Object)

validateWeight

public boolean validateWeight(Node node,
                              java.lang.Object oldWeight)

Validate the weight of a node given the node and its previous weight. The previous weight argument should be set to the weight of the node when the node was last added to the graph or last had its node validated, whichever was more recent. Operation is equivalent to 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.

Parameters:

node - The node whose weight is to be validated.

oldWeight - The previous weight of the node.

Returns:

True if the node weight has changed, as determined by the equals method.

See Also:

validateWeight(Node)

weightArray

public 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. If a weight is common across multiple elements in the collection, it will appear multiple times in the array. If the element collection is null or empty, an empty (zero-element) array is returned.

Parameters:

elementCollection - The collection of graph elements; each element is a Node or an Edge.

Returns:

The weights of the graph elements, in the order that that elements are returned by collection's iterator; each element in the returned array is an Object.

Throws:

java.lang.NullPointerException - If the specified collection contains a null value.

GraphElementException - If the specified collection contains a non-null value that is neither a node nor an edge.

_addEdge

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. The third parameter specifies whether the edge is to be weighted, and the fourth parameter is the weight that is to be applied if the edge is weighted. Returns the edge that is added.

Parameters:

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.

Returns:

The edge.

Throws:

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.

_connect

protected void _connect(Edge edge,
                        Node node)

Connect an edge to a node by appropriately modifying the adjacency information associated with the node. The node is assumed to be in the graph.

Parameters:

edge - The edge.

node - The node.

Throws:

GraphConstructionException - If the edge has already been connected to the node.

_connectEdge

protected void _connectEdge(Edge edge)

Connect a given edge in this graph. The edge and its source and sink nodes are assumed to be in the graph. This method performs operations that are common to the addition of a new edge and the restoration of a hidden edge. Specifically, this method connects, using _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.

Parameters:

edge - The edge to connect.

See Also:

hideEdge(Edge), removeEdge(Edge), _disconnectEdge(Edge), _registerChange()

_disconnect

protected void _disconnect(Edge edge,
                           Node node)

Disconnect an edge from a node that it is incident to. Specifically, this method removes the edge from the set of edges that are considered incident to the node in this graph. This method does nothing if the given edge is not incident to the given node. This method should be overridden to incorporate additional operations that are required to disconnect an edge from a node (see, for example, DirectedGraph.#_disconnect(Edge, Node)).

Parameters:

edge - The edge.

node - The node.

_disconnectEdge

protected void _disconnectEdge(Edge edge)

Disconnect a given edge in this graph. The edge is assumed to be in the graph and not already hidden. This method performs operations that are common to the removal of and hiding of an edge. Specifically, this method disconnects, using _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.

Parameters:

edge - The edge to disconnect.

See Also:

hideEdge(Edge), removeEdge(Edge), _connectEdge(Edge), _registerChange()

_emptyGraph

protected Graph _emptyGraph()

Return an empty graph that has the same run-time type as this graph. This class should be overridden in derived classes that do not have zero-argument constructors.

Returns:

An empty graph.

_initializeAnalyses

protected void _initializeAnalyses()

Initialize the list of analyses that are associated with this graph, and initialize the change counter of the graph.

See Also:

Analysis

_registerChange

protected void _registerChange()

Register a change to the graph by updating the change counter. This method must be called after any change to the graph that may affect (invalidate) any of the computations associated with analyses that this graph is associated with.

See Also:

Analysis

_registerEdge

protected void _registerEdge(Edge edge)

Register a new edge in the graph. The edge is assumed to be non-null, unique, and consistent with the node set. This method performs updates of internal data structures that are required for every edge that is added to the graph. Derived classes can override this method to perform additional updates of internal data structures.

Parameters:

edge - The new edge.

Throws:

GraphWeightException - If the weight of the given edge is not valid, as determined by validEdgeWeight(Object).

See Also:

_registerNode(Node)

_registerNode

protected void _registerNode(Node node)

Register a new node in the graph. The node is assumed to be non-null and unique. This method performs updates of internal data structures that are required for every node that is added to the graph. Derived classes can override this method to perform additional updates of internal data structures.

Parameters:

node - The new node.

Throws:

GraphWeightException - If the weight of the given node is not valid, as determined by validNodeWeight(Object).

See Also:

_registerEdge(Edge)