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

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. 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.