public class DirectedGraph extends Graph
Multiple edges in a graph can be directed between the same pair of nodes. Thus, directed multigraphs are supported.
Yellow (pwhitake) 
Yellow (pwhitake) 
Modifier and Type  Field and Description 

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

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.

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.

_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
protected TransitiveClosureAnalysis _transitiveClosureAnalysis
public DirectedGraph()
public DirectedGraph(int nodeCount)
nodeCount
 The integer specifying the number of nodespublic DirectedGraph(int nodeCount, int edgeCount)
nodeCount
 The number of nodes.edgeCount
 The number of edges.public java.util.Collection backwardReachableNodes(Node node)
node
 A node in this graph.Node
.GraphElementException
 If the specified node is
not a node in this graph.public java.lang.Object[] backwardReachableNodes(java.lang.Object weight)
weight
 A node weight in this graph.Object
.GraphWeightException
 If the specified weight is
not a node weight in this graph.public java.util.Collection backwardReachableNodes(java.util.Collection nodeCollection)
public java.lang.Object[] backwardReachableNodes(java.lang.Object[] weights)
weights
 An array of node weights in this graph; each
element is an Object
.Object
.GraphElementException
 If the one or more of the specified
weights is not a node weight in this graph.public java.util.Collection cycleNodeCollection()
Node
.public java.lang.Object[] cycleNodes()
Object
.public boolean edgeExists(Node node1, Node node2)
node1
 The weight of the first node.node2
 The weight of the second node.public boolean edgeExists(java.lang.Object weight1, java.lang.Object weight2)
(n1.getWeight() == weight1) && (n2.getWeight() == weight2)
.
weight1
 The first (source) node weight.weight2
 The second (sink) node weight.public int inputEdgeCount(Node node)
node
 The node.public java.util.Collection inputEdges(Node node)
node
 The specified node.Edge
.public boolean isAcyclic()
public int outputEdgeCount(Node node)
node
 The node.public java.util.Collection outputEdges(Node node)
node
 The specified node.Edge
.public java.util.Collection predecessorEdges(Node n1, Node n2)
Edge
.n1
 The node n1.n2
 The node n2.successorEdges(Node, Node)
,
Graph.neighborEdges(Node, Node)
public java.util.Collection predecessors(Node node)
node
 The node whose predecessors are to be returned.public java.util.Collection reachableNodes(Node node)
node
 The specified node.Node
.GraphElementException
 If the specified node is
not a node in this graph.public java.lang.Object[] reachableNodes(java.lang.Object weight)
weight
 The specified node weight.Object
.GraphWeightException
 If the specified node weight is
not a node weight in this graph.reachableNodes(Node)
public java.lang.Object[] reachableNodes(java.lang.Object[] weights)
weights
 An array of node weights; each element is an
Object
.Object
.reachableNodes(Node)
public java.util.Collection reachableNodes(java.util.Collection nodeCollection)
public DirectedGraph[] sccDecomposition()
public int selfLoopEdgeCount(Node node)
selfLoopEdgeCount
in class Graph
node
 The node.public int sinkNodeCount()
public java.util.Collection sinkNodes()
Node
.sinkNodeCount()
public int sourceNodeCount()
public java.util.Collection sourceNodes()
Node
.sourceNodeCount()
public java.util.LinkedList subgraphs()
public java.util.Collection successorEdges(Node n1, Node n2)
Edge
.n1
 The node n1.n2
 The node n2.predecessorEdges(Node, Node)
,
Graph.neighborEdges(Node, Node)
public java.util.Collection successors(Node node)
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.node
 The node whose successors are to be returned.public DirectedAcyclicGraph toDirectedAcyclicGraph()
DirectedAcyclicGraph
.GraphException
 If the graph is cyclic.public java.util.List topologicalSort(java.util.Collection nodeCollection) throws GraphActionException
nodeCollection
 The collection of nodes to be sorted;
each element is a Node
.Node
.GraphActionException
 If any two nodes are strongly
connected.topologicalSort(Object[])
public java.lang.Object[] topologicalSort(java.lang.Object[] weights) throws GraphActionException
weights
 The weight set.GraphActionException
 If any two nodes are strongly
connected.topologicalSort(Collection)
public boolean[][] transitiveClosure()
protected void _connect(Edge edge, Node node)
_connect
in class Graph
edge
 The edge.node
 The node.GraphConstructionException
 If the edge has already
been connected to the node.protected void _connectedSubGraph(Node node, DirectedGraph graph, java.util.Collection remainingNodes)
node
 The given node.graph
 The given graph.remainingNodes
 Set of nodes that haven't been reached.protected void _disconnect(Edge edge, Node node)
Graph
_disconnect
in class Graph
edge
 The edge.node
 The node.protected void _initializeAnalyses()
_initializeAnalyses
in class Graph
Analysis
protected void _registerNode(Node node)
_registerNode
in class Graph
node
 The new node.Graph._registerEdge(Edge)