KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > prefuse > action > layout > graph > ForceDirectedLayout


1 package prefuse.action.layout.graph;
2
3 import java.awt.geom.Point2D JavaDoc;
4 import java.awt.geom.Rectangle2D JavaDoc;
5 import java.util.Iterator JavaDoc;
6
7 import prefuse.action.layout.Layout;
8 import prefuse.data.Graph;
9 import prefuse.data.Schema;
10 import prefuse.data.tuple.TupleSet;
11 import prefuse.util.PrefuseLib;
12 import prefuse.util.force.DragForce;
13 import prefuse.util.force.ForceItem;
14 import prefuse.util.force.ForceSimulator;
15 import prefuse.util.force.NBodyForce;
16 import prefuse.util.force.SpringForce;
17 import prefuse.visual.EdgeItem;
18 import prefuse.visual.NodeItem;
19 import prefuse.visual.VisualItem;
20
21
22 /**
23  * <p>Layout that positions graph elements based on a physics simulation of
24  * interacting forces; by default, nodes repel each other, edges act as
25  * springs, and drag forces (similar to air resistance) are applied. This
26  * algorithm can be run for multiple iterations for a run-once layout
27  * computation or repeatedly run in an animated fashion for a dynamic and
28  * interactive layout.</p>
29  *
30  * <p>The running time of this layout algorithm is the greater of O(N log N)
31  * and O(E), where N is the number of nodes and E the number of edges.
32  * The addition of custom force calculation modules may, however, increase
33  * this value.</p>
34  *
35  * <p>The {@link prefuse.util.force.ForceSimulator} used to drive this layout
36  * can be set explicitly, allowing any number of custom force directed layouts
37  * to be created through the user's selection of included
38  * {@link prefuse.util.force.Force} components. Each node in the layout is
39  * mapped to a {@link prefuse.util.force.ForceItem} instance and each edge
40  * to a {@link prefuse.util.force.Spring} instance for storing the state
41  * of the simulation. See the {@link prefuse.util.force} package for more.</p>
42  *
43  * @author <a HREF="http://jheer.org">jeffrey heer</a>
44  */

