KickJava   Java API By Example, From Geeks To Geeks.

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


1 package prefuse.action.layout.graph;
2
3 import java.awt.geom.Rectangle2D JavaDoc;
4 import java.util.Iterator JavaDoc;
5 import java.util.Random 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.visual.EdgeItem;
13 import prefuse.visual.NodeItem;
14 import prefuse.visual.VisualItem;
15
16
17 /**
18  * <p>Layout instance implementing the Fruchterman-Reingold algorithm for
19  * force-directed placement of graph nodes. The computational complexity of
20  * this algorithm is quadratic [O(n^2)] in the number of nodes, so should
21  * only be applied for relatively small graphs, particularly in interactive
22  * situations.</p>
23  *
24  * <p>This implementation was ported from the implementation in the
25  * <a HREF="http://jung.sourceforge.net/">JUNG</a> framework.</p>
26  *
27  * @author Scott White, Yan-Biao Boey, Danyel Fisher
28  * @author <a HREF="http://jheer.org">jeffrey heer</a>
29  */
30 public class FruchtermanReingoldLayout extends Layout {
31
32     private double forceConstant;
33     private double temp;
34     private int maxIter = 700;
35     
36     protected String JavaDoc m_nodeGroup;
37     protected String JavaDoc m_edgeGroup;
38     protected int m_fidx;
39     
40     private static final double EPSILON = 0.000001D;
41     private static final double ALPHA = 0.1;
42     
43     /**
44      * Create a new FruchtermanReingoldLayout.
45      * @param graph the data field to layout. Must resolve to a Graph instance.
46      */
47     public FruchtermanReingoldLayout(String JavaDoc graph) {
48         this(graph, 700);
49     }
50     
51     /**
52      * Create a new FruchtermanReingoldLayout
53      * @param graph the data field to layout. Must resolve to a Graph instance.
54      * @param maxIter the maximum number of iterations of the algorithm to run
55      */
56     public FruchtermanReingoldLayout(String JavaDoc graph, int maxIter) {
57         super(graph);
58         m_nodeGroup = PrefuseLib.getGroupName(graph, Graph.NODES);
59         m_edgeGroup = PrefuseLib.getGroupName(graph, Graph.EDGES);
60         this.maxIter = maxIter;
61     }
62     
63     /**
64      * Get the maximum number of iterations to run of this algorithm.
65      * @return the maximum number of iterations
66      */
67     public int getMaxIterations() {
68         return maxIter;
69     }
70     
71     /**
72      * Set the maximum number of iterations to run of this algorithm.
73      * @param maxIter the maximum number of iterations to use
74      */
75     public void setMaxIterations(int maxIter) {
76         this.maxIter = maxIter;
77     }
78     
79     /**
80      * @see prefuse.action.Action#run(double)
81      */
82     public void run(double frac) {
83         Graph g = (Graph)m_vis.getGroup(m_group);
84         Rectangle2D JavaDoc bounds = super.getLayoutBounds();
85         init(g, bounds);
86
87         for (int curIter=0; curIter < maxIter; curIter++ ) {
88
89             // Calculate repulsion
90 for (Iterator JavaDoc iter = g.nodes(); iter.hasNext();) {
91                 NodeItem n = (NodeItem)iter.next();
92                 if (n.isFixed()) continue;
93                 calcRepulsion(g, n);
94             }
95
96             // Calculate attraction
97 for (Iterator JavaDoc iter = g.edges(); iter.hasNext();) {
98                 EdgeItem e = (EdgeItem) iter.next();
99                 calcAttraction(e);
100             }
101
102             for (Iterator JavaDoc iter = g.nodes(); iter.hasNext();) {
103                 NodeItem n = (NodeItem)iter.next();
104                 if (n.isFixed()) continue;
105                 calcPositions(n,bounds);
106             }
107
108             cool(curIter);
109         }
110         
111         finish(g);
112     }
113     
114     private void init(Graph g, Rectangle2D JavaDoc b) {
115         initSchema(g.getNodes());
116         
117         temp = b.getWidth() / 10;
118         forceConstant = 0.75 *
119             Math.sqrt(b.getHeight()*b.getWidth()/g.getNodeCount());
120         
121         // initialize node positions
122 Iterator JavaDoc nodeIter = g.nodes();
123         Random JavaDoc rand = new Random JavaDoc(42); // get a deterministic layout result
124 double scaleW = ALPHA*b.getWidth()/2;
125         double scaleH = ALPHA*b.getHeight()/2;
126         while ( nodeIter.hasNext() ) {
127             NodeItem n = (NodeItem)nodeIter.next();
128             Params np = getParams(n);
129             np.loc[0] = b.getCenterX() + rand.nextDouble()*scaleW;
130             np.loc[1] = b.getCenterY() + rand.nextDouble()*scaleH;
131         }
132     }
133     
134     private void finish(Graph g) {
135         Iterator JavaDoc nodeIter = g.nodes();
136         while ( nodeIter.hasNext() ) {
137             NodeItem n = (NodeItem)nodeIter.next();
138             Params np = getParams(n);
139             setX(n, null, np.loc[0]);
140             setY(n, null, np.loc[1]);
141         }
142     }
143     
144     public void calcPositions(NodeItem n, Rectangle2D JavaDoc b) {
145         Params np = getParams(n);
146         double deltaLength = Math.max(EPSILON,
147                 Math.sqrt(np.disp[0]*np.disp[0] + np.disp[1]*np.disp[1]));
148         
149         double xDisp = np.disp[0]/deltaLength * Math.min(deltaLength, temp);
150
151         if (Double.isNaN(xDisp)) {
152             System.err.println("Mathematical error... (calcPositions:xDisp)");
153          }
154
155         double yDisp = np.disp[1]/deltaLength * Math.min(deltaLength, temp);
156         
157         np.loc[0] += xDisp;
158         np.loc[1] += yDisp;
159
160         // don't let nodes leave the display
161 double borderWidth = b.getWidth() / 50.0;
162         double x = np.loc[0];
163         if (x < b.getMinX() + borderWidth) {
164             x = b.getMinX() + borderWidth + Math.random() * borderWidth * 2.0;
165         } else if (x > (b.getMaxX() - borderWidth)) {
166             x = b.getMaxX() - borderWidth - Math.random() * borderWidth * 2.0;
167         }
168
169         double y = np.loc[1];
170         if (y < b.getMinY() + borderWidth) {
171             y = b.getMinY() + borderWidth + Math.random() * borderWidth * 2.0;
172         } else if (y > (b.getMaxY() - borderWidth)) {
173             y = b.getMaxY() - borderWidth - Math.random() * borderWidth * 2.0;
174         }
175
176         np.loc[0] = x;
177         np.loc[1] = y;
178     }
179
180     public void calcAttraction(EdgeItem e) {
181         NodeItem n1 = e.getSourceItem();
182         Params n1p = getParams(n1);
183         NodeItem n2 = e.getTargetItem();
184         Params n2p = getParams(n2);
185         
186         double xDelta = n1p.loc[0] - n2p.loc[0];
187         double yDelta = n1p.loc[1] - n2p.loc[1];
188
189         double deltaLength = Math.max(EPSILON,
190                 Math.sqrt(xDelta*xDelta + yDelta*yDelta));
191         double force = (deltaLength*deltaLength) / forceConstant;
192
193         if (Double.isNaN(force)) {
194             System.err.println("Mathematical error...");
195         }
196
197         double xDisp = (xDelta/deltaLength) * force;
198         double yDisp = (yDelta/deltaLength) * force;
199         
200         n1p.disp[0] -= xDisp; n1p.disp[1] -= yDisp;
201         n2p.disp[0] += xDisp; n2p.disp[1] += yDisp;
202     }
203
204     public void calcRepulsion(Graph g, NodeItem n1) {
205         Params np = getParams(n1);
206         np.disp[0] = 0.0; np.disp[1] = 0.0;
207
208         for (Iterator JavaDoc iter2 = g.nodes(); iter2.hasNext();) {
209             NodeItem n2 = (NodeItem) iter2.next();
210             Params n2p = getParams(n2);
211             if (n2.isFixed()) continue;
212             if (n1 != n2) {
213                 double xDelta = np.loc[0] - n2p.loc[0];
214                 double yDelta = np.loc[1] - n2p.loc[1];
215
216                 double deltaLength = Math.max(EPSILON,
217                         Math.sqrt(xDelta*xDelta + yDelta*yDelta));
218
219                 double force = (forceConstant*forceConstant) / deltaLength;
220
221                 if (Double.isNaN(force)) {
222                     System.err.println("Mathematical error...");
223                 }
224
225                 np.disp[0] += (xDelta/deltaLength)*force;
226                 np.disp[1] += (yDelta/deltaLength)*force;
227             }
228         }
229     }
230     
231     private void cool(int curIter) {
232         temp *= (1.0 - curIter / (double) maxIter);
233     }
234
235     // ------------------------------------------------------------------------
236 // Params Schema
237
238     /**
239      * The data field in which the parameters used by this layout are stored.
240      */
241     public static final String JavaDoc PARAMS = "_fruchtermanReingoldParams";
242     /**
243      * The schema for the parameters used by this layout.
244      */
245     public static final Schema PARAMS_SCHEMA = new Schema();
246     static {
247         PARAMS_SCHEMA.addColumn(PARAMS, Params.class);
248     }
249     
250     protected void initSchema(TupleSet ts) {
251         try {
252             ts.addColumns(PARAMS_SCHEMA);
253         } catch ( IllegalArgumentException JavaDoc iae ) {};
254     }
255     
256     private Params getParams(VisualItem item) {
257         Params rp = (Params)item.get(PARAMS);
258         if ( rp == null ) {
259             rp = new Params();
260             item.set(PARAMS, rp);
261         }
262         return rp;
263     }
264     
265     /**
266      * Wrapper class holding parameters used for each node in this layout.
267      */
268     public static class Params implements Cloneable JavaDoc {
269         double[] loc = new double[2];
270         double[] disp = new double[2];
271     }
272     
273 } // end of class FruchtermanReingoldLayout
274
Popular Tags