001: /*
002: * @(#)Spring.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 com.jgraph.JGraph;
025: import com.jgraph.graph.*;
026: import java.awt.Rectangle;
027: import java.awt.Point;
028: import java.util.*;
029:
030: /**
031: * Class to implement Kamada and Kawai's spring algorithm
032: * with modifications).
033: */
034:
035: public class Spring {
036:
037: static java.util.ResourceBundle resource = java.util.ResourceBundle
038: .getBundle("resources.Traduction")/*#BundleType=List*/;
039:
040: protected WFGraph graph;
041:
042: /** Reference the array of vertices we work on */
043: private CellView[] vertices = null;
044:
045: private static Rectangle rect;
046: private static double xmax, xmin, ymax, ymin;
047: private static int orderedList[]; // this is used to enable a quick lookup
048: // of nodes' array values (which might
049: // differ from their index values)
050: private static int N; // nodes in graph; will be set in compute function
051: private static int EDGES; // edges in graph; set in compute function
052: private static long D[][]; //the graphical distances between all pairs
053: private static double K[][]; // spring strengths
054: private static double Ko; // spring constant
055: private static double L[][]; // ideal spring lengths
056: private static double epsilon;
057: private static double delta[];
058: private static int MAX_TIMES_REPOSITIONED = 10; // constant to limit number
059: // of times thru "inner" loop
060: private static int numTimesRepositioned = 0; // counts number of times
061: // thru "inner" loop
062: private static int NUM_TIMES_MOVED[]; // counts number of times each
063: // vertex has been selected to
064: // move
065:
066: private static int HY_SIZE = 10; // these variables control the E
067: private static int HY_PERCENTAGE = 5;// stopping condition and how it
068: private static double E, E_HY[]; // keeps track of its information
069: private static int COUNTER = 0;
070:
071: private static int mv = -1; // the node chosen to move at each iteration
072: private static double partial_x, partial_y, partial_xx, partial_xy,
073: partial_yx, partial_yy;
074: private static boolean connected;
075:
076: private int DEBUG = 3;
077:
078: public Spring() {
079: this (3);
080: }
081:
082: public Spring(int debug) {
083: DEBUG = debug;
084: }
085:
086: public String compute(WFGraph G) {
087: this .graph = G;
088: double tempValue, maxValue, maxDel;
089: int maxTimes = 0;
090: int mvi, i;
091: int v, u; //DefaultVertex v,u;
092:
093: rect = G.fromScreen(G.getBounds());
094:
095: // Init array of vertices
096: Initialize(G);
097:
098: // if graph not entirely contained in drawing area, change drawing area?
099: // change graph?? (want to make sure that graph is inside the drawing
100: // area before starting....) For now (with the "non-bouncing
101: // moving-function" used), this doesn't need to be enforced)
102:
103: // Also check to make sure that graph is connected, or else we need to
104: // exit here
105: /*
106: for(i=0;i<G.getModel().getVertexCount();i++)
107: if (connected == false)
108: {
109: //System.out.println("Error: This algorithm should not be run on a non-connected graph!");
110: return "Error: This algorithm should not be run on a non-connected graph!";
111: }
112: */
113: // and undirected (maybe a prompt dialog box to ask if it should be made
114: // undirected or if we should cancel the algorithm) but for now just exit
115: // here.
116: if (false) //(G.isDirected())
117: {
118: //System.out.println("Error: This algorithm should not be run on an undirected graph.");
119: return resource.getString("spring.error");
120: }
121:
122: // Done with primary checking start main iterative loop:
123: //int DEBUG = 3;
124: while (DEBUG-- > 0) {
125: // if any pair of vertices share the same position, move them away
126: CheckPositions(G);
127:
128: // determine the next vertex to move according to TempFunction
129:
130: maxDel = 0;
131: for (int index = 0; index < N; index++) {
132: v = index; //G.getModel().getVertex(index);
133:
134: delta[v] = Math.sqrt(findDelta2(G, v));
135: if (delta[v] > maxDel)
136: maxDel = delta[v];
137: if (NUM_TIMES_MOVED[v] > maxTimes)
138: maxTimes = NUM_TIMES_MOVED[v];
139: //System.out.println("Delta v="+delta[v]+" v="+v);
140: }
141:
142: mv = 0;
143: mvi = 0;
144: maxValue = 0;
145: v = mv;
146: for (int index = 1; index < N; index++) {
147: v = index;
148: if (maxTimes != 0)
149: tempValue = TempFunction(delta[v] / maxDel,
150: 1 - NUM_TIMES_MOVED[v]);
151: else
152: // the first time, base the decision only upon the delta
153: tempValue = delta[v] / maxDel;
154: if (tempValue > maxValue) {
155: mv = v;
156: mvi = mv;
157: maxValue = tempValue;
158: }
159: }
160:
161: // see if any stopping conditions are met
162: // DEBUG HERE
163: //System.out.println(System.currentTimeMillis()+" testing conditions");
164: if (delta[mvi] < epsilon) {
165: //System.out.println("mvi="+mvi+" epsilon="+epsilon+" delta[mvi]="+delta[mvi]);
166: break;
167: }
168: if (COUNTER > HY_SIZE)
169: if (E_HY[COUNTER % HY_SIZE] * HY_PERCENTAGE / 100.0 > (E = findE(G))) {
170: //System.out.println("Quitting because of history");
171: break;
172: }
173:
174: // can't quit yet, so put the E in the history array and get ready to
175: // find a new position for vertex 'mv'
176:
177: E_HY[COUNTER % HY_SIZE] = E;
178:
179: numTimesRepositioned = 0;
180:
181: while ((delta[mvi] > epsilon)
182: && (numTimesRepositioned < MAX_TIMES_REPOSITIONED)) {
183: //MoveToNewPosition(G); // this function simulates elastic collision
184: // instead of hitting & sticking
185: //MoveToNewPosition1(G); // this function "hits and sticks"
186: MoveToNewPosition2(G); // this function doesn't care
187: delta[mvi] = Math.sqrt(findDelta2(G, mv));
188: numTimesRepositioned++;
189: }//end "inner" while
190:
191: NUM_TIMES_MOVED[mvi]++;
192:
193: //if redraw is on ???
194:
195: //update.update(false);
196:
197: // if the cool stop button (that isn't implemented) has been pressed
198: // redraw
199: // break;
200:
201: }//end "outer" while
202: return null;
203:
204: }//end main compute function
205:
206: private void Initialize(JGraph G) {
207: //CellView v,u;
208: int i;
209: EDGES = 0;
210: // Create array of vertices amd count edges
211: Object[] cells = G.getRoots();
212: LinkedList list = new LinkedList();
213: for (int idx = 0; idx < cells.length; idx++)
214: if (graph.isVertex(cells[idx]))
215: list.add(cells[idx]);
216: else if (graph.isEdge(cells[idx]))
217: EDGES++;
218:
219: // Create array
220: vertices = graph.getView().getMapping(list.toArray());
221: N = vertices.length; //G.numberOfNodes();
222:
223: makeOrderedList(G);
224: NUM_TIMES_MOVED = new int[N];
225: for (i = 0; i < N; i++)
226: NUM_TIMES_MOVED[i] = 0;
227: EDGES = 0;
228: /*
229: for (v = G.firstNode(); v !=null; v = G.nextNode(v))
230: {
231: for (u = G.nextNode(v); u !=null; u = G.nextNode(u))
232: if (v.hasChild(u)) EDGES++;
233: }
234: */
235: //EDGES=G.getModel().getEdgeCount();
236: epsilon = 0.5 * (N + EDGES);
237: findDistances(G);
238: find_l_and_k(G);
239: delta = new double[N];
240: E_HY = new double[HY_SIZE];
241: xmin = rect.x;
242: xmax = xmin + rect.width;
243: ymin = rect.y;
244: ymax = ymin + rect.height;
245: }
246:
247: private void findDistances(JGraph G) {
248: int s, u, v, p;
249: int i, j, vi, pi, si, ui;
250: boolean done[];
251: Queue queue;
252:
253: queue = new Queue();
254: int vertexCount = vertices.length; //G.getModel().getVertexCount();
255: done = new boolean[vertexCount];
256: D = new long[vertexCount][vertexCount];
257:
258: /* Initialize the distance matrix to 0s */
259: for (i = 0; i < vertexCount; i++)
260: for (j = i; j < vertexCount; j++) {
261: D[i][j] = 0;
262: D[j][i] = 0;
263: }
264:
265: /* For each node, do Dijstra... */
266: for (int index = 0; index < vertexCount; index++) {
267:
268: /* Initialize the done array to false */
269: for (i = 0; i < vertexCount; i++)
270: done[i] = false;
271:
272: done[index] = true;
273:
274: // Create array of neighbours
275: CellView[] adj = getVerticesFor(G, index);
276:
277: // Insert all (index,n) pairs
278: for (int idx2 = 0; idx2 < adj.length; idx2++) {
279: v = getIndexOf(adj[idx2]);
280: queue.push(v);
281: queue.push(index);
282: //System.out.println("Pushed "+v+", "+index);
283: done[v] = true;
284: }
285: while (!(queue.isEmpty())) {
286: v = queue.pop();
287: p = queue.pop();
288: //System.out.println("Popped "+v+", "+p);
289: D[index][v] = D[p][index] + 1;
290: D[v][index] = D[index][v];
291: //System.out.println("p="+p+" v="+v+" index="+index);
292:
293: for (int idx3 = 0; idx3 < vertexCount; idx3++) {
294:
295: // Create array of neighbours
296: CellView[] adj2 = getVerticesFor(G, idx3);
297:
298: for (int idx2 = 0; idx2 < adj2.length; idx2++) {
299: u = getIndexOf(adj2[idx2]);
300: if (!(done[u])) {
301: queue.push(u);
302: queue.push(v);
303: done[u] = true;
304: }
305: }
306: }
307: }
308: }/* for s*/
309:
310: /* Change the appropriate remaining 0's to infinities and set value of the
311: boolean variable connected */
312: connected = true;
313: for (i = 0; i < N; i++)
314: for (j = i + 1; j < N; j++)
315: if (D[i][j] == 0) {
316: connected = false;
317: D[i][j] = Long.MAX_VALUE;
318: D[j][i] = Long.MAX_VALUE;
319: }
320: }//end findDistances function
321:
322: public int getIndexOf(CellView v) {
323: for (int i = 0; i < vertices.length; i++)
324: if (vertices[i] == v)
325: return i;
326: //System.out.println("Illegal Argument in getIndexOf: Vertex not found "+v);
327: return 0;
328: }
329:
330: public CellView[] getVerticesFor(JGraph G, int index) {
331: Set set = DefaultGraphModel.getEdges(G.getModel(),
332: new Object[] { vertices[index].getCell() });
333: Object[] obj = set.toArray();
334: if (obj != null) {
335: CellView[] adj = new CellView[obj.length];
336: for (int i = 0; i < obj.length; i++)
337: adj[i] = (CellView) graph.getView().getMapping(
338: graph.getNeighbour(obj[i], vertices[index]),
339: false);
340: return adj;
341: } else
342: return new CellView[0];
343: }
344:
345: private void makeOrderedList(JGraph G) {
346: int highestIndex, i;
347: CellView v;
348:
349: orderedList = new int[vertices.length];
350: for (int index = 0; index < vertices.length; index++) {
351: //s = vertices(index);
352: orderedList[index] = index; //G.getIndexFromNode(v);
353: }
354: }//end makeOrderedList function
355:
356: private static int enume(int Index) {
357: int i;
358:
359: for (i = 0;; i++)
360: if (orderedList[i] == Index)
361: return i;
362: }//end enum function
363:
364: private void find_l_and_k(JGraph G) {
365: if (D.length == 0)
366: return;
367:
368: int i, j;
369: long diam;
370: double Lo;
371:
372: Ko = 0;
373: int vertexCount = vertices.length;
374: L = new double[vertexCount][vertexCount];
375: K = new double[vertexCount][vertexCount];
376: /* Find the diameter of the graph */
377: diam = D[0][0];
378: for (i = 0; i < vertexCount; i++)
379: for (j = i + 1; j < vertexCount; j++) {
380: if ((diam < D[i][j]) && (D[i][j] < Long.MAX_VALUE))
381: diam = D[i][j];
382: Ko += D[i][j];
383: }
384: Ko = Ko / vertexCount;
385:
386: for (i = 0; i < vertexCount; i++)
387: for (j = i + 1; j < vertexCount; j++) {
388: /* Lo is desired edge length */
389: /* Lo = avgEdgeLength(G); *//* this Lo makes it grow */
390: /* Lo = Math.sqrt(findArea(G))/diam;*//* this Lo makes it shrink */
391: Lo = Math.sqrt(rect.width * rect.height / 4) / diam;
392: L[i][j] = Lo * D[i][j];
393: L[j][i] = L[i][j];
394: if (D[i][j] < Long.MAX_VALUE) {
395: /* K[i][j] = Ko/(D[i][j]*D[i][j]);*/
396: K[i][j] = Ko * Ko / (D[i][j] * D[i][j]);
397: //System.out.println("K.i.j="+K[i][j]+" (if)");
398: } else {
399: K[i][j] = 0;
400: //System.out.println("K="+K[i][j]+" (else) D="+D[i][j]+" i="+i+" j="+j);
401: }
402: K[j][i] = K[i][j];
403: }
404: }//end find_l_and_k function
405:
406: private double findDelta2(JGraph G, int v) {
407: findPartials(G, v);
408: double delta = (partial_x * partial_x + partial_y * partial_y);
409: //System.out.println("v="+v+" delta="+delta);
410: return delta;
411: }
412:
413: private void findPartials(JGraph G, int v) {
414: int u;
415: int vi, ui;
416: double dx, dy, dd;
417:
418: vi = v;
419: partial_x = 0;
420: partial_y = 0;
421: partial_xx = 0;
422: partial_xy = 0;
423: partial_yx = 0;
424: partial_yy = 0;
425: for (u = 0; u < N; u++)
426: if (v != u) {
427: ui = u;
428: dx = vertices[v].getBounds().x
429: - vertices[u].getBounds().x;
430: dy = vertices[v].getBounds().y
431: - vertices[u].getBounds().y;
432: dd = Math.sqrt(dx * dx + dy * dy);
433: partial_x += K[vi][ui] * (dx - L[vi][ui] * dx / dd);
434: partial_y += K[vi][ui] * (dy - L[vi][ui] * dy / dd);
435: partial_xx += K[vi][ui]
436: * (1 - L[vi][ui] * dy * dy / (dd * dd * dd));
437: partial_xy += K[vi][ui]
438: * (L[vi][ui] * dx * dy / (dd * dd * dd));
439: partial_yx += K[vi][ui]
440: * (L[vi][ui] * dy * dx / (dd * dd * dd));
441: partial_yy += K[vi][ui]
442: * (1 - L[vi][ui] * dx * dx / (dd * dd * dd));
443: //System.out.println("k.vi.ui="+K[vi][ui]);
444: }
445: }
446:
447: private static double TempFunction(double del, double times) {
448: return (0.5 * del + 0.5 * times);
449: }
450:
451: private double findE(JGraph G) {
452: int u, v;
453: int vi, ui;
454: double dx, dy, dd, dif;
455: double total = 0;
456:
457: for (v = 0; v < N; v++) {
458: vi = v;
459: for (u = v; u < N; u++) {
460: ui = u;
461: dx = vertices[v].getBounds().x
462: - vertices[u].getBounds().x;
463: dy = vertices[v].getBounds().y
464: - vertices[u].getBounds().y;
465: dd = Math.sqrt(dx * dx + dy * dy);
466: dif = dd - L[vi][ui];
467: total += K[vi][ui] * dif * dif;
468: }
469: }
470: return total / 2;
471: }
472:
473: private void MoveToNewPosition(JGraph G) {
474: double A, B, C, D, E, F, dx, dy;
475: double xpos, ypos, xfrac, yfrac;
476:
477: xpos = vertices[mv].getBounds().x;
478: ypos = vertices[mv].getBounds().y;
479:
480: int mvi = mv;
481: findPartials(G, mv);
482: A = partial_xx;
483: B = partial_xy;
484: C = -(partial_x);
485: D = partial_yx;
486: E = partial_yy;
487: F = -(partial_y);
488: dy = (A * F - C * D) / (A * E - B * D);
489: dx = (C * E - B * F) / (A * E - B * D);
490:
491: while ((dy != 0) && (dx != 0)) {
492: if (xpos + dx < xmin)
493: xfrac = (xpos - xmin) / dx;
494: else if (xpos + dx > xmax)
495: xfrac = (xmax - xpos) / dx;
496: else
497: xfrac = 1;
498:
499: if (ypos + dy < ymin)
500: yfrac = (ypos - ymin) / dy;
501: else if (ypos + dy > ymax)
502: yfrac = (ymax - ypos) / dy;
503: else
504: yfrac = 1;
505: //double x = xpos+dx;
506: //double y = ypos+dy;
507:
508: if (xfrac < yfrac) {
509: xpos += dx * xfrac;
510: dx *= (xfrac - 1);
511: ypos += dy * xfrac;
512: dy *= (1 - xfrac);
513: } else if (yfrac < xfrac) {
514: ypos += dy * yfrac;
515: dy *= (yfrac - 1);
516: xpos += dx * yfrac;
517: dx *= (1 - yfrac);
518: } else {
519: xpos += dx;
520: dx = 0;
521: ypos += dy;
522: dy = 0;
523: }
524: }//end while
525:
526: if (xpos < 0)
527: xpos = 0;
528: if (ypos < 0)
529: ypos = 0;
530: Point p = G.snap(new Point((int) xpos, (int) ypos));
531: vertices[mv].getBounds().setLocation(p);
532: vertices[mv].getBounds().setLocation(
533: new Point((int) xpos, (int) ypos));
534: }
535:
536: private void MoveToNewPosition1(JGraph G) {
537: double A, B, C, D, E, F, dx, dy;
538: double xpos, ypos, xfrac, yfrac;
539:
540: xpos = vertices[mv].getBounds().x;
541: ypos = vertices[mv].getBounds().y;
542:
543: int mvi = mv;
544: findPartials(G, mv);
545: A = partial_xx;
546: B = partial_xy;
547: C = -(partial_x);
548: D = partial_yx;
549: E = partial_yy;
550: F = -(partial_y);
551: dy = (A * F - C * D) / (A * E - B * D);
552: dx = (C * E - B * F) / (A * E - B * D);
553:
554: if (xpos + dx < xmin)
555: xfrac = (xpos - xmin) / dx;
556: else if (xpos + dx > xmax)
557: xfrac = (xmax - xpos) / dx;
558: else
559: xfrac = 1;
560:
561: if (ypos + dy < ymin)
562: yfrac = (ypos - ymin) / dy;
563: else if (ypos + dy > ymax)
564: yfrac = (ymax - ypos) / dy;
565: else
566: yfrac = 1;
567:
568: if (xfrac < yfrac) {
569: yfrac = xfrac;
570: } else if (yfrac < xfrac) {
571: xfrac = yfrac;
572: }
573: double x = xpos + dx;
574: double y = ypos + dy;
575:
576: xpos += dx * xfrac;
577: dx = 0;
578: ypos += dy * yfrac;
579: dy = 0;
580:
581: if (xpos < 0)
582: xpos = 0;
583: if (ypos < 0)
584: ypos = 0;
585: Point p = G.snap(new Point((int) xpos, (int) ypos));
586: vertices[mv].getBounds().setLocation(p);
587: }
588:
589: private void MoveToNewPosition2(JGraph G) {
590: double A, B, C, D, E, F, dx, dy;
591: double xpos, ypos, xfrac, yfrac;
592:
593: xpos = vertices[mv].getBounds().x;
594: ypos = vertices[mv].getBounds().y;
595:
596: int mvi = mv;
597: findPartials(G, mv);
598: A = partial_xx;
599: B = partial_xy;
600: C = -(partial_x);
601: D = partial_yx;
602: E = partial_yy;
603: F = -(partial_y);
604: dy = (A * F - C * D) / (A * E - B * D);
605: dx = (C * E - B * F) / (A * E - B * D);
606:
607: if (xpos < 0)
608: xpos = 0;
609: if (ypos < 0)
610: ypos = 0;
611:
612: Point p = G
613: .snap(new Point((int) (xpos + dx), (int) (ypos + dy)));
614: vertices[mv].getBounds().setLocation(p);
615: }
616:
617: private void CheckPositions(JGraph G) {
618: int v, u;
619: int vi, ui;
620: double rand;
621: boolean OK = false;
622:
623: //while(!OK)
624: // {
625: OK = true;
626: for (v = 0; v < N; v++)
627: for (u = v; u < N; u++)
628: if ((vertices[v].getBounds().x == vertices[u]
629: .getBounds().x)
630: && (vertices[v].getBounds().y == vertices[u]
631: .getBounds().y)) {
632: vi = v;
633: ui = u;
634: rand = (1.4 * Math.random() - 1) * L[vi][ui];
635: Point tmp = new Point(vertices[u].getBounds().x
636: + (int) rand, vertices[u].getBounds().y);
637: vertices[u].getBounds().setLocation(tmp);
638: rand = (1.4 * Math.random() - 1) * L[vi][ui];
639: tmp = new Point(vertices[u].getBounds().x
640: + (int) rand, vertices[u].getBounds().y);
641: vertices[u].getBounds().setLocation(tmp);
642: OK = false;
643: }
644: //}
645: }
646:
647: }//end class KK
|