package prefuse.action.layout.graph;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import prefuse.data.Graph;
import prefuse.data.Schema;
import prefuse.data.tuple.TupleSet;
import prefuse.data.util.TreeNodeIterator;
import prefuse.visual.NodeItem;
import prefuse.visual.VisualItem;
/**
*
* TreeLayout instance computing a TreeMap layout that optimizes for low
* aspect ratios of visualized tree nodes. TreeMaps are a form of space-filling
* layout that represents nodes as boxes on the display, with children nodes
* represented as boxes placed within their parent's box.
*
*
* This particular algorithm is taken from Bruls, D.M., C. Huizing, and
* J.J. van Wijk, "Squarified Treemaps" In Data Visualization 2000,
* Proceedings of the Joint Eurographics and IEEE TCVG Sumposium on
* Visualization, 2000, pp. 33-42. Available online at:
*
* http://www.win.tue.nl/~vanwijk/stm.pdf.
*
*
* For more information on TreeMaps in general, see
*
* http://www.cs.umd.edu/hcil/treemap-history/.
*
*
* @version 1.0
* @author jeffrey heer
*/
public class SquarifiedTreeMapLayout extends TreeLayout {
// column value in which layout stores area information
public static final String AREA = "_area";
public static final Schema AREA_SCHEMA = new Schema();
static {
AREA_SCHEMA.addColumn(AREA, double.class);
}
private static Comparator s_cmp = new Comparator() {
public int compare(Object o1, Object o2) {
double s1 = ((VisualItem)o1).getDouble(AREA);
double s2 = ((VisualItem)o2).getDouble(AREA);
return ( s1>s2 ? 1 : (s1 0 ) {
updateArea(c,r);
layout(c, r);
}
}
}
private void updateArea(NodeItem n, Rectangle2D r) {
Rectangle2D b = n.getBounds();
if ( m_frame == 0.0 ) {
// if no framing, simply update bounding rectangle
r.setRect(b);
return;
}
// compute area loss due to frame
double dA = 2*m_frame*(b.getWidth()+b.getHeight()-2*m_frame);
double A = n.getDouble(AREA) - dA;
// compute renormalization factor
double s = 0;
Iterator childIter = n.children();
while ( childIter.hasNext() )
s += ((NodeItem)childIter.next()).getDouble(AREA);
double t = A/s;
// re-normalize children areas
childIter = n.children();
while ( childIter.hasNext() ) {
NodeItem c = (NodeItem)childIter.next();
c.setDouble(AREA, c.getDouble(AREA)*t);
}
// set bounding rectangle and return
r.setRect(b.getX()+m_frame, b.getY()+m_frame,
b.getWidth()-2*m_frame, b.getHeight()-2*m_frame);
return;
}
private void squarify(List c, List row, double w, Rectangle2D r) {
double worst = Double.MAX_VALUE, nworst;
int len;
while ( (len=c.size()) > 0 ) {
// add item to the row list, ignore if negative area
VisualItem item = (VisualItem) c.get(len-1);
double a = item.getDouble(AREA);
if (a <= 0.0) {
c.remove(len-1);
continue;
}
row.add(item);
nworst = worst(row, w);
if ( nworst <= worst ) {
c.remove(len-1);
worst = nworst;
} else {
row.remove(row.size()-1); // remove the latest addition
r = layoutRow(row, w, r); // layout the current row
w = Math.min(r.getWidth(),r.getHeight()); // recompute w
row.clear(); // clear the row
worst = Double.MAX_VALUE;
}
}
if ( row.size() > 0 ) {
r = layoutRow(row, w, r); // layout the current row
row.clear(); // clear the row
}
}
private double worst(List rlist, double w) {
double rmax = Double.MIN_VALUE, rmin = Double.MAX_VALUE, s = 0.0;
Iterator iter = rlist.iterator();
while ( iter.hasNext() ) {
double r = ((VisualItem)iter.next()).getDouble(AREA);
rmin = Math.min(rmin, r);
rmax = Math.max(rmax, r);
s += r;
}
s = s*s; w = w*w;
return Math.max(w*rmax/s, s/(w*rmin));
}
private Rectangle2D layoutRow(List row, double w, Rectangle2D r) {
double s = 0; // sum of row areas
Iterator rowIter = row.iterator();
while ( rowIter.hasNext() )
s += ((VisualItem)rowIter.next()).getDouble(AREA);
double x = r.getX(), y = r.getY(), d = 0;
double h = w==0 ? 0 : s/w;
boolean horiz = (w == r.getWidth());
// set node positions and dimensions
rowIter = row.iterator();
while ( rowIter.hasNext() ) {
NodeItem n = (NodeItem)rowIter.next();
NodeItem p = (NodeItem)n.getParent();
if ( horiz ) {
setX(n, p, x+d);
setY(n, p, y);
} else {
setX(n, p, x);
setY(n, p, y+d);
}
double nw = n.getDouble(AREA)/h;
if ( horiz ) {
setNodeDimensions(n,nw,h);
d += nw;
} else {
setNodeDimensions(n,h,nw);
d += nw;
}
}
// update space available in rectangle r
if ( horiz )
r.setRect(x,y+h,r.getWidth(),r.getHeight()-h);
else
r.setRect(x+h,y,r.getWidth()-h,r.getHeight());
return r;
}
private void setNodeDimensions(NodeItem n, double w, double h) {
n.setBounds(n.getX(), n.getY(), w, h);
}
} // end of class SquarifiedTreeMapLayout