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