KickJava   Java API By Example, From Geeks To Geeks.

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


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.data.Graph;
8 import prefuse.data.Node;
9 import prefuse.data.Schema;
10 import prefuse.data.tuple.TupleSet;
11 import prefuse.util.ArrayLib;
12 import prefuse.util.MathLib;
13 import prefuse.visual.NodeItem;
14
15
16 /**
17  * <p>TreeLayout instance that computes a radial layout, laying out subsequent
18  * depth levels of a tree on circles of progressively increasing radius.
19  * </p>
20  *
21  * <p>The algorithm used is that of Ka-Ping Yee, Danyel Fisher, Rachna Dhamija,
22  * and Marti Hearst in their research paper
23  * <a HREF="http://citeseer.ist.psu.edu/448292.html">Animated Exploration of
24  * Dynamic Graphs with Radial Layout</a>, InfoVis 2001. This algorithm computes
25  * a radial layout which factors in possible variation in sizes, and maintains
26  * both orientation and ordering constraints to facilitate smooth and
27  * understandable transitions between layout configurations.
28  * </p>
29  *
30  * @author <a HREF="http://jheer.org">jeffrey heer</a>
31  */
32 public class RadialTreeLayout extends TreeLayout {
33     
34     public static final int DEFAULT_RADIUS = 50;
35     private static final int MARGIN = 30;
36
37     protected int m_maxDepth = 0;
38     protected double m_radiusInc;
39     protected double m_theta1, m_theta2;
40     protected boolean m_setTheta = false;
41     protected boolean m_autoScale = true;
42     
43     protected Point2D JavaDoc m_origin;
44     protected NodeItem m_prevRoot;
45     
46     /**
47      * Creates a new RadialTreeLayout. Automatic scaling of the radius
48      * values to fit the layout bounds is enabled by default.
49      * @param group the data group to process. This should resolve to
50      * either a Graph or Tree instance.
51      */
52     public RadialTreeLayout(String JavaDoc group) {
53         super(group);
54         m_radiusInc = DEFAULT_RADIUS;
55         m_prevRoot = null;
56         m_theta1 = 0;
57         m_theta2 = m_theta1 + MathLib.TWO_PI;
58     }
59     
60     /**
61      * Creates a new RadialTreeLayout using the specified radius increment
62      * between levels of the layout. Automatic scaling of the radius values
63      * is disabled by default.
64      * @param group the data group to process. This should resolve to
65      * either a Graph or Tree instance.
66      * @param radius the radius increment to use between subsequent rings
67      * in the layout.
68      */
69     public RadialTreeLayout(String JavaDoc group, int radius) {
70         this(group);
71         m_radiusInc = radius;
72         m_autoScale = false;
73     }
74
75     /**
76      * Set the radius increment to use between concentric circles. Note
77      * that this value is used only if auto-scaling is disabled.
78      * @return the radius increment between subsequent rings of the layout
79      * when auto-scaling is disabled
80      */
81     public double getRadiusIncrement() {
82         return m_radiusInc;
83     }
84     
85     /**
86      * Set the radius increment to use between concentric circles. Note
87      * that this value is used only if auto-scaling is disabled.
88      * @param inc the radius increment between subsequent rings of the layout
89      * @see #setAutoScale(boolean)
90      */
91     public void setRadiusIncrement(double inc) {
92         m_radiusInc = inc;
93     }
94
95     /**
96      * Indicates if the layout automatically scales to fit the layout bounds.
97      * @return true if auto-scaling is enabled, false otherwise
98      */
99     public boolean getAutoScale() {
100         return m_autoScale;
101     }
102     
103     /**
104      * Set whether or not the layout should automatically scale itself
105      * to fit the layout bounds.
106      * @param s true to automatically scale to fit display, false otherwise
107      */
108     public void setAutoScale(boolean s) {
109         m_autoScale = s;
110     }
111
112     /**
113      * Constrains this layout to the specified angular sector
114      * @param theta the starting angle, in radians
115      * @param width the angular width, in radians
116      */
117     public void setAngularBounds(double theta, double width) {
118         m_theta1 = theta;
119         m_theta2 = theta+width;
120         m_setTheta = true;
121     }
122
123     /**
124      * @see prefuse.action.Action#run(double)
125      */
126     public void run(double frac) {
127         Graph g = (Graph)m_vis.getGroup(m_group);
128         initSchema(g.getNodes());
129         
130         m_origin = getLayoutAnchor();
131         NodeItem n = getLayoutRoot();
132         Params np = (Params)n.get(PARAMS);
133         
134         // calc relative widths and maximum tree depth
135 // performs one pass over the tree
136 m_maxDepth = 0;
137         calcAngularWidth(n, 0);
138         
139         if ( m_autoScale ) setScale(getLayoutBounds());
140         if ( !m_setTheta ) calcAngularBounds(n);
141                 
142         // perform the layout
143 if ( m_maxDepth > 0 )
144             layout(n, m_radiusInc, m_theta1, m_theta2);
145         
146         // update properties of the root node
147 setX(n, null, m_origin.getX());
148         setY(n, null, m_origin.getY());
149         np.angle = m_theta2-m_theta1;
150     }
151     
152     protected void setScale(Rectangle2D JavaDoc bounds) {
153         double r = Math.min(bounds.getWidth(),bounds.getHeight())/2.0;
154         if ( m_maxDepth > 0 )
155             m_radiusInc = (r-MARGIN)/m_maxDepth;
156     }
157
158     /**
159      * Calculates the angular bounds of the layout, attempting to
160      * preserve the angular orientation of the display across transitions.
161      */
162     private void calcAngularBounds(NodeItem r) {
163         if ( m_prevRoot == null || !m_prevRoot.isValid() || r == m_prevRoot )
164         {
165             m_prevRoot = r;
166             return;
167         }
168         
169         // try to find previous parent of root
170 NodeItem p = m_prevRoot;
171         while ( true ) {
172             NodeItem pp = (NodeItem)p.getParent();
173             if ( pp == r ) {
174                 break;
175             } else if ( pp == null ) {
176                 m_prevRoot = r;
177                 return;
178             }
179             p = pp;
180         }
181
182         // compute offset due to children's angular width
183 double dt = 0;
184         Iterator JavaDoc iter = sortedChildren(r);
185         while ( iter.hasNext() ) {
186             Node n = (Node)iter.next();
187             if ( n == p ) break;
188             dt += ((Params)n.get(PARAMS)).width;
189         }
190         double rw = ((Params)r.get(PARAMS)).width;
191         double pw = ((Params)p.get(PARAMS)).width;
192         dt = -MathLib.TWO_PI * (dt+pw/2)/rw;
193
194         // set angular bounds
195 m_theta1 = dt + Math.atan2(p.getY()-r.getY(), p.getX()-r.getX());
196         m_theta2 = m_theta1 + MathLib.TWO_PI;
197         m_prevRoot = r;
198     }
199
200     /**
201      * Computes relative measures of the angular widths of each
202      * expanded subtree. Node diameters are taken into account
203      * to improve space allocation for variable-sized nodes.
204      *
205      * This method also updates the base angle value for nodes
206      * to ensure proper ordering of nodes.
207      */
208     private double calcAngularWidth(NodeItem n, int d) {
209         if ( d > m_maxDepth ) m_maxDepth = d;
210         double aw = 0;
211         
212         Rectangle2D JavaDoc bounds = n.getBounds();
213         double w = bounds.getWidth(), h = bounds.getHeight();
214         double diameter = d==0 ? 0 : Math.sqrt(w*w+h*h) / d;
215         
216         if ( n.isExpanded() && n.getChildCount() > 0 ) {
217             Iterator JavaDoc childIter = n.children();
218             while ( childIter.hasNext() ) {
219                 NodeItem c = (NodeItem)childIter.next();
220                 aw += calcAngularWidth(c,d+1);
221             }
222             aw = Math.max(diameter, aw);
223         } else {
224             aw = diameter;
225         }
226         ((Params)n.get(PARAMS)).width = aw;
227         return aw;
228     }
229     
230     private static final double normalize(double angle) {
231         while ( angle > MathLib.TWO_PI ) {
232             angle -= MathLib.TWO_PI;
233         }
234         while ( angle < 0 ) {
235             angle += MathLib.TWO_PI;
236         }
237         return angle;
238     }
239     
240     private Iterator JavaDoc sortedChildren(final NodeItem n) {
241         double base = 0;
242         // update base angle for node ordering
243 NodeItem p = (NodeItem)n.getParent();
244         if ( p != null ) {
245             base = normalize(Math.atan2(p.getY()-n.getY(), p.getX()-n.getX()));
246         }
247         int cc = n.getChildCount();
248         if ( cc == 0 ) return null;
249
250         NodeItem c = (NodeItem)n.getFirstChild();
251         
252         // TODO: this is hacky and will break when filtering
253 // how to know that a branch is newly expanded?
254 // is there an alternative property we should check?
255 if ( !c.isStartVisible() ) {
256             // use natural ordering for previously invisible nodes
257 return n.children();
258         }
259         
260         double angle[] = new double[cc];
261         final int idx[] = new int[cc];
262         for ( int i=0; i<cc; ++i, c=(NodeItem)c.getNextSibling() ) {
263             idx[i] = i;
264             angle[i] = normalize(-base +
265                 Math.atan2(c.getY()-n.getY(), c.getX()-n.getX()));
266         }
267         ArrayLib.sort(angle, idx);
268         
269         // return iterator over sorted children
270 return new Iterator JavaDoc() {
271             int cur = 0;
272             public Object JavaDoc next() {
273                 return n.getChild(idx[cur++]);
274             }
275             public boolean hasNext() {
276                 return cur < idx.length;
277             }
278             public void remove() {
279                 throw new UnsupportedOperationException JavaDoc();
280             }
281         };
282     }
283     
284     /**
285      * Compute the layout.
286      * @param n the root of the current subtree under consideration
287      * @param r the radius, current distance from the center
288      * @param theta1 the start (in radians) of this subtree's angular region
289      * @param theta2 the end (in radians) of this subtree's angular region
290      */
291     protected void layout(NodeItem n, double r, double theta1, double theta2) {
292         double dtheta = (theta2-theta1);
293         double dtheta2 = dtheta / 2.0;
294         double width = ((Params)n.get(PARAMS)).width;
295         double cfrac, nfrac = 0.0;
296         
297         Iterator JavaDoc childIter = sortedChildren(n);
298         while ( childIter != null && childIter.hasNext() ) {
299             NodeItem c = (NodeItem)childIter.next();
300             Params cp = (Params)c.get(PARAMS);
301             cfrac = cp.width / width;
302             if ( c.isExpanded() && c.getChildCount()>0 ) {
303                 layout(c, r+m_radiusInc, theta1 + nfrac*dtheta,
304                                          theta1 + (nfrac+cfrac)*dtheta);
305             }
306             setPolarLocation(c, n, r, theta1 + nfrac*dtheta + cfrac*dtheta2);
307             cp.angle = cfrac*dtheta;
308             nfrac += cfrac;
309         }
310         
311     }
312
313     /**
314      * Set the position of the given node, given in polar co-ordinates.
315      * @param n the NodeItem to set the position
316      * @param p the referrer parent NodeItem
317      * @param r the radius
318      * @param t the angle theta
319      */
320     protected void setPolarLocation(NodeItem n, NodeItem p, double r, double t) {
321         setX(n, p, m_origin.getX() + r*Math.cos(t));
322         setY(n, p, m_origin.getY() + r*Math.sin(t));
323     }
324     
325     // ------------------------------------------------------------------------
326 // Params
327
328     /**
329      * The data field in which the parameters used by this layout are stored.
330      */
331     public static final String JavaDoc PARAMS = "_radialTreeLayoutParams";
332     /**
333      * The schema for the parameters used by this layout.
334      */
335     public static final Schema PARAMS_SCHEMA = new Schema();
336     static {
337         PARAMS_SCHEMA.addColumn(PARAMS, Params.class, new Params());
338     }
339     
340     protected void initSchema(TupleSet ts) {
341         ts.addColumns(PARAMS_SCHEMA);
342     }
343     
344     /**
345      * Wrapper class holding parameters used for each node in this layout.
346      */
347     public static class Params implements Cloneable JavaDoc {
348         double width;
349         double angle;
350         public Object JavaDoc clone() {
351             Params p = new Params();
352             p.width = this.width;
353             p.angle = this.angle;
354             return p;
355         }
356     }
357
358 } // end of class RadialTreeLayout
359
Popular Tags