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 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.-
Fields inherited from class edu.isi.pegasus.planner.partitioner.Partitioner
mGraph, mLogger, mProps, mRoot, PACKAGE_NAME, VERSION
-
-
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.
-
-
-
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 classPartitioner
- 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 classPartitioner
- 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 callbacknodes
- the list ofGraphNode
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 callbackparent
- the parent levelchild
- 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.
-
-