Java > Open Source Codes > hero > client > grapheditor > Spring


1 /*
2  * @(#)Spring.java 1.0 1/1/02
3  *
4  * Copyright (C) 2001 Gaudenz Alder
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this library; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19  *
20  */
21
22 package hero.client.grapheditor;
23
24 import com.jgraph.JGraph;
25 import com.jgraph.graph.*;
26 import java.awt.Rectangle ;
27 import java.awt.Point ;
28 import java.util.*;
29
30 /**
31  * Class to implement Kamada and Kawai's spring algorithm
32  * with modifications).
33  */
34
35 public class Spring {
36
37 static java.util.ResourceBundle resource = java.util.ResourceBundle.getBundle("resources.Traduction")/*#BundleType=List*/;
38
39     protected WFGraph graph;
40
41     /** Reference the array of vertices we work on */
42     private CellView[] vertices = null;
43
44    private static Rectangle rect;
45    private static double xmax,xmin,ymax,ymin;
46    private static int orderedList[]; // this is used to enable a quick lookup
47 // of nodes' array values (which might
48 // differ from their index values)
49 private static int N; // nodes in graph; will be set in compute function
50 private static int EDGES; // edges in graph; set in compute function
51 private static long D[][]; //the graphical distances between all pairs
52 private static double K[][]; // spring strengths
53 private static double Ko; // spring constant
54 private static double L[][]; // ideal spring lengths
55 private static double epsilon;
56    private static double delta[];
57    private static int MAX_TIMES_REPOSITIONED = 10; // constant to limit number
58 // of times thru "inner" loop
59 private static int numTimesRepositioned = 0; // counts number of times
60 // thru "inner" loop
61 private static int NUM_TIMES_MOVED[]; // counts number of times each
62 // vertex has been selected to
63 // move
64
65    private static int HY_SIZE = 10; // these variables control the E
66 private static int HY_PERCENTAGE = 5;// stopping condition and how it
67 private static double E,E_HY[]; // keeps track of its information
68 private static int COUNTER = 0;
69
70    private static int mv = -1; // the node chosen to move at each iteration
71 private static double partial_x,partial_y,partial_xx,
72         partial_xy,partial_yx,partial_yy;
73    private static boolean connected;
74
75    private int DEBUG = 3;
76
77    public Spring() {
78     this(3);
79   }
80
81   public Spring(int debug) {
82     DEBUG = debug;
83   }
84
85    public String compute(WFGraph G)
86      {
87       this.graph = G;
88       double tempValue,maxValue,maxDel; int maxTimes = 0;
89       int mvi,i;
90       int v,u; //DefaultVertex v,u;
91
92       rect = G.fromScreen(G.getBounds());
93
94       // Init array of vertices
95 Initialize(G);
96
97       // if graph not entirely contained in drawing area, change drawing area?
98 // change graph?? (want to make sure that graph is inside the drawing
99 // area before starting....) For now (with the "non-bouncing
100 // moving-function" used), this doesn't need to be enforced)
101
102       // Also check to make sure that graph is connected, or else we need to
103 // exit here
104 /*
105          for(i=0;i<G.getModel().getVertexCount();i++)
106             if (connected == false)
107               {
108                //System.out.println("Error: This algorithm should not be run on a non-connected graph!");
109                return "Error: This algorithm should not be run on a non-connected graph!";
110               }
111       */
112       // and undirected (maybe a prompt dialog box to ask if it should be made
113 // undirected or if we should cancel the algorithm) but for now just exit
114 // here.
115 if (false) //(G.isDirected())
116 {
117             //System.out.println("Error: This algorithm should not be run on an undirected graph.");
118 return resource.getString("spring.error");
119            }
120
121
122       // Done with primary checking start main iterative loop:
123 //int DEBUG = 3;
124 while(DEBUG-->0)
125         {
126          // if any pair of vertices share the same position, move them away
127 CheckPositions(G);
128
129          // determine the next vertex to move according to TempFunction
130
131          maxDel = 0;
132          for (int index = 0; index < N; index++) {
133           v = index; //G.getModel().getVertex(index);
134
135            delta[v]=Math.sqrt(findDelta2(G,v));
136            if (delta[v] > maxDel)
137               maxDel = delta[v];
138            if (NUM_TIMES_MOVED[v] > maxTimes)
139               maxTimes = NUM_TIMES_MOVED[v];
140           //System.out.println("Delta v="+delta[v]+" v="+v);
141 }
142
143          mv = 0; mvi = 0;
144          maxValue = 0;
145          v = mv;
146          for (int index = 1; index < N; index++)
147          {
148             v = index;
149             if (maxTimes != 0)
150                tempValue = TempFunction
151              (delta[v]/maxDel,
152              1 - NUM_TIMES_MOVED[v]);
153             else
154                // the first time, base the decision only upon the delta
155 tempValue = delta[v]/maxDel;
156             if (tempValue > maxValue)
157               {
158                mv = v; mvi = mv;
159                maxValue = tempValue;
160               }
161            }
162
163
164          // see if any stopping conditions are met
165 // DEBUG HERE
166 //System.out.println(System.currentTimeMillis()+" testing conditions");
167 if (delta[mvi] < epsilon)
168            {
169             //System.out.println("mvi="+mvi+" epsilon="+epsilon+" delta[mvi]="+delta[mvi]);
170 break;
171            }
172          if (COUNTER > HY_SIZE)
173             if (E_HY[COUNTER%HY_SIZE] * HY_PERCENTAGE/100.0 > (E = findE(G)))
174               {
175                //System.out.println("Quitting because of history");
176 break;
177               }
178
179          // can't quit yet, so put the E in the history array and get ready to
180 // find a new position for vertex 'mv'
181
182          E_HY[COUNTER%HY_SIZE] = E;
183
184          numTimesRepositioned = 0;
185
186          while ( (delta[mvi] > epsilon)
187              && (numTimesRepositioned < MAX_TIMES_REPOSITIONED) )
188            {
189             //MoveToNewPosition(G); // this function simulates elastic collision
190 // instead of hitting & sticking
191 //MoveToNewPosition1(G); // this function "hits and sticks"
192 MoveToNewPosition2(G); // this function doesn't care
193 delta[mvi] = Math.sqrt(findDelta2(G,mv));
194             numTimesRepositioned++;
195            }//end "inner" while
196
197          NUM_TIMES_MOVED[mvi]++;
198
199          //if redraw is on ???
200
201               //update.update(false);
202
203          // if the cool stop button (that isn't implemented) has been pressed
204 // redraw
205 // break;
206
207         }//end "outer" while
208 return null;
209
210      }//end main compute function
211
212
213
214
215
216    private void Initialize(JGraph G)
217      {
218       //CellView v,u;
219 int i;
220       EDGES = 0;
221       // Create array of vertices amd count edges
222 Object [] cells = G.getRoots();
223       LinkedList list = new LinkedList();
224       for (int idx = 0; idx < cells.length; idx++)
225     if (graph.isVertex(cells[idx]))
226           list.add(cells[idx]);
227         else if (graph.isEdge(cells[idx]))
228           EDGES++;
229
230       // Create array
231 vertices = graph.getView().getMapping(list.toArray());
232       N = vertices.length; //G.numberOfNodes();
233
234       makeOrderedList(G);
235       NUM_TIMES_MOVED = new int[N];
236       for (i=0;i<N;i++)
237          NUM_TIMES_MOVED[i] = 0;
238       EDGES=0;
239       /*
240       for (v = G.firstNode(); v !=null; v = G.nextNode(v))
241         {
242          for (u = G.nextNode(v); u !=null; u = G.nextNode(u))
243             if (v.hasChild(u)) EDGES++;
244         }
245       */
246       //EDGES=G.getModel().getEdgeCount();
247 epsilon = 0.5*(N+EDGES);
248       findDistances(G);
249       find_l_and_k(G);
250       delta = new double[N];
251       E_HY = new double[HY_SIZE];
252       xmin = rect.x; xmax = xmin + rect.width;
253       ymin = rect.y; ymax = ymin + rect.height;
254      }
255
256    private void findDistances(JGraph G)
257      {
258       int s,u,v,p;
259       int i,j,vi,pi,si,ui;
260       boolean done[];
261       Queue queue;
262
263       queue = new Queue();
264       int vertexCount = vertices.length; //G.getModel().getVertexCount();
265 done = new boolean[vertexCount];
266       D = new long[vertexCount][vertexCount];
267
268
269       /* Initialize the distance matrix to 0s */
270       for (i=0;i<vertexCount;i++)
271          for (j=i;j<vertexCount;j++)
272             { D[i][j] = 0; D[j][i] = 0; }
273
274
275       /* For each node, do Dijstra... */
276       for (int index = 0; index < vertexCount; index++) {
277
278          /* Initialize the done array to false */
279          for (i=0;i<vertexCount;i++)
280             done[i] = false;
281
282          done[index] = true;
283
284          // Create array of neighbours
285 CellView[] adj = getVerticesFor(G, index);
286
287          // Insert all (index,n) pairs
288 for (int idx2 = 0; idx2 < adj.length; idx2++) {
289             v = getIndexOf(adj[idx2]);
290             queue.push(v);
291             queue.push(index);
292             //System.out.println("Pushed "+v+", "+index);
293 done[v] = true;
294          }
295          while (!(queue.isEmpty()))
296            {
297             v = queue.pop();
298             p = queue.pop();
299             //System.out.println("Popped "+v+", "+p);
300 D[index][v] = D[p][index] + 1;
301             D[v][index] = D[index][v];
302             //System.out.println("p="+p+" v="+v+" index="+index);
303
304            for (int idx3 = 0; idx3 < vertexCount; idx3++) {
305
306              // Create array of neighbours
307 CellView[] adj2 = getVerticesFor(G, idx3);
308
309              for (int idx2 = 0; idx2 < adj2.length; idx2++) {
310                  u = getIndexOf(adj2[idx2]);
311                  if (!(done[u]))
312                  {
313                   queue.push(u);
314                   queue.push(v);
315                   done[u] = true;
316                  }
317                }
318              }
319            }
320         }/* for s*/
321
322    /* Change the appropriate remaining 0's to infinities and set value of the
323       boolean variable connected */
324    connected = true;
325    for (i=0;i<N;i++)
326       for (j=i+1;j<N;j++)
327          if (D[i][j]==0)
328            {
329             connected = false;
330             D[i][j] = Long.MAX_VALUE;
331             D[j][i] = Long.MAX_VALUE;
332            }
333      }//end findDistances function
334
335      public int getIndexOf(CellView v) {
336       for (int i = 0; i < vertices.length; i++)
337         if (vertices[i] == v)
338           return i;
339       //System.out.println("Illegal Argument in getIndexOf: Vertex not found "+v);
340 return 0;
341      }
342
343      public CellView[] getVerticesFor(JGraph G, int index) {
344       Set set = DefaultGraphModel.getEdges(G.getModel(), new Object []{vertices[index].getCell()});
345        Object [] obj = set.toArray();
346        if (obj != null) {
347          CellView[] adj = new CellView[obj.length];
348          for (int i = 0; i < obj.length; i++)
349       adj[i] = (CellView) graph.getView().getMapping(graph.getNeighbour(obj[i], vertices[index]), false);
350          return adj;
351        } else
352         return new CellView[0];
353     }
354
355    private void makeOrderedList(JGraph G)
356      {
357       int highestIndex,i;
358       CellView v;
359
360       orderedList = new int[vertices.length];
361       for (int index = 0; index < vertices.length; index++) {
362         //s = vertices(index);
363 orderedList[index] = index; //G.getIndexFromNode(v);
364 }
365      }//end makeOrderedList function
366
367    private static int enume(int Index)
368      {
369       int i;
370
371       for (i=0; ;i++)
372          if (orderedList[i] == Index)
373             return i;
374      }//end enum function
375
376    private void find_l_and_k(JGraph G)
377      {
378       if(D.length == 0)
379     return;
380
381       int i,j;
382       long diam;
383       double Lo;
384
385       Ko = 0;
386       int vertexCount = vertices.length;
387       L = new double[vertexCount][vertexCount];
388       K = new double[vertexCount][vertexCount];
389       /* Find the diameter of the graph */
390       diam = D[0][0];
391       for (i=0;i<vertexCount;i++)
392          for (j=i+1;j<vertexCount;j++)
393            {
394             if ((diam < D[i][j]) && (D[i][j] < Long.MAX_VALUE))
395                diam = D[i][j];
396             Ko+= D[i][j];
397            }
398       Ko = Ko/vertexCount;
399
400       for (i=0;i<vertexCount;i++)
401          for (j=i+1;j<vertexCount;j++)
402            {
403             /* Lo is desired edge length */
404         /* Lo = avgEdgeLength(G); */ /* this Lo makes it grow */
405         /* Lo = Math.sqrt(findArea(G))/diam;*/ /* this Lo makes it shrink */
406             Lo = Math.sqrt(rect.width*rect.height/4)/diam;
407             L[i][j] = Lo*D[i][j];
408             L[j][i] = L[i][j];
409             if (D[i][j] < Long.MAX_VALUE) {
410                /* K[i][j] = Ko/(D[i][j]*D[i][j]);*/
411               K[i][j] = Ko*Ko/(D[i][j]*D[i][j]);
412               //System.out.println("K.i.j="+K[i][j]+" (if)");
413 } else {
414                K[i][j] = 0;
415               //System.out.println("K="+K[i][j]+" (else) D="+D[i][j]+" i="+i+" j="+j);
416 }
417             K[j][i] = K[i][j];
418            }
419      }//end find_l_and_k function
420
421
422
423
424
425    private double findDelta2(JGraph G,int v)
426      {
427       findPartials(G,v);
428       double delta = (partial_x*partial_x+partial_y*partial_y);
429       //System.out.println("v="+v+" delta="+delta);
430 return delta;
431      }
432
433
434
435
436
437    private void findPartials(JGraph G,int v)
438      {
439       int u;
440       int vi,ui;
441       double dx,dy,dd;
442
443
444       vi = v;
445       partial_x=0;
446       partial_y=0;
447       partial_xx=0;
448       partial_xy=0;
449       partial_yx=0;
450       partial_yy=0;
451       for (u = 0; u<N; u++)
452          if (v!=u)
453            {
454             ui = u;
455             dx = vertices[v].getBounds().x - vertices[u].getBounds().x;
456             dy = vertices[v].getBounds().y - vertices[u].getBounds().y;
457             dd = Math.sqrt(dx*dx+dy*dy);
458             partial_x+= K[vi][ui]*(dx-L[vi][ui]*dx/dd);
459             partial_y+= K[vi][ui]*(dy-L[vi][ui]*dy/dd);
460             partial_xx+= K[vi][ui]*(1-L[vi][ui]*dy*dy/(dd*dd*dd));
461             partial_xy+= K[vi][ui]*(L[vi][ui]*dx*dy/(dd*dd*dd));
462             partial_yx+= K[vi][ui]*(L[vi][ui]*dy*dx/(dd*dd*dd));
463             partial_yy+= K[vi][ui]*(1-L[vi][ui]*dx*dx/(dd*dd*dd));
464             //System.out.println("k.vi.ui="+K[vi][ui]);
465 }
466      }
467
468    private static double TempFunction(double del, double times)
469      {
470       return (0.5 * del + 0.5 * times);
471      }
472
473
474
475
476
477    private double findE(JGraph G)
478      {
479       int u,v;
480       int vi,ui;
481       double dx,dy,dd,dif;
482       double total=0;
483
484       for (v = 0; v <N; v++)
485         {
486          vi = v;
487          for (u = v; u<N; u++)
488            {
489             ui = u;
490             dx = vertices[v].getBounds().x - vertices[u].getBounds().x;
491             dy = vertices[v].getBounds().y - vertices[u].getBounds().y;
492             dd = Math.sqrt(dx*dx+dy*dy);
493             dif = dd - L[vi][ui];
494             total+= K[vi][ui]*dif*dif;
495            }
496         }
497       return total/2;
498      }
499
500
501
502
503
504
505    private void MoveToNewPosition(JGraph G)
506      {
507       double A,B,C,D,E,F,dx,dy;
508       double xpos,ypos,xfrac,yfrac;
509
510       xpos = vertices[mv].getBounds().x;
511       ypos = vertices[mv].getBounds().y;
512
513       int mvi = mv;
514       findPartials(G,mv);
515             A = partial_xx;
516             B = partial_xy;
517             C = -(partial_x);
518             D = partial_yx;
519             E = partial_yy;
520             F = -(partial_y);
521       dy = (A*F-C*D)/(A*E-B*D);
522       dx = (C*E-B*F)/(A*E-B*D);
523
524       while ( (dy != 0) && (dx != 0) )
525         {
526          if (xpos + dx < xmin)
527             xfrac = (xpos - xmin)/dx;
528          else if (xpos + dx > xmax)
529             xfrac = (xmax - xpos)/dx;
530          else
531             xfrac = 1;
532
533
534          if (ypos + dy < ymin)
535             yfrac = (ypos - ymin)/dy;
536          else if (ypos + dy > ymax)
537             yfrac = (ymax - ypos)/dy;
538          else
539             yfrac = 1;
540 //double x = xpos+dx;
541 //double y = ypos+dy;
542
543          if (xfrac < yfrac)
544            {
545             xpos += dx * xfrac;
546             dx *= (xfrac - 1);
547             ypos += dy * xfrac;
548             dy *= (1 - xfrac);
549            }
550          else if (yfrac < xfrac)
551            {
552             ypos += dy * yfrac;
553             dy *= (yfrac - 1);
554             xpos += dx * yfrac;
555             dx *= (1 - yfrac);
556            }
557          else
558            {
559             xpos += dx;
560             dx = 0;
561             ypos += dy;
562             dy = 0;
563            }
564         }//end while
565
566       if (xpos < 0) xpos = 0;
567       if (ypos < 0) ypos = 0;
568       Point p = G.snap(new Point ((int) xpos, (int) ypos));
569       vertices[mv].getBounds().setLocation(p);
570       vertices[mv].getBounds().setLocation(new Point ((int) xpos,(int) ypos));
571      }
572
573    private void MoveToNewPosition1(JGraph G)
574      {
575       double A,B,C,D,E,F,dx,dy;
576       double xpos,ypos,xfrac,yfrac;
577
578       xpos = vertices[mv].getBounds().x;
579       ypos = vertices[mv].getBounds().y;
580
581
582
583       int mvi = mv;
584       findPartials(G,mv);
585             A = partial_xx;
586             B = partial_xy;
587             C = -(partial_x);
588             D = partial_yx;
589             E = partial_yy;
590             F = -(partial_y);
591       dy = (A*F-C*D)/(A*E-B*D);
592       dx = (C*E-B*F)/(A*E-B*D);
593
594          if (xpos + dx < xmin)
595             xfrac = (xpos - xmin)/dx;
596          else if (xpos + dx > xmax)
597             xfrac = (xmax - xpos)/dx;
598          else
599             xfrac = 1;
600
601
602          if (ypos + dy < ymin)
603             yfrac = (ypos - ymin)/dy;
604          else if (ypos + dy > ymax)
605             yfrac = (ymax - ypos)/dy;
606          else
607             yfrac = 1;
608
609          if (xfrac < yfrac)
610            {
611             yfrac = xfrac;
612            }
613          else if (yfrac < xfrac)
614            {
615             xfrac = yfrac;
616            }
617 double x = xpos+dx;
618 double y = ypos+dy;
619
620             xpos += dx*xfrac;
621             dx = 0;
622             ypos += dy*yfrac;
623             dy = 0;
624
625       if (xpos < 0) xpos = 0;
626       if (ypos < 0) ypos = 0;
627       Point p = G.snap(new Point ((int) xpos, (int) ypos));
628       vertices[mv].getBounds().setLocation(p);
629      }
630
631
632
633    private void MoveToNewPosition2(JGraph G)
634      {
635       double A,B,C,D,E,F,dx,dy;
636       double xpos,ypos,xfrac,yfrac;
637
638       xpos = vertices[mv].getBounds().x;
639       ypos = vertices[mv].getBounds().y;
640
641
642
643
644       int mvi = mv;
645       findPartials(G,mv);
646             A = partial_xx;
647             B = partial_xy;
648             C = -(partial_x);
649             D = partial_yx;
650             E = partial_yy;
651             F = -(partial_y);
652       dy = (A*F-C*D)/(A*E-B*D);
653       dx = (C*E-B*F)/(A*E-B*D);
654
655       if (xpos < 0) xpos = 0;
656       if (ypos < 0) ypos = 0;
657
658       Point p = G.snap(new Point ((int) (xpos+dx), (int) (ypos+dy)));
659       vertices[mv].getBounds().setLocation(p);
660      }
661
662
663
664    private void CheckPositions(JGraph G)
665      {
666       int v,u;
667       int vi,ui;
668       double rand;
669       boolean OK = false;
670
671       //while(!OK)
672 // {
673 OK = true;
674          for (v = 0; v < N; v++)
675             for (u = v; u<N; u++)
676                if ((vertices[v].getBounds().x == vertices[u].getBounds().x)
677                   && (vertices[v].getBounds().y == vertices[u].getBounds().y))
678                  {
679                   vi = v;
680                   ui = u;
681                   rand = (1.4*Math.random() - 1) * L[vi][ui];
682                   Point tmp = new Point (vertices[u].getBounds().x + (int) rand , vertices[u].getBounds().y);
683                   vertices[u].getBounds().setLocation(tmp);
684                   rand = (1.4*Math.random() - 1) * L[vi][ui];
685                   tmp = new Point (vertices[u].getBounds().x + (int) rand , vertices[u].getBounds().y);
686                   vertices[u].getBounds().setLocation(tmp);
687                   OK = false;
688                  }
689         //}
690 }
691
692
693   }//end class KK
694

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags