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.map.LazyMap;
18 import java.awt.Dimension;
19 import java.awt.geom.Point2D;
20 import java.util.ConcurrentModificationException;
21 import java.util.HashMap;
25 * Implements the Fruchterman-Reingold force-directed algorithm for node layout.
27 * <p>Behavior is determined by the following settable parameters:
29 * <li/>attraction multiplier: how much edges try to keep their vertices together
30 * <li/>repulsion multiplier: how much vertices try to push each other apart
31 * <li/>maximum iterations: how many iterations this algorithm will use before stopping
33 * Each of the first two defaults to 0.75; the maximum number of iterations defaults to 700.
35 * @see "Fruchterman and Reingold, 'Graph Drawing by Force-directed Placement'"
36 * @see "http://i11www.ilkd.uni-karlsruhe.de/teaching/SS_04/visualisierung/papers/fruchterman91graph.pdf"
37 * @author Scott White, Yan-Biao Boey, Danyel Fisher
39 public class FRLayout<V, E> extends AbstractLayout<V, E> implements IterativeContext {
41 private double forceConstant;
43 private double temperature;
45 private int currentIteration;
47 private int mMaxIterations = 700;
49 private Map<V, FRVertexData> frVertexData =
50 LazyMap.decorate(new HashMap<V,FRVertexData>(), new Factory<FRVertexData>() {
51 public FRVertexData create() {
52 return new FRVertexData();
55 private double attraction_multiplier = 0.75;
57 private double attraction_constant;
59 private double repulsion_multiplier = 0.75;
61 private double repulsion_constant;
63 private double max_dimension;
66 * Creates an instance for the specified graph.
68 public FRLayout(Graph<V, E> g) {
73 * Creates an instance of size {@code d} for the specified graph.
75 public FRLayout(Graph<V, E> g, Dimension d) {
76 super(g, new RandomLocationTransformer<V>(d), d);
78 max_dimension = Math.max(d.height, d.width);
82 public void setSize(Dimension size) {
83 if(initialized == false) {
84 setInitializer(new RandomLocationTransformer<V>(size));
87 max_dimension = Math.max(size.height, size.width);
91 * Sets the attraction multiplier.
93 public void setAttractionMultiplier(double attraction) {
94 this.attraction_multiplier = attraction;
98 * Sets the repulsion multiplier.
100 public void setRepulsionMultiplier(double repulsion) {
101 this.repulsion_multiplier = repulsion;
104 public void reset() {
108 public void initialize() {
112 private void doInit() {
113 Graph<V,E> graph = getGraph();
114 Dimension d = getSize();
115 if(graph != null && d != null) {
116 currentIteration = 0;
117 temperature = d.getWidth() / 10;
123 / graph.getVertexCount());
125 attraction_constant = attraction_multiplier * forceConstant;
126 repulsion_constant = repulsion_multiplier * forceConstant;
130 private double EPSILON = 0.000001D;
133 * Moves the iteration forward one notch, calculation attraction and
134 * repulsion between vertices and edges and cooling the temperature.
136 public synchronized void step() {
140 * Calculate repulsion
145 for(V v1 : getGraph().getVertices()) {
149 } catch(ConcurrentModificationException cme) {}
153 * Calculate attraction
157 for(E e : getGraph().getEdges()) {
162 } catch(ConcurrentModificationException cme) {}
168 for(V v : getGraph().getVertices()) {
169 if (isLocked(v)) continue;
173 } catch(ConcurrentModificationException cme) {}
178 protected synchronized void calcPositions(V v) {
179 FRVertexData fvd = getFRData(v);
180 if(fvd == null) return;
181 Point2D xyd = transform(v);
182 double deltaLength = Math.max(EPSILON, fvd.norm());
184 double newXDisp = fvd.getX() / deltaLength
185 * Math.min(deltaLength, temperature);
187 if (Double.isNaN(newXDisp)) {
188 throw new IllegalArgumentException(
189 "Unexpected mathematical result in FRLayout:calcPositions [xdisp]"); }
191 double newYDisp = fvd.getY() / deltaLength
192 * Math.min(deltaLength, temperature);
193 xyd.setLocation(xyd.getX()+newXDisp, xyd.getY()+newYDisp);
195 double borderWidth = getSize().getWidth() / 50.0;
196 double newXPos = xyd.getX();
197 if (newXPos < borderWidth) {
198 newXPos = borderWidth + Math.random() * borderWidth * 2.0;
199 } else if (newXPos > (getSize().getWidth() - borderWidth)) {
200 newXPos = getSize().getWidth() - borderWidth - Math.random()
204 double newYPos = xyd.getY();
205 if (newYPos < borderWidth) {
206 newYPos = borderWidth + Math.random() * borderWidth * 2.0;
207 } else if (newYPos > (getSize().getHeight() - borderWidth)) {
208 newYPos = getSize().getHeight() - borderWidth
209 - Math.random() * borderWidth * 2.0;
212 xyd.setLocation(newXPos, newYPos);
215 protected void calcAttraction(E e) {
216 Pair<V> endpoints = getGraph().getEndpoints(e);
217 V v1 = endpoints.getFirst();
218 V v2 = endpoints.getSecond();
219 boolean v1_locked = isLocked(v1);
220 boolean v2_locked = isLocked(v2);
222 if(v1_locked && v2_locked) {
223 // both locked, do nothing
226 Point2D p1 = transform(v1);
227 Point2D p2 = transform(v2);
228 if(p1 == null || p2 == null) return;
229 double xDelta = p1.getX() - p2.getX();
230 double yDelta = p1.getY() - p2.getY();
232 double deltaLength = Math.max(EPSILON, Math.sqrt((xDelta * xDelta)
233 + (yDelta * yDelta)));
235 double force = (deltaLength * deltaLength) / attraction_constant;
237 if (Double.isNaN(force)) { throw new IllegalArgumentException(
238 "Unexpected mathematical result in FRLayout:calcPositions [force]"); }
240 double dx = (xDelta / deltaLength) * force;
241 double dy = (yDelta / deltaLength) * force;
242 if(v1_locked == false) {
243 FRVertexData fvd1 = getFRData(v1);
244 fvd1.offset(-dx, -dy);
246 if(v2_locked == false) {
247 FRVertexData fvd2 = getFRData(v2);
252 protected void calcRepulsion(V v1) {
253 FRVertexData fvd1 = getFRData(v1);
256 fvd1.setLocation(0, 0);
259 for(V v2 : getGraph().getVertices()) {
261 // if (isLocked(v2)) continue;
263 Point2D p1 = transform(v1);
264 Point2D p2 = transform(v2);
265 if(p1 == null || p2 == null) continue;
266 double xDelta = p1.getX() - p2.getX();
267 double yDelta = p1.getY() - p2.getY();
269 double deltaLength = Math.max(EPSILON, Math
270 .sqrt((xDelta * xDelta) + (yDelta * yDelta)));
272 double force = (repulsion_constant * repulsion_constant) / deltaLength;
274 if (Double.isNaN(force)) { throw new RuntimeException(
275 "Unexpected mathematical result in FRLayout:calcPositions [repulsion]"); }
277 fvd1.offset((xDelta / deltaLength) * force,
278 (yDelta / deltaLength) * force);
281 } catch(ConcurrentModificationException cme) {
286 private void cool() {
287 temperature *= (1.0 - currentIteration / (double) mMaxIterations);
291 * Sets the maximum number of iterations.
293 public void setMaxIterations(int maxIterations) {
294 mMaxIterations = maxIterations;
297 protected FRVertexData getFRData(V v) {
298 return frVertexData.get(v);
302 * This one is an incremental visualization.
304 public boolean isIncremental() {
309 * Returns true once the current iteration has passed the maximum count,
310 * <tt>MAX_ITERATIONS</tt>.
312 public boolean done() {
313 if (currentIteration > mMaxIterations || temperature < 1.0/max_dimension)
320 protected static class FRVertexData extends Point2D.Double
322 protected void offset(double x, double y)
328 protected double norm()
330 return Math.sqrt(x*x + y*y);