edu.isi.pegasus.planner.partitioner

## Class BFS

- java.lang.Object
- - edu.isi.pegasus.planner.partitioner.Partitioner
  - - edu.isi.pegasus.planner.partitioner.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
`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.

### Fields inherited from class edu.isi.pegasus.planner.partitioner.Partitioner

`mGraph, mLogger, mProps, mRoot, PACKAGE_NAME, VERSION`

### Constructor Summary

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

### Method Summary

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