ptolemy.graph
Class DirectedGraph

java.lang.Object
  ptolemy.graph.Graph
      ptolemy.graph.DirectedGraph

All Implemented Interfaces:

java.lang.Cloneable

Direct Known Subclasses:

DirectedAcyclicGraph

public class DirectedGraph
extends Graph

A directed graph. Some methods in this class have two versions, one that operates on graph nodes, and another that operates on node weights. The latter form is called the weights version. More specifically, the weights version of an operation takes individual node weights or arrays of weights as arguments, and, when applicable, returns individual weights or arrays of weights.

Multiple edges in a graph can be directed between the same pair of nodes. Thus, directed multigraphs are supported.

Since:

Ptolemy II 0.2

Version:

$Id: DirectedGraph.java 57040 2010-01-27 20:52:32Z cxh $

Author:

Yuhong Xiong, Jie Liu, Paul Whitaker, Shuvra S. Bhattacharyya, Shahrooz Shahparnia

Accepted Rating:

Yellow (pwhitake)

Proposed Rating:

Yellow (pwhitake)

Field Summary

private CycleExistenceAnalysis	_acyclicAnalysis
private java.util.HashMap	_inputEdgeMap
private java.util.HashMap	_outputEdgeMap
private SinkNodeAnalysis	_sinkNodeAnalysis
private SourceNodeAnalysis	_sourceNodeAnalysis
private TransitiveClosureAnalysis	_transitiveClosureAnalysis

Constructor Summary

DirectedGraph()
Construct an empty directed graph.

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

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

Method Summary

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	_connectedSubGraph(Node node, DirectedGraph graph, java.util.Collection remainingNodes) Given a node, get all the edges and nodes that are connected to it directly and/or indirectly.
protected void	_disconnect(Edge edge, Node node) Disconnect an edge from a node that it is incident to.
protected void	_initializeAnalyses() Initialize the list of analyses that are associated with this graph, and initialize the change counter of the graph.
private java.util.ArrayList	_inputEdgeList(Node node)
private java.util.ArrayList	_outputEdgeList(Node node)
protected void	_registerNode(Node node) Register a new node in the graph.
private void	_removeIfPresent(java.util.ArrayList list, java.lang.Object element)
java.util.Collection	backwardReachableNodes(java.util.Collection nodeCollection) Find all the nodes that can be reached backward from the specified collection of nodes.
java.util.Collection	backwardReachableNodes(Node node) Find all the nodes that can be reached backward from the specified node.
java.lang.Object[]	backwardReachableNodes(java.lang.Object weight) Find all the nodes that can be reached backward from the specified node (weights version).
java.lang.Object[]	backwardReachableNodes(java.lang.Object[] weights) Find all the nodes that can be reached backward from the specified collection of nodes (weights version).
java.util.Collection	cycleNodeCollection() Return the nodes that are in cycles.
java.lang.Object[]	cycleNodes() Return the nodes that are in cycles (weights version).
boolean	edgeExists(Node node1, Node node2) Test if an edge exists from one node to another.
boolean	edgeExists(java.lang.Object weight1, java.lang.Object weight2) Test whether an edge exists from one node weight to another.
int	inputEdgeCount(Node node) Return the number of input edges of a specified node.
java.util.Collection	inputEdges(Node node) Return the collection of input edges for a specified node.
boolean	isAcyclic() Test if this graph is acyclic (is a DAG).
int	outputEdgeCount(Node node) Return the number of output edges of a specified node.
java.util.Collection	outputEdges(Node node) Return the collection of output edges for a specified node.
java.util.Collection	predecessorEdges(Node n1, Node n2) Return the collection of edges that make a node n2 a predecessor of a node n1.
java.util.Collection	predecessors(Node node) Return all of the predecessors of a given node in the form of a a collection.
java.util.Collection	reachableNodes(java.util.Collection nodeCollection) Find all the nodes that can be reached from the specified collection of nodes.
java.util.Collection	reachableNodes(Node node) Find all the nodes that can be reached from the specified node.
java.lang.Object[]	reachableNodes(java.lang.Object weight) Find all the nodes that can be reached from any node that has the specified node weight (weights version).
java.lang.Object[]	reachableNodes(java.lang.Object[] weights) Find all the nodes that can be reached from the specified collection of nodes (weights version).
DirectedGraph[]	sccDecomposition() Compute the strongly connected component (SCC) decomposition of a graph.
int	selfLoopEdgeCount(Node node) Return the number of self loop edges of a specified node.
int	sinkNodeCount() Return the number of sink nodes in this graph.
java.util.Collection	sinkNodes() Return all the sink nodes in this graph in the form of a collection.
int	sourceNodeCount() Return the number of source nodes in this graph.
java.util.Collection	sourceNodes() Return all the source nodes in this graph in the form of a collection.
java.util.LinkedList	subgraphs() Return a list of disconnected subgraphs of this graph.
java.util.Collection	successorEdges(Node n1, Node n2) Return the collection of edges that make a node n2 a successor of a node n1.
java.util.Collection	successors(Node node) Return all of the successors of a given node in the form of a a collection.
DirectedAcyclicGraph	toDirectedAcyclicGraph() Return an acyclic graph if this graph is acyclic.
java.util.List	topologicalSort(java.util.Collection nodeCollection) Sort a collection of graph nodes in their topological order as long as no two of the given nodes are mutually reachable by each other.
java.lang.Object[]	topologicalSort(java.lang.Object[] weights) Sort the given nodes in their topological order as long as no two of the given nodes are mutually reachable by each other (weights version).
boolean[][]	transitiveClosure() Return transitive closure for the graph.

