KickJava   Java API By Example, From Geeks To Geeks.

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


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.Arrays JavaDoc;
6
7 import prefuse.Constants;
8 import prefuse.Display;
9 import prefuse.data.Graph;
10 import prefuse.data.Schema;
11 import prefuse.data.tuple.TupleSet;
12 import prefuse.util.ArrayLib;
13 import prefuse.visual.NodeItem;
14
15 /**
16  * <p>TreeLayout that computes a tidy layout of a node-link tree
17  * diagram. This algorithm lays out a rooted tree such that each
18  * depth level of the tree is on a shared line. The orientation of the
19  * tree can be set such that the tree goes left-to-right (default),
20  * right-to-left, top-to-bottom, or bottom-to-top.</p>
21  *
22  * <p>The algorithm used is that of Christoph Buchheim, Michael Jünger,
23  * and Sebastian Leipert from their research paper
24  * <a HREF="http://citeseer.ist.psu.edu/buchheim02improving.html">
25  * Improving Walker's Algorithm to Run in Linear Time</a>, Graph Drawing 2002.
26  * This algorithm corrects performance issues in Walker's algorithm, which
27  * generalizes Reingold and Tilford's method for tidy drawings of trees to
28  * support trees with an arbitrary number of children at any given node.</p>
29  *
30  * @author <a HREF="http://jheer.org">jeffrey heer</a>
31  */
32 public class NodeLinkTreeLayout extends TreeLayout {
33     
34     private int m_orientation; // the orientation of the tree
35 private double m_bspace = 5; // the spacing between sibling nodes
36 private double m_tspace = 25; // the spacing between subtrees
37 private double m_dspace = 50; // the spacing between depth levels
38 private double m_offset = 50; // pixel offset for root node position
39
40     private double[] m_depths = new double[10];
41     private int m_maxDepth = 0;
42     
43     private double m_ax, m_ay; // for holding anchor co-ordinates
44
45     /**
46      * Create a new NodeLinkTreeLayout. A left-to-right orientation is assumed.
47      * @param group the data group to layout. Must resolve to a Graph instance.
48      */
49     public NodeLinkTreeLayout(String JavaDoc group) {
50         super(group);
51         m_orientation = Constants.ORIENT_LEFT_RIGHT;
52     }
53     
54     /**
55      * Create a new NodeLinkTreeLayout.
56      * @param group the data group to layout. Must resolve to a Graph instance.
57      * @param orientation the orientation of the tree layout. One of
58      * {@link prefuse.Constants#ORIENT_LEFT_RIGHT},
59      * {@link prefuse.Constants#ORIENT_RIGHT_LEFT},
60      * {@link prefuse.Constants#ORIENT_TOP_BOTTOM}, or
61      * {@link prefuse.Constants#ORIENT_BOTTOM_TOP}.
62      * @param dspace the spacing to maintain between depth levels of the tree
63      * @param bspace the spacing to maintain between sibling nodes
64      * @param tspace the spacing to maintain between neighboring subtrees
65      */
66     public NodeLinkTreeLayout(String JavaDoc group, int orientation,
67             double dspace, double bspace, double tspace)
68     {
69         super(group);
70         m_orientation = orientation;
71         m_dspace = dspace;
72         m_bspace = bspace;
73         m_tspace = tspace;
74     }
75     
76     // ------------------------------------------------------------------------
77
78     /**
79      * Set the orientation of the tree layout.
80      * @param orientation the orientation value. One of
81      * {@link prefuse.Constants#ORIENT_LEFT_RIGHT},
82      * {@link prefuse.Constants#ORIENT_RIGHT_LEFT},
83      * {@link prefuse.Constants#ORIENT_TOP_BOTTOM}, or
84      * {@link prefuse.Constants#ORIENT_BOTTOM_TOP}.
85      */
86     public void setOrientation(int orientation) {
87         if ( orientation < 0 ||
88              orientation >= Constants.ORIENTATION_COUNT ||
89              orientation == Constants.ORIENT_CENTER )
90         {
91             throw new IllegalArgumentException JavaDoc(
92                 "Unsupported orientation value: "+orientation);
93         }
94         m_orientation = orientation;
95     }
96     
97     /**
98      * Get the orientation of the tree layout.
99      * @return the orientation value. One of
100      * {@link prefuse.Constants#ORIENT_LEFT_RIGHT},
101      * {@link prefuse.Constants#ORIENT_RIGHT_LEFT},
102      * {@link prefuse.Constants#ORIENT_TOP_BOTTOM}, or
103      * {@link prefuse.Constants#ORIENT_BOTTOM_TOP}.
104      */
105     public int getOrientation() {
106         return m_orientation;
107     }
108     
109     /**
110      * Set the spacing between depth levels.
111      * @param d the depth spacing to use
112      */
113     public void setDepthSpacing(double d) {
114         m_dspace = d;
115     }
116     
117     /**
118      * Get the spacing between depth levels.
119      * @return the depth spacing
120      */
121     public double getDepthSpacing() {
122         return m_dspace;
123     }
124     
125     /**
126      * Set the spacing between neighbor nodes.
127      * @param b the breadth spacing to use
128      */
129     public void setBreadthSpacing(double b) {
130         m_bspace = b;
131     }
132     
133     /**
134      * Get the spacing between neighbor nodes.
135      * @return the breadth spacing
136      */
137     public double getBreadthSpacing() {
138         return m_bspace;
139     }
140     
141     /**
142      * Set the spacing between neighboring subtrees.
143      * @param s the subtree spacing to use
144      */
145     public void setSubtreeSpacing(double s) {
146         m_tspace = s;
147     }
148     
149     /**
150      * Get the spacing between neighboring subtrees.
151      * @return the subtree spacing
152      */
153     public double getSubtreeSpacing() {
154         return m_tspace;
155     }
156     
157     /**
158      * Set the offset value for placing the root node of the tree. The
159      * dimension in which this offset is applied is dependent upon the
160      * orientation of the tree. For example, in a left-to-right orientation,
161      * the offset will a horizontal offset from the left edge of the layout
162      * bounds.
163      * @param o the value by which to offset the root node of the tree
164      */
165     public void setRootNodeOffset(double o) {
166         m_offset = o;
167     }
168     
169     /**
170      * Get the offset value for placing the root node of the tree.
171      * @return the value by which the root node of the tree is offset
172      */
173     public double getRootNodeOffset() {
174         return m_offset;
175     }
176     
177     // ------------------------------------------------------------------------
178
179     /**
180      * @see prefuse.action.layout.Layout#getLayoutAnchor()
181      */
182     public Point2D JavaDoc getLayoutAnchor() {
183         if ( m_anchor != null )
184             return m_anchor;
185         
186         m_tmpa.setLocation(0,0);
187         if ( m_vis != null ) {
188             Display d = m_vis.getDisplay(0);
189             Rectangle2D JavaDoc b = this.getLayoutBounds();
190             switch ( m_orientation ) {
191             case Constants.ORIENT_LEFT_RIGHT:
192                 m_tmpa.setLocation(m_offset, d.getHeight()/2.0);
193                 break;
194             case Constants.ORIENT_RIGHT_LEFT:
195                 m_tmpa.setLocation(b.getMaxX()-m_offset, d.getHeight()/2.0);
196                 break;
197             case Constants.ORIENT_TOP_BOTTOM:
198                 m_tmpa.setLocation(d.getWidth()/2.0, m_offset);
199                 break;
200             case Constants.ORIENT_BOTTOM_TOP:
201                 m_tmpa.setLocation(d.getWidth()/2.0, b.getMaxY()-m_offset);
202                 break;
203             }
204             d.getInverseTransform().transform(m_tmpa, m_tmpa);
205         }
206         return m_tmpa;
207     }
208     
209     private double spacing(NodeItem l, NodeItem r, boolean siblings) {
210         boolean w = ( m_orientation == Constants.ORIENT_TOP_BOTTOM ||
211                       m_orientation == Constants.ORIENT_BOTTOM_TOP );
212         return (siblings ? m_bspace : m_tspace) + 0.5 *
213             ( w ? l.getBounds().getWidth() + r.getBounds().getWidth()
214                 : l.getBounds().getHeight() + r.getBounds().getHeight() );
215     }
216     
217     private void updateDepths(int depth, NodeItem item) {
218         boolean v = ( m_orientation == Constants.ORIENT_TOP_BOTTOM ||
219                       m_orientation == Constants.ORIENT_BOTTOM_TOP );
220         double d = ( v ? item.getBounds().getHeight()
221                        : item.getBounds().getWidth() );
222         if ( m_depths.length <= depth )
223             m_depths = ArrayLib.resize(m_depths, 3*depth/2);
224         m_depths[depth] = Math.max(m_depths[depth], d);
225         m_maxDepth = Math.max(m_maxDepth, depth);
226     }
227     
228     private void determineDepths() {
229         for ( int i=1; i<m_maxDepth; ++i )
230             m_depths[i] += m_depths[i-1] + m_dspace;
231     }
232     
233     // ------------------------------------------------------------------------
234
235     /**
236      * @see prefuse.action.Action#run(double)
237      */
238     public void run(double frac) {
239         Graph g = (Graph)m_vis.getGroup(m_group);
240         initSchema(g.getNodes());
241         
242         Arrays.fill(m_depths, 0);
243         m_maxDepth = 0;
244         
245         Point2D JavaDoc a = getLayoutAnchor();
246         m_ax = a.getX();
247         m_ay = a.getY();
248         
249         NodeItem root = getLayoutRoot();
250         Params rp = getParams(root);
251         
252         // do first pass - compute breadth information, collect depth info
253 firstWalk(root, 0, 1);
254         
255         // sum up the depth info
256 determineDepths();
257         
258         // do second pass - assign layout positions
259 secondWalk(root, null, -rp.prelim, 0);
260     }
261
262     private void firstWalk(NodeItem n, int num, int depth) {
263         Params np = getParams(n);
264         np.number = num;
265         updateDepths(depth, n);
266         
267         boolean expanded = n.isExpanded();
268         if ( n.getChildCount() == 0 || !expanded ) // is leaf
269 {
270             NodeItem l = (NodeItem)n.getPreviousSibling();
271             if ( l == null ) {
272                 np.prelim = 0;
273             } else {
274                 np.prelim = getParams(l).prelim + spacing(l,n,true);
275             }
276         }
277         else if ( expanded )
278         {
279             NodeItem leftMost = (NodeItem)n.getFirstChild();
280             NodeItem rightMost = (NodeItem)n.getLastChild();
281             NodeItem defaultAncestor = leftMost;
282             NodeItem c = leftMost;
283             for ( int i=0; c != null; ++i, c = (NodeItem)c.getNextSibling() )
284             {
285                 firstWalk(c, i, depth+1);
286                 defaultAncestor = apportion(c, defaultAncestor);
287             }
288             
289             executeShifts(n);
290             
291             double midpoint = 0.5 *
292                 (getParams(leftMost).prelim + getParams(rightMost).prelim);
293             
294             NodeItem left = (NodeItem)n.getPreviousSibling();
295             if ( left != null ) {
296                 np.prelim = getParams(left).prelim + spacing(left, n, true);
297                 np.mod = np.prelim - midpoint;
298             } else {
299                 np.prelim = midpoint;
300             }
301         }
302     }
303     
304     private NodeItem apportion(NodeItem v, NodeItem a) {
305         NodeItem w = (NodeItem)v.getPreviousSibling();
306         if ( w != null ) {
307             NodeItem vip, vim, vop, vom;
308             double sip, sim, sop, som;
309             
310             vip = vop = v;
311             vim = w;
312             vom = (NodeItem)vip.getParent().getFirstChild();
313             
314             sip = getParams(vip).mod;
315             sop = getParams(vop).mod;
316             sim = getParams(vim).mod;
317             som = getParams(vom).mod;
318             
319             NodeItem nr = nextRight(vim);
320             NodeItem nl = nextLeft(vip);
321             while ( nr != null && nl != null ) {
322                 vim = nr;
323                 vip = nl;
324                 vom = nextLeft(vom);
325                 vop = nextRight(vop);
326                 getParams(vop).ancestor = v;
327                 double shift = (getParams(vim).prelim + sim) -
328                     (getParams(vip).prelim + sip) + spacing(vim,vip,false);
329                 if ( shift > 0 ) {
330                     moveSubtree(ancestor(vim,v,a), v, shift);
331                     sip += shift;
332                     sop += shift;
333                 }
334                 sim += getParams(vim).mod;
335                 sip += getParams(vip).mod;
336                 som += getParams(vom).mod;
337                 sop += getParams(vop).mod;
338                 
339                 nr = nextRight(vim);
340                 nl = nextLeft(vip);
341             }
342             if ( nr != null && nextRight(vop) == null ) {
343                 Params vopp = getParams(vop);
344                 vopp.thread = nr;
345                 vopp.mod += sim - sop;
346             }
347             if ( nl != null && nextLeft(vom) == null ) {
348                 Params vomp = getParams(vom);
349                 vomp.thread = nl;
350                 vomp.mod += sip - som;
351                 a = v;
352             }
353         }
354         return a;
355     }
356     
357     private NodeItem nextLeft(NodeItem n) {
358         NodeItem c = null;
359         if ( n.isExpanded() ) c = (NodeItem)n.getFirstChild();
360         return ( c != null ? c : getParams(n).thread );
361     }
362     
363     private NodeItem nextRight(NodeItem n) {
364         NodeItem c = null;
365         if ( n.isExpanded() ) c = (NodeItem)n.getLastChild();
366         return ( c != null ? c : getParams(n).thread );
367     }
368     
369     private void moveSubtree(NodeItem wm, NodeItem wp, double shift) {
370         Params wmp = getParams(wm);
371         Params wpp = getParams(wp);
372         double subtrees = wpp.number - wmp.number;
373         wpp.change -= shift/subtrees;
374         wpp.shift += shift;
375         wmp.change += shift/subtrees;
376         wpp.prelim += shift;
377         wpp.mod += shift;
378     }
379     
380     private void executeShifts(NodeItem n) {
381         double shift = 0, change = 0;
382         for ( NodeItem c = (NodeItem)n.getLastChild();
383               c != null; c = (NodeItem)c.getPreviousSibling() )
384         {
385             Params cp = getParams(c);
386             cp.prelim += shift;
387             cp.mod += shift;
388             change += cp.change;
389             shift += cp.shift + change;
390         }
391     }
392     
393     private NodeItem ancestor(NodeItem vim, NodeItem v, NodeItem a) {
394         NodeItem p = (NodeItem)v.getParent();
395         Params vimp = getParams(vim);
396         if ( vimp.ancestor.getParent() == p ) {
397             return vimp.ancestor;
398         } else {
399             return a;
400         }
401     }
402     
403     private void secondWalk(NodeItem n, NodeItem p, double m, int depth) {
404         Params np = getParams(n);
405         setBreadth(n, p, np.prelim + m);
406         setDepth(n, p, m_depths[depth]);
407         
408         if ( n.isExpanded() ) {
409             depth += 1;
410             for ( NodeItem c = (NodeItem)n.getFirstChild();
411                   c != null; c = (NodeItem)c.getNextSibling() )
412             {
413                 secondWalk(c, n, m + np.mod, depth);
414             }
415         }
416         
417         np.clear();
418     }
419     
420     private void setBreadth(NodeItem n, NodeItem p, double b) {
421         switch ( m_orientation ) {
422         case Constants.ORIENT_LEFT_RIGHT:
423         case Constants.ORIENT_RIGHT_LEFT:
424             setY(n, p, m_ay + b);
425             break;
426         case Constants.ORIENT_TOP_BOTTOM:
427         case Constants.ORIENT_BOTTOM_TOP:
428             setX(n, p, m_ax + b);
429             break;
430         default:
431             throw new IllegalStateException JavaDoc();
432         }
433     }
434     
435     private void setDepth(NodeItem n, NodeItem p, double d) {
436         switch ( m_orientation ) {
437         case Constants.ORIENT_LEFT_RIGHT:
438             setX(n, p, m_ax + d);
439             break;
440         case Constants.ORIENT_RIGHT_LEFT:
441             setX(n, p, m_ax - d);
442             break;
443         case Constants.ORIENT_TOP_BOTTOM:
444             setY(n, p, m_ay + d);
445             break;
446         case Constants.ORIENT_BOTTOM_TOP:
447             setY(n, p, m_ay - d);
448             break;
449         default:
450             throw new IllegalStateException JavaDoc();
451         }
452     }
453     
454     // ------------------------------------------------------------------------
455 // Params Schema
456
457     /**
458      * The data field in which the parameters used by this layout are stored.
459      */
460     public static final String JavaDoc PARAMS = "_reingoldTilfordParams";
461     /**
462      * The schema for the parameters used by this layout.
463      */
464     public static final Schema PARAMS_SCHEMA = new Schema();
465     static {
466         PARAMS_SCHEMA.addColumn(PARAMS, Params.class);
467     }
468     
469     protected void initSchema(TupleSet ts) {
470         ts.addColumns(PARAMS_SCHEMA);
471     }
472     
473     private Params getParams(NodeItem item) {
474         Params rp = (Params)item.get(PARAMS);
475         if ( rp == null ) {
476             rp = new Params();
477             item.set(PARAMS, rp);
478         }
479         if ( rp.number == -2 ) {
480             rp.init(item);
481         }
482         return rp;
483     }
484     
485     /**
486      * Wrapper class holding parameters used for each node in this layout.
487      */
488     public static class Params implements Cloneable JavaDoc {
489         double prelim;
490         double mod;
491         double shift;
492         double change;
493         int number = -2;
494         NodeItem ancestor = null;
495         NodeItem thread = null;
496         
497         public void init(NodeItem item) {
498             ancestor = item;
499             number = -1;
500         }
501         
502         public void clear() {
503             number = -2;
504             prelim = mod = shift = change = 0;
505             ancestor = thread = null;
506         }
507     }
508     
509 } // end of class NodeLinkTreeLayout
510
Popular Tags