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