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.geom.Point2D; | |
11 | import java.util.ConcurrentModificationException; | |
12 | import java.util.Iterator; | |
13 | ||
14 | import cern.colt.matrix.DoubleMatrix1D; | |
15 | import cern.colt.matrix.impl.DenseDoubleMatrix1D; | |
16 | import edu.uci.ics.jung.exceptions.FatalException; | |
17 | import edu.uci.ics.jung.graph.Edge; | |
18 | import edu.uci.ics.jung.graph.Graph; | |
19 | import edu.uci.ics.jung.graph.Vertex; | |
20 | import edu.uci.ics.jung.utils.Pair; | |
21 | import edu.uci.ics.jung.utils.UserData; | |
22 | ||
23 | /** | |
24 | * Implements the Fruchterman-Reingold algorithm for node layout. | |
25 | * | |
26 | * @author Scott White, Yan-Biao Boey, Danyel Fisher | |
27 | */ | |
28 | public class FRLayout extends AbstractLayout implements LayoutMutable { | |
29 | ||
30 | 1 | private static final Object FR_KEY = "edu.uci.ics.jung.FR_Visualization_Key"; |
31 | ||
32 | private double forceConstant; | |
33 | ||
34 | private double temperature; | |
35 | ||
36 | private int currentIteration; | |
37 | ||
38 | 9 | private String status = null; |
39 | ||
40 | 9 | private int mMaxIterations = 700; |
41 | ||
42 | public FRLayout(Graph g) { | |
43 | 9 | super(g); |
44 | 9 | } |
45 | ||
46 | 9 | private double attraction_multiplier = 0.75; |
47 | ||
48 | private double attraction_constant; | |
49 | ||
50 | 9 | private double repulsion_multiplier = 0.75; |
51 | ||
52 | private double repulsion_constant; | |
53 | ||
54 | public void setAttractionMultiplier(double attraction) | |
55 | { | |
56 | 0 | this.attraction_multiplier = attraction; |
57 | 0 | } |
58 | ||
59 | public void setRepulsionMultiplier(double repulsion) | |
60 | { | |
61 | 0 | this.repulsion_multiplier = repulsion; |
62 | 0 | } |
63 | ||
64 | /* | |
65 | * new function for handling updates and changes to the graph | |
66 | */ | |
67 | public synchronized void update() { | |
68 | try { | |
69 | 0 | for (Iterator iter = getGraph().getVertices().iterator(); iter |
70 | 0 | .hasNext();) { |
71 | 0 | Vertex v = (Vertex) iter.next(); |
72 | 0 | Coordinates coord = getCoordinates(v); |
73 | // Coordinates coord = (Coordinates) v.getUserDatum(getBaseKey()); | |
74 | 0 | if (coord == null) { |
75 | 0 | coord = new Coordinates(); |
76 | 0 | v.addUserDatum(getBaseKey(), coord, UserData.REMOVE); |
77 | 0 | initializeLocation(v, coord, getCurrentSize()); |
78 | 0 | initialize_local_vertex(v); |
79 | } | |
80 | ||
81 | } | |
82 | 0 | } catch(ConcurrentModificationException cme) { |
83 | 0 | update(); |
84 | 0 | } |
85 | 0 | initialize_local(); |
86 | 0 | } |
87 | ||
88 | /** | |
89 | * Returns the current temperature and number of iterations elapsed, as a | |
90 | * string. | |
91 | */ | |
92 | public String getStatus() { | |
93 | 2 | return status; |
94 | } | |
95 | ||
96 | public void forceMove(Vertex picked,double x, double y) { | |
97 | 50 | super.forceMove(picked, x, y); |
98 | 50 | } |
99 | ||
100 | protected void initialize_local() { | |
101 | 10 | currentIteration = 0; |
102 | 10 | temperature = getCurrentSize().getWidth() / 10; |
103 | ||
104 | 10 | forceConstant = |
105 | Math | |
106 | .sqrt(getCurrentSize().getHeight() | |
107 | * getCurrentSize().getWidth() | |
108 | / getVisibleGraph().numVertices()); | |
109 | // / Math.max(getVisibleGraph().numEdges(), getVisibleGraph().numVertices())); | |
110 | ||
111 | 10 | attraction_constant = attraction_multiplier * forceConstant; |
112 | 10 | repulsion_constant = repulsion_multiplier * forceConstant; |
113 | ||
114 | // forceConstant = 0.75 * Math | |
115 | // .sqrt(getCurrentSize().getHeight() | |
116 | // * getCurrentSize().getWidth() | |
117 | // / getVisibleGraph().numVertices()); | |
118 | 10 | } |
119 | ||
120 | 9 | private Object key = null; |
121 | ||
122 | 9 | private double EPSILON = 0.000001D; |
123 | ||
124 | /** | |
125 | * Returns a visualization-specific key (that is, specific both to this | |
126 | * instance and <tt>AbstractLayout</tt>) that can be used to access | |
127 | * UserData related to the <tt>AbstractLayout</tt>. | |
128 | */ | |
129 | public Object getKey() { | |
130 | 205426 | if (key == null) key = new Pair(this, FR_KEY); |
131 | 205426 | return key; |
132 | } | |
133 | ||
134 | protected void initialize_local_vertex(Vertex v) { | |
135 | 500 | if (v.getUserDatum(getKey()) == null) { |
136 | 450 | v.addUserDatum(getKey(), new FRVertexData(), UserData.REMOVE); |
137 | } | |
138 | 500 | } |
139 | ||
140 | /** | |
141 | * Moves the iteration forward one notch, calculation attraction and | |
142 | * repulsion between vertices and edges and cooling the temperature. | |
143 | */ | |
144 | public synchronized void advancePositions() { | |
145 | 197 | currentIteration++; |
146 | 197 | status = "VV: " + getVisibleVertices().size() + " IT: " |
147 | + currentIteration + " temp: " + temperature; | |
148 | /** | |
149 | * Calculate repulsion | |
150 | */ | |
151 | while(true) { | |
152 | ||
153 | try { | |
154 | 197 | for (Iterator iter = getVisibleVertices().iterator(); iter.hasNext();) { |
155 | 9466 | Vertex v1 = (Vertex) iter.next(); |
156 | 9466 | if (isLocked(v1)) continue; |
157 | 9466 | calcRepulsion(v1); |
158 | } | |
159 | 197 | break; |
160 | 0 | } catch(ConcurrentModificationException cme) {} |
161 | } | |
162 | ||
163 | /** | |
164 | * Calculate attraction | |
165 | */ | |
166 | while(true) { | |
167 | try { | |
168 | 197 | for (Iterator iter = getVisibleEdges().iterator(); iter.hasNext();) { |
169 | 92772 | Edge e = (Edge) iter.next(); |
170 | ||
171 | 92772 | calcAttraction(e); |
172 | } | |
173 | 197 | break; |
174 | 0 | } catch(ConcurrentModificationException cme) {} |
175 | } | |
176 | ||
177 | // double cumulativeChange = 0; | |
178 | ||
179 | while(true) { | |
180 | try { | |
181 | ||
182 | 197 | for (Iterator iter = getVisibleVertices().iterator(); iter.hasNext();) { |
183 | 9466 | Vertex v = (Vertex) iter.next(); |
184 | 9466 | if (isLocked(v)) continue; |
185 | 9466 | calcPositions(v); |
186 | } | |
187 | 197 | break; |
188 | 0 | } catch(ConcurrentModificationException cme) {} |
189 | } | |
190 | 197 | cool(); |
191 | 197 | } |
192 | ||
193 | public synchronized void calcPositions(Vertex v) { | |
194 | 9466 | FRVertexData fvd = getFRData(v); |
195 | 9466 | if(fvd == null) return; |
196 | 9466 | Coordinates xyd = getCoordinates(v); |
197 | 9466 | double deltaLength = Math.max(EPSILON, Math.sqrt(fvd.disp |
198 | .zDotProduct(fvd.disp))); | |
199 | ||
200 | 9466 | double newXDisp = fvd.getXDisp() / deltaLength |
201 | * Math.min(deltaLength, temperature); | |
202 | ||
203 | 9466 | if (Double.isNaN(newXDisp)) { throw new FatalException( |
204 | "Unexpected mathematical result in FRLayout:calcPositions [xdisp]"); } | |
205 | ||
206 | 9466 | double newYDisp = fvd.getYDisp() / deltaLength |
207 | * Math.min(deltaLength, temperature); | |
208 | 9466 | xyd.addX(newXDisp); |
209 | 9466 | xyd.addY(newYDisp); |
210 | ||
211 | 9466 | double borderWidth = getCurrentSize().getWidth() / 50.0; |
212 | 9466 | double newXPos = xyd.getX(); |
213 | 9466 | if (newXPos < borderWidth) { |
214 | 0 | newXPos = borderWidth + Math.random() * borderWidth * 2.0; |
215 | 9466 | } else if (newXPos > (getCurrentSize().getWidth() - borderWidth)) { |
216 | 0 | newXPos = getCurrentSize().getWidth() - borderWidth - Math.random() |
217 | * borderWidth * 2.0; | |
218 | } | |
219 | //double newXPos = Math.min(getCurrentSize().getWidth() - 20.0, | |
220 | // Math.max(20.0, xyd.getX())); | |
221 | ||
222 | 9466 | double newYPos = xyd.getY(); |
223 | 9466 | if (newYPos < borderWidth) { |
224 | 0 | newYPos = borderWidth + Math.random() * borderWidth * 2.0; |
225 | 9466 | } else if (newYPos > (getCurrentSize().getHeight() - borderWidth)) { |
226 | 0 | newYPos = getCurrentSize().getHeight() - borderWidth |
227 | - Math.random() * borderWidth * 2.0; | |
228 | } | |
229 | //double newYPos = Math.min(getCurrentSize().getHeight() - 20.0, | |
230 | // Math.max(20.0, xyd.getY())); | |
231 | ||
232 | 9466 | xyd.setX(newXPos); |
233 | 9466 | xyd.setY(newYPos); |
234 | 9466 | } |
235 | ||
236 | public void calcAttraction(Edge e) { | |
237 | 92772 | Pair endpoints = e.getEndpoints(); |
238 | 92772 | Vertex v1 = (Vertex)endpoints.getFirst(); |
239 | 92772 | Vertex v2 = (Vertex)endpoints.getSecond(); |
240 | 92772 | boolean v1_locked = isLocked(v1); |
241 | 92772 | boolean v2_locked = isLocked(v2); |
242 | ||
243 | // if both are locked, nothing to do; return | |
244 | 92772 | if (v1_locked && v2_locked) |
245 | 0 | return; |
246 | ||
247 | 92772 | Point2D p1 = getLocation(v1); |
248 | 92772 | Point2D p2 = getLocation(v2); |
249 | 92772 | if(p1 == null || p2 == null) return; |
250 | 92772 | double xDelta = p1.getX() - p2.getX(); |
251 | 92772 | double yDelta = p1.getY() - p2.getY(); |
252 | ||
253 | 92772 | double deltaLength = Math.max(EPSILON, Math.sqrt((xDelta * xDelta) |
254 | + (yDelta * yDelta))); | |
255 | ||
256 | // double force = (deltaLength * deltaLength) / forceConstant; | |
257 | ||
258 | 92772 | double force = (deltaLength * deltaLength) / attraction_constant; |
259 | ||
260 | 92772 | if (Double.isNaN(force)) { throw new FatalException( |
261 | "Unexpected mathematical result in FRLayout:calcPositions [force]"); } | |
262 | ||
263 | 92772 | double dx = (xDelta / deltaLength) * force; |
264 | 92772 | double dy = (yDelta / deltaLength) * force; |
265 | ||
266 | 92772 | if (!v1_locked) |
267 | { | |
268 | 92772 | FRVertexData fvd1 = getFRData(v1); |
269 | 92772 | fvd1.decrementDisp(dx, dy); |
270 | } | |
271 | 92772 | if (!v2_locked) |
272 | { | |
273 | 92772 | FRVertexData fvd2 = getFRData(v2); |
274 | 92772 | fvd2.incrementDisp(dx, dy); |
275 | } | |
276 | 92772 | } |
277 | ||
278 | public void calcRepulsion(Vertex v1) { | |
279 | 9466 | FRVertexData fvd1 = getFRData(v1); |
280 | 9466 | if(fvd1 == null) return; |
281 | 9466 | fvd1.setDisp(0, 0); |
282 | ||
283 | try { | |
284 | 9466 | for (Iterator iter2 = getVisibleVertices().iterator(); iter2.hasNext();) { |
285 | 463316 | Vertex v2 = (Vertex) iter2.next(); |
286 | // if (isLocked(v2)) continue; | |
287 | 463316 | if (v1 != v2) { |
288 | 453850 | Point2D p1 = getLocation(v1); |
289 | 453850 | Point2D p2 = getLocation(v2); |
290 | 453850 | if(p1 == null || p2 == null) continue; |
291 | 453850 | double xDelta = p1.getX() - p2.getX(); |
292 | 453850 | double yDelta = p1.getY() - p2.getY(); |
293 | ||
294 | 453850 | double deltaLength = Math.max(EPSILON, Math |
295 | .sqrt((xDelta * xDelta) + (yDelta * yDelta))); | |
296 | ||
297 | // double force = (forceConstant * forceConstant) / deltaLength; | |
298 | 453850 | double force = (repulsion_constant * repulsion_constant) / deltaLength; |
299 | ||
300 | 453850 | if (Double.isNaN(force)) { throw new FatalException( |
301 | "Unexpected mathematical result in FRLayout:calcPositions [repulsion]"); } | |
302 | ||
303 | 453850 | fvd1.incrementDisp((xDelta / deltaLength) * force, |
304 | (yDelta / deltaLength) * force); | |
305 | } | |
306 | } | |
307 | 0 | } catch(ConcurrentModificationException cme) { |
308 | 0 | calcRepulsion(v1); |
309 | 9466 | } |
310 | 9466 | } |
311 | ||
312 | private void cool() { | |
313 | 197 | temperature *= (1.0 - currentIteration / (double) mMaxIterations); |
314 | 197 | } |
315 | ||
316 | public void setMaxIterations(int maxIterations) { | |
317 | 0 | mMaxIterations = maxIterations; |
318 | 0 | } |
319 | ||
320 | public FRVertexData getFRData(Vertex v) { | |
321 | 204476 | return (FRVertexData) (v.getUserDatum(getKey())); |
322 | } | |
323 | ||
324 | /** | |
325 | * This one is an incremental visualization. | |
326 | */ | |
327 | public boolean isIncremental() { | |
328 | 2 | return true; |
329 | } | |
330 | ||
331 | /** | |
332 | * Returns true once the current iteration has passed the maximum count, | |
333 | * <tt>MAX_ITERATIONS</tt>. | |
334 | */ | |
335 | public boolean incrementsAreDone() { | |
336 | 204 | if (currentIteration > mMaxIterations) { |
337 | // System.out.println("Reached currentIteration =" + currentIteration + ", maxIterations=" + mMaxIterations); | |
338 | 0 | return true; |
339 | } | |
340 | 204 | return false; |
341 | } | |
342 | ||
343 | public static class FRVertexData { | |
344 | ||
345 | private DoubleMatrix1D disp; | |
346 | ||
347 | public FRVertexData() { | |
348 | initialize(); | |
349 | } | |
350 | ||
351 | public void initialize() { | |
352 | disp = new DenseDoubleMatrix1D(2); | |
353 | } | |
354 | ||
355 | public double getXDisp() { | |
356 | return disp.get(0); | |
357 | } | |
358 | ||
359 | public double getYDisp() { | |
360 | return disp.get(1); | |
361 | } | |
362 | ||
363 | public void setDisp(double x, double y) { | |
364 | disp.set(0, x); | |
365 | disp.set(1, y); | |
366 | } | |
367 | ||
368 | public void incrementDisp(double x, double y) { | |
369 | disp.set(0, disp.get(0) + x); | |
370 | disp.set(1, disp.get(1) + y); | |
371 | } | |
372 | ||
373 | public void decrementDisp(double x, double y) { | |
374 | disp.set(0, disp.get(0) - x); | |
375 | disp.set(1, disp.get(1) - y); | |
376 | } | |
377 | } | |
378 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |