package prefuse.action.layout.graph; import java.awt.geom.Point2D; import java.awt.geom.Rectangle2D; import java.util.Arrays; import prefuse.Constants; import prefuse.Display; import prefuse.data.Graph; import prefuse.data.Schema; import prefuse.data.tuple.TupleSet; import prefuse.util.ArrayLib; import prefuse.visual.NodeItem; /** *
TreeLayout that computes a tidy layout of a node-link tree * diagram. This algorithm lays out a rooted tree such that each * depth level of the tree is on a shared line. The orientation of the * tree can be set such that the tree goes left-to-right (default), * right-to-left, top-to-bottom, or bottom-to-top.
* *The algorithm used is that of Christoph Buchheim, Michael Jünger, * and Sebastian Leipert from their research paper * * Improving Walker's Algorithm to Run in Linear Time, Graph Drawing 2002. * This algorithm corrects performance issues in Walker's algorithm, which * generalizes Reingold and Tilford's method for tidy drawings of trees to * support trees with an arbitrary number of children at any given node.
* * @author jeffrey heer */ public class NodeLinkTreeLayout extends TreeLayout { private int m_orientation; // the orientation of the tree private double m_bspace = 5; // the spacing between sibling nodes private double m_tspace = 25; // the spacing between subtrees private double m_dspace = 50; // the spacing between depth levels private double m_offset = 50; // pixel offset for root node position private double[] m_depths = new double[10]; private int m_maxDepth = 0; private double m_ax, m_ay; // for holding anchor co-ordinates /** * Create a new NodeLinkTreeLayout. A left-to-right orientation is assumed. * @param group the data group to layout. Must resolve to a Graph instance. */ public NodeLinkTreeLayout(String group) { super(group); m_orientation = Constants.ORIENT_LEFT_RIGHT; } /** * Create a new NodeLinkTreeLayout. * @param group the data group to layout. Must resolve to a Graph instance. * @param orientation the orientation of the tree layout. One of * {@link prefuse.Constants#ORIENT_LEFT_RIGHT}, * {@link prefuse.Constants#ORIENT_RIGHT_LEFT}, * {@link prefuse.Constants#ORIENT_TOP_BOTTOM}, or * {@link prefuse.Constants#ORIENT_BOTTOM_TOP}. * @param dspace the spacing to maintain between depth levels of the tree * @param bspace the spacing to maintain between sibling nodes * @param tspace the spacing to maintain between neighboring subtrees */ public NodeLinkTreeLayout(String group, int orientation, double dspace, double bspace, double tspace) { super(group); m_orientation = orientation; m_dspace = dspace; m_bspace = bspace; m_tspace = tspace; } // ------------------------------------------------------------------------ /** * Set the orientation of the tree layout. * @param orientation the orientation value. One of * {@link prefuse.Constants#ORIENT_LEFT_RIGHT}, * {@link prefuse.Constants#ORIENT_RIGHT_LEFT}, * {@link prefuse.Constants#ORIENT_TOP_BOTTOM}, or * {@link prefuse.Constants#ORIENT_BOTTOM_TOP}. */ public void setOrientation(int orientation) { if ( orientation < 0 || orientation >= Constants.ORIENTATION_COUNT || orientation == Constants.ORIENT_CENTER ) { throw new IllegalArgumentException( "Unsupported orientation value: "+orientation); } m_orientation = orientation; } /** * Get the orientation of the tree layout. * @return the orientation value. One of * {@link prefuse.Constants#ORIENT_LEFT_RIGHT}, * {@link prefuse.Constants#ORIENT_RIGHT_LEFT}, * {@link prefuse.Constants#ORIENT_TOP_BOTTOM}, or * {@link prefuse.Constants#ORIENT_BOTTOM_TOP}. */ public int getOrientation() { return m_orientation; } /** * Set the spacing between depth levels. * @param d the depth spacing to use */ public void setDepthSpacing(double d) { m_dspace = d; } /** * Get the spacing between depth levels. * @return the depth spacing */ public double getDepthSpacing() { return m_dspace; } /** * Set the spacing between neighbor nodes. * @param b the breadth spacing to use */ public void setBreadthSpacing(double b) { m_bspace = b; } /** * Get the spacing between neighbor nodes. * @return the breadth spacing */ public double getBreadthSpacing() { return m_bspace; } /** * Set the spacing between neighboring subtrees. * @param s the subtree spacing to use */ public void setSubtreeSpacing(double s) { m_tspace = s; } /** * Get the spacing between neighboring subtrees. * @return the subtree spacing */ public double getSubtreeSpacing() { return m_tspace; } /** * Set the offset value for placing the root node of the tree. The * dimension in which this offset is applied is dependent upon the * orientation of the tree. For example, in a left-to-right orientation, * the offset will a horizontal offset from the left edge of the layout * bounds. * @param o the value by which to offset the root node of the tree */ public void setRootNodeOffset(double o) { m_offset = o; } /** * Get the offset value for placing the root node of the tree. * @return the value by which the root node of the tree is offset */ public double getRootNodeOffset() { return m_offset; } // ------------------------------------------------------------------------ /** * @see prefuse.action.layout.Layout#getLayoutAnchor() */ public Point2D getLayoutAnchor() { if ( m_anchor != null ) return m_anchor; m_tmpa.setLocation(0,0); if ( m_vis != null ) { Display d = m_vis.getDisplay(0); Rectangle2D b = this.getLayoutBounds(); switch ( m_orientation ) { case Constants.ORIENT_LEFT_RIGHT: m_tmpa.setLocation(m_offset, d.getHeight()/2.0); break; case Constants.ORIENT_RIGHT_LEFT: m_tmpa.setLocation(b.getMaxX()-m_offset, d.getHeight()/2.0); break; case Constants.ORIENT_TOP_BOTTOM: m_tmpa.setLocation(d.getWidth()/2.0, m_offset); break; case Constants.ORIENT_BOTTOM_TOP: m_tmpa.setLocation(d.getWidth()/2.0, b.getMaxY()-m_offset); break; } d.getInverseTransform().transform(m_tmpa, m_tmpa); } return m_tmpa; } private double spacing(NodeItem l, NodeItem r, boolean siblings) { boolean w = ( m_orientation == Constants.ORIENT_TOP_BOTTOM || m_orientation == Constants.ORIENT_BOTTOM_TOP ); return (siblings ? m_bspace : m_tspace) + 0.5 * ( w ? l.getBounds().getWidth() + r.getBounds().getWidth() : l.getBounds().getHeight() + r.getBounds().getHeight() ); } private void updateDepths(int depth, NodeItem item) { boolean v = ( m_orientation == Constants.ORIENT_TOP_BOTTOM || m_orientation == Constants.ORIENT_BOTTOM_TOP ); double d = ( v ? item.getBounds().getHeight() : item.getBounds().getWidth() ); if ( m_depths.length <= depth ) m_depths = ArrayLib.resize(m_depths, 3*depth/2); m_depths[depth] = Math.max(m_depths[depth], d); m_maxDepth = Math.max(m_maxDepth, depth); } private void determineDepths() { for ( int i=1; i