public class DFAGraph
extends java.lang.Object
DFANode
objects. This class was designed for program analysis that works on a graph
representation but is also useful for implementing any graph algorithms.
Currently available algorithms include reverse post ordering
(topological ordering) and Tarjan's strongly-connected-components (SCC)
algorithm.| Modifier and Type | Class and Description |
|---|---|
class |
DFAGraph.TopIterator |
| Constructor and Description |
|---|
DFAGraph()
Constructs an empty DFAGraph object.
|
| Modifier and Type | Method and Description |
|---|---|
void |
absorb(DFAGraph other)
Absorbs all nodes from another graph.
|
void |
addEdge(DFANode from,
DFANode to)
Adds a directed edge from a node to the other.
|
void |
addNode(DFANode node)
Adds a node to the graph if the node does not exist in the graph.
|
java.util.List<DFANode> |
getEntryNodes()
Returns the list of the nodes that have no predecessors.
|
java.util.List<DFANode> |
getExitNodes()
Returns the list of the nodes that have no successors.
|
DFANode |
getFirst()
Returns the first node in the node list.
|
DFANode |
getLast()
Returns the last node in the node list.
|
DFANode |
getNode(int id)
Returns the node indexed by the specified id in the node list.
|
DFANode |
getNode(java.lang.String key,
java.lang.Object data)
Returns the node that contains the specified key/data pair.
|
DFANode |
getNodeWith(java.lang.String key,
java.lang.Object data)
Returns the node that contains the specified key/data pair.
|
java.util.List |
getSCC(DFANode root)
Returns a strongly-connected components (SCC) forest in the graph
computed by the Tarjan's algorithm.
|
boolean |
isEmpty()
Checks if the graph is empty.
|
boolean |
isReachable(DFANode from,
DFANode to)
Checks if the "to" node is reachable from the "from" node by performing
a depth-first-search.
|
java.util.Iterator<DFANode> |
iterator()
Returns an iterator of the nodes.
|
void |
removeEdge(DFANode from,
DFANode to)
Removes an edge from the graph.
|
void |
removeNode(DFANode node)
Removes a node and its associated edges from the graph.
|
void |
removeNodes(java.util.List<DFANode> nodes)
Removes the specified nodes and their associated edges from the graph.
|
int |
size()
Returns the number of nodes contained in this graph.
|
java.lang.String |
toDot(java.lang.String keys,
int num)
Converts the graph to a string in dot format with the given keys.
|
int |
topologicalSort(DFANode root)
Computes and records the topological ordering of each node starting from
the root node.
|
int |
topologicalSortOptimized(DFANode root)
Uses the same reverse-post ordering algorithm as simple topological
sort.
|
java.lang.String |
toString()
Returns a string that shows the contents of the graph (debugging).
|
public void addNode(DFANode node)
node - the node being added.public void absorb(DFAGraph other)
other - the graph being absorbed.public DFANode getNode(int id)
id - the index of the node.public DFANode getNode(java.lang.String key, java.lang.Object data)
key - the key string.data - the data object.public DFANode getNodeWith(java.lang.String key, java.lang.Object data)
key - the key string.data - the data object.public DFANode getFirst()
CFGraph object.public DFANode getLast()
CFGraph object.public java.util.List<DFANode> getExitNodes()
public java.util.List<DFANode> getEntryNodes()
public boolean isEmpty()
public int size()
public void addEdge(DFANode from, DFANode to)
from - the source node.to - the target node.public void removeNode(DFANode node)
node - the node being removed.public void removeNodes(java.util.List<DFANode> nodes)
nodes - the list of nodes to be removed.public void removeEdge(DFANode from, DFANode to)
from - the source node.to - the target node.public java.lang.String toString()
toString in class java.lang.Objectpublic java.util.List getSCC(DFANode root)
root - the starting node of depth-first search.public int topologicalSort(DFANode root)
root - the starting node of depth-first search.public int topologicalSortOptimized(DFANode root)
root - The starting node for reverse-post orderingpublic boolean isReachable(DFANode from, DFANode to)
from - the start node.to - the destination node.public java.lang.String toDot(java.lang.String keys,
int num)
keys - the keys used in the search for the labels.num - the number of labels being printed.public java.util.Iterator<DFANode> iterator()