Package EDU.purdue.cs.bloat.util

Class Graph

    • Constructor Summary

      Constructors 
      Constructor Description
      Graph()
      Constructor.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      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.

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