2 * Copyright (c) 2003, the JUNG Project and the Regents of the University of
3 * California All rights reserved.
5 * This software is open-source under the BSD license; see either "license.txt"
6 * or http://jung.sourceforge.net/license.txt for a description.
8 package edu.uci.ics.jung.algorithms.layout;
10 import edu.uci.ics.jung.algorithms.layout.util.RandomLocationTransformer;
11 import edu.uci.ics.jung.algorithms.util.IterativeContext;
12 import edu.uci.ics.jung.graph.Graph;
13 import edu.uci.ics.jung.graph.util.Pair;
15 import org.apache.commons.collections15.Factory;
16 import org.apache.commons.collections15.Transformer;
17 import org.apache.commons.collections15.functors.ConstantTransformer;
18 import org.apache.commons.collections15.map.LazyMap;
20 import java.awt.Dimension;
21 import java.awt.event.ComponentAdapter;
22 import java.awt.event.ComponentEvent;
23 import java.awt.geom.Point2D;
24 import java.util.ConcurrentModificationException;
25 import java.util.HashMap;
29 * The SpringLayout package represents a visualization of a set of nodes. The
30 * SpringLayout, which is initialized with a Graph, assigns X/Y locations to
31 * each node. When called <code>relax()</code>, the SpringLayout moves the
32 * visualization forward one step.
34 * @author Danyel Fisher
35 * @author Joshua O'Madadhain
37 public class SpringLayout<V, E> extends AbstractLayout<V,E> implements IterativeContext {
39 protected double stretch = 0.70;
40 protected Transformer<E, Integer> lengthFunction;
41 protected int repulsion_range_sq = 100 * 100;
42 protected double force_multiplier = 1.0 / 3.0;
44 protected Map<V, SpringVertexData> springVertexData =
45 LazyMap.decorate(new HashMap<V, SpringVertexData>(),
46 new Factory<SpringVertexData>() {
47 public SpringVertexData create() {
48 return new SpringVertexData();
52 * Constructor for a SpringLayout for a raw graph with associated
53 * dimension--the input knows how big the graph is. Defaults to the unit
56 @SuppressWarnings("unchecked")
57 public SpringLayout(Graph<V,E> g) {
58 this(g, new ConstantTransformer(30));
62 * Constructor for a SpringLayout for a raw graph with associated component.
64 * @param g the {@code Graph} to lay out
65 * @param length_function provides a length for each edge
67 public SpringLayout(Graph<V,E> g, Transformer<E, Integer> length_function)
70 this.lengthFunction = length_function;
74 * Returns the current value for the stretch parameter.
75 * @see #setStretch(double)
77 public double getStretch() {
82 * Sets the dimensions of the available space for layout to {@code size}.
85 public void setSize(Dimension size) {
86 if(initialized == false)
87 setInitializer(new RandomLocationTransformer<V>(size));
92 * <p>Sets the stretch parameter for this instance. This value
93 * specifies how much the degrees of an edge's incident vertices
94 * should influence how easily the endpoints of that edge
95 * can move (that is, that edge's tendency to change its length).</p>
97 * <p>The default value is 0.70. Positive values less than 1 cause
98 * high-degree vertices to move less than low-degree vertices, and
99 * values > 1 cause high-degree vertices to move more than
100 * low-degree vertices. Negative values will have unpredictable
101 * and inconsistent results.</p>
104 public void setStretch(double stretch) {
105 this.stretch = stretch;
109 * Returns the current value for the node repulsion range.
110 * @see #setRepulsionRange(int)
112 public int getRepulsionRange() {
113 return (int)(Math.sqrt(repulsion_range_sq));
117 * Sets the node repulsion range (in drawing area units) for this instance.
118 * Outside this range, nodes do not repel each other. The default value
119 * is 100. Negative values are treated as their positive equivalents.
122 public void setRepulsionRange(int range) {
123 this.repulsion_range_sq = range * range;
127 * Returns the current value for the edge length force multiplier.
128 * @see #setForceMultiplier(double)
130 public double getForceMultiplier() {
131 return force_multiplier;
135 * Sets the force multiplier for this instance. This value is used to
136 * specify how strongly an edge "wants" to be its default length
137 * (higher values indicate a greater attraction for the default length),
138 * which affects how much its endpoints move at each timestep.
139 * The default value is 1/3. A value of 0 turns off any attempt by the
140 * layout to cause edges to conform to the default length. Negative
141 * values cause long edges to get longer and short edges to get shorter; use
144 public void setForceMultiplier(double force) {
145 this.force_multiplier = force;
148 public void initialize() {
152 * Relaxation step. Moves all nodes a smidge.
156 for(V v : getGraph().getVertices()) {
157 SpringVertexData svd = springVertexData.get(v);
163 svd.edgedx = svd.edgedy = 0;
164 svd.repulsiondx = svd.repulsiondy = 0;
166 } catch(ConcurrentModificationException cme) {
171 calculateRepulsion();
175 protected void relaxEdges() {
177 for(E e : getGraph().getEdges()) {
178 Pair<V> endpoints = getGraph().getEndpoints(e);
179 V v1 = endpoints.getFirst();
180 V v2 = endpoints.getSecond();
182 Point2D p1 = transform(v1);
183 Point2D p2 = transform(v2);
184 if(p1 == null || p2 == null) continue;
185 double vx = p1.getX() - p2.getX();
186 double vy = p1.getY() - p2.getY();
187 double len = Math.sqrt(vx * vx + vy * vy);
189 double desiredLen = lengthFunction.transform(e);
191 // round from zero, if needed [zero would be Bad.].
192 len = (len == 0) ? .0001 : len;
194 double f = force_multiplier * (desiredLen - len) / len;
196 f = f * Math.pow(stretch, (getGraph().degree(v1) + getGraph().degree(v2) - 2));
198 // the actual movement distance 'dx' is the force multiplied by the
202 SpringVertexData v1D, v2D;
203 v1D = springVertexData.get(v1);
204 v2D = springVertexData.get(v2);
211 } catch(ConcurrentModificationException cme) {
216 protected void calculateRepulsion() {
218 for (V v : getGraph().getVertices()) {
219 if (isLocked(v)) continue;
221 SpringVertexData svd = springVertexData.get(v);
222 if(svd == null) continue;
223 double dx = 0, dy = 0;
225 for (V v2 : getGraph().getVertices()) {
226 if (v == v2) continue;
227 Point2D p = transform(v);
228 Point2D p2 = transform(v2);
229 if(p == null || p2 == null) continue;
230 double vx = p.getX() - p2.getX();
231 double vy = p.getY() - p2.getY();
232 double distanceSq = p.distanceSq(p2);
233 if (distanceSq == 0) {
236 } else if (distanceSq < repulsion_range_sq) {
238 dx += factor * vx / distanceSq;
239 dy += factor * vy / distanceSq;
242 double dlen = dx * dx + dy * dy;
244 dlen = Math.sqrt(dlen) / 2;
245 svd.repulsiondx += dx / dlen;
246 svd.repulsiondy += dy / dlen;
249 } catch(ConcurrentModificationException cme) {
250 calculateRepulsion();
254 protected void moveNodes()
256 synchronized (getSize()) {
258 for (V v : getGraph().getVertices()) {
259 if (isLocked(v)) continue;
260 SpringVertexData vd = springVertexData.get(v);
261 if(vd == null) continue;
262 Point2D xyd = transform(v);
264 vd.dx += vd.repulsiondx + vd.edgedx;
265 vd.dy += vd.repulsiondy + vd.edgedy;
267 // keeps nodes from moving any faster than 5 per time unit
268 xyd.setLocation(xyd.getX()+Math.max(-5, Math.min(5, vd.dx)),
269 xyd.getY()+Math.max(-5, Math.min(5, vd.dy)));
271 Dimension d = getSize();
273 int height = d.height;
275 if (xyd.getX() < 0) {
276 xyd.setLocation(0, xyd.getY());
277 } else if (xyd.getX() > width) {
278 xyd.setLocation(width, xyd.getY());
280 if (xyd.getY() < 0) {
281 xyd.setLocation(xyd.getX(), 0);
282 } else if (xyd.getY() > height) {
283 xyd.setLocation(xyd.getX(), height);
287 } catch(ConcurrentModificationException cme) {
293 protected static class SpringVertexData {
294 protected double edgedx;
295 protected double edgedy;
296 protected double repulsiondx;
297 protected double repulsiondy;
299 /** movement speed, x */
302 /** movement speed, y */
308 * Used for changing the size of the layout in response to a component's size.
310 public class SpringDimensionChecker extends ComponentAdapter {
312 public void componentResized(ComponentEvent e) {
313 setSize(e.getComponent().getSize());
318 * This one is an incremental visualization
320 public boolean isIncremental() {
325 * For now, we pretend it never finishes.
327 public boolean done() {
334 public void reset() {