Methods inherited from class ptolemy.graph.Graph

_addEdge, _connectEdge, _disconnectEdge, _emptyGraph, _registerChange, _registerEdge, addAnalysis, addEdge, addEdge, addEdge, addEdge, addEdge, addEdges, addGraph, addNode, addNode, addNodes, addNodeWeight, addNodeWeights, changeCount, clone, cloneAs, connectedComponents, containsEdge, containsEdgeWeight, containsNode, containsNodeWeight, edge, edge, edgeCount, edgeLabel, edgeLabel, edges, edges, edges, edgeWeight, equals, hashCode, hidden, hiddenEdgeCount, hiddenEdges, hideEdge, incidentEdgeCount, incidentEdges, neighborEdges, neighbors, node, node, nodeCount, nodeLabel, nodeLabel, nodes, nodes, nodes, nodeWeight, removeEdge, removeNode, restoreEdge, selfLoopEdgeCount, selfLoopEdges, selfLoopEdges, subgraph, subgraph, toString, validateWeight, validateWeight, validateWeight, validateWeight, validEdgeWeight, validNodeWeight, weightArray

Methods inherited from class java.lang.Object

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

Field Detail

_inputEdgeMap

private java.util.HashMap _inputEdgeMap

_outputEdgeMap

private java.util.HashMap _outputEdgeMap

_acyclicAnalysis

private CycleExistenceAnalysis _acyclicAnalysis

_transitiveClosureAnalysis

private TransitiveClosureAnalysis _transitiveClosureAnalysis

_sinkNodeAnalysis

private SinkNodeAnalysis _sinkNodeAnalysis

_sourceNodeAnalysis

private SourceNodeAnalysis _sourceNodeAnalysis

Constructor Detail

DirectedGraph

public DirectedGraph()

Construct an empty directed graph.

DirectedGraph

public DirectedGraph(int nodeCount)

Construct an empty directed 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 integer specifying the number of nodes

DirectedGraph

public DirectedGraph(int nodeCount,
                     int edgeCount)

Construct an empty directed 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

backwardReachableNodes

public java.util.Collection backwardReachableNodes(Node node)

Find all the nodes that can be reached backward from the specified node. The reachable nodes do not include the argument unless there is a loop from the specified node back to itself.

Parameters:

node - A node in this graph.

Returns:

The collection of nodes that is backward-reachable from the specified node; each element is a Node.

Throws:

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

backwardReachableNodes

public java.lang.Object[] backwardReachableNodes(java.lang.Object weight)

Find all the nodes that can be reached backward from the specified node (weights version). If the specified weight is null, find all the nodes that can be reached backward from any node that is unweighted. The reachable nodes do not include the argument unless there is a loop from the specified node back to itself.

Parameters:

weight - A node weight in this graph.

Returns:

An array of node weights that are backward-reachable from the nodes that have the specified weight; each element is an Object.

Throws:

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

backwardReachableNodes

public java.util.Collection backwardReachableNodes(java.util.Collection nodeCollection)

Find all the nodes that can be reached backward from the specified collection of nodes. The reachable nodes do not include the specific ones unless there is a loop from the specified node back to itself.

Parameters:

nodeCollection - A collection of nodes in this graph; each element is a Node.

Returns:

The collection of nodes that are backward-reachable from the specified nodes; each element is a Node.

backwardReachableNodes

public java.lang.Object[] backwardReachableNodes(java.lang.Object[] weights)

Find all the nodes that can be reached backward from the specified collection of nodes (weights version). The reachable nodes do not include the weights in the argument unless there is a loop from the specified node back to itself.

Parameters:

weights - An array of node weights in this graph; each element is an Object.

Returns:

An array of node weights that are backward-reachable from the nodes that have the specified weights; each element is an Object.

Throws:

GraphElementException - If the one or more of the specified weights is not a node weight in this graph.

cycleNodeCollection

public java.util.Collection cycleNodeCollection()

Return the nodes that are in cycles. If there are multiple cycles, the nodes in all the cycles will be returned.

Returns:

