Line | Hits | Source |
---|---|---|
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.visualization; | |
9 | ||
10 | import java.awt.event.ComponentAdapter; | |
11 | import java.awt.event.ComponentEvent; | |
12 | import java.awt.geom.Point2D; | |
13 | import java.util.ConcurrentModificationException; | |
14 | import java.util.Iterator; | |
15 | ||
16 | import edu.uci.ics.jung.graph.Edge; | |
17 | import edu.uci.ics.jung.graph.Graph; | |
18 | import edu.uci.ics.jung.graph.Vertex; | |
19 | import edu.uci.ics.jung.utils.Pair; | |
20 | import edu.uci.ics.jung.utils.UserData; | |
21 | ||
22 | /** | |
23 | * The SpringLayout package represents a visualization of a set of nodes. The | |
24 | * SpringLayout, which is initialized with a Graph, assigns X/Y locations to | |
25 | * each node. When called <code>relax()</code>, the SpringLayout moves the | |
26 | * visualization forward one step. | |
27 | * | |
28 | * @author Danyel Fisher | |
29 | * @author Joshua O'Madadhain | |
30 | */ | |
31 | public class SpringLayout extends AbstractLayout implements LayoutMutable { | |
32 | ||
33 | 1 | private static final Object SPRING_KEY = "temp_edu.uci.ics.jung.Spring_Visualization_Key"; |
34 | 9 | protected double stretch = 0.70; |
35 | protected LengthFunction lengthFunction; | |
36 | 9 | protected int repulsion_range = 100; |
37 | 9 | protected double force_multiplier = 1.0 / 3.0; |
38 | ||
39 | /** | |
40 | * Returns the status. | |
41 | */ | |
42 | public String getStatus() { | |
43 | 2 | return null; |
44 | } | |
45 | ||
46 | /** | |
47 | * Constructor for a SpringLayout for a raw graph with associated | |
48 | * dimension--the input knows how big the graph is. Defaults to the unit | |
49 | * length function. | |
50 | */ | |
51 | public SpringLayout(Graph g) { | |
52 | 9 | this(g, UNITLENGTHFUNCTION); |
53 | 9 | } |
54 | ||
55 | /** | |
56 | * Constructor for a SpringLayout for a raw graph with associated component. | |
57 | * | |
58 | * @param g | |
59 | * the input Graph | |
60 | * @param f | |
61 | * the length function | |
62 | */ | |
63 | public SpringLayout(Graph g, LengthFunction f) { | |
64 | 9 | super(g); |
65 | 9 | this.lengthFunction = f; |
66 | 9 | } |
67 | ||
68 | /** | |
69 | * @return the current value for the stretch parameter | |
70 | * @see #setStretch(double) | |
71 | */ | |
72 | public double getStretch() | |
73 | { | |
74 | 0 | return stretch; |
75 | } | |
76 | ||
77 | /** | |
78 | * <p>Sets the stretch parameter for this instance. This value | |
79 | * specifies how much the degrees of an edge's incident vertices | |
80 | * should influence how easily the endpoints of that edge | |
81 | * can move (that is, that edge's tendency to change its length).</p> | |
82 | * | |
83 | * <p>The default value is 0.70. Positive values less than 1 cause | |
84 | * high-degree vertices to move less than low-degree vertices, and | |
85 | * values > 1 cause high-degree vertices to move more than | |
86 | * low-degree vertices. Negative values will have unpredictable | |
87 | * and inconsistent results.</p> | |
88 | * @param stretch | |
89 | */ | |
90 | public void setStretch(double stretch) | |
91 | { | |
92 | 0 | this.stretch = stretch; |
93 | 0 | } |
94 | ||
95 | /** | |
96 | * @return the current value for the node repulsion range | |
97 | * @see #setRepulsionRange(int) | |
98 | */ | |
99 | public int getRepulsionRange() | |
100 | { | |
101 | 0 | return repulsion_range; |
102 | } | |
103 | ||
104 | /** | |
105 | * Sets the node repulsion range (in drawing area units) for this instance. | |
106 | * Outside this range, nodes do not repel each other. The default value | |
107 | * is 100. Negative values are treated as their positive equivalents. | |
108 | * @param range | |
109 | */ | |
110 | public void setRepulsionRange(int range) | |
111 | { | |
112 | 0 | this.repulsion_range = range; |
113 | 0 | } |
114 | ||
115 | /** | |
116 | * @return the current value for the edge length force multiplier | |
117 | * @see #setForceMultiplier(double) | |
118 | */ | |
119 | public double getForceMultiplier() | |
120 | { | |
121 | 0 | return force_multiplier; |
122 | } | |
123 | ||
124 | /** | |
125 | * Sets the force multiplier for this instance. This value is used to | |
126 | * specify how strongly an edge "wants" to be its default length | |
127 | * (higher values indicate a greater attraction for the default length), | |
128 | * which affects how much its endpoints move at each timestep. | |
129 | * The default value is 1/3. A value of 0 turns off any attempt by the | |
130 | * layout to cause edges to conform to the default length. Negative | |
131 | * values cause long edges to get longer and short edges to get shorter; use | |
132 | * at your own risk. | |
133 | */ | |
134 | public void setForceMultiplier(double force) | |
135 | { | |
136 | 0 | this.force_multiplier = force; |
137 | 0 | } |
138 | ||
139 | protected void initialize_local() { | |
140 | try { | |
141 | 10 | for (Iterator iter = getGraph().getEdges().iterator(); iter.hasNext();) { |
142 | 5000 | Edge e = (Edge) iter.next(); |
143 | 5000 | SpringEdgeData sed = getSpringData(e); |
144 | 5000 | if (sed == null) { |
145 | 4500 | sed = new SpringEdgeData(e); |
146 | 4500 | e.addUserDatum(getSpringKey(), sed, UserData.REMOVE); |
147 | } | |
148 | 5000 | calcEdgeLength(sed, lengthFunction); |
149 | } | |
150 | 0 | } catch(ConcurrentModificationException cme) { |
151 | 0 | initialize_local(); |
152 | 10 | } |
153 | 10 | } |
154 | ||
155 | 9 | Object key = null; |
156 | ||
157 | public Object getSpringKey() { | |
158 | 80068 | if (key == null) key = new Pair(this, SPRING_KEY); |
159 | 80068 | return key; |
160 | } | |
161 | ||
162 | /** | |
163 | * (non-Javadoc) | |
164 | * | |
165 | * @see edu.uci.ics.jung.visualization.AbstractLayout#initialize_local_vertex(edu.uci.ics.jung.graph.Vertex) | |
166 | */ | |
167 | protected void initialize_local_vertex(Vertex v) { | |
168 | 500 | SpringVertexData vud = getSpringData(v); |
169 | 500 | if (vud == null) { |
170 | 450 | vud = new SpringVertexData(); |
171 | 450 | v.addUserDatum(getSpringKey(), vud, UserData.REMOVE); |
172 | } | |
173 | 500 | } |
174 | ||
175 | /* ------------------------- */ | |
176 | ||
177 | protected void calcEdgeLength(SpringEdgeData sed, LengthFunction f) { | |
178 | 5000 | sed.length = f.getLength(sed.e); |
179 | 5000 | } |
180 | ||
181 | /* ------------------------- */ | |
182 | ||
183 | ||
184 | /** | |
185 | * Relaxation step. Moves all nodes a smidge. | |
186 | */ | |
187 | public void advancePositions() { | |
188 | try { | |
189 | 45 | for (Iterator iter = getVisibleVertices().iterator(); iter.hasNext();) { |
190 | 2154 | Vertex v = (Vertex) iter.next(); |
191 | 2154 | SpringVertexData svd = getSpringData(v); |
192 | 2154 | if (svd == null) { |
193 | 0 | continue; |
194 | } | |
195 | 2154 | svd.dx /= 4; |
196 | 2154 | svd.dy /= 4; |
197 | 2154 | svd.edgedx = svd.edgedy = 0; |
198 | 2154 | svd.repulsiondx = svd.repulsiondy = 0; |
199 | } | |
200 | 0 | } catch(ConcurrentModificationException cme) { |
201 | 0 | advancePositions(); |
202 | 45 | } |
203 | ||
204 | 45 | relaxEdges(); |
205 | 45 | calculateRepulsion(); |
206 | 45 | moveNodes(); |
207 | 45 | } |
208 | ||
209 | protected Vertex getAVertex(Edge e) { | |
210 | 21020 | Vertex v = (Vertex) e.getIncidentVertices().iterator().next(); |
211 | 21020 | return v; |
212 | } | |
213 | ||
214 | protected void relaxEdges() { | |
215 | try { | |
216 | 45 | for (Iterator i = getVisibleEdges().iterator(); i.hasNext();) { |
217 | 21020 | Edge e = (Edge) i.next(); |
218 | ||
219 | 21020 | Vertex v1 = getAVertex(e); |
220 | 21020 | Vertex v2 = e.getOpposite(v1); |
221 | ||
222 | 21020 | Point2D p1 = getLocation(v1); |
223 | 21020 | Point2D p2 = getLocation(v2); |
224 | 21020 | if(p1 == null || p2 == null) continue; |
225 | 21020 | double vx = p1.getX() - p2.getX(); |
226 | 21020 | double vy = p1.getY() - p2.getY(); |
227 | 21020 | double len = Math.sqrt(vx * vx + vy * vy); |
228 | ||
229 | 21020 | SpringEdgeData sed = getSpringData(e); |
230 | 21020 | if (sed == null) { |
231 | 0 | continue; |
232 | } | |
233 | 21020 | double desiredLen = sed.length; |
234 | ||
235 | // round from zero, if needed [zero would be Bad.]. | |
236 | 21020 | len = (len == 0) ? .0001 : len; |
237 | ||
238 | 21020 | double f = force_multiplier * (desiredLen - len) / len; |
239 | ||
240 | 21020 | f = f * Math.pow(stretch, (v1.degree() + v2.degree() - 2)); |
241 | ||
242 | // the actual movement distance 'dx' is the force multiplied by the | |
243 | // distance to go. | |
244 | 21020 | double dx = f * vx; |
245 | 21020 | double dy = f * vy; |
246 | SpringVertexData v1D, v2D; | |
247 | 21020 | v1D = getSpringData(v1); |
248 | 21020 | v2D = getSpringData(v2); |
249 | ||
250 | 21020 | sed.f = f; |
251 | ||
252 | 21020 | v1D.edgedx += dx; |
253 | 21020 | v1D.edgedy += dy; |
254 | 21020 | v2D.edgedx += -dx; |
255 | 21020 | v2D.edgedy += -dy; |
256 | } | |
257 | 0 | } catch(ConcurrentModificationException cme) { |
258 | 0 | relaxEdges(); |
259 | 45 | } |
260 | 45 | } |
261 | ||
262 | protected void calculateRepulsion() { | |
263 | try { | |
264 | 45 | for (Iterator iter = getGraph().getVertices().iterator(); iter |
265 | 2295 | .hasNext();) { |
266 | 2250 | Vertex v = (Vertex) iter.next(); |
267 | 2250 | if (isLocked(v)) continue; |
268 | ||
269 | 2250 | SpringVertexData svd = getSpringData(v); |
270 | 2250 | if(svd == null) continue; |
271 | 2250 | double dx = 0, dy = 0; |
272 | ||
273 | 2250 | for (Iterator iter2 = getGraph().getVertices().iterator(); iter2 |
274 | 114750 | .hasNext();) { |
275 | 112500 | Vertex v2 = (Vertex) iter2.next(); |
276 | 112500 | if (v == v2) continue; |
277 | 110250 | Point2D p = getLocation(v); |
278 | 110250 | Point2D p2 = getLocation(v2); |
279 | 110250 | if(p == null || p2 == null) continue; |
280 | 110250 | double vx = p.getX() - p2.getX(); |
281 | 110250 | double vy = p.getY() - p2.getY(); |
282 | 110250 | double distance = vx * vx + vy * vy; |
283 | 110250 | if (distance == 0) { |
284 | 0 | dx += Math.random(); |
285 | 0 | dy += Math.random(); |
286 | 110250 | } else if (distance < repulsion_range * repulsion_range) { |
287 | 85358 | double factor = 1; |
288 | 85358 | dx += factor * vx / Math.pow(distance, 2); |
289 | 85358 | dy += factor * vy / Math.pow(distance, 2); |
290 | } | |
291 | } | |
292 | 2250 | double dlen = dx * dx + dy * dy; |
293 | 2250 | if (dlen > 0) { |
294 | 2250 | dlen = Math.sqrt(dlen) / 2; |
295 | 2250 | svd.repulsiondx += dx / dlen; |
296 | 2250 | svd.repulsiondy += dy / dlen; |
297 | } | |
298 | } | |
299 | 0 | } catch(ConcurrentModificationException cme) { |
300 | 0 | calculateRepulsion(); |
301 | 45 | } |
302 | 45 | } |
303 | ||
304 | protected void moveNodes() { | |
305 | ||
306 | 45 | synchronized (getCurrentSize()) { |
307 | try { | |
308 | 45 | for (Iterator i = getVisibleVertices().iterator(); i.hasNext();) { |
309 | 2154 | Vertex v = (Vertex) i.next(); |
310 | 2154 | if (isLocked(v)) continue; |
311 | 2154 | SpringVertexData vd = getSpringData(v); |
312 | 2154 | if(vd == null) continue; |
313 | 2154 | Coordinates xyd = getCoordinates(v); |
314 | ||
315 | 2154 | vd.dx += vd.repulsiondx + vd.edgedx; |
316 | 2154 | vd.dy += vd.repulsiondy + vd.edgedy; |
317 | ||
318 | // keeps nodes from moving any faster than 5 per time unit | |
319 | 2154 | xyd.addX(Math.max(-5, Math.min(5, vd.dx))); |
320 | 2154 | xyd.addY(Math.max(-5, Math.min(5, vd.dy))); |
321 | ||
322 | 2154 | int width = getCurrentSize().width; |
323 | 2154 | int height = getCurrentSize().height; |
324 | ||
325 | 2154 | if (xyd.getX() < 0) { |
326 | 114 | xyd.setX(0); |
327 | 2040 | } else if (xyd.getX() > width) { |
328 | 107 | xyd.setX(width); |
329 | } | |
330 | 2154 | if (xyd.getY() < 0) { |
331 | 139 | xyd.setY(0); |
332 | 2015 | } else if (xyd.getY() > height) { |
333 | 99 | xyd.setY(height); |
334 | } | |
335 | ||
336 | } | |
337 | 0 | } catch(ConcurrentModificationException cme) { |
338 | 0 | moveNodes(); |
339 | 45 | } |
340 | 45 | } |
341 | 45 | } |
342 | ||
343 | public SpringVertexData getSpringData(Vertex v) { | |
344 | 49098 | return (SpringVertexData) (v.getUserDatum(getSpringKey())); |
345 | } | |
346 | ||
347 | public SpringEdgeData getSpringData(Edge e) { | |
348 | try { | |
349 | 26020 | return (SpringEdgeData) (e.getUserDatum(getSpringKey())); |
350 | 0 | } catch (ClassCastException cce) { |
351 | 0 | System.out.println(e.getUserDatum(getSpringKey()).getClass()); |
352 | 0 | throw cce; |
353 | } | |
354 | } | |
355 | ||
356 | public double getLength(Edge e) { | |
357 | 0 | return ((SpringEdgeData) e.getUserDatum(getSpringKey())).length; |
358 | } | |
359 | ||
360 | /* ---------------Length Function------------------ */ | |
361 | ||
362 | /** | |
363 | * If the edge is weighted, then override this method to show what the | |
364 | * visualized length is. | |
365 | * | |
366 | * @author Danyel Fisher | |
367 | */ | |
368 | public static interface LengthFunction { | |
369 | ||
370 | public double getLength(Edge e); | |
371 | } | |
372 | ||
373 | /** | |
374 | * Returns all edges as the same length: the input value | |
375 | * @author danyelf | |
376 | */ | |
377 | public static final class UnitLengthFunction implements LengthFunction { | |
378 | ||
379 | int length; | |
380 | ||
381 | public UnitLengthFunction(int length) { | |
382 | this.length = length; | |
383 | } | |
384 | ||
385 | public double getLength(Edge e) { | |
386 | return length; | |
387 | } | |
388 | } | |
389 | ||
390 | 1 | public static final LengthFunction UNITLENGTHFUNCTION = new UnitLengthFunction( |
391 | 30); | |
392 | ||
393 | /* ---------------User Data------------------ */ | |
394 | ||
395 | protected static class SpringVertexData { | |
396 | ||
397 | public double edgedx; | |
398 | ||
399 | public double edgedy; | |
400 | ||
401 | public double repulsiondx; | |
402 | ||
403 | public double repulsiondy; | |
404 | ||
405 | public SpringVertexData() { | |
406 | } | |
407 | ||
408 | /** movement speed, x */ | |
409 | public double dx; | |
410 | ||
411 | /** movement speed, y */ | |
412 | public double dy; | |
413 | } | |
414 | ||
415 | protected static class SpringEdgeData { | |
416 | ||
417 | public double f; | |
418 | ||
419 | public SpringEdgeData(Edge e) { | |
420 | this.e = e; | |
421 | } | |
422 | ||
423 | Edge e; | |
424 | ||
425 | double length; | |
426 | } | |
427 | ||
428 | /* ---------------Resize handler------------------ */ | |
429 | ||
430 | public class SpringDimensionChecker extends ComponentAdapter { | |
431 | ||
432 | public void componentResized(ComponentEvent e) { | |
433 | resize(e.getComponent().getSize()); | |
434 | } | |
435 | } | |
436 | ||
437 | /** | |
438 | * This one is an incremental visualization | |
439 | */ | |
440 | public boolean isIncremental() { | |
441 | 2 | return true; |
442 | } | |
443 | ||
444 | /** | |
445 | * For now, we pretend it never finishes. | |
446 | */ | |
447 | public boolean incrementsAreDone() { | |
448 | 52 | return false; |
449 | } | |
450 | ||
451 | /** | |
452 | * @see edu.uci.ics.jung.visualization.LayoutMutable#update() | |
453 | */ | |
454 | public void update() { | |
455 | try { | |
456 | 0 | for (Iterator iter = getGraph().getVertices().iterator(); iter |
457 | 0 | .hasNext();) { |
458 | 0 | Vertex v = (Vertex) iter.next(); |
459 | 0 | Coordinates coord = (Coordinates) v.getUserDatum(getBaseKey()); |
460 | 0 | if (coord == null) { |
461 | 0 | coord = new Coordinates(); |
462 | 0 | v.addUserDatum(getBaseKey(), coord, UserData.REMOVE); |
463 | 0 | initializeLocation(v, coord, getCurrentSize()); |
464 | 0 | initialize_local_vertex(v); |
465 | } | |
466 | } | |
467 | 0 | } catch(ConcurrentModificationException cme) { |
468 | 0 | update(); |
469 | 0 | } |
470 | 0 | initialize_local(); |
471 | 0 | } |
472 | ||
473 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |