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: */package org.griphyn.cPlanner.partitioner;
015:
016: import org.griphyn.cPlanner.partitioner.graph.GraphNode;
017:
018: import java.util.List;
019: import java.util.ArrayList;
020: import java.util.LinkedList;
021: import java.util.Map;
022: import java.util.HashMap;
023: import java.util.Iterator;
024:
025: /**
026: * Does a topological sort on the Partition.
027: *
028: * @author Karan Vahi
029: * @version $Revision: 50 $
030: */
031:
032: public class Topological //implements Iterator
033: {
034:
035: /**
036: * The partition that has to be sorted.
037: */
038: private Partition mPartition;
039:
040: /**
041: * An array that contains the number of incoming edges to a node.
042: */
043: private int[] mInDegree;
044:
045: /**
046: * A Map that returns the index into mInDegree map for a particular node
047: * in graph. Maps a ID of the node to an int value, which is the index to
048: * to the array containing the in degree for each node.
049: *
050: * @see #mInDegree
051: */
052: private Map mIndexMap;
053:
054: /**
055: * The overloaded constructor.
056: *
057: * @param p the partition that has to be sorted.
058: */
059: public Topological(Partition p) {
060: mPartition = p;
061: initialize();
062: }
063:
064: /**
065: * Initializes the inDegree for each node of the partition.
066: *
067: */
068: public void initialize() {
069: //build up a inDegree map for each node.
070: int order = mPartition.size();
071: mInDegree = new int[order];
072: mIndexMap = new HashMap(order);
073:
074: int index = 0;
075: //each of the root nodes have in degree of 0
076: for (Iterator it = mPartition.getRootNodes().iterator(); it
077: .hasNext();) {
078: GraphNode root = (GraphNode) it.next();
079: mIndexMap.put(root.getID(), new Integer(index));
080: mInDegree[index++] = 0;
081: }
082:
083: //determine inDegree for other nodes
084: for (Iterator it = mPartition.getRelations().entrySet()
085: .iterator(); it.hasNext();) {
086: Map.Entry entry = (Map.Entry) it.next();
087:
088: mIndexMap.put(entry.getKey(), new Integer(index));
089: mInDegree[index++] = ((List) entry.getValue()).size();
090: }
091:
092: //sanity check
093: if (index != order) {
094: throw new RuntimeException(
095: "Index does not match order of partition "
096: + mPartition.getID());
097: }
098:
099: }
100:
101: /**
102: * Topologically sorts the partition and returns a List of
103: * <code>GraphNode</code> elements. The iterator of the list, returns
104: * the elements in the topological order.
105: *
106: * @return List of <code>GraphNode</code> objects
107: */
108: public List sort() {
109: List l = new LinkedList();
110: int order = mPartition.size();
111:
112: //get all the adjaceny list representation
113: Map relations = this .childrenRepresentation();
114:
115: List queue = new LinkedList();
116:
117: //add all the root nodes to queue first
118: for (Iterator it = this .mPartition.getRootNodes().iterator(); it
119: .hasNext();) {
120: queue.add(((GraphNode) it.next()).getID());
121: }
122:
123: int index;
124: while (!queue.isEmpty()) {
125: String nodeID = (String) queue.remove(0);
126: l.add(nodeID);
127:
128: //traverse all the children of the node
129: if (relations.containsKey(nodeID)) {
130: for (Iterator it = ((List) relations.get(nodeID))
131: .iterator(); it.hasNext();) {
132: String childID = (String) it.next();
133: //remove the edge from node to child by decrementing inDegree
134: index = index(childID);
135: mInDegree[index] -= 1;
136:
137: if (mInDegree[index] == 0) {
138: //add the node to the queue
139: queue.add(childID);
140: }
141: }
142: }
143: }
144:
145: //sanity check
146: if (l.size() != order) {
147: throw new RuntimeException(" Partition "
148: + mPartition.getID() + " has a cycle");
149: }
150:
151: return l;
152: }
153:
154: /**
155: * Returns a map that is index by GraphNode ID's and each value is the list
156: * of ID's of children of that GraphNode.
157: *
158: * @return Map that contains adjacency list's for each node.
159: */
160: protected Map childrenRepresentation() {
161: //adjacency list where List contains parents
162: Map m = new HashMap(mPartition.size());
163:
164: for (Iterator it = mPartition.getRelations().entrySet()
165: .iterator(); it.hasNext();) {
166: Map.Entry entry = (Map.Entry) it.next();
167: Object node = entry.getKey();
168: List parents = (List) entry.getValue();
169:
170: List children = null;
171: for (Iterator pit = parents.iterator(); pit.hasNext();) {
172: Object parent = pit.next();
173: //the node should be in parents adjacency list
174: if (m.containsKey(parent)) {
175: children = (List) m.get(parent);
176: children.add(node);
177: } else {
178: children = new ArrayList(5);
179: children.add(node);
180: m.put(parent, children);
181: }
182: }
183: }
184:
185: return m;
186: }
187:
188: /**
189: * Returns the index of a particular node. The index is used as an index into
190: * arrays.
191: *
192: * @param id the id of the node.
193: *
194: * @return the index
195: */
196: private int index(String id) {
197: return ((Integer) mIndexMap.get(id)).intValue();
198: }
199:
200: }
|