2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 package edu.uci.ics.jung.algorithms.layout;
12 * This source is under the same license with JUNG.
13 * http://jung.sourceforge.net/license.txt for a description.
16 import java.awt.Dimension;
17 import java.awt.geom.Point2D;
18 import java.util.ConcurrentModificationException;
20 import edu.uci.ics.jung.algorithms.layout.util.RandomLocationTransformer;
21 import edu.uci.ics.jung.algorithms.shortestpath.Distance;
22 import edu.uci.ics.jung.algorithms.shortestpath.DistanceStatistics;
23 import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath;
24 import edu.uci.ics.jung.algorithms.util.IterativeContext;
25 import edu.uci.ics.jung.graph.Graph;
28 * Implements the Kamada-Kawai algorithm for node layout.
29 * Does not respect filter calls, and sometimes crashes when the view changes to it.
31 * @see "Tomihisa Kamada and Satoru Kawai: An algorithm for drawing general indirect graphs. Information Processing Letters 31(1):7-15, 1989"
32 * @see "Tomihisa Kamada: On visualization of abstract objects and relations. Ph.D. dissertation, Dept. of Information Science, Univ. of Tokyo, Dec. 1988."
34 * @author Masanori Harada
36 public class KKLayout<V,E> extends AbstractLayout<V,E> implements IterativeContext {
38 private double EPSILON = 0.1d;
40 private int currentIteration;
41 private int maxIterations = 2000;
42 private String status = "KKLayout";
44 private double L; // the ideal length of an edge
45 private double K = 1; // arbitrary const number
46 private double[][] dm; // distance matrix
48 private boolean adjustForGravity = true;
49 private boolean exchangeVertices = true;
52 private Point2D[] xydata;
55 * Retrieves graph distances between vertices of the visible graph
57 protected Distance<V> distance;
60 * The diameter of the visible graph. In other words, the maximum over all pairs
61 * of vertices of the length of the shortest path between a and bf the visible graph.
63 protected double diameter;
66 * A multiplicative factor which partly specifies the "preferred" length of an edge (L).
68 private double length_factor = 0.9;
71 * A multiplicative factor which specifies the fraction of the graph's diameter to be
72 * used as the inter-vertex distance between disconnected vertices.
74 private double disconnected_multiplier = 0.5;
77 * Creates an instance for the specified graph.
79 public KKLayout(Graph<V,E> g)
81 this(g, new UnweightedShortestPath<V,E>(g));
85 * Creates an instance for the specified graph and distance metric.
87 public KKLayout(Graph<V,E> g, Distance<V> distance){
89 this.distance = distance;
93 * Sets a multiplicative factor which
94 * partly specifies the "preferred" length of an edge (L).
96 public void setLengthFactor(double length_factor){
97 this.length_factor = length_factor;
101 * Sets a multiplicative factor that specifies the fraction of the graph's diameter to be
102 * used as the inter-vertex distance between disconnected vertices.
104 public void setDisconnectedDistanceMultiplier(double disconnected_multiplier){
105 this.disconnected_multiplier = disconnected_multiplier;
109 * Returns a string with information about the current status of the algorithm.
111 public String getStatus() {
112 return status + this.getSize();
116 * Sets the maximum number of iterations.
118 public void setMaxIterations(int maxIterations) {
119 this.maxIterations = maxIterations;
123 * This one is an incremental visualization.
125 public boolean isIncremental() {
130 * Returns true once the current iteration has passed the maximum count.
132 public boolean done() {
133 if (currentIteration > maxIterations) {
139 @SuppressWarnings("unchecked")
140 public void initialize() {
141 currentIteration = 0;
143 if(graph != null && size != null) {
145 double height = size.getHeight();
146 double width = size.getWidth();
148 int n = graph.getVertexCount();
149 dm = new double[n][n];
150 vertices = (V[])graph.getVertices().toArray();
151 xydata = new Point2D[n];
153 // assign IDs to all visible vertices
157 for(V v : graph.getVertices()) {
158 Point2D xyd = transform(v);
164 } catch(ConcurrentModificationException cme) {}
167 diameter = DistanceStatistics.<V,E>diameter(graph, distance, true);
169 double L0 = Math.min(height, width);
170 L = (L0 / diameter) * length_factor; // length_factor used to be hardcoded to 0.9
171 //L = 0.75 * Math.sqrt(height * width / n);
173 for (int i = 0; i < n - 1; i++) {
174 for (int j = i + 1; j < n; j++) {
175 Number d_ij = distance.getDistance(vertices[i], vertices[j]);
176 Number d_ji = distance.getDistance(vertices[j], vertices[i]);
177 double dist = diameter * disconnected_multiplier;
179 dist = Math.min(d_ij.doubleValue(), dist);
181 dist = Math.min(d_ji.doubleValue(), dist);
182 dm[i][j] = dm[j][i] = dist;
191 double energy = calcEnergy();
192 status = "Kamada-Kawai V=" + getGraph().getVertexCount()
193 + "(" + getGraph().getVertexCount() + ")"
194 + " IT: " + currentIteration
198 int n = getGraph().getVertexCount();
202 double maxDeltaM = 0;
203 int pm = -1; // the node having max deltaM
204 for (int i = 0; i < n; i++) {
205 if (isLocked(vertices[i]))
207 double deltam = calcDeltaM(i);
209 if (maxDeltaM < deltam) {
217 for (int i = 0; i < 100; i++) {
218 double[] dxy = calcDeltaXY(pm);
219 xydata[pm].setLocation(xydata[pm].getX()+dxy[0], xydata[pm].getY()+dxy[1]);
221 double deltam = calcDeltaM(pm);
222 if (deltam < EPSILON)
226 if (adjustForGravity)
229 if (exchangeVertices && maxDeltaM < EPSILON) {
230 energy = calcEnergy();
231 for (int i = 0; i < n - 1; i++) {
232 if (isLocked(vertices[i]))
234 for (int j = i + 1; j < n; j++) {
235 if (isLocked(vertices[j]))
237 double xenergy = calcEnergyIfExchanged(i, j);
238 if (energy > xenergy) {
239 double sx = xydata[i].getX();
240 double sy = xydata[i].getY();
241 xydata[i].setLocation(xydata[j]);
242 xydata[j].setLocation(sx, sy);
250 // fireStateChanged();
255 * Shift all vertices so that the center of gravity is located at
256 * the center of the screen.
258 public void adjustForGravity() {
259 Dimension d = getSize();
260 double height = d.getHeight();
261 double width = d.getWidth();
264 for (int i = 0; i < xydata.length; i++) {
265 gx += xydata[i].getX();
266 gy += xydata[i].getY();
270 double diffx = width / 2 - gx;
271 double diffy = height / 2 - gy;
272 for (int i = 0; i < xydata.length; i++) {
273 xydata[i].setLocation(xydata[i].getX()+diffx, xydata[i].getY()+diffy);
278 * @see edu.uci.ics.jung.visualization.layout.AbstractLayout#setSize(java.awt.Dimension)
281 public void setSize(Dimension size) {
282 if(initialized == false)
283 setInitializer(new RandomLocationTransformer<V>(size));
288 * Enable or disable gravity point adjusting.
290 public void setAdjustForGravity(boolean on) {
291 adjustForGravity = on;
295 * Returns true if gravity point adjusting is enabled.
297 public boolean getAdjustForGravity() {
298 return adjustForGravity;
302 * Enable or disable the local minimum escape technique by
303 * exchanging vertices.
305 public void setExchangeVertices(boolean on) {
306 exchangeVertices = on;
310 * Returns true if the local minimum escape technique by
311 * exchanging vertices is enabled.
313 public boolean getExchangeVertices() {
314 return exchangeVertices;
318 * Determines a step to new position of the vertex m.
320 private double[] calcDeltaXY(int m) {
324 double d2E_dxmdym = 0;
325 double d2E_dymdxm = 0;
328 for (int i = 0; i < vertices.length; i++) {
331 double dist = dm[m][i];
332 double l_mi = L * dist;
333 double k_mi = K / (dist * dist);
334 double dx = xydata[m].getX() - xydata[i].getX();
335 double dy = xydata[m].getY() - xydata[i].getY();
336 double d = Math.sqrt(dx * dx + dy * dy);
337 double ddd = d * d * d;
339 dE_dxm += k_mi * (1 - l_mi / d) * dx;
340 dE_dym += k_mi * (1 - l_mi / d) * dy;
341 d2E_d2xm += k_mi * (1 - l_mi * dy * dy / ddd);
342 d2E_dxmdym += k_mi * l_mi * dx * dy / ddd;
343 d2E_d2ym += k_mi * (1 - l_mi * dx * dx / ddd);
346 // d2E_dymdxm equals to d2E_dxmdym.
347 d2E_dymdxm = d2E_dxmdym;
349 double denomi = d2E_d2xm * d2E_d2ym - d2E_dxmdym * d2E_dymdxm;
350 double deltaX = (d2E_dxmdym * dE_dym - d2E_d2ym * dE_dxm) / denomi;
351 double deltaY = (d2E_dymdxm * dE_dxm - d2E_d2xm * dE_dym) / denomi;
352 return new double[]{deltaX, deltaY};
356 * Calculates the gradient of energy function at the vertex m.
358 private double calcDeltaM(int m) {
361 for (int i = 0; i < vertices.length; i++) {
363 double dist = dm[m][i];
364 double l_mi = L * dist;
365 double k_mi = K / (dist * dist);
367 double dx = xydata[m].getX() - xydata[i].getX();
368 double dy = xydata[m].getY() - xydata[i].getY();
369 double d = Math.sqrt(dx * dx + dy * dy);
371 double common = k_mi * (1 - l_mi / d);
372 dEdxm += common * dx;
373 dEdym += common * dy;
376 return Math.sqrt(dEdxm * dEdxm + dEdym * dEdym);
380 * Calculates the energy function E.
382 private double calcEnergy() {
384 for (int i = 0; i < vertices.length - 1; i++) {
385 for (int j = i + 1; j < vertices.length; j++) {
386 double dist = dm[i][j];
387 double l_ij = L * dist;
388 double k_ij = K / (dist * dist);
389 double dx = xydata[i].getX() - xydata[j].getX();
390 double dy = xydata[i].getY() - xydata[j].getY();
391 double d = Math.sqrt(dx * dx + dy * dy);
394 energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
402 * Calculates the energy function E as if positions of the
403 * specified vertices are exchanged.
405 private double calcEnergyIfExchanged(int p, int q) {
407 throw new RuntimeException("p should be < q");
408 double energy = 0; // < 0
409 for (int i = 0; i < vertices.length - 1; i++) {
410 for (int j = i + 1; j < vertices.length; j++) {
416 double dist = dm[i][j];
417 double l_ij = L * dist;
418 double k_ij = K / (dist * dist);
419 double dx = xydata[ii].getX() - xydata[jj].getX();
420 double dy = xydata[ii].getY() - xydata[jj].getY();
421 double d = Math.sqrt(dx * dx + dy * dy);
423 energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
430 public void reset() {
431 currentIteration = 0;