45 public class ForceDirectedLayout extends Layout {
46     
47     private ForceSimulator m_fsim;
48     private long m_lasttime = -1L;
49     private long m_maxstep = 50L;
50     private boolean m_runonce;
51     private int m_iterations = 100;
52     private boolean m_enforceBounds;
53     
54     protected transient VisualItem referrer;
55     
56     protected String JavaDoc m_nodeGroup;
57     protected String JavaDoc m_edgeGroup;
58     
59     /**
60      * Create a new ForceDirectedLayout. By default, this layout will not
61      * restrict the layout to the layout bounds and will assume it is being
62      * run in animated (rather than run-once) fashion.
63      * @param graph the data group to layout. Must resolve to a Graph instance.
64      */

65     public ForceDirectedLayout(String JavaDoc graph)
66     {
67         this(graph, false, false);
68     }
69
70     /**
71      * Create a new ForceDirectedLayout. The layout will assume it is being
72      * run in animated (rather than run-once) fashion.
73      * @param group the data group to layout. Must resolve to a Graph instance.
74      * @param enforceBounds indicates whether or not the layout should require
75      * that all node placements stay within the layout bounds.
76      */

77     public ForceDirectedLayout(String JavaDoc group, boolean enforceBounds)
78     {
79         this(group, enforceBounds, false);
80     }
81     
82     /**
83      * Create a new ForceDirectedLayout.
84      * @param group the data group to layout. Must resolve to a Graph instance.
85      * @param enforceBounds indicates whether or not the layout should require
86      * that all node placements stay within the layout bounds.
87      * @param runonce indicates if the layout will be run in a run-once or
88      * animated fashion. In run-once mode, the layout will run for a set number
89      * of iterations when invoked. In animation mode, only one iteration of the
90      * layout is computed.
91      */

92     public ForceDirectedLayout(String JavaDoc group,
93             boolean enforceBounds, boolean runonce)
94     {
95         super(group);
96         m_nodeGroup = PrefuseLib.getGroupName(group, Graph.NODES);
97         m_edgeGroup = PrefuseLib.getGroupName(group, Graph.EDGES);
98         
99         m_enforceBounds = enforceBounds;
100         m_runonce = runonce;
101         m_fsim = new ForceSimulator();
102         m_fsim.addForce(new NBodyForce());
103         m_fsim.addForce(new SpringForce());
104         m_fsim.addForce(new DragForce());
105     }
106     
107     /**
108      * Create a new ForceDirectedLayout. The layout will assume it is being
109      * run in animated (rather than run-once) fashion.
110      * @param group the data group to layout. Must resolve to a Graph instance.
111      * @param fsim the force simulator used to drive the layout computation
112      * @param enforceBounds indicates whether or not the layout should require
113      * that all node placements stay within the layout bounds.
114      */

115     public ForceDirectedLayout(String JavaDoc group,
116             ForceSimulator fsim, boolean enforceBounds) {
117         this(group, fsim, enforceBounds, false);
118     }
119     
120     /**
121      * Create a new ForceDirectedLayout.
122      * @param group the data group to layout. Must resolve to a Graph instance.
123      * @param fsim the force simulator used to drive the layout computation
124      * @param enforceBounds indicates whether or not the layout should require
125      * that all node placements stay within the layout bounds.
126      * @param runonce indicates if the layout will be run in a run-once or
127      * animated fashion. In run-once mode, the layout will run for a set number
128      * of iterations when invoked. In animation mode, only one iteration of the
129      * layout is computed.
130      */

131     public ForceDirectedLayout(String JavaDoc group, ForceSimulator fsim,
132             boolean enforceBounds, boolean runonce)
133     {
134         super(group);
135         m_nodeGroup = PrefuseLib.getGroupName(group, Graph.NODES);
136         m_edgeGroup = PrefuseLib.getGroupName(group, Graph.EDGES);
137         
138         m_enforceBounds = enforceBounds;
139         m_runonce = runonce;
140         m_fsim = fsim;
141     }
142     
143     // ------------------------------------------------------------------------
144

145     /**
146      * Get the maximum timestep allowed for integrating node settings between
147      * runs of this layout. When computation times are longer than desired,
148      * and node positions are changing dramatically between animated frames,
149      * the max step time can be lowered to suppress node movement.
150      * @return the maximum timestep allowed for integrating between two
151      * layout steps.
152      */

153     public long getMaxTimeStep() {
154         return m_maxstep;
155     }
156
157     /**
158      * Set the maximum timestep allowed for integrating node settings between
159      * runs of this layout. When computation times are longer than desired,
160      * and node positions are changing dramatically between animated frames,
161      * the max step time can be lowered to suppress node movement.
162      * @param maxstep the maximum timestep allowed for integrating between two
163      * layout steps
164      */

165     public void setMaxTimeStep(long maxstep) {
166         this.m_maxstep = maxstep;
167     }
168     
169     /**
170      * Get the force simulator driving this layout.
171      * @return the force simulator
172      */

173     public ForceSimulator getForceSimulator() {
174         return m_fsim;
175     }
176     
177     /**
178      * Set the force simulator driving this layout.
179      * @param fsim the force simulator
180      */

181     public void setForceSimulator(ForceSimulator fsim) {
182         m_fsim = fsim;
183     }
184     
185     /**
186      * Get the number of iterations to use when computing a layout in
187      * run-once mode.
188      * @return the number of layout iterations to run
189      */

190     public int getIterations() {
191         return m_iterations;
192     }
193
194     /**
195      * Set the number of iterations to use when computing a layout in
196      * run-once mode.
197      * @param iter the number of layout iterations to run
198      */

199     public void setIterations(int iter) {
200         if ( iter < 1 )
201             throw new IllegalArgumentException JavaDoc(
202                     "Iterations must be a positive number!");
203         m_iterations = iter;
204     }
205     
206     /**
207      * Explicitly sets the node and edge groups to use for this layout,
208      * overriding the group setting passed to the constructor.
209      * @param nodeGroup the node data group
210      * @param edgeGroup the edge data group
211      */

212     public void setDataGroups(String JavaDoc nodeGroup, String JavaDoc edgeGroup) {
213         m_nodeGroup = nodeGroup;
214         m_edgeGroup = edgeGroup;
215     }
216     
217     // ------------------------------------------------------------------------
218

219     /**
220      * @see prefuse.action.Action#run(double)
221      */

222     public void run(double frac) {
223         // perform different actions if this is a run-once or
224
// run-continuously layout
225
if ( m_runonce ) {
226             Point2D JavaDoc anchor = getLayoutAnchor();
227             Iterator JavaDoc iter = m_vis.visibleItems(m_nodeGroup);
228             while ( iter.hasNext() ) {
229                 VisualItem item = (NodeItem)iter.next();
230                 item.setX(anchor.getX());
231                 item.setY(anchor.getY());
232             }
233             m_fsim.clear();
234             long timestep = 1000L;
235             initSimulator(m_fsim);
236             for ( int i = 0; i < m_iterations; i++ ) {
237                 // use an annealing schedule to set time step
238
timestep *= (1.0 - i/(double)m_iterations);
239                 long step = timestep+50;
240                 // run simulator
241
m_fsim.runSimulator(step);
242                 // debugging output
243
// if (i % 10 == 0 ) {
244
// System.out.println("iter: "+i);
245
// }
246
}
247             updateNodePositions();
248         } else {
249             // get timestep
250
if ( m_lasttime == -1 )
251                 m_lasttime = System.currentTimeMillis()-20;
252             long time = System.currentTimeMillis();
253             long timestep = Math.min(m_maxstep, time - m_lasttime);
254             m_lasttime = time;
255             
256             // run force simulator
257
m_fsim.clear();
258             initSimulator(m_fsim);
259             m_fsim.runSimulator(timestep);
260             updateNodePositions();
261         }
262         if ( frac == 1.0 ) {
263             reset();
264         }
265     }
266
267     private void updateNodePositions() {
268         Rectangle2D JavaDoc bounds = getLayoutBounds();
269         double x1=0, x2=0, y1=0, y2=0;
270         if ( bounds != null ) {
271             x1 = bounds.getMinX(); y1 = bounds.getMinY();
272             x2 = bounds.getMaxX(); y2 = bounds.getMaxY();
273         }
274         
275         // update positions
276
Iterator JavaDoc iter = m_vis.visibleItems(m_nodeGroup);
277         while ( iter.hasNext() ) {
278             VisualItem item = (VisualItem)iter.next();
279             ForceItem fitem = (ForceItem)item.get(FORCEITEM);
280             
281             if ( item.isFixed() ) {
282                 // clear any force computations
283
fitem.force[0] = 0.0f;
284                 fitem.force[1] = 0.0f;
285                 fitem.velocity[0] = 0.0f;
286                 fitem.velocity[1] = 0.0f;
287                 
288                 if ( Double.isNaN(item.getX()) ) {
289                     setX(item, referrer, 0.0);
290                     setY(item, referrer, 0.0);
291                 }
292                 continue;
293             }
294             
295             double x = fitem.location[0];
296             double y = fitem.location[1];
297             
298             if ( m_enforceBounds && bounds != null) {
299                 Rectangle2D JavaDoc b = item.getBounds();
300                 double hw = b.getWidth()/2;
301                 double hh = b.getHeight()/2;
302                 if ( x+hw > x2 ) x = x2-hw;
303                 if ( x-hw < x1 ) x = x1+hw;
304                 if ( y+hh > y2 ) y = y2-hh;
305                 if ( y-hh < y1 ) y = y1+hh;
306             }
307             
308             // set the actual position
309
setX(item, referrer, x);
310             setY(item, referrer, y);
311         }
312     }
313     
314     /**
315      * Reset the force simulation state for all nodes processed
316      * by this layout.
317      */

318     public void reset() {
319         Iterator JavaDoc iter = m_vis.visibleItems(m_nodeGroup);
320         while ( iter.hasNext() ) {
321             VisualItem item = (VisualItem)iter.next();
322             ForceItem fitem = (ForceItem)item.get(FORCEITEM);
323             if ( fitem != null ) {
324                 fitem.location[0] = (float)item.getEndX();
325                 fitem.location[1] = (float)item.getEndY();
326                 fitem.force[0] = fitem.force[1] = 0;
327                 fitem.velocity[0] = fitem.velocity[1] = 0;
328             }
329         }
330         m_lasttime = -1L;
331     }
332     
333     /**
334      * Loads the simulator with all relevant force items and springs.
335      * @param fsim the force simulator driving this layout
336      */

337     protected void initSimulator(ForceSimulator fsim) {
338         // make sure we have force items to work with
339
TupleSet ts = m_vis.getGroup(m_nodeGroup);
340         if ( ts == null ) return;
341         try {
342             ts.addColumns(FORCEITEM_SCHEMA);
343         } catch ( IllegalArgumentException JavaDoc iae ) { /* ignored */ }
344         
345         float startX = (referrer == null ? 0f : (float)referrer.getX());
346         float startY = (referrer == null ? 0f : (float)referrer.getY());
347         startX = Float.isNaN(startX) ? 0f : startX;
348         startY = Float.isNaN(startY) ? 0f : startY;
349        
350         Iterator JavaDoc iter = m_vis.visibleItems(m_nodeGroup);
351         while ( iter.hasNext() ) {
352             VisualItem item = (VisualItem)iter.next();
353             ForceItem fitem = (ForceItem)item.get(FORCEITEM);
354             fitem.mass = getMassValue(item);
355             double x = item.getEndX();
356             double y = item.getEndY();
357             fitem.location[0] = (Double.isNaN(x) ? startX : (float)x);
358             fitem.location[1] = (Double.isNaN(y) ? startY : (float)y);
359             fsim.addItem(fitem);
360         }
361         if ( m_edgeGroup != null ) {
362             iter = m_vis.visibleItems(m_edgeGroup);
363             while ( iter.hasNext() ) {
364                 EdgeItem e = (EdgeItem)iter.next();
365                 NodeItem n1 = e.getSourceItem();
366                 ForceItem f1 = (ForceItem)n1.get(FORCEITEM);
367                 NodeItem n2 = e.getTargetItem();
368                 ForceItem f2 = (ForceItem)n2.get(FORCEITEM);
369                 float coeff = getSpringCoefficient(e);
370                 float slen = getSpringLength(e);
371                 fsim.addSpring(f1, f2, (coeff>=0?coeff:-1.f), (slen>=0?slen:-1.f));
372             }
373         }
374     }
375     
376     /**
377      * Get the mass value associated with the given node. Subclasses should
378      * override this method to perform custom mass assignment.
379      * @param n the node for which to compute the mass value
380      * @return the mass value for the node. By default, all items are given
381      * a mass value of 1.0.
382      */

383     protected float getMassValue(VisualItem n) {
384         return 1.0f;
385     }
386     
387     /**
388      * Get the spring length for the given edge. Subclasses should
389      * override this method to perform custom spring length assignment.
390      * @param e the edge for which to compute the spring length
391      * @return the spring length for the edge. A return value of
392      * -1 means to ignore this method and use the global default.
393      */

394     protected float getSpringLength(EdgeItem e) {
395         return -1.f;
396     }
397
398     /**
399      * Get the spring coefficient for the given edge, which controls the
400      * tension or strength of the spring. Subclasses should
401      * override this method to perform custom spring tension assignment.
402      * @param e the edge for which to compute the spring coefficient.
403      * @return the spring coefficient for the edge. A return value of
404      * -1 means to ignore this method and use the global default.
405      */

406     protected float getSpringCoefficient(EdgeItem e) {
407         return -1.f;
408     }
409     
410     /**
411      * Get the referrer item to use to set x or y coordinates that are
412      * initialized to NaN.
413      * @return the referrer item.
414      * @see prefuse.util.PrefuseLib#setX(VisualItem, VisualItem, double)
415      * @see prefuse.util.PrefuseLib#setY(VisualItem, VisualItem, double)
416      */

417     public VisualItem getReferrer() {
418         return referrer;
419     }
420     
421     /**
422      * Set the referrer item to use to set x or y coordinates that are
423      * initialized to NaN.
424      * @param referrer the referrer item to use.
425      * @see prefuse.util.PrefuseLib#setX(VisualItem, VisualItem, double)
426      * @see prefuse.util.PrefuseLib#setY(VisualItem, VisualItem, double)
427      */

428     public void setReferrer(VisualItem referrer) {
429         this.referrer = referrer;
430     }
431     
432     // ------------------------------------------------------------------------
433
// ForceItem Schema Addition
434

435     /**
436      * The data field in which the parameters used by this layout are stored.
437      */

438     public static final String JavaDoc FORCEITEM = "_forceItem";
439     /**
440      * The schema for the parameters used by this layout.
441      */

442     public static final Schema FORCEITEM_SCHEMA = new Schema();
443     static {
444         FORCEITEM_SCHEMA.addColumn(FORCEITEM,
445                                    ForceItem.class,
446                                    new ForceItem());
447     }
448     
449 } // end of class ForceDirectedLayout
450
Popular Tags