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. |
copyright © 2003, jcoverage ltd. all rights reserved. |