org.griphyn.cPlanner.partitioner
Class BFS

java.lang.Object
  org.griphyn.cPlanner.partitioner.Partitioner
      org.griphyn.cPlanner.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: 50 $

Author:

Karan Vahi

Field Summary

static 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 LinkedList	mQueue The first in first out queue, that manages the set of gray vertices in a breadth first search.

Fields inherited from class org.griphyn.cPlanner.partitioner.Partitioner

mGraph, mLogger, mProps, mRoot, PACKAGE_NAME, VERSION

Constructor Summary

BFS(GraphNode root, Map graph, PegasusProperties properties)
The overloaded constructor.

Method Summary

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, List nodes, int level) Given a list of jobs, constructs (one or more) partitions out of it.
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 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 String DESCRIPTION

A short description about the partitioner.

See Also:

Constant Field Values

mQueue

private 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,
           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 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,
                                   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 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.