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.vdl.planner;
016:
017: import java.util.Map;
018: import java.util.HashMap;
019: import java.util.List;
020: import java.util.ArrayList;
021: import java.util.Iterator;
022: import java.io.*;
023:
024: /**
025: * Class which implements a topological sort of a graph.
026: *
027: * @author Jens-S. Vöckler
028: * @author Yong Zhao
029: *
030: * @version $Revision: 50 $
031: * @see Graph
032: */
033: public class Topology {
034: /**
035: * The graph representation.
036: */
037: private Graph m_graph;
038:
039: /**
040: * Hashtable to map vertex name to array index.
041: */
042: private Map m_vertexMap;
043:
044: /**
045: * Array to keep the name of each vertex.
046: */
047: private String[] m_vertices;
048:
049: /**
050: * Array to keep the in-degree of each vertex.
051: */
052: private int[] m_inDeg;
053:
054: /**
055: * Queue to keep 0 in-degree vertices.
056: */
057: private List m_inQueue;
058:
059: /**
060: * Constructor, given a graph, construct internal objects
061: * needed for topological sort.
062: *
063: * @param graph is a graph representation.
064: */
065: public Topology(Graph graph) {
066: m_graph = (Graph) graph.clone();
067: init();
068: }
069:
070: /**
071: * Initializes in-degree array and the corresponding 0 in-degree
072: * queue.
073: */
074: public void init() {
075: // allocate memory for collections
076: int n = m_graph.order();
077: m_vertexMap = new HashMap();
078: m_vertices = new String[n];
079: m_inDeg = new int[n];
080: m_inQueue = new ArrayList();
081:
082: // map nodes
083: int i = 0;
084: for (Iterator e = m_graph.getVertices(); e.hasNext();) {
085: String v = (String) e.next();
086: m_vertices[i] = new String(v);
087: m_vertexMap.put(new String(v), new Integer(i));
088: m_inDeg[i] = m_graph.inDegree(v);
089: ++i;
090: }
091:
092: // put 0 in-degree vertices in the queue
093: for (i = 0; i < n; i++) {
094: if (m_inDeg[i] == 0)
095: m_inQueue.add(new Integer(i));
096: }
097: }
098:
099: /**
100: * Sorts the graph topologically. It first invokes the {@link #init()}
101: * method to start the graph over, and initialize data structures.
102: *
103: * @return A sorted list of vortex names.
104: */
105: public String[] sort() {
106: int n = m_graph.order();
107: String[] s = new String[n];
108:
109: int cnt = 0;
110: int i;
111: while (m_inQueue.size() > 0) {
112: i = ((Integer) m_inQueue.remove(0)).intValue();
113: s[cnt++] = new String(m_vertices[i]);
114:
115: List neighbors = m_graph.neighbors(m_vertices[i]);
116: for (int j = 0; j < neighbors.size(); j++) {
117: String w = (String) neighbors.get(j);
118: int k = ((Integer) m_vertexMap.get(w)).intValue();
119: m_inDeg[k] -= 1;
120: if (m_inDeg[k] == 0)
121: m_inQueue.add(new Integer(k));
122: }
123: }
124: if (cnt != n)
125: throw new Error("The graph is not acyclic");
126:
127: return s;
128: }
129:
130: /**
131: * Sorts the graph topologically, but also with regards to stages. It
132: * first invokes the {@link #init()} method to start the graph over,
133: * and initialize data structures.
134: *
135: * @return a sorted list of zero in-degree vertices.
136: */
137: public String[] stageSort() {
138: int n = m_inQueue.size();
139: if (n == 0)
140: return null;
141:
142: String[] s = new String[n];
143: int cnt = 0;
144: while (cnt < n) {
145: int i = ((Integer) m_inQueue.remove(0)).intValue();
146: s[cnt++] = new String(m_vertices[i]);
147:
148: List neighbors = m_graph.neighbors(m_vertices[i]);
149: for (int j = 0; j < neighbors.size(); j++) {
150: String w = (String) neighbors.get(j);
151: int k = ((Integer) m_vertexMap.get(w)).intValue();
152: m_inDeg[k] -= 1;
153: if (m_inDeg[k] == 0)
154: m_inQueue.add(new Integer(k));
155: }
156: }
157: return s;
158: }
159:
160: /**
161: * The main method contains some simple tests for the sorting algorithms.
162: * The graph to test with is read from stdin.
163: *
164: * @param args are commandline arguments.
165: */
166: public static void main(String[] args) {
167: Graph g = new Graph(new BufferedReader(new InputStreamReader(
168: System.in)));
169: Topology t = new Topology(g);
170: String[] r = t.sort();
171:
172: System.out.println("The topological sorting result:");
173: for (int i = 0; i < r.length; i++)
174: System.out.print(r[i] + " ");
175: System.out.println();
176:
177: System.out.println("The stage-by-stage sorting result:");
178: t.init();
179: while ((r = t.stageSort()) != null) {
180: for (int i = 0; i < r.length; i++)
181: System.out.print(r[i] + " ");
182: System.out.println();
183: }
184:
185: System.out.println("Let's do it in reverse");
186: t = new Topology(g.reverseGraph());
187: r = t.sort();
188: System.out.println("The topological sorting result:");
189: for (int i = 0; i < r.length; i++)
190: System.out.print(r[i] + " ");
191: System.out.println();
192: }
193: }
|