001: package prefuse.action.layout.graph;
002:
003: import java.awt.geom.Rectangle2D;
004: import java.util.ArrayList;
005: import java.util.Collections;
006: import java.util.Comparator;
007: import java.util.Iterator;
008: import java.util.List;
009:
010: import prefuse.data.Graph;
011: import prefuse.data.Schema;
012: import prefuse.data.tuple.TupleSet;
013: import prefuse.data.util.TreeNodeIterator;
014: import prefuse.visual.NodeItem;
015: import prefuse.visual.VisualItem;
016:
017: /**
018: * <p>
019: * TreeLayout instance computing a TreeMap layout that optimizes for low
020: * aspect ratios of visualized tree nodes. TreeMaps are a form of space-filling
021: * layout that represents nodes as boxes on the display, with children nodes
022: * represented as boxes placed within their parent's box.
023: * </p>
024: * <p>
025: * This particular algorithm is taken from Bruls, D.M., C. Huizing, and
026: * J.J. van Wijk, "Squarified Treemaps" In <i>Data Visualization 2000,
027: * Proceedings of the Joint Eurographics and IEEE TCVG Sumposium on
028: * Visualization</i>, 2000, pp. 33-42. Available online at:
029: * <a href="http://www.win.tue.nl/~vanwijk/stm.pdf">
030: * http://www.win.tue.nl/~vanwijk/stm.pdf</a>.
031: * </p>
032: * <p>
033: * For more information on TreeMaps in general, see
034: * <a href="http://www.cs.umd.edu/hcil/treemap-history/">
035: * http://www.cs.umd.edu/hcil/treemap-history/</a>.
036: * </p>
037: *
038: * @version 1.0
039: * @author <a href="http://jheer.org">jeffrey heer</a>
040: */
041: public class SquarifiedTreeMapLayout extends TreeLayout {
042:
043: // column value in which layout stores area information
044: public static final String AREA = "_area";
045: public static final Schema AREA_SCHEMA = new Schema();
046: static {
047: AREA_SCHEMA.addColumn(AREA, double.class);
048: }
049:
050: private static Comparator s_cmp = new Comparator() {
051: public int compare(Object o1, Object o2) {
052: double s1 = ((VisualItem) o1).getDouble(AREA);
053: double s2 = ((VisualItem) o2).getDouble(AREA);
054: return (s1 > s2 ? 1 : (s1 < s2 ? -1 : 0));
055: }
056: };
057: private ArrayList m_kids = new ArrayList();
058: private ArrayList m_row = new ArrayList();
059: private Rectangle2D m_r = new Rectangle2D.Double();
060:
061: private double m_frame; // space between parents border and children
062:
063: /**
064: * Creates a new SquarifiedTreeMapLayout with no spacing between
065: * parent areas and their enclosed children.
066: * @param group the data group to layout. Must resolve to a Graph instance.
067: */
068: public SquarifiedTreeMapLayout(String group) {
069: this (group, 0);
070: }
071:
072: /**
073: * Creates a new SquarifiedTreeMapLayout with the specified spacing between
074: * parent areas and their enclosed children.
075: * @param frame the amount of desired framing space between
076: * parent areas and their enclosed children.
077: * @param group the data group to layout. Must resolve to a Graph instance.
078: */
079: public SquarifiedTreeMapLayout(String group, double frame) {
080: super (group);
081: setFrameWidth(frame);
082: }
083:
084: /**
085: * Sets the amount of desired framing space between parent rectangles and
086: * their enclosed children. Use a value of 0 to remove frames altogether.
087: * If you adjust the frame value, you must re-run the layout to see the
088: * change reflected. Negative frame values are not allowed and will result
089: * in an IllegalArgumentException.
090: * @param frame the frame width, 0 for no frames
091: */
092: public void setFrameWidth(double frame) {
093: if (frame < 0)
094: throw new IllegalArgumentException(
095: "Frame value must be greater than or equal to 0.");
096: m_frame = frame;
097: }
098:
099: /**
100: * Gets the amount of desired framing space, in pixels, between
101: * parent rectangles and their enclosed children.
102: * @return the frame width
103: */
104: public double getFrameWidth() {
105: return m_frame;
106: }
107:
108: /**
109: * @see prefuse.action.Action#run(double)
110: */
111: public void run(double frac) {
112: // setup
113: NodeItem root = getLayoutRoot();
114: Rectangle2D b = getLayoutBounds();
115: m_r.setRect(b.getX(), b.getY(), b.getWidth() - 1,
116: 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 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, false);
151: while (iter.hasNext()) {
152: NodeItem n = (NodeItem) iter.next();
153: double area = 0;
154: if (n.getChildCount() == 0) {
155: area = n.getSize();
156: ++leafCount;
157: } else if (n.isExpanded()) {
158: NodeItem c = (NodeItem) n.getFirstChild();
159: for (; c != null; c = (NodeItem) c.getNextSibling()) {
160: area += c.getDouble(AREA);
161: ++leafCount;
162: }
163: }
164: n.setDouble(AREA, area);
165:
166: }
167:
168: // scale sizes by display area factor
169: Rectangle2D b = getLayoutBounds();
170: double area = (b.getWidth() - 1) * (b.getHeight() - 1);
171: double scale = area / root.getDouble(AREA);
172: iter = new TreeNodeIterator(root);
173: while (iter.hasNext()) {
174: NodeItem n = (NodeItem) iter.next();
175: n.setDouble(AREA, n.getDouble(AREA) * scale);
176: }
177: }
178:
179: /**
180: * Compute the tree map layout.
181: */
182: private void layout(NodeItem p, Rectangle2D r) {
183: // create sorted list of children
184: Iterator childIter = p.children();
185: while (childIter.hasNext())
186: m_kids.add(childIter.next());
187: Collections.sort(m_kids, s_cmp);
188:
189: // do squarified layout of siblings
190: double w = Math.min(r.getWidth(), r.getHeight());
191: squarify(m_kids, m_row, w, r);
192: m_kids.clear(); // clear m_kids
193:
194: // recurse
195: childIter = p.children();
196: while (childIter.hasNext()) {
197: NodeItem c = (NodeItem) childIter.next();
198: if (c.getChildCount() > 0 && c.getDouble(AREA) > 0) {
199: updateArea(c, r);
200: layout(c, r);
201: }
202: }
203: }
204:
205: private void updateArea(NodeItem n, Rectangle2D r) {
206: Rectangle2D b = n.getBounds();
207: if (m_frame == 0.0) {
208: // if no framing, simply update bounding rectangle
209: r.setRect(b);
210: return;
211: }
212:
213: // compute area loss due to frame
214: double dA = 2 * m_frame
215: * (b.getWidth() + b.getHeight() - 2 * m_frame);
216: double A = n.getDouble(AREA) - dA;
217:
218: // compute renormalization factor
219: double s = 0;
220: Iterator childIter = n.children();
221: while (childIter.hasNext())
222: s += ((NodeItem) childIter.next()).getDouble(AREA);
223: double t = A / s;
224:
225: // re-normalize children areas
226: childIter = n.children();
227: while (childIter.hasNext()) {
228: NodeItem c = (NodeItem) childIter.next();
229: c.setDouble(AREA, c.getDouble(AREA) * t);
230: }
231:
232: // set bounding rectangle and return
233: r.setRect(b.getX() + m_frame, b.getY() + m_frame, b.getWidth()
234: - 2 * m_frame, b.getHeight() - 2 * m_frame);
235: return;
236: }
237:
238: private void squarify(List c, List row, double w, Rectangle2D r) {
239: double worst = Double.MAX_VALUE, nworst;
240: int len;
241:
242: while ((len = c.size()) > 0) {
243: // add item to the row list, ignore if negative area
244: VisualItem item = (VisualItem) c.get(len - 1);
245: double a = item.getDouble(AREA);
246: if (a <= 0.0) {
247: c.remove(len - 1);
248: continue;
249: }
250: row.add(item);
251:
252: nworst = worst(row, w);
253: if (nworst <= worst) {
254: c.remove(len - 1);
255: worst = nworst;
256: } else {
257: row.remove(row.size() - 1); // remove the latest addition
258: r = layoutRow(row, w, r); // layout the current row
259: w = Math.min(r.getWidth(), r.getHeight()); // recompute w
260: row.clear(); // clear the row
261: worst = Double.MAX_VALUE;
262: }
263: }
264: if (row.size() > 0) {
265: r = layoutRow(row, w, r); // layout the current row
266: row.clear(); // clear the row
267: }
268: }
269:
270: private double worst(List rlist, double w) {
271: double rmax = Double.MIN_VALUE, rmin = Double.MAX_VALUE, s = 0.0;
272: Iterator iter = rlist.iterator();
273: while (iter.hasNext()) {
274: double r = ((VisualItem) iter.next()).getDouble(AREA);
275: rmin = Math.min(rmin, r);
276: rmax = Math.max(rmax, r);
277: s += r;
278: }
279: s = s * s;
280: w = w * w;
281: return Math.max(w * rmax / s, s / (w * rmin));
282: }
283:
284: private Rectangle2D layoutRow(List row, double w, Rectangle2D r) {
285: double s = 0; // sum of row areas
286: Iterator rowIter = row.iterator();
287: while (rowIter.hasNext())
288: s += ((VisualItem) rowIter.next()).getDouble(AREA);
289: double x = r.getX(), y = r.getY(), d = 0;
290: double h = w == 0 ? 0 : s / w;
291: boolean horiz = (w == r.getWidth());
292:
293: // set node positions and dimensions
294: rowIter = row.iterator();
295: while (rowIter.hasNext()) {
296: NodeItem n = (NodeItem) rowIter.next();
297: NodeItem p = (NodeItem) n.getParent();
298: if (horiz) {
299: setX(n, p, x + d);
300: setY(n, p, y);
301: } else {
302: setX(n, p, x);
303: setY(n, p, y + d);
304: }
305: double nw = n.getDouble(AREA) / h;
306: if (horiz) {
307: setNodeDimensions(n, nw, h);
308: d += nw;
309: } else {
310: setNodeDimensions(n, h, nw);
311: d += nw;
312: }
313: }
314: // update space available in rectangle r
315: if (horiz)
316: r.setRect(x, y + h, r.getWidth(), r.getHeight() - h);
317: else
318: r.setRect(x + h, y, r.getWidth() - h, r.getHeight());
319: return r;
320: }
321:
322: private void setNodeDimensions(NodeItem n, double w, double h) {
323: n.setBounds(n.getX(), n.getY(), w, h);
324: }
325:
326: } // end of class SquarifiedTreeMapLayout
|