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 70398 2014-10-22 23:44:32Z cxh $

Author:

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

Accepted Rating:
Yellow (pwhitake)

Proposed Rating:
Yellow (pwhitake)

Field Summary

Fields
Modifier and Type Field and Description

protected TransitiveClosureAnalysis _transitiveClosureAnalysis
The graph analysis for computation of transitive closure.

Fields
Modifier and Type	Field and Description
`protected TransitiveClosureAnalysis`	`_transitiveClosureAnalysis` The graph analysis for computation of transitive closure.

Constructor Summary

Constructors
Constructor and Description
`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

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`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.
`protected void`	`_registerNode(Node node)` Register a new node in the graph.
`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
  - _transitiveClosureAnalysis
```
protected TransitiveClosureAnalysis _transitiveClosureAnalysis
```
    The graph analysis for computation of transitive closure.
- 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)

Class DirectedGraph

Field Summary

Constructor Summary

Method Summary

Methods inherited from class ptolemy.graph.Graph

Methods inherited from class java.lang.Object

Field Detail

_transitiveClosureAnalysis

Constructor Detail

DirectedGraph

DirectedGraph

DirectedGraph

Method Detail

backwardReachableNodes

backwardReachableNodes

backwardReachableNodes

backwardReachableNodes

cycleNodeCollection

cycleNodes

edgeExists

edgeExists

inputEdgeCount

inputEdges

isAcyclic

outputEdgeCount

outputEdges

predecessorEdges

predecessors

reachableNodes

reachableNodes

reachableNodes

reachableNodes

sccDecomposition

selfLoopEdgeCount

sinkNodeCount

sinkNodes

sourceNodeCount

sourceNodes

subgraphs

successorEdges

successors

toDirectedAcyclicGraph

topologicalSort

topologicalSort

transitiveClosure

_connect

_connectedSubGraph

_disconnect

_initializeAnalyses

_registerNode