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.vdl.planner;
017:
018: import java.io.*;
019: import java.util.*;
020:
021: /**
022: * This class is used to represent the graph form of a workflow. The
023: * graph is represented using adjaceny lists. Each node is the name
024: * of a job in the workflow. The arcs represent dependencies of the
025: * jobs on one another.
026: *
027: * @author Jens-S. Vöckler
028: * @author Yong Zhao
029: * @version $Revision $
030: */
031: public class Graph implements Cloneable {
032: /**
033: * The adjacency list representing a graph.
034: */
035: private Map m_adj;
036:
037: /**
038: * Initializes internal objects to hold the graph.
039: */
040: private void initialize() {
041: m_adj = new HashMap();
042: }
043:
044: /**
045: * Default constructor, call the initialize function
046: */
047: public Graph() {
048: initialize();
049: }
050:
051: /**
052: * Clones the graph using a deep copy.
053: */
054: public Object clone() {
055: Graph result = new Graph();
056:
057: for (Iterator i = getVertices(); i.hasNext();) {
058: String node = (String) i.next();
059: result.m_adj.put(new String(node), new ArrayList(
060: neighbors(node)));
061: }
062:
063: return result;
064: }
065:
066: /**
067: * Reads a stream representing the graph. The format of the stream is:
068: *
069: * <pre>
070: * # of vertices
071: * vertex adjcency_list_of_the_vertex
072: * </pre>
073: *
074: * @param reader is an input file open for reading.
075: */
076: public Graph(Reader reader) {
077: String line = null;
078: StringTokenizer token = null;
079:
080: try {
081: LineNumberReader lnr = new LineNumberReader(reader);
082:
083: line = lnr.readLine();
084: token = new StringTokenizer(line);
085: if (token.countTokens() != 1)
086: throw new Error(
087: "Bad format: number of vertices is first line");
088:
089: // number of nodes
090: int n = Integer.parseInt(token.nextToken());
091: initialize();
092:
093: // read rest of graph
094: for (int u = 0; u < n; ++u) {
095: line = lnr.readLine();
096: token = new StringTokenizer(line);
097: if (token.countTokens() < 1)
098: throw new Error(
099: "line "
100: + lnr.getLineNumber()
101: + ": Please specify the vertex and neighbor list.");
102:
103: // add node to graph
104: String node = token.nextToken();
105: addVertex(node);
106:
107: // add arcs to graph
108: while (token.hasMoreTokens()) {
109: String w = token.nextToken();
110: ((List) m_adj.get(node)).add(new String(w));
111: }
112: }
113: } catch (IOException x) {
114: throw new Error("Bad input stream");
115: }
116: }
117:
118: /**
119: * Provides an iterator over the vertices.
120: *
121: * @return an initialized iterator to walk all vertices.
122: */
123: public Iterator getVertices() {
124: return m_adj.keySet().iterator();
125: }
126:
127: /**
128: * Adds a vertex to the adjacency list. The vortex's adjacency
129: * list is initialized to an empty list. If the vortex already
130: * exists, nothing will be done.
131: *
132: * @param node is the name of the vortex to add.
133: * @see #removeVertex( String )
134: */
135: public void addVertex(String node) {
136: if (!m_adj.containsKey(node)) {
137: m_adj.put(new String(node), new ArrayList());
138: }
139: }
140:
141: /**
142: * Removes a vortex from the graph. This is an expensive function,
143: * because the vortex must also be removed from all adjacency lists.
144: *
145: * @param node is the name of the vortex to remove.
146: * @see #addVertex( String )
147: */
148: public void removeVertex(String node) {
149: // remove entry for vortex from adjacency list
150: m_adj.remove(node);
151:
152: // remove vortex from all other adjaceny lists
153: for (Iterator i = getVertices(); i.hasNext();) {
154: List v = (List) m_adj.get((String) i.next());
155: v.remove(node);
156: }
157: }
158:
159: /**
160: * Adds a directed edge between two nodes.
161: *
162: * @param v is the source node
163: * @param w is the destination node
164: * @see #removeArc( String, String )
165: */
166: public void addArc(String v, String w) {
167: // skip, if the arc already exists
168: if (isArc(v, w))
169: return;
170:
171: // add arc
172: ((List) m_adj.get(v)).add(new String(w));
173: }
174:
175: /**
176: * Removes a directed edge between two nodes.
177: *
178: * @param v is the source node
179: * @param w is the destination node
180: * @see #addArc( String, String )
181: */
182: public void removeArc(String v, String w) {
183: ((List) m_adj.get(v)).remove(w);
184: }
185:
186: /**
187: * Predicate to check the existence of a directed edge
188: * between from v to w.
189: *
190: * @param v is the source node
191: * @param w is the destination node
192: */
193: public boolean isArc(String v, String w) {
194: return ((List) m_adj.get(v)).contains(w);
195: }
196:
197: /**
198: * Counts the number of incoming arcs (edges) for a given node.
199: *
200: * @param v is the vortex name to count incoming edge for.
201: * @return the number of incoming edges.
202: * @see #outDegree( String )
203: */
204: public int inDegree(String v) {
205: int result = 0;
206:
207: // for all nodes, see if they have an edge to v
208: for (Iterator i = getVertices(); i.hasNext();) {
209: String w = (String) i.next();
210: if (isArc(w, v))
211: result++;
212: }
213: return result;
214: }
215:
216: /**
217: * Counts the number of outgoing arcs (edges) for a given node.
218: *
219: * @param v is the vortex name to count outgoing edge for.
220: * @return the number of outgoing edges.
221: * @see #inDegree( String )
222: */
223: public int outDegree(String v) {
224: return ((List) m_adj.get(v)).size();
225: }
226:
227: /**
228: * Determines the neighbors of a given node. This is effectively
229: * a copy of the node's adjacency list.
230: *
231: * @param v is the node to determine the neighbors for
232: * @return a copy of the node's adjacency list.
233: */
234: public List neighbors(String v) {
235: return new ArrayList((List) m_adj.get(v));
236: }
237:
238: /**
239: * Counts the number of nodes (vertices) in a graph.
240: * @return the number of vertices.
241: */
242: public int order() {
243: return m_adj.size();
244: }
245:
246: /**
247: * Counts the number of directed edges (arcs) in the graph.
248: * Undirected edges are counted as two directed edges.
249: *
250: * @return number of directed edges.
251: */
252: public int size() {
253: int result = 0;
254: for (Iterator i = m_adj.values().iterator(); i.hasNext();)
255: result += ((List) i.next()).size();
256: return result;
257: }
258:
259: /**
260: * Constructs the reverse graph by inverting the direction of
261: * every arc.
262: * @return a new graph which is the reverse of the current one.
263: */
264: public Graph reverseGraph() {
265: String v = null;
266: Graph result = new Graph();
267:
268: // copy all nodes
269: for (Iterator i = getVertices(); i.hasNext();) {
270: v = (String) i.next();
271: result.addVertex(v);
272: }
273:
274: // copy all edges
275: for (Iterator i = getVertices(); i.hasNext();) {
276: v = (String) i.next();
277: for (Iterator j = ((List) m_adj.get(v)).iterator(); j
278: .hasNext();) {
279: result.addArc((String) j.next(), v);
280: }
281: }
282:
283: return result;
284: }
285:
286: /**
287: * Generates a simple string representation of the graph. The format
288: * of the representation is the same as it is read from a stream.
289: *
290: * @return a complete graph as a single string
291: * @see #Graph( Reader )
292: */
293: public String toString() {
294: String newline = System.getProperty("line.separator", "\r\n");
295: StringBuffer result = new StringBuffer(256);
296:
297: // write order of graph (number of nodes)
298: result.append(order()).append(newline);
299:
300: // write nodes
301: for (Iterator i = getVertices(); i.hasNext();) {
302: String v = (String) i.next();
303: result.append(v);
304:
305: // write adjacency list for node v
306: for (Iterator j = ((List) m_adj.get(v)).iterator(); j
307: .hasNext();) {
308: result.append(' ').append((String) j.next());
309: }
310:
311: result.append(newline);
312: }
313:
314: // done
315: return result.toString();
316: }
317: }
|