1 /*
2 * Copyright (c) 2003, the JUNG Project and the Regents of the University of
3 * California All rights reserved.
4 *
5 * This software is open-source under the BSD license; see either "license.txt"
6 * or http://jung.sourceforge.net/license.txt for a description.
7 */
8 package edu.uci.ics.jung.algorithms.layout3d;
9
10 import java.util.ConcurrentModificationException;
11 import java.util.HashMap;
12 import java.util.Map;
13
14 import javax.media.j3d.BoundingSphere;
15 import javax.vecmath.Point3f;
16 import javax.vecmath.Vector3f;
17
18 import org.apache.commons.collections15.Factory;
19 import org.apache.commons.collections15.map.LazyMap;
20
21 import edu.uci.ics.jung.algorithms.util.IterativeContext;
22 import edu.uci.ics.jung.graph.Graph;
23 import edu.uci.ics.jung.graph.util.Pair;
24
25 /**
26 * Implements the Fruchterman-Reingold algorithm for node layout.
27 *
28 * @author Scott White, Yan-Biao Boey, Danyel Fisher
29 */
30 public class FRLayout<V, E> extends AbstractLayout<V, E> implements IterativeContext {
31
32 private double forceConstant;
33
34 private double temperature;
35
36 private int currentIteration;
37
38 private int mMaxIterations = 700;
39
40 // private Map<V, FRVertexData> frVertexData =
41 // LazyMap.decorate(new HashMap<V,FRVertexData>(), new Factory<FRVertexData>() {
42 // public FRVertexData create() {
43 // return new FRVertexData();
44 // }});
45
46 private Map<V, Vector3f> frVertexData =
47 LazyMap.decorate(new HashMap<V, Vector3f>(), new Factory<Vector3f>() {
48 public Vector3f create() {
49 return new Vector3f();
50 }});
51
52 private double attraction_multiplier = 0.75;
53
54 private double attraction_constant;
55
56 private double repulsion_multiplier = 0.75;
57
58 private double repulsion_constant;
59
60 public FRLayout(Graph<V, E> g) {
61 super(g);
62 }
63
64 public FRLayout(Graph<V, E> g, BoundingSphere d) {
65 super(g, new RandomLocationTransformer<V>(d), d);
66 initialize();
67 }
68
69 /* (non-Javadoc)
70 * @see edu.uci.ics.jung.visualization.layout.AbstractLayout#setSize(java.awt.Dimension)
71 */
72 @Override
73 public void setSize(BoundingSphere size) {
74 setInitializer(new RandomLocationTransformer<V>(size));
75 super.setSize(size);
76 }
77
78 public void setAttractionMultiplier(double attraction) {
79 this.attraction_multiplier = attraction;
80 }
81
82 public void setRepulsionMultiplier(double repulsion) {
83 this.repulsion_multiplier = repulsion;
84 }
85
86 public void reset() {
87 doInit();
88 }
89
90 public void initialize() {
91 doInit();
92 }
93
94 private void doInit() {
95 Graph<V,E> graph = getGraph();
96 BoundingSphere d = getSize();
97 if(graph != null) {//&& d != null) {
98 currentIteration = 0;
99 temperature = d.getRadius() / 10;
100
101 forceConstant =
102 Math
103 .sqrt(d.getRadius()
104 * d.getRadius() * d.getRadius()
105 / graph.getVertexCount());
106
107 attraction_constant = attraction_multiplier * forceConstant;
108 repulsion_constant = repulsion_multiplier * forceConstant;
109 }
110 }
111
112 private double EPSILON = 0.000001D;
113
114 /**
115 * Moves the iteration forward one notch, calculation attraction and
116 * repulsion between vertices and edges and cooling the temperature.
117 */
118 public synchronized void step() {
119 currentIteration++;
120
121 /**
122 * Calculate repulsion
123 */
124 while(true) {
125
126 try {
127 for(V v1 : getGraph().getVertices()) {
128 // if (isLocked(v1)) continue;
129 calcRepulsion(v1);
130 }
131 break;
132 } catch(ConcurrentModificationException cme) {}
133 }
134
135 /**
136 * Calculate attraction
137 */
138 while(true) {
139 try {
140 for(E e : getGraph().getEdges()) {
141
142 calcAttraction(e);
143 }
144 break;
145 } catch(ConcurrentModificationException cme) {}
146 }
147
148
149 while(true) {
150 try {
151 for(V v : getGraph().getVertices()) {
152 if (isLocked(v)) continue;
153 calcPositions(v);
154 }
155 break;
156 } catch(ConcurrentModificationException cme) {}
157 }
158 cool();
159 }
160
161 public synchronized void calcPositions(V v) {
162 // FRVertexData fvd = getFRData(v);
163 Vector3f fvd = frVertexData.get(v);
164 if(fvd == null) return;
165 Point3f xyd = transform(v);
166
167 double deltaLength = Math.max(EPSILON, fvd.length());
168 // double deltaLength = Math.max(EPSILON, Math.sqrt(fvd.disp
169 // .dot(fvd.disp)));
170
171 Vector3f newDisp = new Vector3f(fvd);
172 newDisp.scale((float)(Math.min(deltaLength, temperature)/deltaLength), fvd);
173 // double newXDisp = fvd.getXDisp() / deltaLength
174 // * Math.min(deltaLength, temperature);
175
176 // if (Double.isNaN(newXDisp)) {
177 // throw new IllegalArgumentException(
178 // "Unexpected mathematical result in FRLayout:calcPositions [xdisp]"); }
179 //
180 // double newYDisp = fvd.getYDisp() / deltaLength
181 // * Math.min(deltaLength, temperature);
182 //
183 //
184 // double newZDisp = fvd.getZDisp() / deltaLength
185 // * Math.min(deltaLength, temperature);
186 // System.err.println("deltaLength = "+deltaLength);
187 // System.err.println(v+" was set to "+xyd);
188
189 xyd.add(newDisp);
190
191 // xyd.set((float)(xyd.getX()+newXDisp),
192 // (float)(xyd.getY()+newYDisp),
193 // (float)(xyd.getZ()+newZDisp));
194 // System.err.println("newXDisp="+newXDisp+",newYDisp="+newYDisp+",newZDisp="+newZDisp);
195 // System.err.println(v+" set to "+xyd);
196
197 double borderWidth = getSize().getRadius() / 50.0;
198 double min = -getSize().getRadius() + borderWidth;
199 double max = -min;
200
201 double[] min_pos = new double[3];
202 double[] max_pos = new double[3];
203 for (int i = 0; i < 3; i++)
204 {
205 min_pos[i] = min + Math.random() * borderWidth * 2;
206 max_pos[i] = max - Math.random() * borderWidth * 2;
207 }
208
209
210 xyd.set((float)Math.min(Math.max(xyd.getX(), min_pos[0]), max_pos[0]),
211 (float)Math.min(Math.max(xyd.getY(), min_pos[1]), max_pos[1]),
212 (float)Math.min(Math.max(xyd.getZ(), min_pos[2]), max_pos[2]));
213
214 // double newXPos = xyd.getX();
215 // if (newXPos < min) {
216 // newXPos = min + Math.random() * borderWidth * 2.0;
217 // } else if (newXPos > max) {
218 // newXPos = max - Math.random()
219 // * borderWidth * 2.0;
220 // }
221 //
222 // double newYPos = xyd.getY();
223 // if (newYPos < min) {
224 // newYPos = min + Math.random() * borderWidth * 2.0;
225 // } else if (newYPos > max) {
226 // newYPos = max
227 // - Math.random() * borderWidth * 2.0;
228 // }
229 //
230 // double newZPos = xyd.getZ();
231 // if (newZPos < min) {
232 // newZPos = min + Math.random() * borderWidth * 2.0;
233 // } else if (newZPos > max) {
234 // newZPos = max
235 // - Math.random() * borderWidth * 2.0;
236 // }
237 //
238 // xyd.set((float)newXPos, (float)newYPos, (float)newZPos);
239 }
240
241 public void calcAttraction(E e) {
242 Pair<V> p = getGraph().getEndpoints(e);
243 V v1 = p.getFirst();
244 V v2 = p.getSecond();
245 // V v1 = getGraph().getIncidentVertices(e).iterator().next();
246 // V v2 = getGraph().getOpposite(v1, e);
247 Point3f p1 = transform(v1);
248 Point3f p2 = transform(v2);
249 if(p1 == null || p2 == null) return;
250 // double xDelta = p1.getX() - p2.getX();
251 // double yDelta = p1.getY() - p2.getY();
252 // double zDelta = p1.getZ() - p2.getZ();
253
254 Vector3f delta = new Vector3f();
255 delta.negate(p2);
256 delta.add(p1);
257
258 double deltaLength = Math.max(EPSILON, delta.length());
259
260 // double deltaLength = Math.max(EPSILON, Math.sqrt((xDelta * xDelta)
261 // + (yDelta * yDelta)));
262
263 double force = (deltaLength * deltaLength) / attraction_constant;
264
265 if (Double.isNaN(force)) { throw new IllegalArgumentException(
266 "Unexpected mathematical result in FRLayout:calcPositions [force]"); }
267
268 delta.scale((float)(force / deltaLength));
269
270 frVertexData.get(v2).add(delta);
271 delta.negate();
272 frVertexData.get(v1).add(delta);
273
274 // FRVertexData fvd1 = getFRData(v1);
275 // FRVertexData fvd2 = getFRData(v2);
276 //
277 // fvd1.decrementDisp(
278 // (float)((xDelta / deltaLength) * force),
279 // (float)((yDelta / deltaLength) * force),
280 // (float)((zDelta / deltaLength) * force));
281 // fvd2.incrementDisp(
282 // (float)((xDelta / deltaLength) * force),
283 // (float)((yDelta / deltaLength) * force),
284 // (float)((zDelta / deltaLength) * force));
285 }
286
287 public void calcRepulsion(V v1) {
288 Vector3f fvd1 = frVertexData.get(v1);
289 // FRVertexData fvd1 = getFRData(v1);
290 if(fvd1 == null) return;
291 fvd1.set(0, 0, 0);
292 // fvd1.setDisp(0, 0, 0);
293
294 try {
295 for(V v2 : getGraph().getVertices()) {
296
297 // if (isLocked(v2)) continue;
298 if (v1 != v2) {
299 Point3f p1 = transform(v1);
300 Point3f p2 = transform(v2);
301 if(p1 == null || p2 == null) continue;
302
303 // double xDelta = p1.getX() - p2.getX();
304 // double yDelta = p1.getY() - p2.getY();
305 // double zDelta = p1.getZ() - p2.getZ();
306
307 Vector3f delta = new Vector3f();
308 delta.negate(p2);
309 delta.add(p1);
310
311 double deltaLength = Math.max(EPSILON, delta.length());
312
313 // double deltaLength = Math.max(EPSILON, Math
314 // .sqrt((xDelta * xDelta) + (yDelta * yDelta) + (zDelta * zDelta)));
315
316 double force = (repulsion_constant * repulsion_constant) / deltaLength;
317
318 if (Double.isNaN(force)) { throw new RuntimeException(
319 "Unexpected mathematical result in FRLayout:calcPositions [repulsion]"); }
320
321 delta.scale((float)(force / deltaLength));
322 fvd1.add(delta);
323
324 // fvd1.incrementDisp(
325 // (float)((xDelta / deltaLength) * force),
326 // (float)((yDelta / deltaLength) * force),
327 // (float)((zDelta / deltaLength) * force));
328 }
329 }
330 } catch(ConcurrentModificationException cme) {
331 calcRepulsion(v1);
332 }
333 }
334
335 private void cool() {
336 temperature *= (1.0 - currentIteration / (double) mMaxIterations);
337 }
338
339 public void setMaxIterations(int maxIterations) {
340 mMaxIterations = maxIterations;
341 }
342
343 // public FRVertexData getFRData(V v) {
344 // return frVertexData.get(v);
345 // }
346
347 /**
348 * This one is an incremental visualization.
349 */
350 public boolean isIncremental() {
351 return true;
352 }
353
354 /**
355 * Returns true once the current iteration has passed the maximum count,
356 * <tt>MAX_ITERATIONS</tt>.
357 */
358 public boolean done() {
359 if (currentIteration > mMaxIterations) {
360 return true;
361 }
362 return false;
363 }
364
365 // public static class FRVertexData {
366 //
367 // private Vector3f disp;
368 //
369 // public FRVertexData() {
370 // initialize();
371 // }
372 //
373 // public void initialize() {
374 // disp = new Vector3f();
375 // }
376 //
377 // public double getXDisp() {
378 // return disp.getX();
379 // }
380 //
381 // public double getYDisp() {
382 // return disp.getY();
383 // }
384 //
385 // public double getZDisp() {
386 // return disp.getZ();
387 // }
388 //
389 // public void setDisp(float x, float y, float z) {
390 // disp.set(x,y,z);
391 // }
392 //
393 // public void incrementDisp(float x, float y, float z) {
394 // disp.add(new Vector3f(x,y,z));
395 // }
396 //
397 // public void decrementDisp(float x, float y, float z) {
398 // disp.sub(new Vector3f(x,y,x));
399 // }
400 // }
401 }