The collection of nodes that are in cycles; each element is a Node.

cycleNodes

public java.lang.Object[] cycleNodes()

Return the nodes that are in cycles (weights version). If there are multiple cycles, the nodes in all the cycles will be returned.

Returns:

An array of node weights that are in cycles; each element is an Object.

edgeExists

public boolean edgeExists(Node node1,
                          Node node2)

Test if an edge exists from one node to another.

Parameters:

node1 - The weight of the first node.

node2 - The weight of the second node.

Returns:

True if the graph includes an edge from the first node to the second node; false otherwise.

edgeExists

public boolean edgeExists(java.lang.Object weight1,
                          java.lang.Object weight2)

Test whether an edge exists from one node weight to another. More specifically, test whether there exists an edge (n1, n2) such that

(n1.getWeight() == weight1) && (n2.getWeight() == weight2) .

Parameters:

weight1 - The first (source) node weight.

weight2 - The second (sink) node weight.

Returns:

True if the graph includes an edge from the first node weight to the second node weight.

inputEdgeCount

public int inputEdgeCount(Node node)

Return the number of input edges of a specified node.

Parameters:

node - The node.

Returns:

The number of input edges.

inputEdges

public java.util.Collection inputEdges(Node node)

Return the collection of input edges for a specified node.

Parameters:

node - The specified node.

Returns:

The collection of input edges; each element is an Edge.

isAcyclic

public boolean isAcyclic()

Test if this graph is acyclic (is a DAG).

Returns:

True if the the graph is acyclic, or empty; false otherwise.

outputEdgeCount

public int outputEdgeCount(Node node)

Return the number of output edges of a specified node.

Parameters:

node - The node.

Returns:

The number of output edges.

outputEdges

public java.util.Collection outputEdges(Node node)

Return the collection of output edges for a specified node.

Parameters:

node - The specified node.

Returns:

The collection of output edges; each element is an Edge.

predecessorEdges

public java.util.Collection predecessorEdges(Node n1,
                                             Node n2)

Return the collection of edges that make a node n2 a predecessor of a node n1. In other words, return the collection of edges directed from n2 to n1. Each element of the collection is an Edge.

Parameters:

n1 - The node n1.

n2 - The node n2.

Returns:

The collection of edges that make n2 a predecessor of n1.

See Also:

successorEdges(Node, Node), Graph.neighborEdges(Node, Node)

predecessors

public java.util.Collection predecessors(Node node)

Return all of the predecessors of a given node in the form of a a collection. Each element of the collection is a Node. A predecessor of a node X is a node that is the source of an edge whose sink is X. All elements in the returned collection are unique nodes.

Parameters:

node - The node whose predecessors are to be returned.

Returns:

The predecessors of the node.

reachableNodes

public java.util.Collection reachableNodes(Node node)

Find all the nodes that can be reached from the specified node. The reachable nodes do not include the specific one unless there is a loop from the specified node back to itself.

Parameters:

node - The specified node.

Returns:

The collection of nodes reachable from the specified one; each element is a Node.

Throws:

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

reachableNodes

public java.lang.Object[] reachableNodes(java.lang.Object weight)

Find all the nodes that can be reached from any node that has the specified node weight (weights version). If the specified weight is null, find all the nodes that can be reached from any node that is unweighted.

Parameters:

weight - The specified node weight.

Returns:

An array of node weights reachable from the specified weight; each element is an Object.

Throws:

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

See Also:

reachableNodes(Node)

reachableNodes

public java.lang.Object[] reachableNodes(java.lang.Object[] weights)

Find all the nodes that can be reached from the specified collection of nodes (weights version). The reachable nodes do not include a specified one unless there is a loop from the specified node back to itself.

Parameters:

weights - An array of node weights; each element is an Object.

Returns:

The array of nodes that are reachable from the specified one; each element is an Object.

See Also:

reachableNodes(Node)

reachableNodes

public java.util.Collection reachableNodes(java.util.Collection nodeCollection)

Find all the nodes that can be reached from the specified collection of nodes. The reachable nodes do not include a specified one unless there is a loop from the specified node back to itself.

Parameters:

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

Returns:

The collection of nodes that are reachable from the specified one; each element is a Node.

sccDecomposition

public DirectedGraph[] sccDecomposition()

Compute the strongly connected component (SCC) decomposition of a graph.

Returns:

An array of instances of DirectedGraph that represent the SCCs of the graph in topological order.

selfLoopEdgeCount

public int selfLoopEdgeCount(Node node)

Return the number of self loop edges of a specified node. A directed self loop edge (an edge whose source and sink nodes are identical) is both an input edge and an output edge of the incident node, but it is not duplicated in the set of incident edges. Thus, the number of edges incident edges to a node is equal to I + O - S, where I is the number of input edges, O is the number of output edges, and S is the number of self loop edges.

