1 /*
2 * TouchGraph LLC. Apache-Style Software License
3 *
4 *
5 * Copyright (c) 2001-2002 Alexander Shapiro. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 *
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
17 * distribution.
18 *
19 * 3. The end-user documentation included with the redistribution,
20 * if any, must include the following acknowledgment:
21 * "This product includes software developed by
22 * TouchGraph LLC (http://www.touchgraph.com/)."
23 * Alternately, this acknowledgment may appear in the software itself,
24 * if and wherever such third-party acknowledgments normally appear.
25 *
26 * 4. The names "TouchGraph" or "TouchGraph LLC" must not be used to endorse
27 * or promote products derived from this software without prior written
28 * permission. For written permission, please contact
29 * alex@touchgraph.com
30 *
31 * 5. Products derived from this software may not be called "TouchGraph",
32 * nor may "TouchGraph" appear in their name, without prior written
33 * permission of alex@touchgraph.com.
34 *
35 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
36 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
37 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
38 * DISCLAIMED. IN NO EVENT SHALL TOUCHGRAPH OR ITS CONTRIBUTORS BE
39 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
40 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
41 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
42 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
43 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
44 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
45 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
46 * ====================================================================
47 *
48 */
49
50 package com.touchgraph.graphlayout;
51
52 import com.touchgraph.graphlayout.graphelements.*;
53
54 /*** TGLayout is the thread responsible for graph layout. It updates
55 * the real coordinates of the nodes in the graphEltSet object.
56 * TGPanel sends it resetDamper commands whenever the layout needs
57 * to be adjusted. After every adjustment cycle, TGLayout triggers
58 * a repaint of the TGPanel.
59 *
60 * ********************************************************************
61 * This is the heart of the TouchGraph application. Please provide a
62 * Reference to TouchGraph.com if you are influenced by what you see
63 * below. Your cooperation will insure that this code remains
64 * opensource
65 * ********************************************************************
66 *
67 * <p><b>
68 * Parts of this code build upon Sun's Graph Layout example.
69 * http://java.sun.com/applets/jdk/1.1/demo/GraphLayout/Graph.java
70 * </b></p>
71 *
72 * @author Alexander Shapiro
73 * @version 1.21 $Id: TGLayout.java,v 1.1.1.1 2004/02/06 08:44:05 keesj Exp $
74 */
75 public class TGLayout implements Runnable {
76
77 //private ImmutableGraphEltSet graphEltSet;
78 private TGPanel tgPanel;
79 private Thread relaxer;
80 private double damper=0.0; // A low damper value causes the graph to move slowly
81 private double maxMotion=0; // Keep an eye on the fastest moving node to see if the graph is stabilizing
82 private double lastMaxMotion=0;
83 private double motionRatio = 0; // It's sort of a ratio, equal to lastMaxMotion/maxMotion-1
84 private boolean damping = true; // When damping is true, the damper value decreases
85
86 private double rigidity = 1; // Rigidity has the same effect as the damper, except that it's a constant
87 // a low rigidity value causes things to go slowly.
88 // a value that's too high will cause oscillation
89 private double newRigidity = 1;
90
91 Node dragNode=null;
92
93 // ............
94
95 /*** Constructor with a supplied TGPanel <tt>tgp</tt>.
96 */
97 public TGLayout( TGPanel tgp ) {
98 tgPanel = tgp;
99 //graphEltSet = tgPanel.getGES();
100 relaxer = null;
101 }
102
103 void setRigidity(double r) {
104 newRigidity = r; //update rigidity at the end of the relax() thread
105 }
106
107 void setDragNode(Node n) {
108 dragNode = n;
109 }
110
111
112 //relaxEdges is more like tense edges up. All edges pull nodes closes together;
113 private synchronized void relaxEdges() {
114 TGForEachEdge fee = new TGForEachEdge() {
115 public void forEachEdge(Edge e) {
116
117 double vx = e.to.x - e.from.x;
118 double vy = e.to.y - e.from.y;
119 double len = Math.sqrt(vx * vx + vy * vy);
120
121 double dx=vx*rigidity; //rigidity makes edges tighter
122 double dy=vy*rigidity;
123
124 dx /=(e.getLength()*100);
125 dy /=(e.getLength()*100);
126
127 // Edges pull directly in proportion to the distance between the nodes. This is good,
128 // because we want the edges to be stretchy. The edges are ideal rubberbands. They
129 // They don't become springs when they are too short. That only causes the graph to
130 // oscillate.
131
132 if (e.to.justMadeLocal || !e.from.justMadeLocal) {
133 e.to.dx -= dx*len;
134 e.to.dy -= dy*len;
135 } else {
136 e.to.dx -= dx*len/10;
137 e.to.dy -= dy*len/10;
138 }
139 if (e.from.justMadeLocal || !e.to.justMadeLocal) {
140 e.from.dx += dx*len;
141 e.from.dy += dy*len;
142 } else {
143 e.from.dx += dx*len/10;
144 e.from.dy += dy*len/10;
145 }
146 }
147 };
148
149 tgPanel.getGES().forAllEdges(fee);
150 }
151
152 /*
153 private synchronized void avoidLabels() {
154 for (int i = 0 ; i < graphEltSet.nodeNum() ; i++) {
155 Node n1 = graphEltSet.nodeAt(i);
156 double dx = 0;
157 double dy = 0;
158
159 for (int j = 0 ; j < graphEltSet.nodeNum() ; j++) {
160 if (i == j) {
161 continue; // It's kind of dumb to do things this way. j should go from i+1 to nodeNum.
162 }
163 Node n2 = graphEltSet.nodeAt(j);
164 double vx = n1.x - n2.x;
165 double vy = n1.y - n2.y;
166 double len = vx * vx + vy * vy; // so it's length squared
167 if (len == 0) {
168 dx += Math.random(); // If two nodes are right on top of each other, randomly separate
169 dy += Math.random();
170 } else if (len <600*600) { //600, because we don't want deleted nodes to fly too far away
171 dx += vx / len; // If it was sqrt(len) then a single node surrounded by many others will
172 dy += vy / len; // always look like a circle. This might look good at first, but I think
173 // it makes large graphs look ugly + it contributes to oscillation. A
174 // linear function does not fall off fast enough, so you get rough edges
175 // in the 'force field'
176
177 }
178 }
179 n1.dx += dx*100*rigidity; // rigidity makes nodes avoid each other more.
180 n1.dy += dy*100*rigidity; // I was surprised to see that this exactly balances multiplying edge tensions
181 // by the rigidity, and thus has the effect of slowing the graph down, while
182 // keeping it looking identical.
183
184 }
185 }
186 */
187
188 private synchronized void avoidLabels() {
189 TGForEachNodePair fenp = new TGForEachNodePair() {
190 public void forEachNodePair(Node n1, Node n2) {
191 double dx=0;
192 double dy=0;
193 double vx = n1.x - n2.x;
194 double vy = n1.y - n2.y;
195 double len = vx * vx + vy * vy; //so it's length squared
196 if (len == 0) {
197 dx = Math.random(); //If two nodes are right on top of each other, randomly separate
198 dy = Math.random();
199 } else if (len <600*600) { //600, because we don't want deleted nodes to fly too far away
200 dx = vx / len; // If it was sqrt(len) then a single node surrounded by many others will
201 dy = vy / len; // always look like a circle. This might look good at first, but I think
202 // it makes large graphs look ugly + it contributes to oscillation. A
203 // linear function does not fall off fast enough, so you get rough edges
204 // in the 'force field'
205 }
206
207 int repSum = n1.repulsion * n2.repulsion/100;
208
209 if(n1.justMadeLocal || !n2.justMadeLocal) {
210 n1.dx += dx*repSum*rigidity;
211 n1.dy += dy*repSum*rigidity;
212 }
213 else {
214 n1.dx += dx*repSum*rigidity/10;
215 n1.dy += dy*repSum*rigidity/10;
216 }
217 if (n2.justMadeLocal || !n1.justMadeLocal) {
218 n2.dx -= dx*repSum*rigidity;
219 n2.dy -= dy*repSum*rigidity;
220 }
221 else {
222 n2.dx -= dx*repSum*rigidity/10;
223 n2.dy -= dy*repSum*rigidity/10;
224 }
225 }
226 };
227
228 tgPanel.getGES().forAllNodePairs(fenp);
229 }
230
231 public void startDamper() {
232 damping = true;
233 }
234
235 public void stopDamper() {
236 damping = false;
237 damper = 1.0; //A value of 1.0 means no damping
238 }
239
240 public void resetDamper() { //reset the damper, but don't keep damping.
241 damping = true;
242 damper = 1.0;
243 }
244
245 public void stopMotion() { // stabilize the graph, but do so gently by setting the damper to a low value
246 damping = true;
247 if (damper>0.3)
248 damper = 0.3;
249 else
250 damper = 0;
251 }
252
253 public void damp() {
254 if (damping) {
255 if(motionRatio<=0.001) { //This is important. Only damp when the graph starts to move faster
256 //When there is noise, you damp roughly half the time. (Which is a lot)
257 //
258 //If things are slowing down, then you can let them do so on their own,
259 //without damping.
260
261 //If max motion<0.2, damp away
262 //If by the time the damper has ticked down to 0.9, maxMotion is still>1, damp away
263 //We never want the damper to be negative though
264 if ((maxMotion<0.2 || (maxMotion>1 && damper<0.9)) && damper > 0.01) damper -= 0.01;
265 //If we've slowed down significanly, damp more aggresively (then the line two below)
266 else if (maxMotion<0.4 && damper > 0.003) damper -= 0.003;
267 //If max motion is pretty high, and we just started damping, then only damp slightly
268 else if(damper>0.0001) damper -=0.0001;
269 }
270 }
271 if(maxMotion<0.001 && damping) {
272 damper=0;
273 }
274 }
275
276
277 private synchronized void moveNodes() {
278 lastMaxMotion = maxMotion;
279 final double[] maxMotionA = new double[1];
280 maxMotionA[0]=0;
281
282 TGForEachNode fen = new TGForEachNode() {
283 public void forEachNode(Node n) {
284 double dx = n.dx;
285 double dy = n.dy;
286 dx*=damper; //The damper slows things down. It cuts down jiggling at the last moment, and optimizes
287 dy*=damper; //layout. As an experiment, get rid of the damper in these lines, and make a
288 //long straight line of nodes. It wiggles too much and doesn't straighten out.
289
290 n.dx=dx/2; //Slow down, but don't stop. Nodes in motion store momentum. This helps when the force
291 n.dy=dy/2; //on a node is very low, but you still want to get optimal layout.
292
293 double distMoved = Math.sqrt(dx*dx+dy*dy); //how far did the node actually move?
294
295 if (!n.fixed && !(n==dragNode) ) {
296 n.x += Math.max(-30, Math.min(30, dx)); //don't move faster then 30 units at a time.
297 n.y += Math.max(-30, Math.min(30, dy)); //I forget when this is important. Stopping severed nodes from
298 //flying away?
299 }
300 maxMotionA[0]=Math.max(distMoved,maxMotionA[0]);
301 }
302 };
303
304 tgPanel.getGES().forAllNodes(fen);
305
306 maxMotion=maxMotionA[0];
307 if (maxMotion>0) motionRatio = lastMaxMotion/maxMotion-1; //subtract 1 to make a positive value mean that
308 else motionRatio = 0; //things are moving faster
309
310 damp();
311
312 }
313
314 private synchronized void relax() {
315 for (int i=0;i<10;i++) {
316 relaxEdges();
317 avoidLabels();
318 moveNodes();
319 }
320 if(rigidity!=newRigidity) rigidity= newRigidity; //update rigidity
321 tgPanel.repaintAfterMove();
322 }
323
324 private void myWait() { //I think it was Netscape that caused me not to use Wait, or was it java 1.1?
325 try {
326 Thread.sleep(100);
327 } catch (InterruptedException e) {
328 //break;
329 }
330 }
331
332 public void run() {
333 Thread me = Thread.currentThread();
334 // me.setPriority(1); //Makes standard executable look better, but the applet look worse.
335 while (relaxer == me) {
336 relax();
337 try {
338 Thread.sleep(20); //Delay to wait for the prior repaint command to finish.
339 while(damper<0.1 && damping && maxMotion<0.001) myWait();
340 //System.out.println("damping " + damping + " damp " + damper + " maxM " + maxMotion + " motR " + motionRatio );
341 } catch (InterruptedException e) {
342 break;
343 }
344 }
345 }
346
347 public void start() {
348 relaxer = new Thread(this);
349 relaxer.start();
350 }
351
352 public void stop() {
353 relaxer = null;
354 }
355
356 } // end com.touchgraph.graphlayout.TGLayout