Package edu.isi.pegasus.planner.partitioner

Class BFS

  • Direct Known Subclasses:
    Horizontal
    public class BFS
extends Partitioner
    This does a modified breadth first search of the graph to identify the levels. A node is put in a level only if all the parents of that node are already assigned a level.
    Version:
    $Revision$
    Author:
    Karan Vahi

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static java.lang.String DESCRIPTION
      A short description about the partitioner.
      private int mCurrentDepth
      The current depth of the nodes that are being traversed in the BFS.
      private java.util.LinkedList mQueue
      The first in first out queue, that manages the set of gray vertices in a breadth first search.

    • Constructor Summary

      Constructors 
      Constructor Description
      BFS​(GraphNode root, java.util.Map graph, PegasusProperties properties)
      The overloaded constructor.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      protected void constructLevelRelations​(Callback c, int parent, int child)
      Calls out to the callback with appropriate relations between the partitions constructed for the levels.
      protected void constructPartitions​(Callback c, java.util.List nodes, int level)
      Given a list of jobs, constructs (one or more) partitions out of it.
      java.lang.String description()
      Returns a textual description of the transfer implementation.
      void determinePartitions​(Callback c)
      Does a constrained breadth first search to identify the partitions, and calls out to write out the partition graph.
      protected void done​(Callback c)
      Indicates that we are done with the partitioning.
      private java.lang.String getPartitionID​(int level)
      Constructs the id for the partition.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • DESCRIPTION

        public static final java.lang.String DESCRIPTION
        A short description about the partitioner.
        See Also:
        Constant Field Values

      • mQueue

        private java.util.LinkedList mQueue
        The first in first out queue, that manages the set of gray vertices in a breadth first search.

      • mCurrentDepth

        private int mCurrentDepth
        The current depth of the nodes that are being traversed in the BFS.

    • Constructor Detail

      • BFS

        public BFS​(GraphNode root,
           java.util.Map graph,
           PegasusProperties properties)
        The overloaded constructor.
        Parameters:
        root - the dummy root node of the graph.
        graph - the map containing all the nodes of the graph keyed by the logical id of the nodes.
        properties - the properties passed to the planner.

    • Method Detail

      • determinePartitions

        public void determinePartitions​(Callback c)
        Does a constrained breadth first search to identify the partitions, and calls out to write out the partition graph.
        Specified by:
        determinePartitions in class Partitioner
        Parameters:
        c - the callback for the partitioner.

      • description

        public java.lang.String description()
        Returns a textual description of the transfer implementation.
        Specified by:
        description in class Partitioner
        Returns:
        a short textual description

      • constructPartitions

        protected void constructPartitions​(Callback c,
                                   java.util.List nodes,
                                   int level)
        Given a list of jobs, constructs (one or more) partitions out of it. Calls out to the partitioner callback, for each of the partitions constructed.
        Parameters:
        c - the parititoner callback
        nodes - the list of GraphNode objects on a particular level.
        level - the level as determined from the root of the workflow.

      • constructLevelRelations

        protected void constructLevelRelations​(Callback c,
                                       int parent,
                                       int child)
        Calls out to the callback with appropriate relations between the partitions constructed for the levels.
        Parameters:
        c - the parititoner callback
        parent - the parent level
        child - the child level.

      • done

        protected void done​(Callback c)
        Indicates that we are done with the partitioning. Calls out to the appropriate callback function

      • getPartitionID

        private java.lang.String getPartitionID​(int level)
        Constructs the id for the partition.
        Parameters:
        level - the depth from the root of the graph.
        Returns:
        the ID for the Partition.