DFAGraph

java.lang.Object
- cetus.analysis.DFAGraph

Direct Known Subclasses:

CFGraph, IPAGraph
```
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.

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

class DFAGraph.TopIterator

Nested Classes
Modifier and Type	Class and Description
`class`	`DFAGraph.TopIterator`

Constructor Summary

Constructors
Constructor and Description

DFAGraph()
Constructs an empty DFAGraph object.

Constructors
Constructor and Description
`DFAGraph()` Constructs an empty DFAGraph object.

Method Summary

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

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

- 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
```
public 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
```
public 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)
```
    Removes the specified nodes and their associated edges from the graph.
    
    Parameters:
    nodes - the list of nodes to be removed.
  - 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 (SCC 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.
  - topologicalSortOptimized
```
public int topologicalSortOptimized(DFANode root)
```
    Uses the same reverse-post ordering algorithm as simple topological sort. But in the presence of cycles introduced by loops, the ordering is optimized to ensure that the entire loop body is reverse-post ordered before the loop exit statements. This can help decrease time during an iterative data flow analysis where subsequent program statements are analyzed without having complete information from the loop. This strategy is also essential for specific analyses such as points-to analysis
    
    Parameters:
    root - The starting node for reverse-post ordering
    
    Returns:
    as with simple topological sort, returns the order of the first reverse-post ordered node
  - 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.

Class DFAGraph

Nested Class Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

DFAGraph

Method Detail

addNode

absorb

getNode

getNode

getNodeWith

getFirst

getLast

getExitNodes

getEntryNodes

isEmpty

size

addEdge

removeNode

removeNodes

removeEdge

toString

getSCC

topologicalSort

topologicalSortOptimized

isReachable

toDot

iterator