| 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. |