Class Graph

java.lang.Object
EDU.purdue.cs.bloat.util.Graph
Direct Known Subclasses:
FlowGraph
public class Graph extends 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:

  • Field Details

    • 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 Details

    • Graph

      public Graph()
      Constructor.

  • Method Details

    • roots

      public Collection roots()
      Returns:
      The roots of this Graph. That is, the nodes with no predacessors.

    • reverseRoots

      public Collection reverseRoots()
      Returns:
      The reverse roots of this Graph. That is, the nodes with no successors.

    • succs

      public Collection succs(GraphNode v)
      Return the successors of a given node.

    • preds

      public 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 List preOrder()
      Returns the nodes in this Graph ordered by their pre-order index.

    • postOrder

      public 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(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(Object key)
      Returns the node in this Graph with a given key.

    • keySet

      public Set keySet()
      Returns a Set of the keys used to uniquely identify the nodes in this Graph.

    • removeNode

      public void removeNode(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 String toString()
      Overrides:
      toString in class 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 Collection nodes()
      Returns all the nodes in this Graph.

    • size

      public int size()
      Returns the number of nodes in this Graph.