Class MapGraph

  • All Implemented Interfaces:
    Graph, GraphNodeContent

    public class MapGraph
    extends java.lang.Object
    implements Graph
    An implementation of the Graph that is backed by a Map.
    Version:
    $Revision$
    Author:
    Karan Vahi vahi@isi.edu
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      protected class  MapGraph.BottomUpIterator
      An inner iterator class that traverses through the Graph bottom up.
      protected class  MapGraph.MapGraphIterator
      An inner iterator class that traverses through the Graph.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private LogManager mLogger
      The handle to the logging manager.
      protected java.util.Map mStore
      The map indexed by the id of the GraphNode, used for storing the nodes of the Graph.
      • Fields inherited from interface edu.isi.pegasus.planner.partitioner.graph.Graph

        VERSION
    • Constructor Summary

      Constructors 
      Constructor Description
      MapGraph()
      The default constructor.
      MapGraph​(boolean preserveInsertionOrder)
      The overloaded constructor
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addEdge​(GraphNode parent, GraphNode child)
      Adds an edge between two already existing nodes in the graph.
      void addEdge​(java.lang.String parent, java.lang.String child)
      Adds an edge between two already existing nodes in the graph.
      void addEdges​(java.lang.String child, java.util.List parents)
      A convenience method that allows for bulk addition of edges between already existing nodes in the graph.
      void addNode​(GraphNode node)
      Adds a node to the Graph.
      void addRoot​(GraphNode root)
      Adds a single root node to the Graph.
      java.util.Iterator bottomUpIterator()
      Returns an iterator that traverses the graph bottom up from the leaves.
      java.lang.Object clone()
      Returns a copy of the object.
      java.lang.Object get​(java.lang.Object key)
      It returns the value associated with the key in the map.
      java.util.List<GraphNode> getLeaves()
      Returns the leaf nodes of the Graph.
      GraphNode getNode​(java.lang.String identifier)
      Returns the node matching the id passed.
      java.util.List<GraphNode> getRoots()
      Returns the root nodes of the Graph.
      boolean isEmpty()
      Returns a boolean if there are no nodes in the graph.
      java.util.Iterator iterator()
      Returns an iterator that traverses through the graph using a graph traversal algorithm.
      java.util.Iterator nodeIterator()
      Returns an iterator for the nodes in the Graph.
      boolean remove​(java.lang.String identifier)
      Removes a node from the Graph.
      void resetEdges()
      Resets all the dependencies in the Graph, while preserving the nodes.
      int size()
      Returns the number of nodes in the graph.
      java.util.Iterator<GraphNode> topologicalSortIterator()
      Returns an iterator for the graph that traverses in topological sort order.
      java.lang.String toString()
      The textual representation of the graph node.
      • Methods inherited from class java.lang.Object

        equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
    • Field Detail

      • mStore

        protected java.util.Map mStore
        The map indexed by the id of the GraphNode, used for storing the nodes of the Graph. The value for each key is the corresponding GraphNode of the class.
      • mLogger

        private LogManager mLogger
        The handle to the logging manager.
    • Constructor Detail

      • MapGraph

        public MapGraph()
        The default constructor.
      • MapGraph

        public MapGraph​(boolean preserveInsertionOrder)
        The overloaded constructor
        Parameters:
        preserveInsertionOrder - a boolean indicating whether you want to preserve insertion order. If set to true, the nodeIterator() will return nodes in the order they were added.
    • Method Detail

      • addNode

        public void addNode​(GraphNode node)
        Adds a node to the Graph. It overwrites an already existing node with the same ID.
        Specified by:
        addNode in interface Graph
        Parameters:
        node - the node to be added to the Graph.
      • getNode

        public GraphNode getNode​(java.lang.String identifier)
        Returns the node matching the id passed.
        Specified by:
        getNode in interface Graph
        Parameters:
        identifier - the id of the node.
        Returns:
        the node matching the ID else null.
      • addRoot

        public void addRoot​(GraphNode root)
        Adds a single root node to the Graph. All the exisitng roots of the Graph become children of the root.
        Specified by:
        addRoot in interface Graph
        Parameters:
        root - the GraphNode to be added as a root.
        Throws:
        java.lang.RuntimeException - if a node with the same id already exists.
      • resetEdges

        public void resetEdges()
        Resets all the dependencies in the Graph, while preserving the nodes. The resulting Graph is a graph of independent nodes.
        Specified by:
        resetEdges in interface Graph
      • remove

        public boolean remove​(java.lang.String identifier)
        Removes a node from the Graph.
        Specified by:
        remove in interface Graph
        Parameters:
        identifier - the id of the node to be removed.
        Returns:
        boolean indicating whether the node was removed or not.
      • getRoots

        public java.util.List<GraphNode> getRoots()
        Returns the root nodes of the Graph.
        Specified by:
        getRoots in interface Graph
        Returns:
        a list containing GraphNode corressponding to the root nodes.
      • getLeaves

        public java.util.List<GraphNode> getLeaves()
        Returns the leaf nodes of the Graph.
        Specified by:
        getLeaves in interface Graph
        Returns:
        a list containing GraphNode corressponding to the leaf nodes.
      • addEdge

        public void addEdge​(java.lang.String parent,
                            java.lang.String child)
        Adds an edge between two already existing nodes in the graph.
        Specified by:
        addEdge in interface Graph
        Parameters:
        parent - the parent node ID.
        parent - the parent node ID.
        child - the child node ID.
      • addEdge

        public void addEdge​(GraphNode parent,
                            GraphNode child)
        Adds an edge between two already existing nodes in the graph.
        Specified by:
        addEdge in interface Graph
        Parameters:
        parent - the parent node .
        child - the child node .
      • addEdges

        public void addEdges​(java.lang.String child,
                             java.util.List parents)
        A convenience method that allows for bulk addition of edges between already existing nodes in the graph.
        Specified by:
        addEdges in interface Graph
        Parameters:
        parent - the parent node ID
        parents - list of parent identifiers as String.
      • size

        public int size()
        Returns the number of nodes in the graph.
        Specified by:
        size in interface Graph
        Returns:
        the number of nodes
      • nodeIterator

        public java.util.Iterator nodeIterator()
        Returns an iterator for the nodes in the Graph.
        Specified by:
        nodeIterator in interface Graph
        Returns:
        Iterator
      • iterator

        public java.util.Iterator iterator()
        Returns an iterator that traverses through the graph using a graph traversal algorithm. At any one time, only one iterator can iterate through the graph.
        Specified by:
        iterator in interface Graph
        Returns:
        Iterator through the nodes of the graph.
      • bottomUpIterator

        public java.util.Iterator bottomUpIterator()
        Returns an iterator that traverses the graph bottom up from the leaves. At any one time, only one iterator can iterate through the graph.
        Specified by:
        bottomUpIterator in interface Graph
        Returns:
        Iterator through the nodes of the graph.
      • topologicalSortIterator

        public java.util.Iterator<GraphNode> topologicalSortIterator()
        Returns an iterator for the graph that traverses in topological sort order.
        Specified by:
        topologicalSortIterator in interface Graph
        Returns:
        Iterator through the nodes of the graph.
      • toString

        public java.lang.String toString()
        The textual representation of the graph node.
        Overrides:
        toString in class java.lang.Object
        Returns:
        textual description.
      • isEmpty

        public boolean isEmpty()
        Returns a boolean if there are no nodes in the graph.
        Specified by:
        isEmpty in interface Graph
        Returns:
        boolean
      • clone

        public java.lang.Object clone()
        Returns a copy of the object.
        Overrides:
        clone in class java.lang.Object
        Returns:
        clone of the object.
      • get

        public java.lang.Object get​(java.lang.Object key)
        It returns the value associated with the key in the map.
        Parameters:
        key - the key to the entry in the map.