Overrides:

selfLoopEdgeCount in class Graph

Parameters:

node - The node.

Returns:

The number of self loop edges.

sinkNodeCount

public int sinkNodeCount()

Return the number of sink nodes in this graph. A sink node is a node that has no output edges.

Returns:

The number of sink nodes.

sinkNodes

public java.util.Collection sinkNodes()

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

Returns:

The sink nodes in this graph.

See Also:

sinkNodeCount()

sourceNodeCount

public int sourceNodeCount()

Return the number of source nodes in this graph. A source node is a node that has no input edges.

Returns:

The number of source nodes.

sourceNodes

public java.util.Collection sourceNodes()

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

Returns:

The source nodes in this graph.

See Also:

sourceNodeCount()

subgraphs

public java.util.LinkedList subgraphs()

Return a list of disconnected subgraphs of this graph.

Returns:

A list of disconnected subgraphs.

successorEdges

public java.util.Collection successorEdges(Node n1,
                                           Node n2)

Return the collection of edges that make a node n2 a successor of a node n1. In other words, return the collection of edges directed from n1 to n2. Each element of the collection is an Edge.

Parameters:

n1 - The node n1.

n2 - The node n2.

Returns:

The collection of edges that make n2 a successor of n1.

See Also:

predecessorEdges(Node, Node), Graph.neighborEdges(Node, Node)

successors

public java.util.Collection successors(Node node)

Return all of the successors of a given node in the form of a a collection. Each element of the collection is a Node. A successor of a node X is a node that is the sink of an edge whose source is X. All elements in the returned collection are unique nodes.

Parameters:

node - The node whose successors are to be returned.

Returns:

The successors of the node.

toDirectedAcyclicGraph

public DirectedAcyclicGraph toDirectedAcyclicGraph()

Return an acyclic graph if this graph is acyclic.

Returns:

An acyclic graph in the form of DirectedAcyclicGraph.

Throws:

GraphException - If the graph is cyclic.

topologicalSort

public java.util.List topologicalSort(java.util.Collection nodeCollection)
                               throws GraphActionException

Sort a collection of graph nodes in their topological order as long as no two of the given nodes are mutually reachable by each other. This method uses the transitive closure matrix. Since generally the graph is checked for cyclicity before this method is called, the use of the transitive closure matrix should not add any overhead. A bubble sort is used for the internal implementation, so the complexity is O(V^2).

Parameters:

nodeCollection - The collection of nodes to be sorted; each element is a Node.

Returns:

The nodes in their sorted order in the form of a list; each element is a Node.

Throws:

GraphActionException - If any two nodes are strongly connected.

See Also:

topologicalSort(Object[])

topologicalSort

public java.lang.Object[] topologicalSort(java.lang.Object[] weights)
                                   throws GraphActionException

Sort the given nodes in their topological order as long as no two of the given nodes are mutually reachable by each other (weights version). The set of nodes to sort is taken as the set of nodes whose weights are contained in the specified weight set. The weights of the sorted nodes are returned.

Parameters:

weights - The weight set.

Returns:

The weights of the sorted nodes.

Throws:

GraphActionException - If any two nodes are strongly connected.

See Also:

topologicalSort(Collection)

transitiveClosure

public boolean[][] transitiveClosure()

Return transitive closure for the graph.

Returns:

Transitive closure for the graph.

_connect

protected void _connect(Edge edge,
                        Node node)

Connect an edge to a node by appropriately modifying the adjacency information associated with the node.

Overrides:

_connect in class Graph

Parameters:

edge - The edge.

node - The node.

Throws:

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

_connectedSubGraph

protected void _connectedSubGraph(Node node,
                                  DirectedGraph graph,
                                  java.util.Collection remainingNodes)

Given a node, get all the edges and nodes that are connected to it directly and/or indirectly. Add them in the given graph. Remove the nodes from the remaining nodes. FIXME: Hidden edges not considered.

Parameters:

node - The given node.

graph - The given graph.

remainingNodes - Set of nodes that haven't been reached.

_disconnect

protected void _disconnect(Edge edge,
                           Node node)

Description copied from class: Graph

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

Overrides:

_disconnect in class Graph

Parameters:

edge - The edge.

node - The node.

_initializeAnalyses

protected void _initializeAnalyses()

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

Overrides:

_initializeAnalyses in class Graph

See Also:

Analysis

_registerNode

protected void _registerNode(Node node)

Register a new node in the graph.

Overrides:

_registerNode in class Graph

Parameters:

node - The new node.

See Also:

Graph._registerEdge(Edge)

_inputEdgeList

private java.util.ArrayList _inputEdgeList(Node node)

_outputEdgeList

private java.util.ArrayList _outputEdgeList(Node node)

_removeIfPresent

private void _removeIfPresent(java.util.ArrayList list,
                              java.lang.Object element)