1 /** 2 * Constructs a new, empty tree layout. Layouts are not typically constructed 3 * directly; instead, they are added to an existing panel via 4 * {@link pv.Mark#add}. 5 * 6 * @class Implements a node-link tree diagram using the Reingold-Tilford "tidy" 7 * tree layout algorithm. The specific algorithm used by this layout is based on 8 * <a href="http://citeseer.ist.psu.edu/buchheim02improving.html">"Improving 9 * Walker's Algorithm to Run in Linear Time"</A> by C. Buchheim, M. Jünger 10 * & S. Leipert, Graph Drawing 2002. This layout supports both cartesian and 11 * radial orientations orientations for node-link diagrams. 12 * 13 * <p>The tree layout supports a "group" property, which if true causes siblings 14 * to be positioned closer together than unrelated nodes at the same depth. The 15 * layout can be configured using the <tt>depth</tt> and <tt>breadth</tt> 16 * properties, which control the increments in pixel space between nodes in both 17 * dimensions, similar to the indent layout. 18 * 19 * <p>For more details on how to use this layout, see 20 * {@link pv.Layout.Hierarchy}. 21 * 22 * @extends pv.Layout.Hierarchy 23 */ 24 pv.Layout.Tree = function() { 25 pv.Layout.Hierarchy.call(this); 26 }; 27 28 pv.Layout.Tree.prototype = pv.extend(pv.Layout.Hierarchy) 29 .property("group", Number) 30 .property("breadth", Number) 31 .property("depth", Number) 32 .property("orient", String); 33 34 /** 35 * Default properties for tree layouts. The default orientation is "top", the 36 * default group parameter is 1, and the default breadth and depth offsets are 37 * 15 and 60 respectively. 38 * 39 * @type pv.Layout.Tree 40 */ 41 pv.Layout.Tree.prototype.defaults = new pv.Layout.Tree() 42 .extend(pv.Layout.Hierarchy.prototype.defaults) 43 .group(1) 44 .breadth(15) 45 .depth(60) 46 .orient("top"); 47 48 /** @private */ 49 pv.Layout.Tree.prototype.buildImplied = function(s) { 50 if (pv.Layout.Hierarchy.prototype.buildImplied.call(this, s)) return; 51 52 var nodes = s.nodes, 53 orient = s.orient, 54 depth = s.depth, 55 breadth = s.breadth, 56 group = s.group, 57 w = s.width, 58 h = s.height; 59 60 /** @private */ 61 function firstWalk(v) { 62 var l, r, a; 63 if (!v.firstChild) { 64 if (l = v.previousSibling) { 65 v.prelim = l.prelim + distance(v.depth, true); 66 } 67 } else { 68 l = v.firstChild; 69 r = v.lastChild; 70 a = l; // default ancestor 71 for (var c = l; c; c = c.nextSibling) { 72 firstWalk(c); 73 a = apportion(c, a); 74 } 75 executeShifts(v); 76 var midpoint = .5 * (l.prelim + r.prelim); 77 if (l = v.previousSibling) { 78 v.prelim = l.prelim + distance(v.depth, true); 79 v.mod = v.prelim - midpoint; 80 } else { 81 v.prelim = midpoint; 82 } 83 } 84 } 85 86 /** @private */ 87 function secondWalk(v, m, depth) { 88 v.breadth = v.prelim + m; 89 m += v.mod; 90 for (var c = v.firstChild; c; c = c.nextSibling) { 91 secondWalk(c, m, depth); 92 } 93 } 94 95 /** @private */ 96 function apportion(v, a) { 97 var w = v.previousSibling; 98 if (w) { 99 var vip = v, 100 vop = v, 101 vim = w, 102 vom = v.parentNode.firstChild, 103 sip = vip.mod, 104 sop = vop.mod, 105 sim = vim.mod, 106 som = vom.mod, 107 nr = nextRight(vim), 108 nl = nextLeft(vip); 109 while (nr && nl) { 110 vim = nr; 111 vip = nl; 112 vom = nextLeft(vom); 113 vop = nextRight(vop); 114 vop.ancestor = v; 115 var shift = (vim.prelim + sim) - (vip.prelim + sip) + distance(vim.depth, false); 116 if (shift > 0) { 117 moveSubtree(ancestor(vim, v, a), v, shift); 118 sip += shift; 119 sop += shift; 120 } 121 sim += vim.mod; 122 sip += vip.mod; 123 som += vom.mod; 124 sop += vop.mod; 125 nr = nextRight(vim); 126 nl = nextLeft(vip); 127 } 128 if (nr && !nextRight(vop)) { 129 vop.thread = nr; 130 vop.mod += sim - sop; 131 } 132 if (nl && !nextLeft(vom)) { 133 vom.thread = nl; 134 vom.mod += sip - som; 135 a = v; 136 } 137 } 138 return a; 139 } 140 141 /** @private */ 142 function nextLeft(v) { 143 return v.firstChild || v.thread; 144 } 145 146 /** @private */ 147 function nextRight(v) { 148 return v.lastChild || v.thread; 149 } 150 151 /** @private */ 152 function moveSubtree(wm, wp, shift) { 153 var subtrees = wp.number - wm.number; 154 wp.change -= shift / subtrees; 155 wp.shift += shift; 156 wm.change += shift / subtrees; 157 wp.prelim += shift; 158 wp.mod += shift; 159 } 160 161 /** @private */ 162 function executeShifts(v) { 163 var shift = 0, change = 0; 164 for (var c = v.lastChild; c; c = c.previousSibling) { 165 c.prelim += shift; 166 c.mod += shift; 167 change += c.change; 168 shift += c.shift + change; 169 } 170 } 171 172 /** @private */ 173 function ancestor(vim, v, a) { 174 return (vim.ancestor.parentNode == v.parentNode) ? vim.ancestor : a; 175 } 176 177 /** @private */ 178 function distance(depth, siblings) { 179 return (siblings ? 1 : (group + 1)) / ((orient == "radial") ? depth : 1); 180 } 181 182 /* Initialize temporary layout variables. TODO: store separately. */ 183 var root = nodes[0]; 184 root.visitAfter(function(v, i) { 185 v.ancestor = v; 186 v.prelim = 0; 187 v.mod = 0; 188 v.change = 0; 189 v.shift = 0; 190 v.number = v.previousSibling ? (v.previousSibling.number + 1) : 0; 191 v.depth = i; 192 }); 193 194 /* Compute the layout using Buchheim et al.'s algorithm. */ 195 firstWalk(root); 196 secondWalk(root, -root.prelim, 0); 197 198 /** @private Returns the angle of the given node. */ 199 function midAngle(n) { 200 return (orient == "radial") ? n.breadth / depth : 0; 201 } 202 203 /** @private */ 204 function x(n) { 205 switch (orient) { 206 case "left": return n.depth; 207 case "right": return w - n.depth; 208 case "top": 209 case "bottom": return n.breadth + w / 2; 210 case "radial": return w / 2 + n.depth * Math.cos(midAngle(n)); 211 } 212 } 213 214 /** @private */ 215 function y(n) { 216 switch (orient) { 217 case "left": 218 case "right": return n.breadth + h / 2; 219 case "top": return n.depth; 220 case "bottom": return h - n.depth; 221 case "radial": return h / 2 + n.depth * Math.sin(midAngle(n)); 222 } 223 } 224 225 /* Clear temporary layout variables; transform depth and breadth. */ 226 root.visitAfter(function(v) { 227 v.breadth *= breadth; 228 v.depth *= depth; 229 v.midAngle = midAngle(v); 230 v.x = x(v); 231 v.y = y(v); 232 if (v.firstChild) v.midAngle += Math.PI; 233 delete v.breadth; 234 delete v.depth; 235 delete v.ancestor; 236 delete v.prelim; 237 delete v.mod; 238 delete v.change; 239 delete v.shift; 240 delete v.number; 241 delete v.thread; 242 }); 243 }; 244 245 /** 246 * The offset between siblings nodes; defaults to 15. 247 * 248 * @type number 249 * @name pv.Layout.Tree.prototype.breadth 250 */ 251 252 /** 253 * The offset between parent and child nodes; defaults to 60. 254 * 255 * @type number 256 * @name pv.Layout.Tree.prototype.depth 257 */ 258 259 /** 260 * The orientation. The default orientation is "top", which means that the root 261 * node is placed on the top edge, leaf nodes appear at the bottom, and internal 262 * nodes are in-between. The following orientations are supported:<ul> 263 * 264 * <li>left - left-to-right. 265 * <li>right - right-to-left. 266 * <li>top - top-to-bottom. 267 * <li>bottom - bottom-to-top. 268 * <li>radial - radially, with the root at the center.</ul> 269 * 270 * @type string 271 * @name pv.Layout.Tree.prototype.orient 272 */ 273 274 /** 275 * The sibling grouping, i.e., whether differentiating space is placed between 276 * sibling groups. The default is 1 (or true), causing sibling leaves to be 277 * separated by one breadth offset. Setting this to false (or 0) causes 278 * non-siblings to be adjacent. 279 * 280 * @type number 281 * @name pv.Layout.Tree.prototype.group 282 */ 283