001: package prefuse.action.layout.graph;
002:
003: import java.awt.geom.Point2D;
004: import java.awt.geom.Rectangle2D;
005: import java.util.Iterator;
006:
007: import prefuse.data.Graph;
008: import prefuse.data.Node;
009: import prefuse.data.Schema;
010: import prefuse.data.tuple.TupleSet;
011: import prefuse.util.ArrayLib;
012: import prefuse.util.MathLib;
013: import prefuse.visual.NodeItem;
014:
015: /**
016: * <p>TreeLayout instance that computes a radial layout, laying out subsequent
017: * depth levels of a tree on circles of progressively increasing radius.
018: * </p>
019: *
020: * <p>The algorithm used is that of Ka-Ping Yee, Danyel Fisher, Rachna Dhamija,
021: * and Marti Hearst in their research paper
022: * <a href="http://citeseer.ist.psu.edu/448292.html">Animated Exploration of
023: * Dynamic Graphs with Radial Layout</a>, InfoVis 2001. This algorithm computes
024: * a radial layout which factors in possible variation in sizes, and maintains
025: * both orientation and ordering constraints to facilitate smooth and
026: * understandable transitions between layout configurations.
027: * </p>
028: *
029: * @author <a href="http://jheer.org">jeffrey heer</a>
030: */
031: public class RadialTreeLayout extends TreeLayout {
032:
033: public static final int DEFAULT_RADIUS = 50;
034: private static final int MARGIN = 30;
035:
036: protected int m_maxDepth = 0;
037: protected double m_radiusInc;
038: protected double m_theta1, m_theta2;
039: protected boolean m_setTheta = false;
040: protected boolean m_autoScale = true;
041:
042: protected Point2D m_origin;
043: protected NodeItem m_prevRoot;
044:
045: /**
046: * Creates a new RadialTreeLayout. Automatic scaling of the radius
047: * values to fit the layout bounds is enabled by default.
048: * @param group the data group to process. This should resolve to
049: * either a Graph or Tree instance.
050: */
051: public RadialTreeLayout(String group) {
052: super (group);
053: m_radiusInc = DEFAULT_RADIUS;
054: m_prevRoot = null;
055: m_theta1 = 0;
056: m_theta2 = m_theta1 + MathLib.TWO_PI;
057: }
058:
059: /**
060: * Creates a new RadialTreeLayout using the specified radius increment
061: * between levels of the layout. Automatic scaling of the radius values
062: * is disabled by default.
063: * @param group the data group to process. This should resolve to
064: * either a Graph or Tree instance.
065: * @param radius the radius increment to use between subsequent rings
066: * in the layout.
067: */
068: public RadialTreeLayout(String group, int radius) {
069: this (group);
070: m_radiusInc = radius;
071: m_autoScale = false;
072: }
073:
074: /**
075: * Set the radius increment to use between concentric circles. Note
076: * that this value is used only if auto-scaling is disabled.
077: * @return the radius increment between subsequent rings of the layout
078: * when auto-scaling is disabled
079: */
080: public double getRadiusIncrement() {
081: return m_radiusInc;
082: }
083:
084: /**
085: * Set the radius increment to use between concentric circles. Note
086: * that this value is used only if auto-scaling is disabled.
087: * @param inc the radius increment between subsequent rings of the layout
088: * @see #setAutoScale(boolean)
089: */
090: public void setRadiusIncrement(double inc) {
091: m_radiusInc = inc;
092: }
093:
094: /**
095: * Indicates if the layout automatically scales to fit the layout bounds.
096: * @return true if auto-scaling is enabled, false otherwise
097: */
098: public boolean getAutoScale() {
099: return m_autoScale;
100: }
101:
102: /**
103: * Set whether or not the layout should automatically scale itself
104: * to fit the layout bounds.
105: * @param s true to automatically scale to fit display, false otherwise
106: */
107: public void setAutoScale(boolean s) {
108: m_autoScale = s;
109: }
110:
111: /**
112: * Constrains this layout to the specified angular sector
113: * @param theta the starting angle, in radians
114: * @param width the angular width, in radians
115: */
116: public void setAngularBounds(double theta, double width) {
117: m_theta1 = theta;
118: m_theta2 = theta + width;
119: m_setTheta = true;
120: }
121:
122: /**
123: * @see prefuse.action.Action#run(double)
124: */
125: public void run(double frac) {
126: Graph g = (Graph) m_vis.getGroup(m_group);
127: initSchema(g.getNodes());
128:
129: m_origin = getLayoutAnchor();
130: NodeItem n = getLayoutRoot();
131: Params np = (Params) n.get(PARAMS);
132:
133: // calc relative widths and maximum tree depth
134: // performs one pass over the tree
135: m_maxDepth = 0;
136: calcAngularWidth(n, 0);
137:
138: if (m_autoScale)
139: setScale(getLayoutBounds());
140: if (!m_setTheta)
141: calcAngularBounds(n);
142:
143: // perform the layout
144: if (m_maxDepth > 0)
145: layout(n, m_radiusInc, m_theta1, m_theta2);
146:
147: // update properties of the root node
148: setX(n, null, m_origin.getX());
149: setY(n, null, m_origin.getY());
150: np.angle = m_theta2 - m_theta1;
151: }
152:
153: protected void setScale(Rectangle2D bounds) {
154: double r = Math.min(bounds.getWidth(), bounds.getHeight()) / 2.0;
155: if (m_maxDepth > 0)
156: m_radiusInc = (r - MARGIN) / m_maxDepth;
157: }
158:
159: /**
160: * Calculates the angular bounds of the layout, attempting to
161: * preserve the angular orientation of the display across transitions.
162: */
163: private void calcAngularBounds(NodeItem r) {
164: if (m_prevRoot == null || !m_prevRoot.isValid()
165: || r == m_prevRoot) {
166: m_prevRoot = r;
167: return;
168: }
169:
170: // try to find previous parent of root
171: NodeItem p = m_prevRoot;
172: while (true) {
173: NodeItem pp = (NodeItem) p.getParent();
174: if (pp == r) {
175: break;
176: } else if (pp == null) {
177: m_prevRoot = r;
178: return;
179: }
180: p = pp;
181: }
182:
183: // compute offset due to children's angular width
184: double dt = 0;
185: Iterator iter = sortedChildren(r);
186: while (iter.hasNext()) {
187: Node n = (Node) iter.next();
188: if (n == p)
189: break;
190: dt += ((Params) n.get(PARAMS)).width;
191: }
192: double rw = ((Params) r.get(PARAMS)).width;
193: double pw = ((Params) p.get(PARAMS)).width;
194: dt = -MathLib.TWO_PI * (dt + pw / 2) / rw;
195:
196: // set angular bounds
197: m_theta1 = dt
198: + Math.atan2(p.getY() - r.getY(), p.getX() - r.getX());
199: m_theta2 = m_theta1 + MathLib.TWO_PI;
200: m_prevRoot = r;
201: }
202:
203: /**
204: * Computes relative measures of the angular widths of each
205: * expanded subtree. Node diameters are taken into account
206: * to improve space allocation for variable-sized nodes.
207: *
208: * This method also updates the base angle value for nodes
209: * to ensure proper ordering of nodes.
210: */
211: private double calcAngularWidth(NodeItem n, int d) {
212: if (d > m_maxDepth)
213: m_maxDepth = d;
214: double aw = 0;
215:
216: Rectangle2D bounds = n.getBounds();
217: double w = bounds.getWidth(), h = bounds.getHeight();
218: double diameter = d == 0 ? 0 : Math.sqrt(w * w + h * h) / d;
219:
220: if (n.isExpanded() && n.getChildCount() > 0) {
221: Iterator childIter = n.children();
222: while (childIter.hasNext()) {
223: NodeItem c = (NodeItem) childIter.next();
224: aw += calcAngularWidth(c, d + 1);
225: }
226: aw = Math.max(diameter, aw);
227: } else {
228: aw = diameter;
229: }
230: ((Params) n.get(PARAMS)).width = aw;
231: return aw;
232: }
233:
234: private static final double normalize(double angle) {
235: while (angle > MathLib.TWO_PI) {
236: angle -= MathLib.TWO_PI;
237: }
238: while (angle < 0) {
239: angle += MathLib.TWO_PI;
240: }
241: return angle;
242: }
243:
244: private Iterator sortedChildren(final NodeItem n) {
245: double base = 0;
246: // update base angle for node ordering
247: NodeItem p = (NodeItem) n.getParent();
248: if (p != null) {
249: base = normalize(Math.atan2(p.getY() - n.getY(), p.getX()
250: - n.getX()));
251: }
252: int cc = n.getChildCount();
253: if (cc == 0)
254: return null;
255:
256: NodeItem c = (NodeItem) n.getFirstChild();
257:
258: // TODO: this is hacky and will break when filtering
259: // how to know that a branch is newly expanded?
260: // is there an alternative property we should check?
261: if (!c.isStartVisible()) {
262: // use natural ordering for previously invisible nodes
263: return n.children();
264: }
265:
266: double angle[] = new double[cc];
267: final int idx[] = new int[cc];
268: for (int i = 0; i < cc; ++i, c = (NodeItem) c.getNextSibling()) {
269: idx[i] = i;
270: angle[i] = normalize(-base
271: + Math.atan2(c.getY() - n.getY(), c.getX()
272: - n.getX()));
273: }
274: ArrayLib.sort(angle, idx);
275:
276: // return iterator over sorted children
277: return new Iterator() {
278: int cur = 0;
279:
280: public Object next() {
281: return n.getChild(idx[cur++]);
282: }
283:
284: public boolean hasNext() {
285: return cur < idx.length;
286: }
287:
288: public void remove() {
289: throw new UnsupportedOperationException();
290: }
291: };
292: }
293:
294: /**
295: * Compute the layout.
296: * @param n the root of the current subtree under consideration
297: * @param r the radius, current distance from the center
298: * @param theta1 the start (in radians) of this subtree's angular region
299: * @param theta2 the end (in radians) of this subtree's angular region
300: */
301: protected void layout(NodeItem n, double r, double theta1,
302: double theta2) {
303: double dtheta = (theta2 - theta1);
304: double dtheta2 = dtheta / 2.0;
305: double width = ((Params) n.get(PARAMS)).width;
306: double cfrac, nfrac = 0.0;
307:
308: Iterator childIter = sortedChildren(n);
309: while (childIter != null && childIter.hasNext()) {
310: NodeItem c = (NodeItem) childIter.next();
311: Params cp = (Params) c.get(PARAMS);
312: cfrac = cp.width / width;
313: if (c.isExpanded() && c.getChildCount() > 0) {
314: layout(c, r + m_radiusInc, theta1 + nfrac * dtheta,
315: theta1 + (nfrac + cfrac) * dtheta);
316: }
317: setPolarLocation(c, n, r, theta1 + nfrac * dtheta + cfrac
318: * dtheta2);
319: cp.angle = cfrac * dtheta;
320: nfrac += cfrac;
321: }
322:
323: }
324:
325: /**
326: * Set the position of the given node, given in polar co-ordinates.
327: * @param n the NodeItem to set the position
328: * @param p the referrer parent NodeItem
329: * @param r the radius
330: * @param t the angle theta
331: */
332: protected void setPolarLocation(NodeItem n, NodeItem p, double r,
333: double t) {
334: setX(n, p, m_origin.getX() + r * Math.cos(t));
335: setY(n, p, m_origin.getY() + r * Math.sin(t));
336: }
337:
338: // ------------------------------------------------------------------------
339: // Params
340:
341: /**
342: * The data field in which the parameters used by this layout are stored.
343: */
344: public static final String PARAMS = "_radialTreeLayoutParams";
345: /**
346: * The schema for the parameters used by this layout.
347: */
348: public static final Schema PARAMS_SCHEMA = new Schema();
349: static {
350: PARAMS_SCHEMA.addColumn(PARAMS, Params.class, new Params());
351: }
352:
353: protected void initSchema(TupleSet ts) {
354: ts.addColumns(PARAMS_SCHEMA);
355: }
356:
357: /**
358: * Wrapper class holding parameters used for each node in this layout.
359: */
360: public static class Params implements Cloneable {
361: double width;
362: double angle;
363:
364: public Object clone() {
365: Params p = new Params();
366: p.width = this .width;
367: p.angle = this .angle;
368: return p;
369: }
370: }
371:
372: } // end of class RadialTreeLayout
|