View Javadoc

1   /*
2    * Copyright (c) 2003, the JUNG Project and the Regents of the University of
3    * California All rights reserved.
4    *
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.
7    */
8   package edu.uci.ics.jung.algorithms.layout;
9   
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;
14  
15  import org.apache.commons.collections15.Factory;
16  import org.apache.commons.collections15.map.LazyMap;
17  
18  import java.awt.Dimension;
19  import java.awt.geom.Point2D;
20  import java.util.ConcurrentModificationException;
21  import java.util.HashMap;
22  import java.util.Map;
23  
24  /**
25   * Implements the Fruchterman-Reingold force-directed algorithm for node layout.
26   * 
27   * <p>Behavior is determined by the following settable parameters:
28   * <ul>
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
32   * </ul>
33   * Each of the first two defaults to 0.75; the maximum number of iterations defaults to 700.
34   *
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
38   */
39  public class FRLayout<V, E> extends AbstractLayout<V, E> implements IterativeContext {
40  
41      private double forceConstant;
42  
43      private double temperature;
44  
45      private int currentIteration;
46  
47      private int mMaxIterations = 700;
48  
49      private Map<V, FRVertexData> frVertexData =
50      	LazyMap.decorate(new HashMap<V,FRVertexData>(), new Factory<FRVertexData>() {
51      		public FRVertexData create() {
52      			return new FRVertexData();
53      		}});
54  
55      private double attraction_multiplier = 0.75;
56  
57      private double attraction_constant;
58  
59      private double repulsion_multiplier = 0.75;
60  
61      private double repulsion_constant;
62  
63      private double max_dimension;
64  
65      /**
66       * Creates an instance for the specified graph.
67       */
68      public FRLayout(Graph<V, E> g) {
69          super(g);
70      }
71  
72      /**
73       * Creates an instance of size {@code d} for the specified graph.
74       */
75      public FRLayout(Graph<V, E> g, Dimension d) {
76          super(g, new RandomLocationTransformer<V>(d), d);
77          initialize();
78          max_dimension = Math.max(d.height, d.width);
79      }
80  
81  	@Override
82  	public void setSize(Dimension size) {
83  		if(initialized == false) {
84  			setInitializer(new RandomLocationTransformer<V>(size));
85  		}
86  		super.setSize(size);
87          max_dimension = Math.max(size.height, size.width);
88  	}
89  
90  	/**
91  	 * Sets the attraction multiplier.
92  	 */
93  	public void setAttractionMultiplier(double attraction) {
94          this.attraction_multiplier = attraction;
95      }
96  
97  	/**
98  	 * Sets the repulsion multiplier.
99  	 */
100     public void setRepulsionMultiplier(double repulsion) {
101         this.repulsion_multiplier = repulsion;
102     }
103 
104 	public void reset() {
105 		doInit();
106 	}
107 
108     public void initialize() {
109     	doInit();
110     }
111 
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;
118 
119     		forceConstant =
120     			Math
121     			.sqrt(d.getHeight()
122     					* d.getWidth()
123     					/ graph.getVertexCount());
124 
125     		attraction_constant = attraction_multiplier * forceConstant;
126     		repulsion_constant = repulsion_multiplier * forceConstant;
127     	}
128     }
129 
130     private double EPSILON = 0.000001D;
131 
132     /**
133      * Moves the iteration forward one notch, calculation attraction and
134      * repulsion between vertices and edges and cooling the temperature.
135      */
136     public synchronized void step() {
137         currentIteration++;
138 
139         /**
140          * Calculate repulsion
141          */
142         while(true) {
143 
144             try {
145                 for(V v1 : getGraph().getVertices()) {
146                     calcRepulsion(v1);
147                 }
148                 break;
149             } catch(ConcurrentModificationException cme) {}
150         }
151 
152         /**
153          * Calculate attraction
154          */
155         while(true) {
156             try {
157                 for(E e : getGraph().getEdges()) {
158 
159                     calcAttraction(e);
160                 }
161                 break;
162             } catch(ConcurrentModificationException cme) {}
163         }
164 
165 
166         while(true) {
167             try {
168                 for(V v : getGraph().getVertices()) {
169                     if (isLocked(v)) continue;
170                     calcPositions(v);
171                 }
172                 break;
173             } catch(ConcurrentModificationException cme) {}
174         }
175         cool();
176     }
177 
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());
183 
184         double newXDisp = fvd.getX() / deltaLength
185                 * Math.min(deltaLength, temperature);
186 
187         if (Double.isNaN(newXDisp)) {
188         	throw new IllegalArgumentException(
189                 "Unexpected mathematical result in FRLayout:calcPositions [xdisp]"); }
190 
191         double newYDisp = fvd.getY() / deltaLength
192                 * Math.min(deltaLength, temperature);
193         xyd.setLocation(xyd.getX()+newXDisp, xyd.getY()+newYDisp);
194 
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()
201                     * borderWidth * 2.0;
202         }
203 
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;
210         }
211 
212         xyd.setLocation(newXPos, newYPos);
213     }
214 
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);
221 
222         if(v1_locked && v2_locked) {
223         	// both locked, do nothing
224         	return;
225         }
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();
231 
232         double deltaLength = Math.max(EPSILON, Math.sqrt((xDelta * xDelta)
233                 + (yDelta * yDelta)));
234 
235         double force = (deltaLength * deltaLength) / attraction_constant;
236 
237         if (Double.isNaN(force)) { throw new IllegalArgumentException(
238                 "Unexpected mathematical result in FRLayout:calcPositions [force]"); }
239 
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);
245         }
246         if(v2_locked == false) {
247         	FRVertexData fvd2 = getFRData(v2);
248         	fvd2.offset(dx, dy);
249         }
250     }
251 
252     protected void calcRepulsion(V v1) {
253         FRVertexData fvd1 = getFRData(v1);
254         if(fvd1 == null)
255             return;
256         fvd1.setLocation(0, 0);
257 
258         try {
259             for(V v2 : getGraph().getVertices()) {
260 
261 //                if (isLocked(v2)) continue;
262                 if (v1 != v2) {
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();
268 
269                     double deltaLength = Math.max(EPSILON, Math
270                             .sqrt((xDelta * xDelta) + (yDelta * yDelta)));
271 
272                     double force = (repulsion_constant * repulsion_constant) / deltaLength;
273 
274                     if (Double.isNaN(force)) { throw new RuntimeException(
275                     "Unexpected mathematical result in FRLayout:calcPositions [repulsion]"); }
276 
277                     fvd1.offset((xDelta / deltaLength) * force,
278                             (yDelta / deltaLength) * force);
279                 }
280             }
281         } catch(ConcurrentModificationException cme) {
282             calcRepulsion(v1);
283         }
284     }
285 
286     private void cool() {
287         temperature *= (1.0 - currentIteration / (double) mMaxIterations);
288     }
289 
290     /**
291      * Sets the maximum number of iterations.
292      */
293     public void setMaxIterations(int maxIterations) {
294         mMaxIterations = maxIterations;
295     }
296 
297     protected FRVertexData getFRData(V v) {
298         return frVertexData.get(v);
299     }
300 
301     /**
302      * This one is an incremental visualization.
303      */
304     public boolean isIncremental() {
305         return true;
306     }
307 
308     /**
309      * Returns true once the current iteration has passed the maximum count,
310      * <tt>MAX_ITERATIONS</tt>.
311      */
312     public boolean done() {
313         if (currentIteration > mMaxIterations || temperature < 1.0/max_dimension)
314         {
315             return true;
316         }
317         return false;
318     }
319 
320     protected static class FRVertexData extends Point2D.Double
321     {
322         protected void offset(double x, double y)
323         {
324             this.x += x;
325             this.y += y;
326         }
327 
328         protected double norm()
329         {
330             return Math.sqrt(x*x + y*y);
331         }
332      }
333 }