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:
016: package org.griphyn.cPlanner.partitioner.graph;
017:
018: import org.griphyn.cPlanner.classes.Data;
019:
020: import org.griphyn.cPlanner.common.LogManager;
021:
022: import java.util.Iterator;
023: import java.util.LinkedList;
024: import java.util.List;
025: import java.util.Map;
026: import java.util.HashMap;
027:
028: /**
029: * An implementation of the Graph that is backed by a Map.
030: *
031: * @author Karan Vahi vahi@isi.edu
032: * @version $Revision: 50 $
033: */
034:
035: public class MapGraph implements Graph {
036:
037: /**
038: * The map indexed by the id of the <code>GraphNode</code>, used for storing
039: * the nodes of the Graph. The value for each key is the corresponding
040: * <code>GraphNode</code> of the class.
041: *
042: */
043: protected Map mStore;
044:
045: /**
046: * The handle to the logging manager.
047: */
048: private LogManager mLogger;
049:
050: /**
051: * The default constructor.
052: */
053: public MapGraph() {
054: mStore = new HashMap();
055: mLogger = LogManager.getInstance();
056: }
057:
058: /**
059: * Adds a node to the Graph. It overwrites an already existing node with the
060: * same ID.
061: *
062: * @param node the node to be added to the Graph.
063: */
064: public void addNode(GraphNode node) {
065: mStore.put(node.getID(), node);
066: }
067:
068: /**
069: * Returns the node matching the id passed.
070: *
071: * @param identifier the id of the node.
072: *
073: * @return the node matching the ID else null.
074: */
075: public GraphNode getNode(String identifier) {
076: Object obj = get(identifier);
077: return (obj == null) ? null : (GraphNode) obj;
078: }
079:
080: /**
081: * Adds a single root node to the Graph. All the exisitng roots of the
082: * Graph become children of the root.
083: *
084: * @param root the <code>GraphNode</code> to be added as a root.
085: *
086: * @throws RuntimeException if a node with the same id already exists.
087: */
088: public void addRoot(GraphNode root) {
089: //sanity check
090: if (mStore.containsKey(root.getID())) {
091: throw new RuntimeException("Node with ID already exists:"
092: + root.getID());
093: }
094:
095: List existingRoots = getRoots();
096: root.setChildren(existingRoots);
097:
098: //for existing root nodes, add a parent as the new Root
099: for (Iterator it = existingRoots.iterator(); it.hasNext();) {
100: GraphNode existing = (GraphNode) it.next();
101: existing.addParent(root);
102: }
103:
104: //add the new root into the graph
105: addNode(root);
106:
107: }
108:
109: /**
110: * Removes a node from the Graph.
111: *
112: * @param identifier the id of the node to be removed.
113: *
114: * @return boolean indicating whether the node was removed or not.
115: */
116: public boolean remove(String identifier) {
117:
118: Object obj = get(identifier);
119: if (obj == null) {
120: //node does not exist only.
121: return false;
122: }
123:
124: GraphNode removalNode = (GraphNode) obj;
125:
126: // the parents of the node now become parents of the children
127: List parents = removalNode.getParents();
128: List children = removalNode.getChildren();
129: for (Iterator pIt = parents.iterator(); pIt.hasNext();) {
130: GraphNode parent = (GraphNode) pIt.next();
131: //for the parent the removal node is no longer a child
132: parent.removeChild(removalNode);
133:
134: //for each child make the parent it's parent instead of removed node
135: for (Iterator cIt = children.iterator(); cIt.hasNext();) {
136: GraphNode child = (GraphNode) cIt.next();
137: child.removeParent(removalNode);
138: child.addParent(parent);
139: parent.addChild(child);
140: }
141: }
142:
143: //we have the correct linkages now
144: //remove the node from the store.
145: mStore.remove(identifier);
146: return true;
147:
148: }
149:
150: /**
151: * Returns the root nodes of the Graph.
152: *
153: * @return a list containing <code>GraphNode</code> corressponding to the
154: * root nodes.
155: */
156: public List getRoots() {
157: List rootNodes = new LinkedList();
158:
159: for (Iterator it = mStore.entrySet().iterator(); it.hasNext();) {
160: GraphNode gn = (GraphNode) ((Map.Entry) it.next())
161: .getValue();
162: if (gn.getParents() == null || gn.getParents().isEmpty()) {
163: rootNodes.add(gn);
164: }
165: }
166:
167: return rootNodes;
168:
169: //Not Generating a dummy node
170: //add a dummy node that is a root to all these nodes.
171: // String rootId = this.DUMMY_NODE_ID;
172: // mRoot = new GraphNode(rootId,rootId);
173: // mRoot.setChildren(rootNodes);
174: // put(rootId,mRoot);
175: //System.out.println(dummyNode);
176:
177: }
178:
179: /**
180: * Returns the leaf nodes of the Graph.
181: *
182: * @return a list containing <code>GraphNode</code> corressponding to the
183: * leaf nodes.
184: */
185: public List getLeaves() {
186: List leaves = new LinkedList();
187:
188: for (Iterator it = mStore.entrySet().iterator(); it.hasNext();) {
189: GraphNode gn = (GraphNode) ((Map.Entry) it.next())
190: .getValue();
191: if (gn.getChildren() == null || gn.getChildren().isEmpty()) {
192: leaves.add(gn);
193: }
194: }
195:
196: return leaves;
197: }
198:
199: /**
200: * Adds an edge between two already existing nodes in the graph.
201: *
202: * @param parent the parent node ID.
203: * @param child the child node ID.
204: */
205: public void addEdge(String parent, String child) {
206: GraphNode childNode = (GraphNode) getNode(child);
207: GraphNode parentNode = (GraphNode) getNode(parent);
208:
209: String notExist = (childNode == null) ? childNode.getID()
210: : (parentNode == null) ? parent : null;
211:
212: if (notExist != null) {
213: /* should be replaced by Graph Exception */
214: throw new RuntimeException(
215: "The node with identifier doesnt exist " + notExist);
216: }
217:
218: childNode.addParent(parentNode);
219: parentNode.addChild(childNode);
220:
221: }
222:
223: /**
224: * A convenience method that allows for bulk addition of edges between
225: * already existing nodes in the graph.
226: *
227: * @param child the child node ID
228: * @param parents list of parent identifiers as <code>String</code>.
229: */
230: public void addEdges(String child, List parents) {
231: GraphNode childNode = (GraphNode) getNode(child);
232:
233: if (childNode == null) {
234: /* should be replaced by Graph Exception */
235: throw new RuntimeException(
236: "The node with identifier doesnt exist " + child);
237: }
238:
239: String parentId;
240: List parentList = new LinkedList();
241:
242: //construct the references to the parent nodes
243: for (Iterator it = parents.iterator(); it.hasNext();) {
244: parentId = (String) it.next();
245: GraphNode parentNode = (GraphNode) get(parentId);
246:
247: if (parentNode == null) {
248: /* should be replaced by Graph Exception */
249: throw new RuntimeException(
250: "The node with identifier doesnt exist "
251: + parentId);
252: }
253:
254: parentList.add(parentNode);
255:
256: //add the child to the parent's child list
257: parentNode.addChild(childNode);
258: }
259: childNode.setParents(parentList);
260:
261: }
262:
263: /**
264: * Returns an iterator for the nodes in the Graph.
265: *
266: * @return Iterator
267: */
268: public Iterator nodeIterator() {
269: return mStore.values().iterator();
270: }
271:
272: /**
273: * Returns an iterator that traverses through the graph using a graph
274: * traversal algorithm. At any one time, only one iterator can
275: * iterate through the graph.
276: *
277: * @return Iterator through the nodes of the graph.
278: */
279: public Iterator iterator() {
280: return new MapGraphIterator();
281: }
282:
283: /**
284: * The textual representation of the graph node.
285: *
286: * @return textual description.
287: */
288: public String toString() {
289: String newLine = System.getProperty("line.separator", "\r\n");
290: String indent = "\t";
291: StringBuffer sb = new StringBuffer(32);
292:
293: GraphNode node;
294: for (Iterator it = nodeIterator(); it.hasNext();) {
295: node = (GraphNode) it.next();
296: sb.append(newLine).append(indent).append("Job ->").append(
297: node.getID());
298:
299: //write out the node children
300: sb.append(" Children's {");
301: for (Iterator it1 = node.getChildren().iterator(); it1
302: .hasNext();) {
303: sb.append(((GraphNode) it1.next()).getID()).append(',');
304: }
305: sb.append("}");
306:
307: //write out the node's parents
308: sb.append(" Parents {");
309: for (Iterator it1 = node.getParents().iterator(); it1
310: .hasNext();) {
311: sb.append(((GraphNode) it1.next()).getID()).append(',');
312: }
313: sb.append("}");
314:
315: }
316:
317: return sb.toString();
318: }
319:
320: /**
321: * Returns a copy of the object.
322: *
323: * @return clone of the object.
324: */
325: public Object clone() {
326: return new java.lang.CloneNotSupportedException(
327: "Clone() not implemented in GraphNode");
328: }
329:
330: /**
331: * It returns the value associated with the key in the map.
332: *
333: * @param key the key to the entry in the map.
334: */
335: public Object get(Object key) {
336: return mStore.get(key);
337: }
338:
339: /**
340: * An inner iterator class that traverses through the Graph.
341: * The traversal of the graph is a modified BFS. A node is added to
342: * the queue only when all it's parents have been added to the queue.
343: */
344: protected class MapGraphIterator implements Iterator {
345:
346: /**
347: * The first in first out queue, that manages the set of gray vertices in a
348: * breadth first search.
349: */
350: private LinkedList mQueue;
351:
352: /**
353: * The current depth of the nodes that are being traversed in the BFS.
354: */
355: private int mCurrentDepth;
356:
357: /**
358: * A temporary list that stores all the nodes on a particular level.
359: */
360: private List mLevelList;
361:
362: /**
363: * The default constructor.
364: */
365: public MapGraphIterator() {
366: mQueue = new LinkedList();
367: mLevelList = new LinkedList();
368: mCurrentDepth = -1;
369:
370: //sanity intialization of all nodes depth
371: for (Iterator it = nodeIterator(); it.hasNext();) {
372: GraphNode node = (GraphNode) it.next();
373: node.setDepth(mCurrentDepth);
374: }
375:
376: //intialize all the root nodes depth to 0
377: //and put them in the queue
378: mCurrentDepth = 0;
379: for (Iterator it = getRoots().iterator(); it.hasNext();) {
380: GraphNode node = (GraphNode) it.next();
381: node.setDepth(mCurrentDepth);
382: mQueue.add(node);
383: }
384: }
385:
386: /**
387: * Always returns false, as an empty iterator.
388: *
389: * @return true if there are still nodes in the queue.
390: */
391: public boolean hasNext() {
392: return !mQueue.isEmpty();
393: }
394:
395: /**
396: * Returns the next object in the traversal order.
397: *
398: * @return null
399: */
400: public Object next() {
401: GraphNode node = (GraphNode) mQueue.getFirst();
402:
403: int depth = node.getDepth();
404: if (mCurrentDepth < depth) {
405:
406: if (mCurrentDepth > 0) {
407: //we are done with one level!
408: //that is when the callback should happen
409: }
410:
411: //a new level starts
412: mCurrentDepth++;
413: mLevelList.clear();
414: }
415: //mLogger.log( "Adding to level " + mCurrentDepth + " " + node.getID(),
416: // LogManager.DEBUG_MESSAGE_LEVEL);
417: mLevelList.add(node);
418:
419: node.setColor(GraphNode.BLACK_COLOR);
420:
421: //add the children to the list only if all the parents
422: //of the child nodes have been traversed.
423: for (Iterator it = node.getChildren().iterator(); it
424: .hasNext();) {
425: GraphNode child = (GraphNode) it.next();
426: if (!child.isColor(GraphNode.GRAY_COLOR)
427: && child.parentsColored(GraphNode.BLACK_COLOR)) {
428: //mLogger.log( "Adding to queue " + child.getID(),
429: // LogManager.DEBUG_MESSAGE_LEVEL );
430: child.setDepth(depth + 1);
431: child.setColor(GraphNode.GRAY_COLOR);
432: mQueue.addLast(child);
433: }
434:
435: }
436: node = (GraphNode) mQueue.removeFirst();
437: //mLogger.log( "Removed " + node.getID(),
438: // LogManager.DEBUG_MESSAGE_LEVEL);
439: return node;
440:
441: }
442:
443: /**
444: * Method is not supported.
445: */
446: public void remove() {
447: throw new java.lang.UnsupportedOperationException(
448: "Method remove() not supported");
449: }
450:
451: }//end of internal iterator class
452: }
|