Package EDU.purdue.cs.bloat.util

Class Graph

java.lang.Object

EDU.purdue.cs.bloat.util.Graph

Direct Known Subclasses:

FlowGraph

public class Graph
extends java.lang.Object

Graph represents a graph of nodes with directed edges between them. GraphNodes are created and are added to the Graph before the edges can be constructed. Each GraphNode as a unique key associated with it. For instance, if a Graph represents a control flow graph, each GraphNode would be associated with a basic block.

See Also:

addNode(java.lang.Object, EDU.purdue.cs.bloat.util.GraphNode), addEdge(EDU.purdue.cs.bloat.util.GraphNode, EDU.purdue.cs.bloat.util.GraphNode), GraphNode, FlowGraph

Field Summary

Fields

Modifier and Type	Field	Description
protected int	edgeModCount
protected int	nodeModCount
protected int	removingEdge
protected int	removingNode
protected int	revRootEdgeModCount
protected int	rootEdgeModCount

Constructor Summary

Constructors

Constructor	Description
Graph()	Constructor.

Method Summary

Modifier and Type	Method	Description
void	addEdge(GraphNode v, GraphNode w)	Adds a directed edge from node v to node w.
void	addNode(java.lang.Object key, GraphNode node)	Insertes a node (and its associated key) into this Graph.
GraphNode	getNode(java.lang.Object key)	Returns the node in this Graph with a given key.
boolean	hasEdge(GraphNode v, GraphNode w)	Searches this Graph for an (directed) edge between two GraphNodes.
boolean	hasNode(GraphNode v)	Searchs this Graph for a given GraphNode.
boolean	isAncestorToDescendent(GraphNode v, GraphNode w)	Determines whether or not a node v is an ancestor (has a lower pre-order index and a higher post-order index) of a node w.
java.util.Set	keySet()	Returns a Set of the keys used to uniquely identify the nodes in this Graph.
java.util.Collection	nodes()	Returns all the nodes in this Graph.
java.util.List	postOrder()	Return the nodes in this Graph ordered by their post-order index.
int	postOrderIndex(GraphNode node)	Returns the index of a given node in a post-order ordering of this Graph.
java.util.Collection	preds(GraphNode v)	Returns the predacessors of a given node.
java.util.List	preOrder()	Returns the nodes in this Graph ordered by their pre-order index.
int	preOrderIndex(GraphNode node)	Returns the index of a given node in a pre-order ordering of this Graph.
void	removeEdge(GraphNode v, GraphNode w)
void	removeNode(java.lang.Object key)	Removes a node with a given key from the Graph.
void	removeUnreachable()	Removes all nodes from this Graph that cannot be reached in a pre-order traversal of the Graph.
java.util.Collection	reverseRoots()
java.util.Collection	roots()
int	size()	Returns the number of nodes in this Graph.
java.util.Collection	succs(GraphNode v)	Return the successors of a given node.
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

rootEdgeModCount

protected int rootEdgeModCount

revRootEdgeModCount

protected int revRootEdgeModCount

nodeModCount

protected int nodeModCount

edgeModCount

protected int edgeModCount

removingNode

protected int removingNode

removingEdge

protected int removingEdge

Constructor Detail

Graph

public Graph()

Constructor.

Method Detail

roots

public java.util.Collection roots()

Returns:

The roots of this Graph. That is, the nodes with no predacessors.

reverseRoots

public java.util.Collection reverseRoots()

Returns:

The reverse roots of this Graph. That is, the nodes with no successors.

succs

public java.util.Collection succs(GraphNode v)

Return the successors of a given node.

preds

public java.util.Collection preds(GraphNode v)

Returns the predacessors of a given node.

isAncestorToDescendent

public boolean isAncestorToDescendent(GraphNode v,
                                      GraphNode w)

Determines whether or not a node v is an ancestor (has a lower pre-order index and a higher post-order index) of a node w.

Parameters:

v - Candidate ancestor node.

w - Candidate descendent node.

Returns:

True, if v is an ancestor of w.

preOrderIndex

public int preOrderIndex(GraphNode node)

Returns the index of a given node in a pre-order ordering of this Graph.

postOrderIndex

public int postOrderIndex(GraphNode node)

Returns the index of a given node in a post-order ordering of this Graph.

preOrder

public java.util.List preOrder()

Returns the nodes in this Graph ordered by their pre-order index.

postOrder

public java.util.List postOrder()

Return the nodes in this Graph ordered by their post-order index.

removeUnreachable

public void removeUnreachable()

Removes all nodes from this Graph that cannot be reached in a pre-order traversal of the Graph. These nodes have a pre-order index of -1.

addNode

public void addNode(java.lang.Object key,
                    GraphNode node)

Insertes a node (and its associated key) into this Graph.

Parameters:

key - A unique value associated with this node. For instance, if this Graph represented a control flow graph, the key would be a basic block.

node - The node to be added.

getNode

public GraphNode getNode(java.lang.Object key)

Returns the node in this Graph with a given key.

keySet

public java.util.Set keySet()

Returns a Set of the keys used to uniquely identify the nodes in this Graph.

removeNode

public void removeNode(java.lang.Object key)

Removes a node with a given key from the Graph.

Parameters:

key - The key associated with the node to remove.

addEdge

public void addEdge(GraphNode v,
                    GraphNode w)

Adds a directed edge from node v to node w.

Parameters:

v - Source node.

w - Destination node.

removeEdge

public void removeEdge(GraphNode v,
                       GraphNode w)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

hasNode

public boolean hasNode(GraphNode v)

Searchs this Graph for a given GraphNode.

Parameters:

v - GraphNode to search for.

Returns:

True, if this Graphs contains v.

hasEdge

public boolean hasEdge(GraphNode v,
                       GraphNode w)

Searches this Graph for an (directed) edge between two GraphNodes.

Parameters:

v - Source node of desired edge.

w - Destination node of desired edge.

Returns:

True, if an edge exists between nodes v and w.

nodes

public java.util.Collection nodes()

Returns all the nodes in this Graph.

size

public int size()

Returns the number of nodes in this Graph.