|
1
21
22 package hero.client.grapheditor;
23
24 import java.awt.Point  ;
25 import java.util.ArrayList ;
26 import java.util.Comparator ;
27 import java.util.HashSet ;
28 import java.util.Hashtable ;
29 import java.util.Iterator ;
30 import java.util.SortedSet ;
31 import java.util.TreeSet ;
32
33 import com.jgraph.JGraph;
34 import com.jgraph.graph.CellView;
35 import com.jgraph.graph.DefaultGraphModel;
36 import com.jgraph.graph.EdgeView;
37 import com.jgraph.graph.GraphModel;
38
39 public class GPGraphTools {
40
41 public CostFunction createDefaultCostFunction() {
42 return new DefaultCostFunction();
43 }
44
45
49 public int getComponentCount(WFGraph graph) {
50 GraphModel m = graph.getModel();
51 UnionFind uf = new UnionFind();
52 Object [] all = graph.getAll();
53 Object [] v = graph.getVertices(all);
55 for (int i = 0; i < v.length; i++)
56 uf.find(v[i]);
57 Object [] e = graph.getEdges(all);
59 for (int i = 0; i < e.length; i++) {
60 Object source = graph.getSourceVertex(e[i]);
61 Object target = graph.getTargetVertex(e[i]);
62 uf.union(uf.find(source), uf.find(target));
63 }
64 return uf.getSetCount();
65 }
66
67
71 public Object [] getShortestPath(WFGraph graph, Object from,
72 Object to, CostFunction cf)
73 {
74 if (cf == null)
75 cf = createDefaultCostFunction();
76 GraphModel model = graph.getModel();
77 PriorityQueue q = new PriorityQueue();
78 Hashtable pred = new Hashtable ();
79 q.setPrio(from, 0);
80 Object [] all = graph.getAll();
82 int jmax = graph.getVertices(all).length;
83 for (int j = 0; j < jmax; j++) {
84 double prio = q.getPrio();
85 Object obj = q.pop();
86 if (obj == to)
87 break;
88 Object [] tmp = new Object []{obj};
89 Object [] e = DefaultGraphModel.getEdges(model, tmp).toArray();
90 if (e != null) {
91 for (int i = 0; i < e.length; i++) {
92 Object neighbour = graph.getNeighbour(e[i], obj);
93 double newPrio = prio + cf.getCost(graph, e[i]);
94 if (neighbour != null && neighbour != obj &&
95 newPrio < q.getPrio(neighbour))
96 {
97 pred.put(neighbour, e[i]);
98 q.setPrio(neighbour, newPrio);
99 }
100 }
101 }
102 if (q.isEmpty())
103 break;
104 }
105 ArrayList list = new ArrayList ();
107 Object obj = to;
108 while (obj != null) {
109 list.add(obj);
110 Object edge = pred.get(obj);
111 if (edge != null) {
112 list.add(edge);
113 obj = graph.getNeighbour(edge, obj);
114 } else
115 obj = null;
116 }
117 return list.toArray();
118 }
119
120
124 public Object [] getSpanningTree(WFGraph graph, CostFunction cf) {
125 if (cf == null)
126 cf = createDefaultCostFunction();
127 Object [] all = graph.getAll();
128 SortedSet edges = sort(graph, graph.getEdges(all), cf);
129 UnionFind uf = new UnionFind();
130 HashSet result = new HashSet ();
131 while (!edges.isEmpty()) {
132 Object edge = edges.first();
133 edges.remove(edge);
134 Object setA, setB;
135 setA = uf.find(graph.getSourceVertex(edge));
136 setB = uf.find(graph.getTargetVertex(edge));
137 if (setA == null || setB == null || setA != setB) {
138 uf.union(setA, setB);
139 result.add(edge);
140 }
141 }
142 HashSet v = new HashSet ();
144 Iterator it = result.iterator();
145 while (it.hasNext()) {
146 Object edge = it.next();
147 Object source = graph.getSourceVertex(edge);
148 Object target = graph.getTargetVertex(edge);
149 if (source != null)
150 v.add(source);
151 if (target != null)
152 v.add(target);
153 }
154 Object [] cells = new Object [result.size()+v.size()];
155 System.arraycopy(result.toArray(), 0, cells, 0, result.size());
156 System.arraycopy(v.toArray(), 0, cells, result.size(), v.size());
157 return cells;
158 }
159
160
164 public SortedSet sort(final JGraph graph, Object [] cells, final CostFunction cf) {
165 TreeSet set = new TreeSet (new Comparator () {
166 public int compare(Object o1, Object o2) {
167 Double d1 = new Double (cf.getCost(graph, o1));
168 Double d2 = new Double (cf.getCost(graph, o2));
169 return d1.compareTo(d2);
170 }
171 });
172 for (int i = 0; i < cells.length; i++)
173 set.add(cells[i]);
174 return set;
175 }
176
177
181 public interface CostFunction {
182
183 public double getCost(JGraph graph, Object cell);
184
185 }
186
187 public class DefaultCostFunction implements CostFunction {
188
189 public double getCost(JGraph graph, Object cell) {
190 CellView view = graph.getView().getMapping(cell, false);
191 return getLength(view);
192 }
193 }
194
195 public static double getLength(CellView view) {
196 double cost = 1;
197 if (view instanceof EdgeView) {
198 EdgeView edge = (EdgeView) view;
199 Point last = null, current = null;
200 for (int i = 0; i < edge.getPointCount(); i++) {
201 current = edge.getPoint(i);
202 if (last != null)
203 cost += last.distance(current);
204 last = current;
205 }
206 }
207 return cost;
208 }
209
210
214 public class UnionFind {
215
216 protected Hashtable sets = new Hashtable (),
217 cells = new Hashtable ();
218
219
220 public int getSetCount() {
221 return sets.size();
222 }
223
224
225 public Object find(Object cell) {
226 Object set = null;
227 if (cell != null) {
228 set = cells.get(cell);
229 if (set == null) {
230 set = cell;
231 cells.put(cell, set);
232 HashSet contents = new HashSet ();
233 contents.add(cell);
234 sets.put(set, contents);
235 }
236 }
237 return set;
238 }
239
240
241 public Object union(Object set1, Object set2) {
242 if (set1 != null && set2 != null && set1 != set2) {
243 HashSet tmp1 = (HashSet ) sets.get(set1);
244 HashSet tmp2 = (HashSet ) sets.get(set2);
245 if (tmp1 != null && tmp2 != null) {
246 if (tmp1.size() < tmp2.size()) {
247 Object tmp = tmp1; tmp1 = tmp2; tmp2 = (HashSet ) tmp;
248 tmp = set1; set1 = set2; set2 = tmp;
249 }
250 tmp1.addAll(tmp2);
251 sets.remove(set2);
252 Iterator it = tmp2.iterator();
253 while (it.hasNext())
254 cells.put(it.next(), set1);
255 }
256 }
257 return set1;
258 }
259
260 }
261
262
266 public class PriorityQueue {
267
268 protected Hashtable prio = new Hashtable ();
269
270 protected HashSet data = new HashSet ();
271
272 protected double minPrio = Double.MAX_VALUE;
273
274 protected Object minElt = null;
275
276 public boolean isEmpty() {
277 return data.isEmpty();
278 }
279
280 public Object pop() {
282 Object tmp = minElt;
283 data.remove(tmp);
284 update();
285 return tmp;
286 }
287
288
289 public double getPrio() {
290 return minPrio;
291 }
292
293
294 public double getPrio(Object obj) {
295 if (obj != null) {
296 Double d = (Double ) prio.get(obj);
297 if (d != null)
298 return d.doubleValue();
299 }
300 return Double.MAX_VALUE;
301 }
302
303 protected void update() {
304 Iterator it = data.iterator();
305 minElt = null;
306 minPrio = Double.MAX_VALUE;
307 while (it.hasNext()) {
308 Object tmp = it.next();
309 double prio = getPrio(tmp);
310 if (prio < minPrio) {
311 minPrio = prio;
312 minElt = tmp;
313 }
314 }
315 }
316
317
318 public void setPrio(Object obj, double prio) {
319 Double d = new Double (prio);
320 this.prio.put(obj, d);
321 data.add(obj);
322 if (prio < minPrio) {
323 minPrio = prio;
324 minElt = obj;
325 }
326 }
327
328 }
329
330 }
331 |
Popular Tags |
Java API By Example, From Geeks To Geeks.