# Coverage details for edu.uci.ics.jung.visualization.contrib.KKLayoutInt

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. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.