relax(), the SpringLayout moves the
* visualization forward one step.
*
* @author Danyel Fisher
* @author Joshua O'Madadhain
*/
static class CALSpringLayout {
double repulsion_range_sq = sqr(0.5);
double repulsionFactor = 0.02/*0.01*/;
double desiredLength = 0.3;
AutoMap < Circle , SpringVertexData > springVertexData = new AutoMap(SpringVertexData.class);
CirclesAndLines cal;
CALSpringLayout() {}
CALSpringLayout(CirclesAndLines cal) {
this.cal = cal;}
/**
* Sets the stretch parameter for this instance. This value * specifies how much the degrees of an edge's incident vertices * should influence how easily the endpoints of that edge * can move (that is, that edge's tendency to change its length).
* *The default value is 0.70. Positive values less than 1 cause * high-degree vertices to move less than low-degree vertices, and * values > 1 cause high-degree vertices to move more than * low-degree vertices. Negative values will have unpredictable * and inconsistent results.
* @param stretch */ double stretch = 0.70; /** * Returns the current value for the node repulsion range. * @see #setRepulsionRange(int) */ public int getRepulsionRange() { return (int)(Math.sqrt(repulsion_range_sq)); } /** * Sets the node repulsion range (in drawing area units) for this instance. * Outside this range, nodes do not repel each other. The default value * is 100. Negative values are treated as their positive equivalents. * @param range */ public void setRepulsionRange(int range) { this.repulsion_range_sq = range * range; } /** * Sets the force multiplier for this instance. This value is used to * specify how strongly an edge "wants" to be its default length * (higher values indicate a greater attraction for the default length), * which affects how much its endpoints move at each timestep. * The default value is 1/3. A value of 0 turns off any attempt by the * layout to cause edges to conform to the default length. Negative * values cause long edges to get longer and short edges to get shorter; use * at your own risk. */ double force_multiplier = 1.0 / 3.0; /** * Relaxation step. Moves all nodes a smidge. */ void step() { for (Circle v : cal.circles) { SpringVertexData svd = springVertexData.get(v); if (svd == null) continue; svd.dx /= 4; svd.dy /= 4; svd.edgedx = svd.edgedy = 0; svd.repulsiondx = svd.repulsiondy = 0; } relaxEdges(); calculateRepulsion(); moveNodes(); } protected void relaxEdges() { try { for (Line e : cal.lines) { Circle v1 = e.a, v2 = e.b; Point2D p1 = transform(v1); Point2D p2 = transform(v2); if(p1 == null || p2 == null) continue; double vx = p1.getX() - p2.getX(); double vy = p1.getY() - p2.getY(); double len = Math.sqrt(vx * vx + vy * vy); // round from zero, if needed [zero would be Bad.]. len = (len == 0) ? .0001 : len; double f = force_multiplier * (desiredLength - len) / len; // XXX? f = f * Math.pow(stretch, (getGraph().degree(v1) + getGraph().degree(v2) - 2)); // 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); v1D.edgedx += dx; v1D.edgedy += dy; v2D.edgedx += -dx; v2D.edgedy += -dy; } } catch(ConcurrentModificationException cme) { relaxEdges(); } } void calculateRepulsion() { for (Circle v : cal.circles) { SpringVertexData svd = springVertexData.get(v); if(svd == null) continue; double dx = 0, dy = 0; for (Circle v2 : cal.circles) { if (v == v2) continue; Point2D p = transform(v); Point2D p2 = transform(v2); if(p == null || p2 == null) continue; double vx = p.getX() - p2.getX(); double vy = p.getY() - p2.getY(); double distanceSq = p.distanceSq(p2); if (distanceSq == 0) { dx += Math.random()*0.01; dy += Math.random()*0.01; } else if (distanceSq < repulsion_range_sq) { double factor = 1; dx += factor * vx / distanceSq; dy += factor * vy / distanceSq; } } double dlen = dx * dx + dy * dy; if (dlen > 0) { dlen = Math.sqrt(dlen) / 2 / repulsionFactor; svd.repulsiondx += dx / dlen; svd.repulsiondy += dy / dlen; } } } protected void moveNodes() { for (Circle v : cal.circles) { SpringVertexData vd = springVertexData.get(v); if (vd == null) continue; Point2D xyd = transform(v); vd.dx += vd.repulsiondx + vd.edgedx; vd.dy += vd.repulsiondy + vd.edgedy; // keeps nodes from moving any faster than 5 per time unit v.x += Math.max(-5, Math.min(5, vd.dx)); v.y += Math.max(-5, Math.min(5, vd.dy)); } calCenterStepwise(cal, 0.1); } Point2D transform(Circle v) { return new Point2D.Double(v.x, v.y); } static class SpringVertexData { double edgedx; double edgedy; double repulsiondx; double repulsiondy; /** movement speed, x */ protected double dx; /** movement speed, y */ protected double dy; } } static abstract class F0 { abstract A get(); } static abstract class F1