third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/FRLayout.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.map.LazyMap;
  17
  18 import java.awt.Dimension;
  19 import java.awt.geom.Point2D;
  20 import java.util.ConcurrentModificationException;
  21 import java.util.HashMap;
  22 import java.util.Map;
  23
  24 /**
  25  * Implements the Fruchterman-Reingold force-directed algorithm for node layout.
  26  *
  27  * <p>Behavior is determined by the following settable parameters:
  28  * <ul>
  29  * <li/>attraction multiplier: how much edges try to keep their vertices together
  30  * <li/>repulsion multiplier: how much vertices try to push each other apart
  31  * <li/>maximum iterations: how many iterations this algorithm will use before stopping
  32  * </ul>
  33  * Each of the first two defaults to 0.75; the maximum number of iterations defaults to 700.
  34  *
  35  * @see "Fruchterman and Reingold, 'Graph Drawing by Force-directed Placement'"
  36  * @see "http://i11www.ilkd.uni-karlsruhe.de/teaching/SS_04/visualisierung/papers/fruchterman91graph.pdf"
  37  * @author Scott White, Yan-Biao Boey, Danyel Fisher
  38  */
  39 public class FRLayout<V, E> extends AbstractLayout<V, E> implements IterativeContext {
  40
  41     private double forceConstant;
  42
  43     private double temperature;
  44
  45     private int currentIteration;
  46
  47     private int mMaxIterations = 700;
  48
  49     private Map<V, FRVertexData> frVertexData =
  50         LazyMap.decorate(new HashMap<V,FRVertexData>(), new Factory<FRVertexData>() {
  51                 public FRVertexData create() {
  52                         return new FRVertexData();
  53                 }});
  54
  55     private double attraction_multiplier = 0.75;
  56
  57     private double attraction_constant;
  58
  59     private double repulsion_multiplier = 0.75;
  60
  61     private double repulsion_constant;
  62
  63     private double max_dimension;
  64
  65     /**
  66      * Creates an instance for the specified graph.
  67      */
  68     public FRLayout(Graph<V, E> g) {
  69         super(g);
  70     }
  71
  72     /**
  73      * Creates an instance of size {@code d} for the specified graph.
  74      */
  75     public FRLayout(Graph<V, E> g, Dimension d) {
  76         super(g, new RandomLocationTransformer<V>(d), d);
  77         initialize();
  78         max_dimension = Math.max(d.height, d.width);
  79     }
  80
  81         @Override
  82         public void setSize(Dimension size) {
  83                 if(initialized == false) {
  84                         setInitializer(new RandomLocationTransformer<V>(size));
  85                 }
  86                 super.setSize(size);
  87         max_dimension = Math.max(size.height, size.width);
  88         }
  89
  90         /**
  91          * Sets the attraction multiplier.
  92          */
  93         public void setAttractionMultiplier(double attraction) {
  94         this.attraction_multiplier = attraction;
  95     }
  96
  97         /**
  98          * Sets the repulsion multiplier.
  99          */
 100     public void setRepulsionMultiplier(double repulsion) {
 101         this.repulsion_multiplier = repulsion;
 102     }
 103
 104         public void reset() {
 105                 doInit();
 106         }
 107
 108     public void initialize() {
 109         doInit();
 110     }
 111
 112     private void doInit() {
 113         Graph<V,E> graph = getGraph();
 114         Dimension d = getSize();
 115         if(graph != null && d != null) {
 116                 currentIteration = 0;
 117                 temperature = d.getWidth() / 10;
 118
 119                 forceConstant =
 120                         Math
 121                         .sqrt(d.getHeight()
 122                                         * d.getWidth()
 123                                         / graph.getVertexCount());
 124
 125                 attraction_constant = attraction_multiplier * forceConstant;
 126                 repulsion_constant = repulsion_multiplier * forceConstant;
 127         }
 128     }
 129
 130     private double EPSILON = 0.000001D;
 131
 132     /**
 133      * Moves the iteration forward one notch, calculation attraction and
 134      * repulsion between vertices and edges and cooling the temperature.
 135      */
 136     public synchronized void step() {
 137         currentIteration++;
 138
 139         /**
 140          * Calculate repulsion
 141          */
 142         while(true) {
 143
 144             try {
 145                 for(V v1 : getGraph().getVertices()) {
 146                     calcRepulsion(v1);
 147                 }
 148                 break;
 149             } catch(ConcurrentModificationException cme) {}
 150         }
 151
 152         /**
 153          * Calculate attraction
 154          */
 155         while(true) {
 156             try {
 157                 for(E e : getGraph().getEdges()) {
 158
 159                     calcAttraction(e);
 160                 }
 161                 break;
 162             } catch(ConcurrentModificationException cme) {}
 163         }
 164
 165
 166         while(true) {
 167             try {
 168                 for(V v : getGraph().getVertices()) {
 169                     if (isLocked(v)) continue;
 170                     calcPositions(v);
 171                 }
 172                 break;
 173             } catch(ConcurrentModificationException cme) {}
 174         }
 175         cool();
 176     }
 177
 178     protected synchronized void calcPositions(V v) {
 179         FRVertexData fvd = getFRData(v);
 180         if(fvd == null) return;
 181         Point2D xyd = transform(v);
 182         double deltaLength = Math.max(EPSILON, fvd.norm());
 183
 184         double newXDisp = fvd.getX() / deltaLength
 185                 * Math.min(deltaLength, temperature);
 186
 187         if (Double.isNaN(newXDisp)) {
 188                 throw new IllegalArgumentException(
 189                 "Unexpected mathematical result in FRLayout:calcPositions [xdisp]"); }
 190
 191         double newYDisp = fvd.getY() / deltaLength
 192                 * Math.min(deltaLength, temperature);
 193         xyd.setLocation(xyd.getX()+newXDisp, xyd.getY()+newYDisp);
 194
 195         double borderWidth = getSize().getWidth() / 50.0;
 196         double newXPos = xyd.getX();
 197         if (newXPos < borderWidth) {
 198             newXPos = borderWidth + Math.random() * borderWidth * 2.0;
 199         } else if (newXPos > (getSize().getWidth() - borderWidth)) {
 200             newXPos = getSize().getWidth() - borderWidth - Math.random()
 201                     * borderWidth * 2.0;
 202         }
 203
 204         double newYPos = xyd.getY();
 205         if (newYPos < borderWidth) {
 206             newYPos = borderWidth + Math.random() * borderWidth * 2.0;
 207         } else if (newYPos > (getSize().getHeight() - borderWidth)) {
 208             newYPos = getSize().getHeight() - borderWidth
 209                     - Math.random() * borderWidth * 2.0;
 210         }
 211
 212         xyd.setLocation(newXPos, newYPos);
 213     }
 214
 215     protected void calcAttraction(E e) {
 216         Pair<V> endpoints = getGraph().getEndpoints(e);
 217         V v1 = endpoints.getFirst();
 218         V v2 = endpoints.getSecond();
 219         boolean v1_locked = isLocked(v1);
 220         boolean v2_locked = isLocked(v2);
 221
 222         if(v1_locked && v2_locked) {
 223                 // both locked, do nothing
 224                 return;
 225         }
 226         Point2D p1 = transform(v1);
 227         Point2D p2 = transform(v2);
 228         if(p1 == null || p2 == null) return;
 229         double xDelta = p1.getX() - p2.getX();
 230         double yDelta = p1.getY() - p2.getY();
 231
 232         double deltaLength = Math.max(EPSILON, Math.sqrt((xDelta * xDelta)
 233                 + (yDelta * yDelta)));
 234
 235         double force = (deltaLength * deltaLength) / attraction_constant;
 236
 237         if (Double.isNaN(force)) { throw new IllegalArgumentException(
 238                 "Unexpected mathematical result in FRLayout:calcPositions [force]"); }
 239
 240         double dx = (xDelta / deltaLength) * force;
 241         double dy = (yDelta / deltaLength) * force;
 242         if(v1_locked == false) {
 243                 FRVertexData fvd1 = getFRData(v1);
 244                 fvd1.offset(-dx, -dy);
 245         }
 246         if(v2_locked == false) {
 247                 FRVertexData fvd2 = getFRData(v2);
 248                 fvd2.offset(dx, dy);
 249         }
 250     }
 251
 252     protected void calcRepulsion(V v1) {
 253         FRVertexData fvd1 = getFRData(v1);
 254         if(fvd1 == null)
 255             return;
 256         fvd1.setLocation(0, 0);
 257
 258         try {
 259             for(V v2 : getGraph().getVertices()) {
 260
 261 //                if (isLocked(v2)) continue;
 262                 if (v1 != v2) {
 263                     Point2D p1 = transform(v1);
 264                     Point2D p2 = transform(v2);
 265                     if(p1 == null || p2 == null) continue;
 266                     double xDelta = p1.getX() - p2.getX();
 267                     double yDelta = p1.getY() - p2.getY();
 268
 269                     double deltaLength = Math.max(EPSILON, Math
 270                             .sqrt((xDelta * xDelta) + (yDelta * yDelta)));
 271
 272                     double force = (repulsion_constant * repulsion_constant) / deltaLength;
 273
 274                     if (Double.isNaN(force)) { throw new RuntimeException(
 275                     "Unexpected mathematical result in FRLayout:calcPositions [repulsion]"); }
 276
 277                     fvd1.offset((xDelta / deltaLength) * force,
 278                             (yDelta / deltaLength) * force);
 279                 }
 280             }
 281         } catch(ConcurrentModificationException cme) {
 282             calcRepulsion(v1);
 283         }
 284     }
 285
 286     private void cool() {
 287         temperature *= (1.0 - currentIteration / (double) mMaxIterations);
 288     }
 289
 290     /**
 291      * Sets the maximum number of iterations.
 292      */
 293     public void setMaxIterations(int maxIterations) {
 294         mMaxIterations = maxIterations;
 295     }
 296
 297     protected FRVertexData getFRData(V v) {
 298         return frVertexData.get(v);
 299     }
 300
 301     /**
 302      * This one is an incremental visualization.
 303      */
 304     public boolean isIncremental() {
 305         return true;
 306     }
 307
 308     /**
 309      * Returns true once the current iteration has passed the maximum count,
 310      * <tt>MAX_ITERATIONS</tt>.
 311      */
 312     public boolean done() {
 313         if (currentIteration > mMaxIterations || temperature < 1.0/max_dimension)
 314         {
 315             return true;
 316         }
 317         return false;
 318     }
 319
 320     protected static class FRVertexData extends Point2D.Double
 321     {
 322         protected void offset(double x, double y)
 323         {
 324             this.x += x;
 325             this.y += y;
 326         }
 327
 328         protected double norm()
 329         {
 330             return Math.sqrt(x*x + y*y);
 331         }
 332      }
 333 }