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

   1 /*
   2  * Copyright (c) 2003, the JUNG Project and the Regents of the University of
   3  * California All rights reserved.
   4  *
   5  * This software is open-source under the BSD license; see either "license.txt"
   6  * or http://jung.sourceforge.net/license.txt for a description.
   7  */
   8 package edu.uci.ics.jung.algorithms.layout;
   9
  10 import edu.uci.ics.jung.algorithms.layout.util.RandomLocationTransformer;
  11 import edu.uci.ics.jung.algorithms.util.IterativeContext;
  12 import edu.uci.ics.jung.graph.Graph;
  13 import edu.uci.ics.jung.graph.util.Pair;
  14
  15 import org.apache.commons.collections15.Factory;
  16 import org.apache.commons.collections15.Transformer;
  17 import org.apache.commons.collections15.functors.ConstantTransformer;
  18 import org.apache.commons.collections15.map.LazyMap;
  19
  20 import java.awt.Dimension;
  21 import java.awt.event.ComponentAdapter;
  22 import java.awt.event.ComponentEvent;
  23 import java.awt.geom.Point2D;
  24 import java.util.ConcurrentModificationException;
  25 import java.util.HashMap;
  26 import java.util.Map;
  27
  28 /**
  29  * The SpringLayout package represents a visualization of a set of nodes. The
  30  * SpringLayout, which is initialized with a Graph, assigns X/Y locations to
  31  * each node. When called <code>relax()</code>, the SpringLayout moves the
  32  * visualization forward one step.
  33  *
  34  * @author Danyel Fisher
  35  * @author Joshua O'Madadhain
  36  */
  37 public class SpringLayout<V, E> extends AbstractLayout<V,E> implements IterativeContext {
  38
  39     protected double stretch = 0.70;
  40     protected Transformer<E, Integer> lengthFunction;
  41     protected int repulsion_range_sq = 100 * 100;
  42     protected double force_multiplier = 1.0 / 3.0;
  43
  44     protected Map<V, SpringVertexData> springVertexData =
  45         LazyMap.decorate(new HashMap<V, SpringVertexData>(),
  46                         new Factory<SpringVertexData>() {
  47                                         public SpringVertexData create() {
  48                                                 return new SpringVertexData();
  49                                         }});
  50
  51     /**
  52      * Constructor for a SpringLayout for a raw graph with associated
  53      * dimension--the input knows how big the graph is. Defaults to the unit
  54      * length function.
  55      */
  56     @SuppressWarnings("unchecked")
  57     public SpringLayout(Graph<V,E> g) {
  58         this(g, new ConstantTransformer(30));
  59     }
  60
  61     /**
  62      * Constructor for a SpringLayout for a raw graph with associated component.
  63      *
  64      * @param g the {@code Graph} to lay out
  65      * @param length_function provides a length for each edge
  66      */
  67     public SpringLayout(Graph<V,E> g, Transformer<E, Integer> length_function)
  68     {
  69         super(g);
  70         this.lengthFunction = length_function;
  71     }
  72
  73     /**
  74      * Returns the current value for the stretch parameter.
  75      * @see #setStretch(double)
  76      */
  77     public double getStretch() {
  78         return stretch;
  79     }
  80
  81     /**
  82      * Sets the dimensions of the available space for layout to {@code size}.
  83      */
  84         @Override
  85         public void setSize(Dimension size) {
  86                 if(initialized == false)
  87                         setInitializer(new RandomLocationTransformer<V>(size));
  88                 super.setSize(size);
  89         }
  90
  91     /**
  92      * <p>Sets the stretch parameter for this instance.  This value
  93      * specifies how much the degrees of an edge's incident vertices
  94      * should influence how easily the endpoints of that edge
  95      * can move (that is, that edge's tendency to change its length).</p>
  96      *
  97      * <p>The default value is 0.70.  Positive values less than 1 cause
  98      * high-degree vertices to move less than low-degree vertices, and
  99      * values > 1 cause high-degree vertices to move more than
 100      * low-degree vertices.  Negative values will have unpredictable
 101      * and inconsistent results.</p>
 102      * @param stretch
 103      */
 104     public void setStretch(double stretch) {
 105         this.stretch = stretch;
 106     }
 107
 108     /**
 109      * Returns the current value for the node repulsion range.
 110      * @see #setRepulsionRange(int)
 111      */
 112     public int getRepulsionRange() {
 113         return (int)(Math.sqrt(repulsion_range_sq));
 114     }
 115
 116     /**
 117      * Sets the node repulsion range (in drawing area units) for this instance.
 118      * Outside this range, nodes do not repel each other.  The default value
 119      * is 100.  Negative values are treated as their positive equivalents.
 120      * @param range
 121      */
 122     public void setRepulsionRange(int range) {
 123         this.repulsion_range_sq = range * range;
 124     }
 125
 126     /**
 127      * Returns the current value for the edge length force multiplier.
 128      * @see #setForceMultiplier(double)
 129      */
 130     public double getForceMultiplier() {
 131         return force_multiplier;
 132     }
 133
 134     /**
 135      * Sets the force multiplier for this instance.  This value is used to
 136      * specify how strongly an edge "wants" to be its default length
 137      * (higher values indicate a greater attraction for the default length),
 138      * which affects how much its endpoints move at each timestep.
 139      * The default value is 1/3.  A value of 0 turns off any attempt by the
 140      * layout to cause edges to conform to the default length.  Negative
 141      * values cause long edges to get longer and short edges to get shorter; use
 142      * at your own risk.
 143      */
 144     public void setForceMultiplier(double force) {
 145         this.force_multiplier = force;
 146     }
 147
 148     public void initialize() {
 149     }
 150
 151     /**
 152      * Relaxation step. Moves all nodes a smidge.
 153      */
 154     public void step() {
 155         try {
 156                 for(V v : getGraph().getVertices()) {
 157                         SpringVertexData svd = springVertexData.get(v);
 158                         if (svd == null) {
 159                                 continue;
 160                         }
 161                         svd.dx /= 4;
 162                         svd.dy /= 4;
 163                         svd.edgedx = svd.edgedy = 0;
 164                         svd.repulsiondx = svd.repulsiondy = 0;
 165                 }
 166         } catch(ConcurrentModificationException cme) {
 167                 step();
 168         }
 169
 170         relaxEdges();
 171         calculateRepulsion();
 172         moveNodes();
 173     }
 174
 175     protected void relaxEdges() {
 176         try {
 177                 for(E e : getGraph().getEdges()) {
 178                     Pair<V> endpoints = getGraph().getEndpoints(e);
 179                         V v1 = endpoints.getFirst();
 180                         V v2 = endpoints.getSecond();
 181
 182                         Point2D p1 = transform(v1);
 183                         Point2D p2 = transform(v2);
 184                         if(p1 == null || p2 == null) continue;
 185                         double vx = p1.getX() - p2.getX();
 186                         double vy = p1.getY() - p2.getY();
 187                         double len = Math.sqrt(vx * vx + vy * vy);
 188
 189                         double desiredLen = lengthFunction.transform(e);
 190
 191                         // round from zero, if needed [zero would be Bad.].
 192                         len = (len == 0) ? .0001 : len;
 193
 194                         double f = force_multiplier * (desiredLen - len) / len;
 195
 196                         f = f * Math.pow(stretch, (getGraph().degree(v1) + getGraph().degree(v2) - 2));
 197
 198                         // the actual movement distance 'dx' is the force multiplied by the
 199                         // distance to go.
 200                         double dx = f * vx;
 201                         double dy = f * vy;
 202                         SpringVertexData v1D, v2D;
 203                         v1D = springVertexData.get(v1);
 204                         v2D = springVertexData.get(v2);
 205
 206                         v1D.edgedx += dx;
 207                         v1D.edgedy += dy;
 208                         v2D.edgedx += -dx;
 209                         v2D.edgedy += -dy;
 210                 }
 211         } catch(ConcurrentModificationException cme) {
 212                 relaxEdges();
 213         }
 214     }
 215
 216     protected void calculateRepulsion() {
 217         try {
 218         for (V v : getGraph().getVertices()) {
 219             if (isLocked(v)) continue;
 220
 221             SpringVertexData svd = springVertexData.get(v);
 222             if(svd == null) continue;
 223             double dx = 0, dy = 0;
 224
 225             for (V v2 : getGraph().getVertices()) {
 226                 if (v == v2) continue;
 227                 Point2D p = transform(v);
 228                 Point2D p2 = transform(v2);
 229                 if(p == null || p2 == null) continue;
 230                 double vx = p.getX() - p2.getX();
 231                 double vy = p.getY() - p2.getY();
 232                 double distanceSq = p.distanceSq(p2);
 233                 if (distanceSq == 0) {
 234                     dx += Math.random();
 235                     dy += Math.random();
 236                 } else if (distanceSq < repulsion_range_sq) {
 237                     double factor = 1;
 238                     dx += factor * vx / distanceSq;
 239                     dy += factor * vy / distanceSq;
 240                 }
 241             }
 242             double dlen = dx * dx + dy * dy;
 243             if (dlen > 0) {
 244                 dlen = Math.sqrt(dlen) / 2;
 245                 svd.repulsiondx += dx / dlen;
 246                 svd.repulsiondy += dy / dlen;
 247             }
 248         }
 249         } catch(ConcurrentModificationException cme) {
 250             calculateRepulsion();
 251         }
 252     }
 253
 254     protected void moveNodes()
 255     {
 256         synchronized (getSize()) {
 257             try {
 258                 for (V v : getGraph().getVertices()) {
 259                     if (isLocked(v)) continue;
 260                     SpringVertexData vd = springVertexData.get(v);
 261                     if(vd == null) continue;
 262                     Point2D xyd = transform(v);
 263
 264                     vd.dx += vd.repulsiondx + vd.edgedx;
 265                     vd.dy += vd.repulsiondy + vd.edgedy;
 266
 267                     // keeps nodes from moving any faster than 5 per time unit
 268                     xyd.setLocation(xyd.getX()+Math.max(-5, Math.min(5, vd.dx)),
 269                                 xyd.getY()+Math.max(-5, Math.min(5, vd.dy)));
 270
 271                     Dimension d = getSize();
 272                     int width = d.width;
 273                     int height = d.height;
 274
 275                     if (xyd.getX() < 0) {
 276                         xyd.setLocation(0, xyd.getY());
 277                     } else if (xyd.getX() > width) {
 278                         xyd.setLocation(width, xyd.getY());
 279                     }
 280                     if (xyd.getY() < 0) {
 281                         xyd.setLocation(xyd.getX(), 0);
 282                     } else if (xyd.getY() > height) {
 283                         xyd.setLocation(xyd.getX(), height);
 284                     }
 285
 286                 }
 287             } catch(ConcurrentModificationException cme) {
 288                 moveNodes();
 289             }
 290         }
 291     }
 292
 293     protected static class SpringVertexData {
 294         protected double edgedx;
 295         protected double edgedy;
 296         protected double repulsiondx;
 297         protected double repulsiondy;
 298
 299         /** movement speed, x */
 300         protected double dx;
 301
 302         /** movement speed, y */
 303         protected double dy;
 304     }
 305
 306
 307     /**
 308      * Used for changing the size of the layout in response to a component's size.
 309      */
 310     public class SpringDimensionChecker extends ComponentAdapter {
 311         @Override
 312         public void componentResized(ComponentEvent e) {
 313             setSize(e.getComponent().getSize());
 314         }
 315     }
 316
 317     /**
 318      * This one is an incremental visualization
 319      */
 320     public boolean isIncremental() {
 321         return true;
 322     }
 323
 324     /**
 325      * For now, we pretend it never finishes.
 326      */
 327     public boolean done() {
 328         return false;
 329     }
 330
 331     /**
 332      * No effect.
 333      */
 334         public void reset() {
 335         }
 336 }