+++ /dev/null
-/*
- * Copyright (c) 2003, the JUNG Project and the Regents of the University
- * of California
- * All rights reserved.
- *
- * This software is open-source under the BSD license; see either
- * "license.txt" or
- * http://jung.sourceforge.net/license.txt for a description.
- *
- * Created on Dec 4, 2003
- */
-package edu.uci.ics.jung.algorithms.layout;
-
-import java.awt.Dimension;
-import java.awt.geom.Point2D;
-import java.util.Collection;
-import java.util.HashMap;
-import java.util.Map;
-
-import edu.uci.ics.jung.graph.Graph;
-import edu.uci.ics.jung.graph.util.Pair;
-
-/**
- * An implementation of {@code Layout} suitable for tree-like directed
- * acyclic graphs. Parts of it will probably not terminate if the graph is
- * cyclic! The layout will result in directed edges pointing generally upwards.
- * Any vertices with no successors are considered to be level 0, and tend
- * towards the top of the layout. Any vertex has a level one greater than the
- * maximum level of all its successors.
- *
- *
- * @author John Yesberg
- */
-public class DAGLayout<V, E> extends SpringLayout<V,E> {
-
- /**
- * Each vertex has a minimumLevel. Any vertex with no successors has
- * minimumLevel of zero. The minimumLevel of any vertex must be strictly
- * greater than the minimumLevel of its parents. (Vertex A is a parent of
- * Vertex B iff there is an edge from B to A.) Typically, a vertex will
- * have a minimumLevel which is one greater than the minimumLevel of its
- * parent's. However, if the vertex has two parents, its minimumLevel will
- * be one greater than the maximum of the parents'. We need to calculate
- * the minimumLevel for each vertex. When we layout the graph, vertices
- * cannot be drawn any higher than the minimumLevel. The graphHeight of a
- * graph is the greatest minimumLevel that is used. We will modify the
- * SpringLayout calculations so that nodes cannot move above their assigned
- * minimumLevel.
- */
- private Map<V,Number> minLevels = new HashMap<V,Number>();
- // Simpler than the "pair" technique.
- static int graphHeight;
- static int numRoots;
- final double SPACEFACTOR = 1.3;
- // How much space do we allow for additional floating at the bottom.
- final double LEVELATTRACTIONRATE = 0.8;
-
- /**
- * A bunch of parameters to help work out when to stop quivering.
- *
- * If the MeanSquareVel(ocity) ever gets below the MSV_THRESHOLD, then we
- * will start a final cool-down phase of COOL_DOWN_INCREMENT increments. If
- * the MeanSquareVel ever exceeds the threshold, we will exit the cool down
- * phase, and continue looking for another opportunity.
- */
- final double MSV_THRESHOLD = 10.0;
- double meanSquareVel;
- boolean stoppingIncrements = false;
- int incrementsLeft;
- final int COOL_DOWN_INCREMENTS = 200;
-
- /**
- * Creates an instance for the specified graph.
- */
- public DAGLayout(Graph<V,E> g) {
- super(g);
- }
-
- /**
- * setRoot calculates the level of each vertex in the graph. Level 0 is
- * allocated to any vertex with no successors. Level n+1 is allocated to
- * any vertex whose successors' maximum level is n.
- */
- public void setRoot(Graph<V,E> g) {
- numRoots = 0;
- for(V v : g.getVertices()) {
- Collection<V> successors = getGraph().getSuccessors(v);
- if (successors.size() == 0) {
- setRoot(v);
- numRoots++;
- }
- }
- }
-
- /**
- * Set vertex v to be level 0.
- */
- public void setRoot(V v) {
- minLevels.put(v, new Integer(0));
- // set all the levels.
- propagateMinimumLevel(v);
- }
-
- /**
- * A recursive method for allocating the level for each vertex. Ensures
- * that all predecessors of v have a level which is at least one greater
- * than the level of v.
- *
- * @param v
- */
- public void propagateMinimumLevel(V v) {
- int level = minLevels.get(v).intValue();
- for(V child : getGraph().getPredecessors(v)) {
- int oldLevel, newLevel;
- Number o = minLevels.get(child);
- if (o != null)
- oldLevel = o.intValue();
- else
- oldLevel = 0;
- newLevel = Math.max(oldLevel, level + 1);
- minLevels.put(child, new Integer(newLevel));
-
- if (newLevel > graphHeight)
- graphHeight = newLevel;
- propagateMinimumLevel(child);
- }
- }
-
- /**
- * Sets random locations for a vertex within the dimensions of the space.
- * This overrides the method in AbstractLayout
- *
- * @param coord
- * @param d
- */
- private void initializeLocation(
- V v,
- Point2D coord,
- Dimension d) {
-
- int level = minLevels.get(v).intValue();
- int minY = (int) (level * d.getHeight() / (graphHeight * SPACEFACTOR));
- double x = Math.random() * d.getWidth();
- double y = Math.random() * (d.getHeight() - minY) + minY;
- coord.setLocation(x,y);
- }
-
- @Override
- public void setSize(Dimension size) {
- super.setSize(size);
- for(V v : getGraph().getVertices()) {
- initializeLocation(v,transform(v),getSize());
- }
- }
-
- /**
- * Had to override this one as well, to ensure that setRoot() is called.
- */
- @Override
- public void initialize() {
- super.initialize();
- setRoot(getGraph());
- }
-
- /**
- * Override the moveNodes() method from SpringLayout. The only change we
- * need to make is to make sure that nodes don't float higher than the minY
- * coordinate, as calculated by their minimumLevel.
- */
- @Override
- protected void moveNodes() {
- // Dimension d = currentSize;
- double oldMSV = meanSquareVel;
- meanSquareVel = 0;
-
- synchronized (getSize()) {
-
- for(V v : getGraph().getVertices()) {
- if (isLocked(v))
- continue;
- SpringLayout.SpringVertexData vd = springVertexData.get(v);
- Point2D xyd = transform(v);
-
- int width = getSize().width;
- int height = getSize().height;
-
- // (JY addition: three lines are new)
- int level =
- minLevels.get(v).intValue();
- int minY = (int) (level * height / (graphHeight * SPACEFACTOR));
- int maxY =
- level == 0
- ? (int) (height / (graphHeight * SPACEFACTOR * 2))
- : height;
-
- // JY added 2* - double the sideways repulsion.
- vd.dx += 2 * vd.repulsiondx + vd.edgedx;
- vd.dy += vd.repulsiondy + vd.edgedy;
-
- // JY Addition: Attract the vertex towards it's minimumLevel
- // height.
- double delta = xyd.getY() - minY;
- vd.dy -= delta * LEVELATTRACTIONRATE;
- if (level == 0)
- vd.dy -= delta * LEVELATTRACTIONRATE;
- // twice as much at the top.
-
- // JY addition:
- meanSquareVel += (vd.dx * vd.dx + vd.dy * vd.dy);
-
- // keeps nodes from moving any faster than 5 per time unit
- xyd.setLocation(xyd.getX()+Math.max(-5, Math.min(5, vd.dx)) , xyd.getY()+Math.max(-5, Math.min(5, vd.dy)) );
-
- if (xyd.getX() < 0) {
- xyd.setLocation(0, xyd.getY());
- } else if (xyd.getX() > width) {
- xyd.setLocation(width, xyd.getY());
- }
-
- // (JY addition: These two lines replaced 0 with minY)
- if (xyd.getY() < minY) {
- xyd.setLocation(xyd.getX(), minY);
- // (JY addition: replace height with maxY)
- } else if (xyd.getY() > maxY) {
- xyd.setLocation(xyd.getX(), maxY);
- }
-
- // (JY addition: if there's only one root, anchor it in the
- // middle-top of the screen)
- if (numRoots == 1 && level == 0) {
- xyd.setLocation(width/2, xyd.getY());
- }
- }
- }
- //System.out.println("MeanSquareAccel="+meanSquareVel);
- if (!stoppingIncrements
- && Math.abs(meanSquareVel - oldMSV) < MSV_THRESHOLD) {
- stoppingIncrements = true;
- incrementsLeft = COOL_DOWN_INCREMENTS;
- } else if (
- stoppingIncrements
- && Math.abs(meanSquareVel - oldMSV) <= MSV_THRESHOLD) {
- incrementsLeft--;
- if (incrementsLeft <= 0)
- incrementsLeft = 0;
- }
- }
-
- /**
- * Override incrementsAreDone so that we can eventually stop.
- */
- @Override
- public boolean done() {
- if (stoppingIncrements && incrementsLeft == 0)
- return true;
- else
- return false;
- }
-
- /**
- * Override forceMove so that if someone moves a node, we can re-layout
- * everything.
- */
- @Override
- public void setLocation(V picked, double x, double y) {
- Point2D coord = transform(picked);
- coord.setLocation(x,y);
- stoppingIncrements = false;
- }
-
- /**
- * Override forceMove so that if someone moves a node, we can re-layout
- * everything.
- */
- @Override
- public void setLocation(V picked, Point2D p) {
- Point2D coord = transform(picked);
- coord.setLocation(p);
- stoppingIncrements = false;
- }
-
- /**
- * Overridden relaxEdges. This one reduces the effect of edges between
- * greatly different levels.
- *
- */
- @Override
- protected void relaxEdges() {
- for(E e : getGraph().getEdges()) {
- Pair<V> endpoints = getGraph().getEndpoints(e);
- V v1 = endpoints.getFirst();
- V v2 = endpoints.getSecond();
-
- Point2D p1 = transform(v1);
- Point2D p2 = transform(v2);
- double vx = p1.getX() - p2.getX();
- double vy = p1.getY() - p2.getY();
- double len = Math.sqrt(vx * vx + vy * vy);
-
- // JY addition.
- int level1 =
- minLevels.get(v1).intValue();
- int level2 =
- minLevels.get(v2).intValue();
-
- // desiredLen *= Math.pow( 1.1, (v1.degree() + v2.degree()) );
-// double desiredLen = getLength(e);
- double desiredLen = lengthFunction.transform(e);
-
- // round from zero, if needed [zero would be Bad.].
- len = (len == 0) ? .0001 : len;
-
- // force factor: optimal length minus actual length,
- // is made smaller as the current actual length gets larger.
- // why?
-
- // System.out.println("Desired : " + getLength( e ));
- double f = force_multiplier * (desiredLen - len) / len;
-
- f = f * Math.pow(stretch / 100.0,
- (getGraph().degree(v1) + getGraph().degree(v2) -2));
-
- // JY addition. If this is an edge which stretches a long way,
- // don't be so concerned about it.
- if (level1 != level2)
- f = f / Math.pow(Math.abs(level2 - level1), 1.5);
-
- // f= Math.min( 0, f );
-
- // the actual movement distance 'dx' is the force multiplied by the
- // distance to go.
- double dx = f * vx;
- double dy = f * vy;
- SpringVertexData v1D, v2D;
- v1D = springVertexData.get(v1);
- v2D = springVertexData.get(v2);
-
-// SpringEdgeData<E> sed = getSpringEdgeData(e);
-// sed.f = f;
-
- v1D.edgedx += dx;
- v1D.edgedy += dy;
- v2D.edgedx += -dx;
- v2D.edgedy += -dy;
- }
- }
-}
Code Review / controller.git / blobdiff