third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/layout/DAGLayout.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  * Created on Dec 4, 2003
  11  */
  12 package edu.uci.ics.jung.algorithms.layout;
  13
  14 import java.awt.Dimension;
  15 import java.awt.geom.Point2D;
  16 import java.util.Collection;
  17 import java.util.HashMap;
  18 import java.util.Map;
  19
  20 import edu.uci.ics.jung.graph.Graph;
  21 import edu.uci.ics.jung.graph.util.Pair;
  22
  23 /**
  24  * An implementation of {@code Layout} suitable for tree-like directed
  25  * acyclic graphs. Parts of it will probably not terminate if the graph is
  26  * cyclic! The layout will result in directed edges pointing generally upwards.
  27  * Any vertices with no successors are considered to be level 0, and tend
  28  * towards the top of the layout. Any vertex has a level one greater than the
  29  * maximum level of all its successors.
  30  *
  31  *
  32  * @author John Yesberg
  33  */
  34 public class DAGLayout<V, E> extends SpringLayout<V,E> {
  35
  36     /**
  37      * Each vertex has a minimumLevel. Any vertex with no successors has
  38      * minimumLevel of zero. The minimumLevel of any vertex must be strictly
  39      * greater than the minimumLevel of its parents. (Vertex A is a parent of
  40      * Vertex B iff there is an edge from B to A.) Typically, a vertex will
  41      * have a minimumLevel which is one greater than the minimumLevel of its
  42      * parent's. However, if the vertex has two parents, its minimumLevel will
  43      * be one greater than the maximum of the parents'. We need to calculate
  44      * the minimumLevel for each vertex. When we layout the graph, vertices
  45      * cannot be drawn any higher than the minimumLevel. The graphHeight of a
  46      * graph is the greatest minimumLevel that is used. We will modify the
  47      * SpringLayout calculations so that nodes cannot move above their assigned
  48      * minimumLevel.
  49      */
  50         private Map<V,Number> minLevels = new HashMap<V,Number>();
  51         // Simpler than the "pair" technique.
  52         static int graphHeight;
  53         static int numRoots;
  54         final double SPACEFACTOR = 1.3;
  55         // How much space do we allow for additional floating at the bottom.
  56         final double LEVELATTRACTIONRATE = 0.8;
  57
  58         /**
  59          * A bunch of parameters to help work out when to stop quivering.
  60          *
  61          * If the MeanSquareVel(ocity) ever gets below the MSV_THRESHOLD, then we
  62          * will start a final cool-down phase of COOL_DOWN_INCREMENT increments. If
  63          * the MeanSquareVel ever exceeds the threshold, we will exit the cool down
  64          * phase, and continue looking for another opportunity.
  65          */
  66         final double MSV_THRESHOLD = 10.0;
  67         double meanSquareVel;
  68         boolean stoppingIncrements = false;
  69         int incrementsLeft;
  70         final int COOL_DOWN_INCREMENTS = 200;
  71
  72         /**
  73          * Creates an instance for the specified graph.
  74          */
  75         public DAGLayout(Graph<V,E> g) {
  76                 super(g);
  77         }
  78
  79         /**
  80          * setRoot calculates the level of each vertex in the graph. Level 0 is
  81          * allocated to any vertex with no successors. Level n+1 is allocated to
  82          * any vertex whose successors' maximum level is n.
  83          */
  84         public void setRoot(Graph<V,E> g) {
  85                 numRoots = 0;
  86                 for(V v : g.getVertices()) {
  87                         Collection<V> successors = getGraph().getSuccessors(v);
  88                         if (successors.size() == 0) {
  89                                 setRoot(v);
  90                                 numRoots++;
  91                         }
  92                 }
  93         }
  94
  95         /**
  96          * Set vertex v to be level 0.
  97          */
  98         public void setRoot(V v) {
  99                 minLevels.put(v, new Integer(0));
 100                 // set all the levels.
 101                 propagateMinimumLevel(v);
 102         }
 103
 104         /**
 105          * A recursive method for allocating the level for each vertex. Ensures
 106          * that all predecessors of v have a level which is at least one greater
 107          * than the level of v.
 108          *
 109          * @param v
 110          */
 111         public void propagateMinimumLevel(V v) {
 112                 int level = minLevels.get(v).intValue();
 113                 for(V child : getGraph().getPredecessors(v)) {
 114                         int oldLevel, newLevel;
 115                         Number o = minLevels.get(child);
 116                         if (o != null)
 117                                 oldLevel = o.intValue();
 118                         else
 119                                 oldLevel = 0;
 120                         newLevel = Math.max(oldLevel, level + 1);
 121                         minLevels.put(child, new Integer(newLevel));
 122
 123                         if (newLevel > graphHeight)
 124                                 graphHeight = newLevel;
 125                         propagateMinimumLevel(child);
 126                 }
 127         }
 128
 129         /**
 130          * Sets random locations for a vertex within the dimensions of the space.
 131          * This overrides the method in AbstractLayout
 132          *
 133          * @param coord
 134          * @param d
 135          */
 136         private void initializeLocation(
 137                 V v,
 138                 Point2D coord,
 139                 Dimension d) {
 140
 141                 int level = minLevels.get(v).intValue();
 142                 int minY = (int) (level * d.getHeight() / (graphHeight * SPACEFACTOR));
 143                 double x = Math.random() * d.getWidth();
 144                 double y = Math.random() * (d.getHeight() - minY) + minY;
 145                 coord.setLocation(x,y);
 146         }
 147
 148         @Override
 149         public void setSize(Dimension size) {
 150                 super.setSize(size);
 151                 for(V v : getGraph().getVertices()) {
 152                         initializeLocation(v,transform(v),getSize());
 153                 }
 154         }
 155
 156         /**
 157          * Had to override this one as well, to ensure that setRoot() is called.
 158          */
 159         @Override
 160         public void initialize() {
 161                 super.initialize();
 162                 setRoot(getGraph());
 163         }
 164
 165         /**
 166          * Override the moveNodes() method from SpringLayout. The only change we
 167          * need to make is to make sure that nodes don't float higher than the minY
 168          * coordinate, as calculated by their minimumLevel.
 169          */
 170         @Override
 171         protected void moveNodes() {
 172                 // Dimension d = currentSize;
 173                 double oldMSV = meanSquareVel;
 174                 meanSquareVel = 0;
 175
 176                 synchronized (getSize()) {
 177
 178                         for(V v : getGraph().getVertices()) {
 179                                 if (isLocked(v))
 180                                         continue;
 181                                 SpringLayout.SpringVertexData vd = springVertexData.get(v);
 182                                 Point2D xyd = transform(v);
 183
 184                                 int width = getSize().width;
 185                                 int height = getSize().height;
 186
 187                                 // (JY addition: three lines are new)
 188                                 int level =
 189                                         minLevels.get(v).intValue();
 190                                 int minY = (int) (level * height / (graphHeight * SPACEFACTOR));
 191                                 int maxY =
 192                                         level == 0
 193                                                 ? (int) (height / (graphHeight * SPACEFACTOR * 2))
 194                                                 : height;
 195
 196                                 // JY added 2* - double the sideways repulsion.
 197                                 vd.dx += 2 * vd.repulsiondx + vd.edgedx;
 198                                 vd.dy += vd.repulsiondy + vd.edgedy;
 199
 200                                 // JY Addition: Attract the vertex towards it's minimumLevel
 201                                 // height.
 202                                 double delta = xyd.getY() - minY;
 203                                 vd.dy -= delta * LEVELATTRACTIONRATE;
 204                                 if (level == 0)
 205                                         vd.dy -= delta * LEVELATTRACTIONRATE;
 206                                 // twice as much at the top.
 207
 208                                 // JY addition:
 209                                 meanSquareVel += (vd.dx * vd.dx + vd.dy * vd.dy);
 210
 211                                 // keeps nodes from moving any faster than 5 per time unit
 212                                 xyd.setLocation(xyd.getX()+Math.max(-5, Math.min(5, vd.dx)) , xyd.getY()+Math.max(-5, Math.min(5, vd.dy)) );
 213
 214                                 if (xyd.getX() < 0) {
 215                                         xyd.setLocation(0, xyd.getY());
 216                                 } else if (xyd.getX() > width) {
 217                                         xyd.setLocation(width, xyd.getY());
 218                                 }
 219
 220                                 // (JY addition: These two lines replaced 0 with minY)
 221                                 if (xyd.getY() < minY) {
 222                                         xyd.setLocation(xyd.getX(), minY);
 223                                         // (JY addition: replace height with maxY)
 224                                 } else if (xyd.getY() > maxY) {
 225                                         xyd.setLocation(xyd.getX(), maxY);
 226                                 }
 227
 228                                 // (JY addition: if there's only one root, anchor it in the
 229                                 // middle-top of the screen)
 230                                 if (numRoots == 1 && level == 0) {
 231                                         xyd.setLocation(width/2, xyd.getY());
 232                                 }
 233                         }
 234                 }
 235                 //System.out.println("MeanSquareAccel="+meanSquareVel);
 236                 if (!stoppingIncrements
 237                         && Math.abs(meanSquareVel - oldMSV) < MSV_THRESHOLD) {
 238                         stoppingIncrements = true;
 239                         incrementsLeft = COOL_DOWN_INCREMENTS;
 240                 } else if (
 241                         stoppingIncrements
 242                                 && Math.abs(meanSquareVel - oldMSV) <= MSV_THRESHOLD) {
 243                         incrementsLeft--;
 244                         if (incrementsLeft <= 0)
 245                                 incrementsLeft = 0;
 246                 }
 247         }
 248
 249         /**
 250          * Override incrementsAreDone so that we can eventually stop.
 251          */
 252         @Override
 253         public boolean done() {
 254                 if (stoppingIncrements && incrementsLeft == 0)
 255                         return true;
 256                 else
 257                         return false;
 258         }
 259
 260         /**
 261          * Override forceMove so that if someone moves a node, we can re-layout
 262          * everything.
 263          */
 264         @Override
 265         public void setLocation(V picked, double x, double y) {
 266                 Point2D coord = transform(picked);
 267                 coord.setLocation(x,y);
 268                 stoppingIncrements = false;
 269         }
 270
 271         /**
 272          * Override forceMove so that if someone moves a node, we can re-layout
 273          * everything.
 274          */
 275         @Override
 276         public void setLocation(V picked, Point2D p) {
 277                 Point2D coord = transform(picked);
 278                 coord.setLocation(p);
 279                 stoppingIncrements = false;
 280         }
 281
 282         /**
 283          * Overridden relaxEdges. This one reduces the effect of edges between
 284          * greatly different levels.
 285          *
 286          */
 287         @Override
 288         protected void relaxEdges() {
 289                 for(E e : getGraph().getEdges()) {
 290                     Pair<V> endpoints = getGraph().getEndpoints(e);
 291                         V v1 = endpoints.getFirst();
 292                         V v2 = endpoints.getSecond();
 293
 294                         Point2D p1 = transform(v1);
 295                         Point2D p2 = transform(v2);
 296                         double vx = p1.getX() - p2.getX();
 297                         double vy = p1.getY() - p2.getY();
 298                         double len = Math.sqrt(vx * vx + vy * vy);
 299
 300                         // JY addition.
 301                         int level1 =
 302                                 minLevels.get(v1).intValue();
 303                         int level2 =
 304                                 minLevels.get(v2).intValue();
 305
 306                         // desiredLen *= Math.pow( 1.1, (v1.degree() + v2.degree()) );
 307 //          double desiredLen = getLength(e);
 308                         double desiredLen = lengthFunction.transform(e);
 309
 310                         // round from zero, if needed [zero would be Bad.].
 311                         len = (len == 0) ? .0001 : len;
 312
 313                         // force factor: optimal length minus actual length,
 314                         // is made smaller as the current actual length gets larger.
 315                         // why?
 316
 317                         // System.out.println("Desired : " + getLength( e ));
 318                         double f = force_multiplier * (desiredLen - len) / len;
 319
 320                         f = f * Math.pow(stretch / 100.0,
 321                                         (getGraph().degree(v1) + getGraph().degree(v2) -2));
 322
 323                         // JY addition. If this is an edge which stretches a long way,
 324                         // don't be so concerned about it.
 325                         if (level1 != level2)
 326                                 f = f / Math.pow(Math.abs(level2 - level1), 1.5);
 327
 328                         // f= Math.min( 0, f );
 329
 330                         // the actual movement distance 'dx' is the force multiplied by the
 331                         // distance to go.
 332                         double dx = f * vx;
 333                         double dy = f * vy;
 334                         SpringVertexData v1D, v2D;
 335                         v1D = springVertexData.get(v1);
 336                         v2D = springVertexData.get(v2);
 337
 338 //                      SpringEdgeData<E> sed = getSpringEdgeData(e);
 339 //                      sed.f = f;
 340
 341                         v1D.edgedx += dx;
 342                         v1D.edgedy += dy;
 343                         v2D.edgedx += -dx;
 344                         v2D.edgedy += -dy;
 345                 }
 346         }
 347 }