Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University | |
3 | * of California | |
4 | * All rights reserved. | |
5 | * | |
6 | * This software is open-source under the BSD license; see either | |
7 | * "license.txt" or | |
8 | * http://jung.sourceforge.net/license.txt for a description. | |
9 | */ | |
10 | package edu.uci.ics.jung.visualization.contrib; | |
11 | /* | |
12 | * This source is under the same license with JUNG. | |
13 | * http://jung.sourceforge.net/license.txt for a description. | |
14 | */ | |
15 | ||
16 | import java.awt.Dimension; | |
17 | import java.util.ConcurrentModificationException; | |
18 | import java.util.Iterator; | |
19 | ||
20 | import edu.uci.ics.jung.algorithms.shortestpath.Distance; | |
21 | import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath; | |
22 | import edu.uci.ics.jung.graph.Graph; | |
23 | import edu.uci.ics.jung.graph.Vertex; | |
24 | import edu.uci.ics.jung.statistics.GraphStatistics; | |
25 | import edu.uci.ics.jung.visualization.AbstractLayout; | |
26 | import edu.uci.ics.jung.visualization.Coordinates; | |
27 | ||
28 | /** | |
29 | * Implements the Kamada-Kawai algorithm for node layout. | |
30 | * Does not respect filter calls, and sometimes crashes when the view changes to it. | |
31 | * | |
32 | * @see "Tomihisa Kamada and Satoru Kawai: An algorithm for drawing general indirect graphs. Information Processing Letters 31(1):7-15, 1989" | |
33 | * @see "Tomihisa Kamada: On visualization of abstract objects and relations. Ph.D. dissertation, Dept. of Information Science, Univ. of Tokyo, Dec. 1988." | |
34 | * | |
35 | * @author Masanori Harada | |
36 | */ | |
37 | public class KKLayout extends AbstractLayout { | |
38 | ||
39 | 0 | private double EPSILON = 0.1d; |
40 | ||
41 | private int currentIteration; | |
42 | 0 | private int maxIterations = 2000; |
43 | 0 | private String status = "KKLayout"; |
44 | ||
45 | private double L; // the ideal length of an edge | |
46 | 0 | private double K = 1; // arbitrary const number |
47 | private double[][] dm; // distance matrix | |
48 | ||
49 | 0 | private boolean adjustForGravity = true; |
50 | 0 | private boolean exchangeVertices = true; |
51 | ||
52 | private Vertex[] vertices; | |
53 | private Coordinates[] xydata; | |
54 | ||
55 | /** | |
56 | * Retrieves graph distances between vertices of the visible graph | |
57 | */ | |
58 | protected Distance distance; | |
59 | ||
60 | /** | |
61 | * The diameter of the visible graph. In other words, the maximum over all pairs | |
62 | * of vertices of the length of the shortest path between a and bf the visible graph. | |
63 | */ | |
64 | protected double diameter; | |
65 | ||
66 | /** | |
67 | * A multiplicative factor which partly specifies the "preferred" length of an edge (L). | |
68 | */ | |
69 | 0 | private double length_factor = 0.9; |
70 | ||
71 | /** | |
72 | * A multiplicative factor which specifies the fraction of the graph's diameter to be | |
73 | * used as the inter-vertex distance between disconnected vertices. | |
74 | */ | |
75 | 0 | private double disconnected_multiplier = 0.5; |
76 | ||
77 | public KKLayout(Graph g) | |
78 | { | |
79 | 0 | this(g, new UnweightedShortestPath(g)); |
80 | 0 | } |
81 | ||
82 | public KKLayout(Graph g, Distance distance) | |
83 | { | |
84 | 0 | super(g); |
85 | 0 | this.distance = distance; |
86 | 0 | } |
87 | ||
88 | /** | |
89 | * Sets a multiplicative factor which | |
90 | * partly specifies the "preferred" length of an edge (L). | |
91 | */ | |
92 | public void setLengthFactor(double length_factor) | |
93 | { | |
94 | 0 | this.length_factor = length_factor; |
95 | 0 | } |
96 | ||
97 | /** | |
98 | * Sets a multiplicative factor that specifies the fraction of the graph's diameter to be | |
99 | * used as the inter-vertex distance between disconnected vertices. | |
100 | */ | |
101 | public void setDisconnectedDistanceMultiplier(double disconnected_multiplier) | |
102 | { | |
103 | 0 | this.disconnected_multiplier = disconnected_multiplier; |
104 | 0 | } |
105 | ||
106 | public String getStatus() { | |
107 | 0 | return status + this.getCurrentSize(); |
108 | } | |
109 | ||
110 | public void setMaxIterations(int maxIterations) { | |
111 | 0 | this.maxIterations = maxIterations; |
112 | 0 | } |
113 | ||
114 | /** | |
115 | * This one is an incremental visualization. | |
116 | */ | |
117 | public boolean isIncremental() { | |
118 | 0 | return true; |
119 | } | |
120 | ||
121 | /** | |
122 | * Returns true once the current iteration has passed the maximum count. | |
123 | */ | |
124 | public boolean incrementsAreDone() { | |
125 | 0 | if (currentIteration > maxIterations) { |
126 | 0 | return true; |
127 | } | |
128 | 0 | return false; |
129 | } | |
130 | ||
131 | protected void initialize_local() { | |
132 | 0 | currentIteration = 0; |
133 | 0 | } |
134 | ||
135 | protected void initializeLocations() { | |
136 | 0 | super.initializeLocations(); |
137 | ||
138 | 0 | Dimension d = getCurrentSize(); |
139 | 0 | double height = d.getHeight(); |
140 | 0 | double width = d.getWidth(); |
141 | ||
142 | 0 | int n = getGraph().getVertices().size(); |
143 | 0 | dm = new double[n][n]; |
144 | 0 | vertices = new Vertex[n]; |
145 | 0 | xydata = new Coordinates[n]; |
146 | ||
147 | // assign IDs to all visible vertices | |
148 | while(true) { | |
149 | try { | |
150 | 0 | int index = 0; |
151 | 0 | for (Iterator iter = getGraph().getVertices().iterator(); |
152 | 0 | iter.hasNext(); ) { |
153 | 0 | Vertex v = (Vertex) iter.next(); |
154 | 0 | Coordinates xyd = getCoordinates(v); |
155 | 0 | vertices[index] = v; |
156 | 0 | xydata[index] = xyd; |
157 | 0 | index++; |
158 | } | |
159 | 0 | break; |
160 | 0 | } catch(ConcurrentModificationException cme) {} |
161 | } | |
162 | ||
163 | 0 | diameter = GraphStatistics.diameter(getGraph(), distance, true); |
164 | ||
165 | 0 | double L0 = Math.min(height, width); |
166 | 0 | L = (L0 / diameter) * length_factor; // length_factor used to be hardcoded to 0.9 |
167 | //L = 0.75 * Math.sqrt(height * width / n); | |
168 | ||
169 | 0 | for (int i = 0; i < n - 1; i++) |
170 | { | |
171 | 0 | for (int j = i + 1; j < n; j++) |
172 | { | |
173 | 0 | Number d_ij = distance.getDistance(vertices[i], vertices[j]); |
174 | 0 | Number d_ji = distance.getDistance(vertices[j], vertices[i]); |
175 | 0 | double dist = diameter * disconnected_multiplier; |
176 | 0 | if (d_ij != null) |
177 | 0 | dist = Math.min(d_ij.doubleValue(), dist); |
178 | 0 | if (d_ji != null) |
179 | 0 | dist = Math.min(d_ji.doubleValue(), dist); |
180 | 0 | dm[i][j] = dm[j][i] = dist; |
181 | } | |
182 | } | |
183 | 0 | } |
184 | ||
185 | protected void initialize_local_vertex(Vertex v) { | |
186 | 0 | } |
187 | ||
188 | public void advancePositions() { | |
189 | 0 | currentIteration++; |
190 | 0 | double energy = calcEnergy(); |
191 | 0 | status = "Kamada-Kawai V=" + getVisibleVertices().size() |
192 | + "(" + getGraph().numVertices() + ")" | |
193 | + " IT: " + currentIteration | |
194 | + " E=" + energy | |
195 | ; | |
196 | ||
197 | 0 | int n = getVisibleGraph().numVertices(); |
198 | 0 | if (n == 0) |
199 | 0 | return; |
200 | ||
201 | 0 | double maxDeltaM = 0; |
202 | 0 | int pm = -1; // the node having max deltaM |
203 | 0 | for (int i = 0; i < n; i++) { |
204 | 0 | if (isLocked(vertices[i])) |
205 | 0 | continue; |
206 | 0 | double deltam = calcDeltaM(i); |
207 | //System.out.println("* i=" + i + " deltaM=" + deltam); | |
208 | 0 | if (maxDeltaM < deltam) { |
209 | 0 | maxDeltaM = deltam; |
210 | 0 | pm = i; |
211 | } | |
212 | } | |
213 | 0 | if (pm == -1) |
214 | 0 | return; |
215 | ||
216 | 0 | for (int i = 0; i < 100; i++) { |
217 | 0 | double[] dxy = calcDeltaXY(pm); |
218 | 0 | xydata[pm].add(dxy[0], dxy[1]); |
219 | 0 | double deltam = calcDeltaM(pm); |
220 | 0 | if (deltam < EPSILON) |
221 | 0 | break; |
222 | //if (dxy[0] > 1 || dxy[1] > 1 || dxy[0] < -1 || dxy[1] < -1) | |
223 | // break; | |
224 | } | |
225 | ||
226 | 0 | if (adjustForGravity) |
227 | 0 | adjustForGravity(); |
228 | ||
229 | 0 | if (exchangeVertices && maxDeltaM < EPSILON) { |
230 | 0 | energy = calcEnergy(); |
231 | 0 | for (int i = 0; i < n - 1; i++) { |
232 | 0 | if (isLocked(vertices[i])) |
233 | 0 | continue; |
234 | 0 | for (int j = i + 1; j < n; j++) { |
235 | 0 | if (isLocked(vertices[j])) |
236 | 0 | continue; |
237 | 0 | double xenergy = calcEnergyIfExchanged(i, j); |
238 | 0 | if (energy > xenergy) { |
239 | 0 | double sx = xydata[i].getX(); |
240 | 0 | double sy = xydata[i].getY(); |
241 | 0 | xydata[i].setX(xydata[j].getX()); |
242 | 0 | xydata[i].setY(xydata[j].getY()); |
243 | 0 | xydata[j].setX(sx); |
244 | 0 | xydata[j].setY(sy); |
245 | //System.out.println("SWAP " + i + " with " + j + | |
246 | // " maxDeltaM=" + maxDeltaM); | |
247 | 0 | return; |
248 | } | |
249 | } | |
250 | } | |
251 | } | |
252 | 0 | } |
253 | ||
254 | /** | |
255 | * Shift all vertices so that the center of gravity is located at | |
256 | * the center of the screen. | |
257 | */ | |
258 | public void adjustForGravity() { | |
259 | 0 | Dimension d = getCurrentSize(); |
260 | 0 | double height = d.getHeight(); |
261 | 0 | double width = d.getWidth(); |
262 | 0 | double gx = 0; |
263 | 0 | double gy = 0; |
264 | 0 | for (int i = 0; i < xydata.length; i++) { |
265 | 0 | gx += xydata[i].getX(); |
266 | 0 | gy += xydata[i].getY(); |
267 | } | |
268 | 0 | gx /= xydata.length; |
269 | 0 | gy /= xydata.length; |
270 | 0 | double diffx = width / 2 - gx; |
271 | 0 | double diffy = height / 2 - gy; |
272 | 0 | for (int i = 0; i < xydata.length; i++) { |
273 | 0 | xydata[i].add(diffx, diffy); |
274 | } | |
275 | 0 | } |
276 | ||
277 | /** | |
278 | * Enable or disable gravity point adjusting. | |
279 | */ | |
280 | public void setAdjustForGravity(boolean on) { | |
281 | 0 | adjustForGravity = on; |
282 | 0 | } |
283 | ||
284 | /** | |
285 | * Returns true if gravity point adjusting is enabled. | |
286 | */ | |
287 | public boolean getAdjustForGravity() { | |
288 | 0 | return adjustForGravity; |
289 | } | |
290 | ||
291 | /** | |
292 | * Enable or disable the local minimum escape technique by | |
293 | * exchanging vertices. | |
294 | */ | |
295 | public void setExchangeVertices(boolean on) { | |
296 | 0 | exchangeVertices = on; |
297 | 0 | } |
298 | ||
299 | /** | |
300 | * Returns true if the local minimum escape technique by | |
301 | * exchanging vertices is enabled. | |
302 | */ | |
303 | public boolean getExchangeVertices() { | |
304 | 0 | return exchangeVertices; |
305 | } | |
306 | ||
307 | /** | |
308 | * Determines a step to new position of the vertex m. | |
309 | */ | |
310 | private double[] calcDeltaXY(int m) { | |
311 | 0 | double dE_dxm = 0; |
312 | 0 | double dE_dym = 0; |
313 | 0 | double d2E_d2xm = 0; |
314 | 0 | double d2E_dxmdym = 0; |
315 | 0 | double d2E_dymdxm = 0; |
316 | 0 | double d2E_d2ym = 0; |
317 | ||
318 | 0 | for (int i = 0; i < vertices.length; i++) { |
319 | 0 | if (i != m) { |
320 | ||
321 | 0 | double dist = dm[m][i]; |
322 | 0 | double l_mi = L * dist; |
323 | 0 | double k_mi = K / (dist * dist); |
324 | 0 | double dx = xydata[m].getX() - xydata[i].getX(); |
325 | 0 | double dy = xydata[m].getY() - xydata[i].getY(); |
326 | 0 | double d = Math.sqrt(dx * dx + dy * dy); |
327 | 0 | double ddd = d * d * d; |
328 | ||
329 | 0 | dE_dxm += k_mi * (1 - l_mi / d) * dx; |
330 | 0 | dE_dym += k_mi * (1 - l_mi / d) * dy; |
331 | 0 | d2E_d2xm += k_mi * (1 - l_mi * dy * dy / ddd); |
332 | 0 | d2E_dxmdym += k_mi * l_mi * dx * dy / ddd; |
333 | 0 | d2E_d2ym += k_mi * (1 - l_mi * dx * dx / ddd); |
334 | } | |
335 | } | |
336 | // d2E_dymdxm equals to d2E_dxmdym. | |
337 | 0 | d2E_dymdxm = d2E_dxmdym; |
338 | ||
339 | 0 | double denomi = d2E_d2xm * d2E_d2ym - d2E_dxmdym * d2E_dymdxm; |
340 | 0 | double deltaX = (d2E_dxmdym * dE_dym - d2E_d2ym * dE_dxm) / denomi; |
341 | 0 | double deltaY = (d2E_dymdxm * dE_dxm - d2E_d2xm * dE_dym) / denomi; |
342 | 0 | return new double[]{deltaX, deltaY}; |
343 | } | |
344 | ||
345 | /** | |
346 | * Calculates the gradient of energy function at the vertex m. | |
347 | */ | |
348 | private double calcDeltaM(int m) { | |
349 | 0 | double dEdxm = 0; |
350 | 0 | double dEdym = 0; |
351 | 0 | for (int i = 0; i < vertices.length; i++) { |
352 | 0 | if (i != m) { |
353 | 0 | double dist = dm[m][i]; |
354 | 0 | double l_mi = L * dist; |
355 | 0 | double k_mi = K / (dist * dist); |
356 | ||
357 | 0 | double dx = xydata[m].getX() - xydata[i].getX(); |
358 | 0 | double dy = xydata[m].getY() - xydata[i].getY(); |
359 | 0 | double d = Math.sqrt(dx * dx + dy * dy); |
360 | ||
361 | 0 | double common = k_mi * (1 - l_mi / d); |
362 | 0 | dEdxm += common * dx; |
363 | 0 | dEdym += common * dy; |
364 | } | |
365 | } | |
366 | 0 | return Math.sqrt(dEdxm * dEdxm + dEdym * dEdym); |
367 | } | |
368 | ||
369 | /** | |
370 | * Calculates the energy function E. | |
371 | */ | |
372 | private double calcEnergy() { | |
373 | 0 | double energy = 0; |
374 | 0 | for (int i = 0; i < vertices.length - 1; i++) { |
375 | 0 | for (int j = i + 1; j < vertices.length; j++) { |
376 | 0 | double dist = dm[i][j]; |
377 | 0 | double l_ij = L * dist; |
378 | 0 | double k_ij = K / (dist * dist); |
379 | 0 | double dx = xydata[i].getX() - xydata[j].getX(); |
380 | 0 | double dy = xydata[i].getY() - xydata[j].getY(); |
381 | 0 | double d = Math.sqrt(dx * dx + dy * dy); |
382 | ||
383 | ||
384 | 0 | energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij - |
385 | 2 * l_ij * d); | |
386 | } | |
387 | } | |
388 | 0 | return energy; |
389 | } | |
390 | ||
391 | /** | |
392 | * Calculates the energy function E as if positions of the | |
393 | * specified vertices are exchanged. | |
394 | */ | |
395 | private double calcEnergyIfExchanged(int p, int q) { | |
396 | 0 | if (p >= q) |
397 | 0 | throw new RuntimeException("p should be < q"); |
398 | 0 | double energy = 0; // < 0 |
399 | 0 | for (int i = 0; i < vertices.length - 1; i++) { |
400 | 0 | for (int j = i + 1; j < vertices.length; j++) { |
401 | 0 | int ii = i; |
402 | 0 | int jj = j; |
403 | 0 | if (i == p) ii = q; |
404 | 0 | if (j == q) jj = p; |
405 | ||
406 | 0 | double dist = dm[i][j]; |
407 | 0 | double l_ij = L * dist; |
408 | 0 | double k_ij = K / (dist * dist); |
409 | 0 | double dx = xydata[ii].getX() - xydata[jj].getX(); |
410 | 0 | double dy = xydata[ii].getY() - xydata[jj].getY(); |
411 | 0 | double d = Math.sqrt(dx * dx + dy * dy); |
412 | ||
413 | 0 | energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij - |
414 | 2 * l_ij * d); | |
415 | } | |
416 | } | |
417 | 0 | return energy; |
418 | } | |
419 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |