cetus.analysis
Class DFAGraph

java.lang.Object
  cetus.analysis.DFAGraph

Direct Known Subclasses:

CFGraph

public class DFAGraph
extends java.lang.Object

Class DFAGraph represents a directed graph with a set of 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.

Field Summary

protected java.util.ArrayList<DFANode>

nodes

Constructor Summary

DFAGraph()
Constructs an empty DFAGraph object.

Method Summary

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.
protected DFANode	getFirst() Returns the first node in the node list.
protected 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)
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.
java.lang.String	toString() Returns a string that shows the contents of the graph (debugging).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

nodes

protected java.util.ArrayList<DFANode> nodes

Constructor Detail

DFAGraph

public DFAGraph()

Constructs an empty DFAGraph object.

Method Detail

addNode

public void addNode(DFANode node)

Adds a node to the graph if the node does not exist in the graph.

Parameters:

node - the node being added.

absorb

public void absorb(DFAGraph other)

Absorbs all nodes from another graph.

Parameters:

other - the graph being absorbed.

getNode

public DFANode getNode(int id)

Returns the node indexed by the specified id in the node list.

Parameters:

id - the index of the node.

Returns:

the node indexed by id.

getNode

public DFANode getNode(java.lang.String key,
                       java.lang.Object data)

Returns the node that contains the specified key/data pair.

Parameters:

key - the key string.

data - the data object.

Returns:

the node if there exists a node such that data==node.getData(key), null if no such node exists.

getNodeWith

public DFANode getNodeWith(java.lang.String key,
                           java.lang.Object data)

Returns the node that contains the specified key/data pair.

Parameters:

key - the key string.

data - the data object.

Returns:

the node if there exists a node such that data.equals(node.getData(key)), null if no such node exists.

getFirst

protected DFANode getFirst()

Returns the first node in the node list. This method is useful only when constructing a CFGraph object.

Returns:

the first entry in the node list.

getLast

protected DFANode getLast()

Returns the last node in the node list. This method is useful only when constructing a CFGraph object.

Returns:

the last entry in the node list.

getExitNodes

public java.util.List<DFANode> getExitNodes()

Returns the list of the nodes that have no successors.

Returns:

the list of the nodes.

getEntryNodes

public java.util.List<DFANode> getEntryNodes()

Returns the list of the nodes that have no predecessors.

Returns:

the list of such nodes.

isEmpty

public boolean isEmpty()

Checks if the graph is empty.

Returns:

true if it is, false otherwise.

size

public int size()

Returns the number of nodes contained in this graph.

Returns:

the size.

addEdge

public void addEdge(DFANode from,
                    DFANode to)

Adds a directed edge from a node to the other. Nodes are also added to the graph if they are not present in the graph.

Parameters:

from - the source node.

to - the target node.

removeNode

public void removeNode(DFANode node)

Removes a node and its associated edges from the graph.

Parameters:

node - the node being removed.

removeNodes

public void removeNodes(java.util.List<DFANode> nodes)

removeEdge

public void removeEdge(DFANode from,
                       DFANode to)

Removes an edge from the graph.

Parameters:

from - the source node.

to - the target node.

toString

public java.lang.String toString()

Returns a string that shows the contents of the graph (debugging).

Overrides:

toString in class java.lang.Object

Returns:

the contents of the graph in string.

getSCC

public java.util.List getSCC(DFANode root)

Returns a strongly-connected components (SCC) forest in the graph computed by the Tarjan's algorithm.

Parameters:

root - the starting node of depth-first search.

Returns:

a list of lists of nodes (forest).

topologicalSort

public int topologicalSort(DFANode root)

Computes and records the topological ordering of each node starting from the root node. After calling this method, each node contains an integer number (order) mapped by the key "top-order" ranging from #total_nodes-#reachable_nodes to #total_nodes-1 and the "top-order" of an unreachable node is -1. For example, the nodes of a graph with no unreachable nodes are numbered from 0 to #total_nodes-1.

Parameters:

root - the starting node of depth-first search.

Returns:

the least non-negative numbering of all nodes in the graph.

isReachable

public boolean isReachable(DFANode from,
                           DFANode to)

Checks if the "to" node is reachable from the "from" node by performing a depth-first-search.

Parameters:

from - the start node.

to - the destination node.

Returns:

true if it is reachable, false otherwise.

toDot

public java.lang.String toDot(java.lang.String keys,
                              int num)

Converts the graph to a string in dot format with the given keys. The nodes in the resulting dot format contain node labels mapped by the given keys. For example, toDot("stmt", 1) will label each node with the data object mapped by "stmt".

Parameters:

keys - the keys used in the search for the labels.

num - the number of labels being printed.

Returns:

the result string.

iterator

public java.util.Iterator<DFANode> iterator()

Returns an iterator of the nodes.

Returns:

the iterator.