Coverage details for edu.uci.ics.jung.visualization.contrib.DAGLayout

LineHitsSource
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 /*
11  * Created on Dec 4, 2003
12  */
13 package edu.uci.ics.jung.visualization.contrib;
14  
15 /**
16  * @author danyelf
17  */
18 /*
19  * Created on 4/12/2003
20  *
21  */
22  
23 import java.awt.Dimension;
24 import java.awt.geom.Point2D;
25 import java.util.Iterator;
26 import java.util.Set;
27  
28 import edu.uci.ics.jung.graph.Edge;
29 import edu.uci.ics.jung.graph.Graph;
30 import edu.uci.ics.jung.graph.Vertex;
31 import edu.uci.ics.jung.utils.UserData;
32 import edu.uci.ics.jung.visualization.Coordinates;
33 import edu.uci.ics.jung.visualization.SpringLayout;
34  
35 /**
36  * @author John Yesberg
37  *
38  * DAGLayout is a layout algorithm which is suitable for tree-like directed
39  * acyclic graphs. Parts of it will probably not terminate if the graph is
40  * cyclic! The layout will result in directed edges pointing generally upwards.
41  * Any vertices with no successors are considered to be level 0, and tend
42  * towards the top of the layout. Any vertex has a level one greater than the
43  * maximum level of all its successors.
44  *
45  * Note: had to make minor access changes to SpringLayout to make this work.
46  * FORCE_CONSTANT, LengthFunction, SpringVertexData, and SpringEdgeData were
47  * all made "protected".
48  */
49 public class DAGLayout extends SpringLayout {
50  
51     protected static final String MINIMUMLEVELKEY = "DAGLayout.minimumLevel";
52     // Simpler than the "pair" technique.
53     static int graphHeight;
54     static int numRoots;
550    final double SPACEFACTOR = 1.3;
56     // How much space do we allow for additional floating at the bottom.
570    final double LEVELATTRACTIONRATE = 0.8;
58  
59     /*
60      * A bunch of parameters to help work out when to stop quivering.
61      *
62      * If the MeanSquareVel(ocity) ever gets below the MSV_THRESHOLD, then we
63      * will start a final cool-down phase of COOL_DOWN_INCREMENT increments. If
64      * the MeanSquareVel ever exceeds the threshold, we will exit the cool down
65      * phase, and continue looking for another opportunity.
66      */
670    final double MSV_THRESHOLD = 10.0;
68     static double meanSquareVel;
690    static boolean stoppingIncrements = false;
70     static int incrementsLeft;
710    final int COOL_DOWN_INCREMENTS = 200;
72     /*
73      * @param g
74      */
75     public DAGLayout(Graph g) {
760        super(g);
770    }
78  
79     /*
80      * Each vertex has a minimumLevel. Any vertex with no successors has
81      * minimumLevel of zero. The minimumLevel of any vertex must be strictly
82      * greater than the minimumLevel of its parents. (Vertex A is a parent of
83      * Vertex B iff there is an edge from B to A.) Typically, a vertex will
84      * have a minimumLevel which is one greater than the minimumLevel of its
85      * parent's. However, if the vertex has two parents, its minimumLevel will
86      * be one greater than the maximum of the parents'. We need to calculate
87      * the minimumLevel for each vertex. When we layout the graph, vertices
88      * cannot be drawn any higher than the minimumLevel. The graphHeight of a
89      * graph is the greatest minimumLevel that is used. We will modify the
90      * SpringLayout calculations so that nodes cannot move above their assigned
91      * minimumLevel.
92      */
93  
94     /**
95      * setRoot calculates the level of each vertex in the graph. Level 0 is
96      * allocated to any vertex with no successors. Level n+1 is allocated to
97      * any vertex whose successors' maximum level is n.
98      */
99  
100     public static void setRoot(Graph g) {
1010        numRoots = 0;
1020        Set verts = g.getVertices();
1030        Iterator iter = verts.iterator();
104         Vertex v;
105         Set successors;
1060        while (iter.hasNext()) {
1070            v = (Vertex) iter.next();
1080            successors = v.getSuccessors();
1090            if (successors.size() == 0) {
1100                setRoot(v);
1110                numRoots++;
112             }
113         }
1140    }
115  
116     /**
117      * Set vertex v to be level 0.
118      */
119  
120     public static void setRoot(Vertex v) {
1210        v.setUserDatum(MINIMUMLEVELKEY, new Integer(0), UserData.REMOVE);
122         //
123         // Iterate through now, setting all the levels.
1240        propagateMinimumLevel(v);
1250    }
126  
127     /**
128      * A recursive method for allocating the level for each vertex. Ensures
129      * that all predecessors of v have a level which is at least one greater
130      * than the level of v.
131      *
132      * @param v
133      */
134  
135     public static void propagateMinimumLevel(Vertex v) {
1360        int level = ((Integer) v.getUserDatum(MINIMUMLEVELKEY)).intValue();
1370        Set predecessors = v.getPredecessors();
1380        Iterator iter = predecessors.iterator();
139         Vertex child; // odd to use predecessors for child, isn't it. Sorry!
1400        while (iter.hasNext()) {
1410            child = (Vertex) iter.next();
142             int oldLevel, newLevel;
1430            Object o = child.getUserDatum(MINIMUMLEVELKEY);
1440            if (o != null)
1450                oldLevel = ((Integer) o).intValue();
146             else
1470                oldLevel = 0;
1480            newLevel = Math.max(oldLevel, level + 1);
1490            child.setUserDatum(
150                 MINIMUMLEVELKEY,
151                 new Integer(newLevel),
152                 UserData.REMOVE);
1530            if (newLevel > graphHeight)
1540                graphHeight = newLevel;
1550            propagateMinimumLevel(child);
156         }
1570    }
158  
159     /**
160      * Sets random locations for a vertex within the dimensions of the space.
161      * This overrides the method in AbstractLayout
162      *
163      * @param coord
164      * @param d
165      */
166     protected void initializeLocation(
167         Vertex v,
168         Coordinates coord,
169         Dimension d) {
170         //if (v.getUserDatum(MINIMUMLEVELKEY)==null) setRoot(getGraph());
1710        int level = ((Integer) v.getUserDatum(MINIMUMLEVELKEY)).intValue();
1720        int minY = (int) (level * d.getHeight() / (graphHeight * SPACEFACTOR));
1730        double x = Math.random() * d.getWidth();
1740        double y = Math.random() * (d.getHeight() - minY) + minY;
1750        coord.setX(x);
1760        coord.setY(y);
1770    }
178  
179     /**
180      * Had to override this one as well, to ensure that setRoot() is called.
181      */
182     protected void initialize_local() {
1830        for (Iterator iter = getGraph().getEdges().iterator();
1840            iter.hasNext();
185             ) {
1860            Edge e = (Edge) iter.next();
1870            SpringEdgeData sed = getSpringData(e);
1880            if (sed == null) {
1890                sed = new SpringEdgeData(e);
1900                e.addUserDatum(getSpringKey(), sed, UserData.REMOVE);
191             }
1920            calcEdgeLength(sed, lengthFunction);
193         }
1940        setRoot(getGraph());
1950    }
196  
197     /**
198      * Override the moveNodes() method from SpringLayout. The only change we
199      * need to make is to make sure that nodes don't float higher than the minY
200      * coordinate, as calculated by their minimumLevel.
201      */
202     protected void moveNodes() {
203         // Dimension d = currentSize;
2040        double oldMSV = meanSquareVel;
2050        meanSquareVel = 0;
206  
2070        synchronized (getCurrentSize()) {
208  
209             // int showingNodes = 0;
210  
2110            for (Iterator i = getVisibleVertices().iterator(); i.hasNext();) {
2120                Vertex v = (Vertex) i.next();
2130                if (isLocked(v))
2140                    continue;
2150                SpringLayout.SpringVertexData vd = getSpringData(v);
2160                Coordinates xyd = getCoordinates(v);
217  
2180                int width = getCurrentSize().width;
2190                int height = getCurrentSize().height;
220  
221                 // (JY addition: three lines are new)
2220                int level =
223                     ((Integer) v.getUserDatum(MINIMUMLEVELKEY)).intValue();
2240                int minY = (int) (level * height / (graphHeight * SPACEFACTOR));
2250                int maxY =
226                     level == 0
227                         ? (int) (height / (graphHeight * SPACEFACTOR * 2))
228                         : height;
229  
230                 // JY added 2* - double the sideways repulsion.
2310                vd.dx += 2 * vd.repulsiondx + vd.edgedx;
2320                vd.dy += vd.repulsiondy + vd.edgedy;
233  
234                 // JY Addition: Attract the vertex towards it's minimumLevel
235                 // height.
2360                double delta = xyd.getY() - minY;
2370                vd.dy -= delta * LEVELATTRACTIONRATE;
2380                if (level == 0)
2390                    vd.dy -= delta * LEVELATTRACTIONRATE;
240                 // twice as much at the top.
241  
242                 // JY addition:
2430                meanSquareVel += (vd.dx * vd.dx + vd.dy * vd.dy);
244  
245                 // keeps nodes from moving any faster than 5 per time unit
2460                xyd.addX(Math.max(-5, Math.min(5, vd.dx)));
2470                xyd.addY(Math.max(-5, Math.min(5, vd.dy)));
248  
2490                if (xyd.getX() < 0) {
2500                    xyd.setX(0);
2510                } else if (xyd.getX() > width) {
2520                    xyd.setX(width);
253                 }
254  
255                 // (JY addition: These two lines replaced 0 with minY)
2560                if (xyd.getY() < minY) {
2570                    xyd.setY(minY);
258                     // (JY addition: replace height with maxY)
2590                } else if (xyd.getY() > maxY) {
2600                    xyd.setY(maxY);
261                 }
262  
263                 // (JY addition: if there's only one root, anchor it in the
264                 // middle-top of the screen)
2650                if (numRoots == 1 && level == 0) {
2660                    xyd.setX(width / 2);
267                     //xyd.setY(0);
268                 }
269  
270             }
2710        }
272         //System.out.println("MeanSquareAccel="+meanSquareVel);
2730        if (!stoppingIncrements
274             && Math.abs(meanSquareVel - oldMSV) < MSV_THRESHOLD) {
2750            stoppingIncrements = true;
2760            incrementsLeft = COOL_DOWN_INCREMENTS;
2770        } else if (
278             stoppingIncrements
279                 && Math.abs(meanSquareVel - oldMSV) <= MSV_THRESHOLD) {
2800            incrementsLeft--;
2810            if (incrementsLeft <= 0)
2820                incrementsLeft = 0;
283         }
2840    }
285  
286     /**
287      * Override incrementsAreDone so that we can eventually stop.
288      */
289     public boolean incrementsAreDone() {
2900        if (stoppingIncrements && incrementsLeft == 0)
2910            return true;
292         else
2930            return false;
294     }
295  
296     /**
297      * Override forceMove so that if someone moves a node, we can re-layout
298      * everything.
299      */
300     public void forceMove(Vertex picked, int x, int y) {
3010        Coordinates coord = getCoordinates(picked);
3020        coord.setX(x);
3030        coord.setY(y);
3040        stoppingIncrements = false;
3050    }
306  
307     /**
308      * Overridden relaxEdges. This one reduces the effect of edges between
309      * greatly different levels.
310      *
311      */
312  
313     protected void relaxEdges() {
3140        for (Iterator i = getVisibleEdges().iterator(); i.hasNext();) {
3150            Edge e = (Edge) i.next();
316  
3170            Vertex v1 = getAVertex(e);
3180            Vertex v2 = e.getOpposite(v1);
319  
3200            Point2D p1 = getLocation(v1);
3210            Point2D p2 = getLocation(v2);
3220            double vx = p1.getX() - p2.getX();
3230            double vy = p1.getY() - p2.getY();
3240            double len = Math.sqrt(vx * vx + vy * vy);
325  
326             // JY addition.
3270            int level1 =
328                 ((Integer) v1.getUserDatum(MINIMUMLEVELKEY)).intValue();
3290            int level2 =
330                 ((Integer) v2.getUserDatum(MINIMUMLEVELKEY)).intValue();
331  
3320            double desiredLen = getLength(e);
333             // desiredLen *= Math.pow( 1.1, (v1.degree() + v2.degree()) );
334  
335             // round from zero, if needed [zero would be Bad.].
3360            len = (len == 0) ? .0001 : len;
337  
338             // force factor: optimal length minus actual length,
339             // is made smaller as the current actual length gets larger.
340             // why?
341  
342             // System.out.println("Desired : " + getLength( e ));
3430            double f = force_multiplier * (desiredLen - len) / len;
344  
3450            f = f * Math.pow(stretch / 100.0, (v1.degree() + v2.degree() - 2));
346  
347             // JY addition. If this is an edge which stretches a long way,
348             // don't be so concerned about it.
3490            if (level1 != level2)
3500                f = f / Math.pow(Math.abs(level2 - level1), 1.5);
351  
352             // f= Math.min( 0, f );
353  
354             // the actual movement distance 'dx' is the force multiplied by the
355             // distance to go.
3560            double dx = f * vx;
3570            double dy = f * vy;
358             SpringVertexData v1D, v2D;
3590            v1D = getSpringData(v1);
3600            v2D = getSpringData(v2);
361  
3620            SpringEdgeData sed = getSpringData(e);
3630            sed.f = f;
364  
3650            v1D.edgedx += dx;
3660            v1D.edgedy += dy;
3670            v2D.edgedx += -dx;
3680            v2D.edgedy += -dy;
369         }
3700    }
371  
372 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.