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 java.awt.Dimension;
11  import java.awt.geom.Point2D;
12  import java.awt.geom.Rectangle2D;
13  import java.util.ConcurrentModificationException;
14  import java.util.HashMap;
15  import java.util.Map;
16  
17  import org.apache.commons.collections15.Factory;
18  import org.apache.commons.collections15.map.LazyMap;
19  
20  import edu.uci.ics.jung.algorithms.layout.util.RandomLocationTransformer;
21  import edu.uci.ics.jung.algorithms.util.IterativeContext;
22  import edu.uci.ics.jung.graph.Graph;
23  import edu.uci.ics.jung.graph.util.Pair;
24  
25  /**
26   * Implements the Fruchterman-Reingold force-directed algorithm for node layout.
27   * This is an experimental attempt at optimizing {@code FRLayout}; if it is successful
28   * it will be folded back into {@code FRLayout} (and this class will disappear).
29   * 
30   * <p>Behavior is determined by the following settable parameters:
31   * <ul>
32   * <li/>attraction multiplier: how much edges try to keep their vertices together
33   * <li/>repulsion multiplier: how much vertices try to push each other apart
34   * <li/>maximum iterations: how many iterations this algorithm will use before stopping
35   * </ul>
36   * Each of the first two defaults to 0.75; the maximum number of iterations defaults to 700.
37  
38   * 
39   * @see "Fruchterman and Reingold, 'Graph Drawing by Force-directed Placement'"
40   * @see http://i11www.ilkd.uni-karlsruhe.de/teaching/SS_04/visualisierung/papers/fruchterman91graph.pdf
41   * 
42   * @author Tom Nelson
43   * @author Scott White, Yan-Biao Boey, Danyel Fisher
44   */
45  public class FRLayout2<V, E> extends AbstractLayout<V, E> implements IterativeContext {
46  
47      private double forceConstant;
48  
49      private double temperature;
50  
51      private int currentIteration;
52  
53      private int maxIterations = 700;
54      
55      private Map<V, Point2D> frVertexData = 
56      	LazyMap.decorate(new HashMap<V,Point2D>(), new Factory<Point2D>() {
57      		public Point2D create() {
58      			return new Point2D.Double();
59      		}});
60  
61      private double attraction_multiplier = 0.75;
62      
63      private double attraction_constant;
64      
65      private double repulsion_multiplier = 0.75;
66      
67      private double repulsion_constant;
68      
69      private double max_dimension;
70      
71      private Rectangle2D innerBounds = new Rectangle2D.Double();
72      
73      private boolean checked = false;
74      
75      /**
76       * Creates an instance for the specified graph.
77       */
78      public FRLayout2(Graph<V, E> g) {
79          super(g);
80      }
81      
82      /**
83       * Creates an instance of size {@code d} for the specified graph.
84       */
85      public FRLayout2(Graph<V, E> g, Dimension d) {
86          super(g, new RandomLocationTransformer<V>(d), d);
87          max_dimension = Math.max(d.height, d.width);
88          initialize();
89      }
90      
91  	@Override
92  	public void setSize(Dimension size) {
93  		if(initialized == false) 
94  			setInitializer(new RandomLocationTransformer<V>(size));
95  		super.setSize(size);
96  		double t = size.width/50.0;
97  		innerBounds.setFrameFromDiagonal(t,t,size.width-t,size.height-t);
98          max_dimension = Math.max(size.height, size.width);
99  	}
100 
101     /**
102      * Sets the attraction multiplier.
103      */
104 	public void setAttractionMultiplier(double attraction) {
105         this.attraction_multiplier = attraction;
106     }
107     
108     /**
109      * Sets the repulsion multiplier.
110      */
111     public void setRepulsionMultiplier(double repulsion) {
112         this.repulsion_multiplier = repulsion;
113     }
114     
115 	public void reset() {
116 		doInit();
117 	}
118     
119     public void initialize() {
120     	doInit();
121     }
122 
123     private void doInit() {
124     	Graph<V,E> graph = getGraph();
125     	Dimension d = getSize();
126     	if(graph != null && d != null) {
127     		currentIteration = 0;
128     		temperature = d.getWidth() / 10;
129 
130     		forceConstant = 
131     			Math
132     			.sqrt(d.getHeight()
133     					* d.getWidth()
134     					/ graph.getVertexCount());
135 
136     		attraction_constant = attraction_multiplier * forceConstant;
137     		repulsion_constant = repulsion_multiplier * forceConstant;
138     	}
139     }
140 
141     private double EPSILON = 0.000001D;
142 
143     /**
144      * Moves the iteration forward one notch, calculation attraction and
145      * repulsion between vertices and edges and cooling the temperature.
146      */
147     public synchronized void step() {
148         currentIteration++;
149 
150         /**
151          * Calculate repulsion
152          */
153         while(true) {
154             
155             try {
156                 for(V v1 : getGraph().getVertices()) {
157                     calcRepulsion(v1);
158                 }
159                 break;
160             } catch(ConcurrentModificationException cme) {}
161         }
162 
163         /**
164          * Calculate attraction
165          */
166         while(true) {
167             try {
168                 for(E e : getGraph().getEdges()) {
169                     calcAttraction(e);
170                 }
171                 break;
172             } catch(ConcurrentModificationException cme) {}
173         }
174 
175 
176         while(true) {
177             try {    
178                 for(V v : getGraph().getVertices()) {
179                     if (isLocked(v)) continue;
180                     calcPositions(v);
181                 }
182                 break;
183             } catch(ConcurrentModificationException cme) {}
184         }
185         cool();
186     }
187 
188     protected synchronized void calcPositions(V v) {
189         Point2D fvd = this.frVertexData.get(v);
190         if(fvd == null) return;
191         Point2D xyd = transform(v);
192         double deltaLength = Math.max(EPSILON, 
193         		Math.sqrt(fvd.getX()*fvd.getX()+fvd.getY()*fvd.getY()));
194 
195         double newXDisp = fvd.getX() / deltaLength
196                 * Math.min(deltaLength, temperature);
197 
198         assert Double.isNaN(newXDisp) == false : "Unexpected mathematical result in FRLayout:calcPositions [xdisp]";
199 
200         double newYDisp = fvd.getY() / deltaLength
201                 * Math.min(deltaLength, temperature);
202         double newX = xyd.getX()+Math.max(-5, Math.min(5,newXDisp));
203         double newY = xyd.getY()+Math.max(-5, Math.min(5,newYDisp));
204         
205         newX = Math.max(innerBounds.getMinX(), Math.min(newX, innerBounds.getMaxX()));
206         newY = Math.max(innerBounds.getMinY(), Math.min(newY, innerBounds.getMaxY()));
207         
208         xyd.setLocation(newX, newY);
209 
210     }
211 
212     protected void calcAttraction(E e) {
213     	Pair<V> endpoints = getGraph().getEndpoints(e);
214         V v1 = endpoints.getFirst();
215         V v2 = endpoints.getSecond();
216         boolean v1_locked = isLocked(v1);
217         boolean v2_locked = isLocked(v2);
218         
219         if(v1_locked && v2_locked) {
220         	// both locked, do nothing
221         	return;
222         }
223         Point2D p1 = transform(v1);
224         Point2D p2 = transform(v2);
225         if(p1 == null || p2 == null) return;
226         double xDelta = p1.getX() - p2.getX();
227         double yDelta = p1.getY() - p2.getY();
228 
229         double deltaLength = Math.max(EPSILON, p1.distance(p2));
230 
231         double force = deltaLength  / attraction_constant;
232 
233         assert Double.isNaN(force) == false : "Unexpected mathematical result in FRLayout:calcPositions [force]";
234 
235         double dx = xDelta * force;
236         double dy = yDelta * force;
237         Point2D fvd1 = frVertexData.get(v1);
238         Point2D fvd2 = frVertexData.get(v2);
239         if(v2_locked) {
240         	// double the offset for v1, as v2 will not be moving in
241         	// the opposite direction
242         	fvd1.setLocation(fvd1.getX()-2*dx, fvd1.getY()-2*dy);
243         } else {
244         fvd1.setLocation(fvd1.getX()-dx, fvd1.getY()-dy);
245         }
246         if(v1_locked) {
247         	// double the offset for v2, as v1 will not be moving in
248         	// the opposite direction
249         	fvd2.setLocation(fvd2.getX()+2*dx, fvd2.getY()+2*dy);
250         } else {
251         fvd2.setLocation(fvd2.getX()+dx, fvd2.getY()+dy);
252     }
253     }
254 
255     protected void calcRepulsion(V v1) {
256         Point2D fvd1 = frVertexData.get(v1);
257         if(fvd1 == null) return;
258         fvd1.setLocation(0, 0);
259         boolean v1_locked = isLocked(v1);
260 
261         try {
262             for(V v2 : getGraph().getVertices()) {
263 
264                 boolean v2_locked = isLocked(v2);
265             	if (v1_locked && v2_locked) continue;
266                 if (v1 != v2) {
267                     Point2D p1 = transform(v1);
268                     Point2D p2 = transform(v2);
269                     if(p1 == null || p2 == null) continue;
270                     double xDelta = p1.getX() - p2.getX();
271                     double yDelta = p1.getY() - p2.getY();
272                     
273                     double deltaLength = Math.max(EPSILON, p1.distanceSq(p2));
274                     
275                     double force = (repulsion_constant * repulsion_constant);// / deltaLength;
276                     
277                     double forceOverDeltaLength = force / deltaLength;
278                     
279                     assert Double.isNaN(force) == false : "Unexpected mathematical result in FRLayout:calcPositions [repulsion]";
280                     
281                     if(v2_locked) {
282                     	// double the offset for v1, as v2 will not be moving in
283                     	// the opposite direction
284                     	fvd1.setLocation(fvd1.getX()+2 * xDelta * forceOverDeltaLength,
285                     		fvd1.getY()+ 2 * yDelta * forceOverDeltaLength);
286                     } else {
287                     	fvd1.setLocation(fvd1.getX()+xDelta * forceOverDeltaLength,
288                         		fvd1.getY()+yDelta * forceOverDeltaLength);
289                 }
290             }
291             }
292         } catch(ConcurrentModificationException cme) {
293             calcRepulsion(v1);
294         }
295     }
296 
297     private void cool() {
298         temperature *= (1.0 - currentIteration / (double) maxIterations);
299     }
300 
301     /**
302      * Sets the maximum number of iterations.
303      */
304     public void setMaxIterations(int maxIterations) {
305         this.maxIterations = maxIterations;
306     }
307 
308     /**
309      * This one is an incremental visualization.
310      */
311     public boolean isIncremental() {
312         return true;
313     }
314 
315     /**
316      * Returns true once the current iteration has passed the maximum count,
317      * <tt>MAX_ITERATIONS</tt>.
318      */
319     public boolean done() {
320         if (currentIteration > maxIterations || temperature < 1.0/max_dimension) { 
321             if (!checked)
322             {
323 //                System.out.println("current iteration: " + currentIteration);
324 //                System.out.println("temperature: " + temperature);
325                 checked = true;
326             }
327             return true; 
328         } 
329         return false;
330     }
331 }