KickJava   Java API By Example, From Geeks To Geeks.

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


1 package prefuse.action.layout.graph;
2
3 import java.awt.geom.Rectangle2D JavaDoc;
4 import java.util.ArrayList JavaDoc;
5 import java.util.Collections JavaDoc;
6 import java.util.Comparator JavaDoc;
7 import java.util.Iterator JavaDoc;
8 import java.util.List JavaDoc;
9
10 import prefuse.data.Graph;
11 import prefuse.data.Schema;
12 import prefuse.data.tuple.TupleSet;
13 import prefuse.data.util.TreeNodeIterator;
14 import prefuse.visual.NodeItem;
15 import prefuse.visual.VisualItem;
16
17
18 /**
19  * <p>
20  * TreeLayout instance computing a TreeMap layout that optimizes for low
21  * aspect ratios of visualized tree nodes. TreeMaps are a form of space-filling
22  * layout that represents nodes as boxes on the display, with children nodes
23  * represented as boxes placed within their parent's box.
24  * </p>
25  * <p>
26  * This particular algorithm is taken from Bruls, D.M., C. Huizing, and
27  * J.J. van Wijk, "Squarified Treemaps" In <i>Data Visualization 2000,
28  * Proceedings of the Joint Eurographics and IEEE TCVG Sumposium on
29  * Visualization</i>, 2000, pp. 33-42. Available online at:
30  * <a HREF="http://www.win.tue.nl/~vanwijk/stm.pdf">
31  * http://www.win.tue.nl/~vanwijk/stm.pdf</a>.
32  * </p>
33  * <p>
34  * For more information on TreeMaps in general, see
35  * <a HREF="http://www.cs.umd.edu/hcil/treemap-history/">
36  * http://www.cs.umd.edu/hcil/treemap-history/</a>.
37  * </p>
38  *
39  * @version 1.0
40  * @author <a HREF="http://jheer.org">jeffrey heer</a>
41  */
42 public class SquarifiedTreeMapLayout extends TreeLayout {
43
44     // column value in which layout stores area information
45 public static final String JavaDoc AREA = "_area";
46     public static final Schema AREA_SCHEMA = new Schema();
47     static {
48         AREA_SCHEMA.addColumn(AREA, double.class);
49     }
50     
51     private static Comparator JavaDoc s_cmp = new Comparator JavaDoc() {
52         public int compare(Object JavaDoc o1, Object JavaDoc o2) {
53             double s1 = ((VisualItem)o1).getDouble(AREA);
54             double s2 = ((VisualItem)o2).getDouble(AREA);
55             return ( s1>s2 ? 1 : (s1<s2 ? -1 : 0));
56         }
57     };
58     private ArrayList JavaDoc m_kids = new ArrayList JavaDoc();
59     private ArrayList JavaDoc m_row = new ArrayList JavaDoc();
60     private Rectangle2D JavaDoc m_r = new Rectangle2D.Double JavaDoc();
61     
62     private double m_frame; // space between parents border and children
63
64     /**
65      * Creates a new SquarifiedTreeMapLayout with no spacing between
66      * parent areas and their enclosed children.
67      * @param group the data group to layout. Must resolve to a Graph instance.
68      */
69     public SquarifiedTreeMapLayout(String JavaDoc group) {
70         this(group, 0);
71     }
72     
73     /**
74      * Creates a new SquarifiedTreeMapLayout with the specified spacing between
75      * parent areas and their enclosed children.
76      * @param frame the amount of desired framing space between
77      * parent areas and their enclosed children.
78      * @param group the data group to layout. Must resolve to a Graph instance.
79      */
80     public SquarifiedTreeMapLayout(String JavaDoc group, double frame) {
81         super(group);
82         setFrameWidth(frame);
83     }
84     
85     /**
86      * Sets the amount of desired framing space between parent rectangles and
87      * their enclosed children. Use a value of 0 to remove frames altogether.
88      * If you adjust the frame value, you must re-run the layout to see the
89      * change reflected. Negative frame values are not allowed and will result
90      * in an IllegalArgumentException.
91      * @param frame the frame width, 0 for no frames
92      */
93     public void setFrameWidth(double frame) {
94         if ( frame < 0 )
95             throw new IllegalArgumentException JavaDoc(
96                     "Frame value must be greater than or equal to 0.");
97         m_frame = frame;
98     }
99
100     /**
101      * Gets the amount of desired framing space, in pixels, between
102      * parent rectangles and their enclosed children.
103      * @return the frame width
104      */
105     public double getFrameWidth() {
106         return m_frame;
107     }
108     
109     /**
110      * @see prefuse.action.Action#run(double)
111      */
112     public void run(double frac) {
113         // setup
114 NodeItem root = getLayoutRoot();
115         Rectangle2D JavaDoc b = getLayoutBounds();
116         m_r.setRect(b.getX(), b.getY(), b.getWidth()-1, b.getHeight()-1);
117         
118         // process size values
119 computeAreas(root);
120         
121         // layout root node
122 setX(root, null, 0);
123         setY(root, null, 0);
124         root.setBounds(0, 0, m_r.getWidth(), m_r.getHeight());
125
126         // layout the tree
127 updateArea(root, m_r);
128         layout(root, m_r);
129     }
130     
131     /**
132      * Compute the pixel areas of nodes based on their size values.
133      */
134     private void computeAreas(NodeItem root) {
135         int leafCount = 0;
136         
137         // ensure area data column exists
138 Graph g = (Graph)m_vis.getGroup(m_group);
139         TupleSet nodes = g.getNodes();
140         nodes.addColumns(AREA_SCHEMA);
141         
142         // reset all sizes to zero
143 Iterator JavaDoc iter = new TreeNodeIterator(root);
144         while ( iter.hasNext() ) {
145             NodeItem n = (NodeItem)iter.next();
146             n.setDouble(AREA, 0);
147         }
148         
149         // set raw sizes, compute leaf count
150 iter = new TreeNodeIterator(root);
151         while ( iter.hasNext() ) {
152             NodeItem n = (NodeItem)iter.next();
153             if ( n.getChildCount() == 0 ) {
154                 double sz = n.getSize();
155                 n.setDouble(AREA, sz);
156                 NodeItem p = (NodeItem)n.getParent();
157                 for (; p!=null; p=(NodeItem)p.getParent())
158                     p.setDouble(AREA, sz + p.getDouble(AREA));
159                 ++leafCount;
160             }
161         }
162         
163         // scale sizes by display area factor
164 Rectangle2D JavaDoc b = getLayoutBounds();
165         double area = (b.getWidth()-1)*(b.getHeight()-1);
166         double scale = area/root.getDouble(AREA);
167         iter = new TreeNodeIterator(root);
168         while ( iter.hasNext() ) {
169             NodeItem n = (NodeItem)iter.next();
170             n.setDouble(AREA, n.getDouble(AREA)*scale);
171         }
172     }
173     
174     /**
175      * Compute the tree map layout.
176      */
177     private void layout(NodeItem p, Rectangle2D JavaDoc r) {
178         // create sorted list of children
179 Iterator JavaDoc childIter = p.children();
180         while ( childIter.hasNext() )
181             m_kids.add(childIter.next());
182         Collections.sort(m_kids, s_cmp);
183         
184         // do squarified layout of siblings
185 double w = Math.min(r.getWidth(),r.getHeight());
186         squarify(m_kids, m_row, w, r);
187         m_kids.clear(); // clear m_kids
188
189         // recurse
190 childIter = p.children();
191         while ( childIter.hasNext() ) {
192             NodeItem c = (NodeItem)childIter.next();
193             if ( c.getChildCount() > 0 ) {
194                 updateArea(c,r);
195                 layout(c, r);
196             }
197         }
198     }
199     
200     private void updateArea(NodeItem n, Rectangle2D JavaDoc r) {
201         Rectangle2D JavaDoc b = n.getBounds();
202         if ( m_frame == 0.0 ) {
203             // if no framing, simply update bounding rectangle
204 r.setRect(b);
205             return;
206         }
207         
208         // compute area loss due to frame
209 double dA = 2*m_frame*(b.getWidth()+b.getHeight()-2*m_frame);
210         double A = n.getDouble(AREA) - dA;
211         
212         // compute renormalization factor
213 double s = 0;
214         Iterator JavaDoc childIter = n.children();
215         while ( childIter.hasNext() )
216             s += ((NodeItem)childIter.next()).getDouble(AREA);
217         double t = A/s;
218         
219         // re-normalize children areas
220 childIter = n.children();
221         while ( childIter.hasNext() ) {
222             NodeItem c = (NodeItem)childIter.next();
223             c.setDouble(AREA, c.getDouble(AREA)*t);
224         }
225         
226         // set bounding rectangle and return
227 r.setRect(b.getX()+m_frame, b.getY()+m_frame,
228                   b.getWidth()-2*m_frame, b.getHeight()-2*m_frame);
229         return;
230     }
231     
232     private void squarify(List JavaDoc c, List JavaDoc row, double w, Rectangle2D JavaDoc r) {
233         double worst = Double.MAX_VALUE, nworst;
234         int len;
235         
236         while ( (len=c.size()) > 0 ) {
237             // add item to the row list, ignore if negative area
238 VisualItem item = (VisualItem) c.get(len-1);
239             double a = item.getDouble(AREA);
240             if (a <= 0.0) {
241                 c.remove(len-1);
242                 continue;
243             }
244             row.add(item);
245             
246             nworst = worst(row, w);
247             if ( nworst <= worst ) {
248                 c.remove(len-1);
249                 worst = nworst;
250             } else {
251                 row.remove(row.size()-1); // remove the latest addition
252 r = layoutRow(row, w, r); // layout the current row
253 w = Math.min(r.getWidth(),r.getHeight()); // recompute w
254 row.clear(); // clear the row
255 worst = Double.MAX_VALUE;
256             }
257         }
258         if ( row.size() > 0 ) {
259             r = layoutRow(row, w, r); // layout the current row
260 row.clear(); // clear the row
261 }
262     }
263
264     private double worst(List JavaDoc rlist, double w) {
265         double rmax = Double.MIN_VALUE, rmin = Double.MAX_VALUE, s = 0.0;
266         Iterator JavaDoc iter = rlist.iterator();
267         while ( iter.hasNext() ) {
268             double r = ((VisualItem)iter.next()).getDouble(AREA);
269             rmin = Math.min(rmin, r);
270             rmax = Math.max(rmax, r);
271             s += r;
272         }
273         s = s*s; w = w*w;
274         return Math.max(w*rmax/s, s/(w*rmin));
275     }
276     
277     private Rectangle2D JavaDoc layoutRow(List JavaDoc row, double w, Rectangle2D JavaDoc r) {
278         double s = 0; // sum of row areas
279 Iterator JavaDoc rowIter = row.iterator();
280         while ( rowIter.hasNext() )
281             s += ((VisualItem)rowIter.next()).getDouble(AREA);
282         double x = r.getX(), y = r.getY(), d = 0;
283         double h = w==0 ? 0 : s/w;
284         boolean horiz = (w == r.getWidth());
285         
286         // set node positions and dimensions
287 rowIter = row.iterator();
288         while ( rowIter.hasNext() ) {
289             NodeItem n = (NodeItem)rowIter.next();
290             NodeItem p = (NodeItem)n.getParent();
291             if ( horiz ) {
292                 setX(n, p, x+d);
293                 setY(n, p, y);
294             } else {
295                 setX(n, p, x);
296                 setY(n, p, y+d);
297             }
298             double nw = n.getDouble(AREA)/h;
299             if ( horiz ) {
300                 setNodeDimensions(n,nw,h);
301                 d += nw;
302             } else {
303                 setNodeDimensions(n,h,nw);
304                 d += nw;
305             }
306         }
307         // update space available in rectangle r
308 if ( horiz )
309             r.setRect(x,y+h,r.getWidth(),r.getHeight()-h);
310         else
311             r.setRect(x+h,y,r.getWidth()-h,r.getHeight());
312         return r;
313     }
314     
315     private void setNodeDimensions(NodeItem n, double w, double h) {
316         n.setBounds(n.getX(), n.getY(), w, h);
317     }
318     
319 } // end of class SquarifiedTreeMapLayout
320
Popular Tags