third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/KKLayout.java

   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.algorithms.layout;
  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.awt.geom.Point2D;
  18 import java.util.ConcurrentModificationException;
  19
  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;
  26
  27 /**
  28  * Implements the Kamada-Kawai algorithm for node layout.
  29  * Does not respect filter calls, and sometimes crashes when the view changes to it.
  30  *
  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."
  33  *
  34  * @author Masanori Harada
  35  */
  36 public class KKLayout<V,E> extends AbstractLayout<V,E> implements IterativeContext {
  37
  38         private double EPSILON = 0.1d;
  39
  40         private int currentIteration;
  41     private int maxIterations = 2000;
  42         private String status = "KKLayout";
  43
  44         private double L;                       // the ideal length of an edge
  45         private double K = 1;           // arbitrary const number
  46         private double[][] dm;     // distance matrix
  47
  48         private boolean adjustForGravity = true;
  49         private boolean exchangeVertices = true;
  50
  51         private V[] vertices;
  52         private Point2D[] xydata;
  53
  54     /**
  55      * Retrieves graph distances between vertices of the visible graph
  56      */
  57     protected Distance<V> distance;
  58
  59     /**
  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.
  62      */
  63         protected double diameter;
  64
  65     /**
  66      * A multiplicative factor which partly specifies the "preferred" length of an edge (L).
  67      */
  68     private double length_factor = 0.9;
  69
  70     /**
  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.
  73      */
  74     private double disconnected_multiplier = 0.5;
  75
  76         /**
  77          * Creates an instance for the specified graph.
  78          */
  79         public KKLayout(Graph<V,E> g)
  80     {
  81         this(g, new UnweightedShortestPath<V,E>(g));
  82         }
  83
  84         /**
  85          * Creates an instance for the specified graph and distance metric.
  86          */
  87     public KKLayout(Graph<V,E> g, Distance<V> distance){
  88         super(g);
  89         this.distance = distance;
  90     }
  91
  92     /**
  93      * Sets a multiplicative factor which
  94      * partly specifies the "preferred" length of an edge (L).
  95      */
  96     public void setLengthFactor(double length_factor){
  97         this.length_factor = length_factor;
  98     }
  99
 100     /**
 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.
 103      */
 104     public void setDisconnectedDistanceMultiplier(double disconnected_multiplier){
 105         this.disconnected_multiplier = disconnected_multiplier;
 106     }
 107
 108     /**
 109      * Returns a string with information about the current status of the algorithm.
 110      */
 111         public String getStatus() {
 112                 return status + this.getSize();
 113         }
 114
 115         /**
 116          * Sets the maximum number of iterations.
 117          */
 118     public void setMaxIterations(int maxIterations) {
 119         this.maxIterations = maxIterations;
 120     }
 121
 122         /**
 123          * This one is an incremental visualization.
 124          */
 125         public boolean isIncremental() {
 126                 return true;
 127         }
 128
 129         /**
 130          * Returns true once the current iteration has passed the maximum count.
 131          */
 132         public boolean done() {
 133                 if (currentIteration > maxIterations) {
 134                         return true;
 135                 }
 136                 return false;
 137         }
 138
 139         @SuppressWarnings("unchecked")
 140     public void initialize() {
 141         currentIteration = 0;
 142
 143         if(graph != null && size != null) {
 144
 145                 double height = size.getHeight();
 146                 double width = size.getWidth();
 147
 148                 int n = graph.getVertexCount();
 149                 dm = new double[n][n];
 150                 vertices = (V[])graph.getVertices().toArray();
 151                 xydata = new Point2D[n];
 152
 153                 // assign IDs to all visible vertices
 154                 while(true) {
 155                         try {
 156                                 int index = 0;
 157                                 for(V v : graph.getVertices()) {
 158                                         Point2D xyd = transform(v);
 159                                         vertices[index] = v;
 160                                         xydata[index] = xyd;
 161                                         index++;
 162                                 }
 163                                 break;
 164                         } catch(ConcurrentModificationException cme) {}
 165                 }
 166
 167                 diameter = DistanceStatistics.<V,E>diameter(graph, distance, true);
 168
 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);
 172
 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;
 178                                 if (d_ij != null)
 179                                         dist = Math.min(d_ij.doubleValue(), dist);
 180                                 if (d_ji != null)
 181                                         dist = Math.min(d_ji.doubleValue(), dist);
 182                                 dm[i][j] = dm[j][i] = dist;
 183                         }
 184                 }
 185         }
 186         }
 187
 188         public void step() {
 189                 try {
 190                         currentIteration++;
 191                         double energy = calcEnergy();
 192                         status = "Kamada-Kawai V=" + getGraph().getVertexCount()
 193                         + "(" + getGraph().getVertexCount() + ")"
 194                         + " IT: " + currentIteration
 195                         + " E=" + energy
 196                         ;
 197
 198                         int n = getGraph().getVertexCount();
 199                         if (n == 0)
 200                                 return;
 201
 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]))
 206                                         continue;
 207                                 double deltam = calcDeltaM(i);
 208
 209                                 if (maxDeltaM < deltam) {
 210                                         maxDeltaM = deltam;
 211                                         pm = i;
 212                                 }
 213                         }
 214                         if (pm == -1)
 215                                 return;
 216
 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]);
 220
 221                                 double deltam = calcDeltaM(pm);
 222                                 if (deltam < EPSILON)
 223                                         break;
 224                         }
 225
 226                         if (adjustForGravity)
 227                                 adjustForGravity();
 228
 229                         if (exchangeVertices && maxDeltaM < EPSILON) {
 230                                 energy = calcEnergy();
 231                                 for (int i = 0; i < n - 1; i++) {
 232                                         if (isLocked(vertices[i]))
 233                                                 continue;
 234                                         for (int j = i + 1; j < n; j++) {
 235                                                 if (isLocked(vertices[j]))
 236                                                         continue;
 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);
 243                                                         return;
 244                                                 }
 245                                         }
 246                                 }
 247                         }
 248                 }
 249                 finally {
 250 //                      fireStateChanged();
 251                 }
 252         }
 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                 Dimension d = getSize();
 260                 double height = d.getHeight();
 261                 double width = d.getWidth();
 262                 double gx = 0;
 263                 double gy = 0;
 264                 for (int i = 0; i < xydata.length; i++) {
 265                         gx += xydata[i].getX();
 266                         gy += xydata[i].getY();
 267                 }
 268                 gx /= xydata.length;
 269                 gy /= xydata.length;
 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);
 274                 }
 275         }
 276
 277     /* (non-Javadoc)
 278          * @see edu.uci.ics.jung.visualization.layout.AbstractLayout#setSize(java.awt.Dimension)
 279          */
 280         @Override
 281         public void setSize(Dimension size) {
 282                 if(initialized == false)
 283                         setInitializer(new RandomLocationTransformer<V>(size));
 284                 super.setSize(size);
 285         }
 286
 287         /**
 288          * Enable or disable gravity point adjusting.
 289          */
 290         public void setAdjustForGravity(boolean on) {
 291                 adjustForGravity = on;
 292         }
 293
 294         /**
 295          * Returns true if gravity point adjusting is enabled.
 296          */
 297         public boolean getAdjustForGravity() {
 298                 return adjustForGravity;
 299         }
 300
 301         /**
 302          * Enable or disable the local minimum escape technique by
 303          * exchanging vertices.
 304          */
 305         public void setExchangeVertices(boolean on) {
 306                 exchangeVertices = on;
 307         }
 308
 309         /**
 310          * Returns true if the local minimum escape technique by
 311          * exchanging vertices is enabled.
 312          */
 313         public boolean getExchangeVertices() {
 314                 return exchangeVertices;
 315         }
 316
 317         /**
 318          * Determines a step to new position of the vertex m.
 319          */
 320         private double[] calcDeltaXY(int m) {
 321                 double dE_dxm = 0;
 322                 double dE_dym = 0;
 323                 double d2E_d2xm = 0;
 324                 double d2E_dxmdym = 0;
 325                 double d2E_dymdxm = 0;
 326                 double d2E_d2ym = 0;
 327
 328                 for (int i = 0; i < vertices.length; i++) {
 329                         if (i != m) {
 330
 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;
 338
 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);
 344                         }
 345                 }
 346                 // d2E_dymdxm equals to d2E_dxmdym.
 347                 d2E_dymdxm = d2E_dxmdym;
 348
 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};
 353         }
 354
 355         /**
 356          * Calculates the gradient of energy function at the vertex m.
 357          */
 358         private double calcDeltaM(int m) {
 359                 double dEdxm = 0;
 360                 double dEdym = 0;
 361                 for (int i = 0; i < vertices.length; i++) {
 362                         if (i != m) {
 363                 double dist = dm[m][i];
 364                                 double l_mi = L * dist;
 365                                 double k_mi = K / (dist * dist);
 366
 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);
 370
 371                                 double common = k_mi * (1 - l_mi / d);
 372                                 dEdxm += common * dx;
 373                                 dEdym += common * dy;
 374                         }
 375                 }
 376                 return Math.sqrt(dEdxm * dEdxm + dEdym * dEdym);
 377         }
 378
 379         /**
 380          * Calculates the energy function E.
 381          */
 382         private double calcEnergy() {
 383                 double energy = 0;
 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);
 392
 393
 394                                 energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
 395                                                                           2 * l_ij * d);
 396                         }
 397                 }
 398                 return energy;
 399         }
 400
 401         /**
 402          * Calculates the energy function E as if positions of the
 403          * specified vertices are exchanged.
 404          */
 405         private double calcEnergyIfExchanged(int p, int q) {
 406                 if (p >= 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++) {
 411                                 int ii = i;
 412                                 int jj = j;
 413                                 if (i == p) ii = q;
 414                                 if (j == q) jj = p;
 415
 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);
 422
 423                                 energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
 424                                                                           2 * l_ij * d);
 425                         }
 426                 }
 427                 return energy;
 428         }
 429
 430         public void reset() {
 431                 currentIteration = 0;
 432         }
 433 }