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

Line | Hits | Source
--- | --- | ---
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;`
55 | 0 | `final double SPACEFACTOR = 1.3;`
56 |  | `// How much space do we allow for additional floating at the bottom.`
57 | 0 | `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 |  | `*/`
67 | 0 | `final double MSV_THRESHOLD = 10.0;`
68 |  | `static double meanSquareVel;`
69 | 0 | `static boolean stoppingIncrements = false;`
70 |  | `static int incrementsLeft;`
71 | 0 | `final int COOL_DOWN_INCREMENTS = 200;`
72 |  | `/*`
73 |  | `* @param g`
74 |  | `*/`
75 |  | `public DAGLayout(Graph g) {`
76 | 0 | `super(g);`
77 | 0 | `}`
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) {`
101 | 0 | `numRoots = 0;`
102 | 0 | `Set verts = g.getVertices();`
103 | 0 | `Iterator iter = verts.iterator();`
104 |  | `Vertex v;`
105 |  | `Set successors;`
106 | 0 | `while (iter.hasNext()) {`
107 | 0 | `v = (Vertex) iter.next();`
108 | 0 | `successors = v.getSuccessors();`
109 | 0 | `if (successors.size() == 0) {`
110 | 0 | `setRoot(v);`
111 | 0 | `numRoots++;`
112 |  | `}`
113 |  | `}`
114 | 0 | `}`
115 |  | ``
116 |  | `/**`
117 |  | `* Set vertex v to be level 0.`
118 |  | `*/`
119 |  | ``
120 |  | `public static void setRoot(Vertex v) {`
121 | 0 | `v.setUserDatum(MINIMUMLEVELKEY, new Integer(0), UserData.REMOVE);`
122 |  | `//`
123 |  | `// Iterate through now, setting all the levels.`
124 | 0 | `propagateMinimumLevel(v);`
125 | 0 | `}`
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) {`
136 | 0 | `int level = ((Integer) v.getUserDatum(MINIMUMLEVELKEY)).intValue();`
137 | 0 | `Set predecessors = v.getPredecessors();`
138 | 0 | `Iterator iter = predecessors.iterator();`
139 |  | `Vertex child; // odd to use predecessors for child, isn't it. Sorry!`
140 | 0 | `while (iter.hasNext()) {`
141 | 0 | `child = (Vertex) iter.next();`
142 |  | `int oldLevel, newLevel;`
143 | 0 | `Object o = child.getUserDatum(MINIMUMLEVELKEY);`
144 | 0 | `if (o != null)`
145 | 0 | `oldLevel = ((Integer) o).intValue();`
146 |  | `else`
147 | 0 | `oldLevel = 0;`
148 | 0 | `newLevel = Math.max(oldLevel, level + 1);`
149 | 0 | `child.setUserDatum(`
150 |  | `MINIMUMLEVELKEY,`
151 |  | `new Integer(newLevel),`
152 |  | `UserData.REMOVE);`
153 | 0 | `if (newLevel > graphHeight)`
154 | 0 | `graphHeight = newLevel;`
155 | 0 | `propagateMinimumLevel(child);`
156 |  | `}`
157 | 0 | `}`
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());`
171 | 0 | `int level = ((Integer) v.getUserDatum(MINIMUMLEVELKEY)).intValue();`
172 | 0 | `int minY = (int) (level * d.getHeight() / (graphHeight * SPACEFACTOR));`
173 | 0 | `double x = Math.random() * d.getWidth();`
174 | 0 | `double y = Math.random() * (d.getHeight() - minY) + minY;`
175 | 0 | `coord.setX(x);`
176 | 0 | `coord.setY(y);`
177 | 0 | `}`
178 |  | ``
179 |  | `/**`
180 |  | `* Had to override this one as well, to ensure that setRoot() is called.`
181 |  | `*/`
182 |  | `protected void initialize_local() {`
183 | 0 | `for (Iterator iter = getGraph().getEdges().iterator();`
184 | 0 | `iter.hasNext();`
185 |  | `) {`
186 | 0 | `Edge e = (Edge) iter.next();`
187 | 0 | `SpringEdgeData sed = getSpringData(e);`
188 | 0 | `if (sed == null) {`
189 | 0 | `sed = new SpringEdgeData(e);`
190 | 0 | `e.addUserDatum(getSpringKey(), sed, UserData.REMOVE);`
191 |  | `}`
192 | 0 | `calcEdgeLength(sed, lengthFunction);`
193 |  | `}`
194 | 0 | `setRoot(getGraph());`
195 | 0 | `}`
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;`
204 | 0 | `double oldMSV = meanSquareVel;`
205 | 0 | `meanSquareVel = 0;`
206 |  | ``
207 | 0 | `synchronized (getCurrentSize()) {`
208 |  | ``
209 |  | `// int showingNodes = 0;`
210 |  | ``
211 | 0 | `for (Iterator i = getVisibleVertices().iterator(); i.hasNext();) {`
212 | 0 | `Vertex v = (Vertex) i.next();`
213 | 0 | `if (isLocked(v))`
214 | 0 | `continue;`
215 | 0 | `SpringLayout.SpringVertexData vd = getSpringData(v);`
216 | 0 | `Coordinates xyd = getCoordinates(v);`
217 |  | ``
218 | 0 | `int width = getCurrentSize().width;`
219 | 0 | `int height = getCurrentSize().height;`
220 |  | ``
221 |  | `// (JY addition: three lines are new)`
222 | 0 | `int level =`
223 |  | `((Integer) v.getUserDatum(MINIMUMLEVELKEY)).intValue();`
224 | 0 | `int minY = (int) (level * height / (graphHeight * SPACEFACTOR));`
225 | 0 | `int maxY =`
226 |  | `level == 0`
227 |  | `? (int) (height / (graphHeight * SPACEFACTOR * 2))`
228 |  | `: height;`
229 |  | ``
230 |  | `// JY added 2* - double the sideways repulsion.`
231 | 0 | `vd.dx += 2 * vd.repulsiondx + vd.edgedx;`
232 | 0 | `vd.dy += vd.repulsiondy + vd.edgedy;`
233 |  | ``
234 |  | `// JY Addition: Attract the vertex towards it's minimumLevel`
235 |  | `// height.`
236 | 0 | `double delta = xyd.getY() - minY;`
237 | 0 | `vd.dy -= delta * LEVELATTRACTIONRATE;`
238 | 0 | `if (level == 0)`
239 | 0 | `vd.dy -= delta * LEVELATTRACTIONRATE;`
240 |  | `// twice as much at the top.`
241 |  | ``
242 |  | `// JY addition:`
243 | 0 | `meanSquareVel += (vd.dx * vd.dx + vd.dy * vd.dy);`
244 |  | ``
245 |  | `// keeps nodes from moving any faster than 5 per time unit`
246 | 0 | `xyd.addX(Math.max(-5, Math.min(5, vd.dx)));`
247 | 0 | `xyd.addY(Math.max(-5, Math.min(5, vd.dy)));`
248 |  | ``
249 | 0 | `if (xyd.getX() < 0) {`
250 | 0 | `xyd.setX(0);`
251 | 0 | `} else if (xyd.getX() > width) {`
252 | 0 | `xyd.setX(width);`
253 |  | `}`
254 |  | ``
255 |  | `// (JY addition: These two lines replaced 0 with minY)`
256 | 0 | `if (xyd.getY() < minY) {`
257 | 0 | `xyd.setY(minY);`
258 |  | `// (JY addition: replace height with maxY)`
259 | 0 | `} else if (xyd.getY() > maxY) {`
260 | 0 | `xyd.setY(maxY);`
261 |  | `}`
262 |  | ``
263 |  | `// (JY addition: if there's only one root, anchor it in the`
264 |  | `// middle-top of the screen)`
265 | 0 | `if (numRoots == 1 && level == 0) {`
266 | 0 | `xyd.setX(width / 2);`
267 |  | `//xyd.setY(0);`
268 |  | `}`
269 |  | ``
270 |  | `}`
271 | 0 | `}`
272 |  | `//System.out.println("MeanSquareAccel="+meanSquareVel);`
273 | 0 | `if (!stoppingIncrements`
274 |  | `&& Math.abs(meanSquareVel - oldMSV) < MSV_THRESHOLD) {`
275 | 0 | `stoppingIncrements = true;`
276 | 0 | `incrementsLeft = COOL_DOWN_INCREMENTS;`
277 | 0 | `} else if (`
278 |  | `stoppingIncrements`
279 |  | `&& Math.abs(meanSquareVel - oldMSV) <= MSV_THRESHOLD) {`
280 | 0 | `incrementsLeft--;`
281 | 0 | `if (incrementsLeft <= 0)`
282 | 0 | `incrementsLeft = 0;`
283 |  | `}`
284 | 0 | `}`
285 |  | ``
286 |  | `/**`
287 |  | `* Override incrementsAreDone so that we can eventually stop.`
288 |  | `*/`
289 |  | `public boolean incrementsAreDone() {`
290 | 0 | `if (stoppingIncrements && incrementsLeft == 0)`
291 | 0 | `return true;`
292 |  | `else`
293 | 0 | `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) {`
301 | 0 | `Coordinates coord = getCoordinates(picked);`
302 | 0 | `coord.setX(x);`
303 | 0 | `coord.setY(y);`
304 | 0 | `stoppingIncrements = false;`
305 | 0 | `}`
306 |  | ``
307 |  | `/**`
308 |  | `* Overridden relaxEdges. This one reduces the effect of edges between`
309 |  | `* greatly different levels.`
310 |  | `*`
311 |  | `*/`
312 |  | ``
313 |  | `protected void relaxEdges() {`
314 | 0 | `for (Iterator i = getVisibleEdges().iterator(); i.hasNext();) {`
315 | 0 | `Edge e = (Edge) i.next();`
316 |  | ``
317 | 0 | `Vertex v1 = getAVertex(e);`
318 | 0 | `Vertex v2 = e.getOpposite(v1);`
319 |  | ``
320 | 0 | `Point2D p1 = getLocation(v1);`
321 | 0 | `Point2D p2 = getLocation(v2);`
322 | 0 | `double vx = p1.getX() - p2.getX();`
323 | 0 | `double vy = p1.getY() - p2.getY();`
324 | 0 | `double len = Math.sqrt(vx * vx + vy * vy);`
325 |  | ``
326 |  | `// JY addition.`
327 | 0 | `int level1 =`
328 |  | `((Integer) v1.getUserDatum(MINIMUMLEVELKEY)).intValue();`
329 | 0 | `int level2 =`
330 |  | `((Integer) v2.getUserDatum(MINIMUMLEVELKEY)).intValue();`
331 |  | ``
332 | 0 | `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.].`
336 | 0 | `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 ));`
343 | 0 | `double f = force_multiplier * (desiredLen - len) / len;`
344 |  | ``
345 | 0 | `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.`
349 | 0 | `if (level1 != level2)`
350 | 0 | `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.`
356 | 0 | `double dx = f * vx;`
357 | 0 | `double dy = f * vy;`
358 |  | `SpringVertexData v1D, v2D;`
359 | 0 | `v1D = getSpringData(v1);`
360 | 0 | `v2D = getSpringData(v2);`
361 |  | ``
362 | 0 | `SpringEdgeData sed = getSpringData(e);`
363 | 0 | `sed.f = f;`
364 |  | ``
365 | 0 | `v1D.edgedx += dx;`
366 | 0 | `v1D.edgedy += dy;`
367 | 0 | `v2D.edgedx += -dx;`
368 | 0 | `v2D.edgedy += -dy;`
369 |  | `}`
370 | 0 | `}`
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.