001: /*
002: * @(#)GPGraphTools.java 1.0 1/1/02
003: *
004: * Copyright (C) 2001 Gaudenz Alder
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation; either
009: * version 2.1 of the License, or (at your option) any later version.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: *
016: * You should have received a copy of the GNU Lesser General Public
017: * License along with this library; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019: *
020: */
021:
022: package hero.client.grapheditor;
023:
024: import java.awt.Point;
025: import java.util.ArrayList;
026: import java.util.Comparator;
027: import java.util.HashSet;
028: import java.util.Hashtable;
029: import java.util.Iterator;
030: import java.util.SortedSet;
031: import java.util.TreeSet;
032:
033: import com.jgraph.JGraph;
034: import com.jgraph.graph.CellView;
035: import com.jgraph.graph.DefaultGraphModel;
036: import com.jgraph.graph.EdgeView;
037: import com.jgraph.graph.GraphModel;
038:
039: public class GPGraphTools {
040:
041: public CostFunction createDefaultCostFunction() {
042: return new DefaultCostFunction();
043: }
044:
045: //
046: // Component Counting
047: //
048:
049: public int getComponentCount(WFGraph graph) {
050: GraphModel m = graph.getModel();
051: UnionFind uf = new UnionFind();
052: Object[] all = graph.getAll();
053: // Vertices
054: Object[] v = graph.getVertices(all);
055: for (int i = 0; i < v.length; i++)
056: uf.find(v[i]);
057: // Edges
058: Object[] e = graph.getEdges(all);
059: for (int i = 0; i < e.length; i++) {
060: Object source = graph.getSourceVertex(e[i]);
061: Object target = graph.getTargetVertex(e[i]);
062: uf.union(uf.find(source), uf.find(target));
063: }
064: return uf.getSetCount();
065: }
066:
067: //
068: // Dijkstra Algorithm
069: //
070:
071: public Object[] getShortestPath(WFGraph graph, Object from,
072: Object to, CostFunction cf) {
073: if (cf == null)
074: cf = createDefaultCostFunction();
075: GraphModel model = graph.getModel();
076: PriorityQueue q = new PriorityQueue();
077: Hashtable pred = new Hashtable();
078: q.setPrio(from, 0);
079: // Main Loop
080: Object[] all = graph.getAll();
081: int jmax = graph.getVertices(all).length;
082: for (int j = 0; j < jmax; j++) {
083: double prio = q.getPrio();
084: Object obj = q.pop();
085: if (obj == to)
086: break;
087: Object[] tmp = new Object[] { obj };
088: Object[] e = DefaultGraphModel.getEdges(model, tmp)
089: .toArray();
090: if (e != null) {
091: for (int i = 0; i < e.length; i++) {
092: Object neighbour = graph.getNeighbour(e[i], obj);
093: double newPrio = prio + cf.getCost(graph, e[i]);
094: if (neighbour != null && neighbour != obj
095: && newPrio < q.getPrio(neighbour)) {
096: pred.put(neighbour, e[i]);
097: q.setPrio(neighbour, newPrio);
098: }
099: }
100: }
101: if (q.isEmpty())
102: break;
103: }
104: // Return Path-Array
105: ArrayList list = new ArrayList();
106: Object obj = to;
107: while (obj != null) {
108: list.add(obj);
109: Object edge = pred.get(obj);
110: if (edge != null) {
111: list.add(edge);
112: obj = graph.getNeighbour(edge, obj);
113: } else
114: obj = null;
115: }
116: return list.toArray();
117: }
118:
119: //
120: // Kruskal Algorithm
121: //
122:
123: public Object[] getSpanningTree(WFGraph graph, CostFunction cf) {
124: if (cf == null)
125: cf = createDefaultCostFunction();
126: Object[] all = graph.getAll();
127: SortedSet edges = sort(graph, graph.getEdges(all), cf);
128: UnionFind uf = new UnionFind();
129: HashSet result = new HashSet();
130: while (!edges.isEmpty()) {
131: Object edge = edges.first();
132: edges.remove(edge);
133: Object setA, setB;
134: setA = uf.find(graph.getSourceVertex(edge));
135: setB = uf.find(graph.getTargetVertex(edge));
136: if (setA == null || setB == null || setA != setB) {
137: uf.union(setA, setB);
138: result.add(edge);
139: }
140: }
141: // Create set of vertices
142: HashSet v = new HashSet();
143: Iterator it = result.iterator();
144: while (it.hasNext()) {
145: Object edge = it.next();
146: Object source = graph.getSourceVertex(edge);
147: Object target = graph.getTargetVertex(edge);
148: if (source != null)
149: v.add(source);
150: if (target != null)
151: v.add(target);
152: }
153: Object[] cells = new Object[result.size() + v.size()];
154: System.arraycopy(result.toArray(), 0, cells, 0, result.size());
155: System
156: .arraycopy(v.toArray(), 0, cells, result.size(), v
157: .size());
158: return cells;
159: }
160:
161: //
162: // Sorting With CostFunction
163: //
164:
165: public SortedSet sort(final JGraph graph, Object[] cells,
166: final CostFunction cf) {
167: TreeSet set = new TreeSet(new Comparator() {
168: public int compare(Object o1, Object o2) {
169: Double d1 = new Double(cf.getCost(graph, o1));
170: Double d2 = new Double(cf.getCost(graph, o2));
171: return d1.compareTo(d2);
172: }
173: });
174: for (int i = 0; i < cells.length; i++)
175: set.add(cells[i]);
176: return set;
177: }
178:
179: //
180: // Cost Function
181: //
182:
183: public interface CostFunction {
184:
185: public double getCost(JGraph graph, Object cell);
186:
187: }
188:
189: public class DefaultCostFunction implements CostFunction {
190:
191: public double getCost(JGraph graph, Object cell) {
192: CellView view = graph.getView().getMapping(cell, false);
193: return getLength(view);
194: }
195: }
196:
197: public static double getLength(CellView view) {
198: double cost = 1;
199: if (view instanceof EdgeView) {
200: EdgeView edge = (EdgeView) view;
201: Point last = null, current = null;
202: for (int i = 0; i < edge.getPointCount(); i++) {
203: current = edge.getPoint(i);
204: if (last != null)
205: cost += last.distance(current);
206: last = current;
207: }
208: }
209: return cost;
210: }
211:
212: //
213: // Union-Find
214: //
215:
216: public class UnionFind {
217:
218: protected Hashtable sets = new Hashtable(),
219: cells = new Hashtable();
220:
221: /* Return the number of distinct sets. */
222: public int getSetCount() {
223: return sets.size();
224: }
225:
226: /* Return an object identifying the set that contains the given cell. */
227: public Object find(Object cell) {
228: Object set = null;
229: if (cell != null) {
230: set = cells.get(cell);
231: if (set == null) {
232: set = cell;
233: cells.put(cell, set);
234: HashSet contents = new HashSet();
235: contents.add(cell);
236: sets.put(set, contents);
237: }
238: }
239: return set;
240: }
241:
242: /* Union the given sets such that all elements belong to the same set. */
243: public Object union(Object set1, Object set2) {
244: if (set1 != null && set2 != null && set1 != set2) {
245: HashSet tmp1 = (HashSet) sets.get(set1);
246: HashSet tmp2 = (HashSet) sets.get(set2);
247: if (tmp1 != null && tmp2 != null) {
248: if (tmp1.size() < tmp2.size()) {
249: Object tmp = tmp1;
250: tmp1 = tmp2;
251: tmp2 = (HashSet) tmp;
252: tmp = set1;
253: set1 = set2;
254: set2 = tmp;
255: }
256: tmp1.addAll(tmp2);
257: sets.remove(set2);
258: Iterator it = tmp2.iterator();
259: while (it.hasNext())
260: cells.put(it.next(), set1);
261: }
262: }
263: return set1;
264: }
265:
266: }
267:
268: //
269: // Priority Queue
270: //
271:
272: public class PriorityQueue {
273:
274: protected Hashtable prio = new Hashtable();
275:
276: protected HashSet data = new HashSet();
277:
278: protected double minPrio = Double.MAX_VALUE;
279:
280: protected Object minElt = null;
281:
282: public boolean isEmpty() {
283: return data.isEmpty();
284: }
285:
286: // Removes element but holds prio
287: public Object pop() {
288: Object tmp = minElt;
289: data.remove(tmp);
290: update();
291: return tmp;
292: }
293:
294: /* Return the priority of the top element. */
295: public double getPrio() {
296: return minPrio;
297: }
298:
299: /* Return the priority of the given element. */
300: public double getPrio(Object obj) {
301: if (obj != null) {
302: Double d = (Double) prio.get(obj);
303: if (d != null)
304: return d.doubleValue();
305: }
306: return Double.MAX_VALUE;
307: }
308:
309: protected void update() {
310: Iterator it = data.iterator();
311: minElt = null;
312: minPrio = Double.MAX_VALUE;
313: while (it.hasNext()) {
314: Object tmp = it.next();
315: double prio = getPrio(tmp);
316: if (prio < minPrio) {
317: minPrio = prio;
318: minElt = tmp;
319: }
320: }
321: }
322:
323: /* Set the priority of the given element and add to queue if necessary. */
324: public void setPrio(Object obj, double prio) {
325: Double d = new Double(prio);
326: this.prio.put(obj, d);
327: data.add(obj);
328: if (prio < minPrio) {
329: minPrio = prio;
330: minElt = obj;
331: }
332: }
333:
334: }
335:
336: }
|