2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 * Created on Dec 4, 2003
12 package edu.uci.ics.jung.algorithms.layout;
14 import java.awt.Dimension;
15 import java.awt.geom.Point2D;
16 import java.util.Collection;
17 import java.util.HashMap;
20 import edu.uci.ics.jung.graph.Graph;
21 import edu.uci.ics.jung.graph.util.Pair;
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.
32 * @author John Yesberg
34 public class DAGLayout<V, E> extends SpringLayout<V,E> {
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
50 private Map<V,Number> minLevels = new HashMap<V,Number>();
51 // Simpler than the "pair" technique.
52 static int graphHeight;
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;
59 * A bunch of parameters to help work out when to stop quivering.
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.
66 final double MSV_THRESHOLD = 10.0;
68 boolean stoppingIncrements = false;
70 final int COOL_DOWN_INCREMENTS = 200;
73 * Creates an instance for the specified graph.
75 public DAGLayout(Graph<V,E> g) {
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.
84 public void setRoot(Graph<V,E> g) {
86 for(V v : g.getVertices()) {
87 Collection<V> successors = getGraph().getSuccessors(v);
88 if (successors.size() == 0) {
96 * Set vertex v to be level 0.
98 public void setRoot(V v) {
99 minLevels.put(v, new Integer(0));
100 // set all the levels.
101 propagateMinimumLevel(v);
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.
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);
117 oldLevel = o.intValue();
120 newLevel = Math.max(oldLevel, level + 1);
121 minLevels.put(child, new Integer(newLevel));
123 if (newLevel > graphHeight)
124 graphHeight = newLevel;
125 propagateMinimumLevel(child);
130 * Sets random locations for a vertex within the dimensions of the space.
131 * This overrides the method in AbstractLayout
136 private void initializeLocation(
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);
149 public void setSize(Dimension size) {
151 for(V v : getGraph().getVertices()) {
152 initializeLocation(v,transform(v),getSize());
157 * Had to override this one as well, to ensure that setRoot() is called.
160 public void initialize() {
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.
171 protected void moveNodes() {
172 // Dimension d = currentSize;
173 double oldMSV = meanSquareVel;
176 synchronized (getSize()) {
178 for(V v : getGraph().getVertices()) {
181 SpringLayout.SpringVertexData vd = springVertexData.get(v);
182 Point2D xyd = transform(v);
184 int width = getSize().width;
185 int height = getSize().height;
187 // (JY addition: three lines are new)
189 minLevels.get(v).intValue();
190 int minY = (int) (level * height / (graphHeight * SPACEFACTOR));
193 ? (int) (height / (graphHeight * SPACEFACTOR * 2))
196 // JY added 2* - double the sideways repulsion.
197 vd.dx += 2 * vd.repulsiondx + vd.edgedx;
198 vd.dy += vd.repulsiondy + vd.edgedy;
200 // JY Addition: Attract the vertex towards it's minimumLevel
202 double delta = xyd.getY() - minY;
203 vd.dy -= delta * LEVELATTRACTIONRATE;
205 vd.dy -= delta * LEVELATTRACTIONRATE;
206 // twice as much at the top.
209 meanSquareVel += (vd.dx * vd.dx + vd.dy * vd.dy);
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)) );
214 if (xyd.getX() < 0) {
215 xyd.setLocation(0, xyd.getY());
216 } else if (xyd.getX() > width) {
217 xyd.setLocation(width, xyd.getY());
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);
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());
235 //System.out.println("MeanSquareAccel="+meanSquareVel);
236 if (!stoppingIncrements
237 && Math.abs(meanSquareVel - oldMSV) < MSV_THRESHOLD) {
238 stoppingIncrements = true;
239 incrementsLeft = COOL_DOWN_INCREMENTS;
242 && Math.abs(meanSquareVel - oldMSV) <= MSV_THRESHOLD) {
244 if (incrementsLeft <= 0)
250 * Override incrementsAreDone so that we can eventually stop.
253 public boolean done() {
254 if (stoppingIncrements && incrementsLeft == 0)
261 * Override forceMove so that if someone moves a node, we can re-layout
265 public void setLocation(V picked, double x, double y) {
266 Point2D coord = transform(picked);
267 coord.setLocation(x,y);
268 stoppingIncrements = false;
272 * Override forceMove so that if someone moves a node, we can re-layout
276 public void setLocation(V picked, Point2D p) {
277 Point2D coord = transform(picked);
278 coord.setLocation(p);
279 stoppingIncrements = false;
283 * Overridden relaxEdges. This one reduces the effect of edges between
284 * greatly different levels.
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();
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);
302 minLevels.get(v1).intValue();
304 minLevels.get(v2).intValue();
306 // desiredLen *= Math.pow( 1.1, (v1.degree() + v2.degree()) );
307 // double desiredLen = getLength(e);
308 double desiredLen = lengthFunction.transform(e);
310 // round from zero, if needed [zero would be Bad.].
311 len = (len == 0) ? .0001 : len;
313 // force factor: optimal length minus actual length,
314 // is made smaller as the current actual length gets larger.
317 // System.out.println("Desired : " + getLength( e ));
318 double f = force_multiplier * (desiredLen - len) / len;
320 f = f * Math.pow(stretch / 100.0,
321 (getGraph().degree(v1) + getGraph().degree(v2) -2));
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);
328 // f= Math.min( 0, f );
330 // the actual movement distance 'dx' is the force multiplied by the
334 SpringVertexData v1D, v2D;
335 v1D = springVertexData.get(v1);
336 v2D = springVertexData.get(v2);
338 // SpringEdgeData<E> sed = getSpringEdgeData(e);