001: /*
002: * This file or a portion of this file is licensed under the terms of
003: * the Globus Toolkit Public License, found in file GTPL, or at
004: * http://www.globus.org/toolkit/download/license.html. This notice must
005: * appear in redistributions of this file, with or without modification.
006: *
007: * Redistributions of this Software, with or without modification, must
008: * reproduce the GTPL in: (1) the Software, or (2) the Documentation or
009: * some other similar material which is provided with the Software (if
010: * any).
011: *
012: * Copyright 1999-2004 University of Chicago and The University of
013: * Southern California. All rights reserved.
014: */
015: package org.griphyn.cPlanner.partitioner;
016:
017: import org.griphyn.cPlanner.common.LogManager;
018: import org.griphyn.cPlanner.common.PegasusProperties;
019:
020: import org.griphyn.cPlanner.partitioner.graph.GraphNode;
021:
022: import java.util.Iterator;
023: import java.util.LinkedList;
024: import java.util.List;
025: import java.util.ArrayList;
026: import java.util.Map;
027:
028: /**
029: * This does a modified breadth first search of the graph to identify the levels.
030: * A node is put in a level only if all the parents of that node are already
031: * assigned a level.
032: *
033: * @author Karan Vahi
034: * @version $Revision: 50 $
035: */
036: public class BFS extends Partitioner {
037:
038: /**
039: * A short description about the partitioner.
040: */
041: public static final String DESCRIPTION = "Level Based Partitioning";
042:
043: /**
044: * The first in first out queue, that manages the set of gray vertices in a
045: * breadth first search.
046: */
047: private LinkedList mQueue;
048:
049: /**
050: * The current depth of the nodes that are being traversed in the BFS.
051: */
052: private int mCurrentDepth;
053:
054: /**
055: * The overloaded constructor.
056: *
057: * @param root the dummy root node of the graph.
058: * @param graph the map containing all the nodes of the graph keyed by
059: * the logical id of the nodes.
060: * @param properties the properties passed to the planner.
061: */
062: public BFS(GraphNode root, Map graph, PegasusProperties properties) {
063: super (root, graph, properties);
064: mQueue = new LinkedList();
065: mCurrentDepth = -1;
066: }
067:
068: /**
069: * Does a constrained breadth first search to identify the partitions, and
070: * calls out to write out the partition graph.
071: *
072: * @param c the callback for the partitioner.
073: */
074: public void determinePartitions(Callback c) {
075: mCurrentDepth = 0;
076: GraphNode node;
077: GraphNode child;
078: int depth = 0;
079: List levelList = new java.util.LinkedList();
080: int i = 0;
081: //they contain those nodes whose parents have not been traversed as yet
082: //but the BFS did it.
083: List orphans = new java.util.LinkedList();
084:
085: //set the depth of the dummy root as 0
086: mRoot.setDepth(mCurrentDepth);
087:
088: mQueue.addLast(mRoot);
089:
090: while (!mQueue.isEmpty()) {
091: node = (GraphNode) mQueue.getFirst();
092: depth = node.getDepth();
093: if (mCurrentDepth < depth) {
094:
095: if (mCurrentDepth > 0) {
096: //we are done with one level!
097: constructPartitions(c, levelList, mCurrentDepth);
098: }
099:
100: //a new level starts
101: mCurrentDepth++;
102: levelList.clear();
103: }
104: mLogger.log("Adding to level " + mCurrentDepth + " "
105: + node.getID(), LogManager.DEBUG_MESSAGE_LEVEL);
106: levelList.add(node);
107:
108: //look at the orphans first to see if any
109: //of the dependency has changed or not.
110: /*it = orphans.iterator();
111: while(it.hasNext()){
112: child = (GraphNode)it.next();
113: if(child.parentsBlack()){
114: child.setDepth(depth + 1);
115: System.out.println("Set depth of " + child.getID() + " to " + child.getDepth());
116:
117: child.traversed();
118: mQueue.addLast(child);
119: }
120:
121: //remove the child from the orphan
122: it.remove();
123: }*/
124:
125: node.setColor(GraphNode.BLACK_COLOR);
126: for (Iterator it = node.getChildren().iterator(); it
127: .hasNext();) {
128: child = (GraphNode) it.next();
129: if (!child.isColor(GraphNode.GRAY_COLOR)
130: && child.parentsColored(GraphNode.BLACK_COLOR)) {
131: mLogger.log("Adding to queue " + child.getID(),
132: LogManager.DEBUG_MESSAGE_LEVEL);
133: child.setDepth(depth + 1);
134: child.setColor(GraphNode.GRAY_COLOR);
135: mQueue.addLast(child);
136: }
137: /*else if(!child.isTraversed() && !child.parentsBlack()){
138: //we have to do the bumping effect
139: System.out.println("Bumping child " + child);
140: orphans.add(child);
141: }*/
142: }
143: node = (GraphNode) mQueue.removeFirst();
144: mLogger.log("Removed " + node.getID(),
145: LogManager.DEBUG_MESSAGE_LEVEL);
146: }
147:
148: //handle the last level of the BFS
149: constructPartitions(c, levelList, mCurrentDepth);
150:
151: //all the partitions are dependant sequentially
152: for (i = mCurrentDepth; i > 1; i--) {
153: constructLevelRelations(c, i - 1, i);
154:
155: }
156:
157: done(c);
158: }
159:
160: /**
161: * Returns a textual description of the transfer implementation.
162: *
163: * @return a short textual description
164: */
165: public String description() {
166: return this .DESCRIPTION;
167: }
168:
169: /**
170: * Given a list of jobs, constructs (one or more) partitions out of it.
171: * Calls out to the partitioner callback, for each of the partitions
172: * constructed.
173: *
174: * @param c the parititoner callback
175: * @param nodes the list of <code>GraphNode</code> objects on a particular level.
176: * @param level the level as determined from the root of the workflow.
177: */
178: protected void constructPartitions(Callback c, List nodes, int level) {
179: //we want to ignore the dummy node partition
180: String id = getPartitionID(mCurrentDepth);
181: Partition p = new Partition(nodes, id);
182: p.setIndex(mCurrentDepth);
183:
184: p.constructPartition();
185: mLogger.log(
186: "Partition " + p.getID() + " is :" + p.getNodeIDs(),
187: LogManager.DEBUG_MESSAGE_LEVEL);
188: c.cbPartition(p);
189:
190: }
191:
192: /**
193: * Calls out to the callback with appropriate relations between the partitions
194: * constructed for the levels.
195: *
196: * @param c the parititoner callback
197: * @param parent the parent level
198: * @param child the child level.
199: */
200: protected void constructLevelRelations(Callback c, int parent,
201: int child) {
202: String childID = getPartitionID(child);
203: String parentID = getPartitionID(parent);
204: List parents = new ArrayList(1);
205: parents.add(parentID);
206: c.cbParents(childID, parents);
207:
208: }
209:
210: /**
211: * Indicates that we are done with the partitioning.
212: * Calls out to the appropriate callback function
213: */
214: protected void done(Callback c) {
215: //done with the partitioning
216: c.cbDone();
217: }
218:
219: /**
220: * Constructs the id for the partition.
221: *
222: * @param level the depth from the root of the graph.
223: *
224: * @return the ID for the Partition.
225: */
226: private String getPartitionID(int level) {
227: StringBuffer sb = new StringBuffer(5);
228: sb.append("ID").append(level);
229: return sb.toString();
230: }
231:
232: }
|