KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > netbeans > modules > xml > nbprefuse > layout > NbFruchtermanReingoldLayout


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