1/* 2 * box-algorithm that I wrote for drawing trees with different node sizes and splitting in different directions 3 * 4 * The following aesthetic criteria are satisfied: 5 * 6 * 1) No overlapping text 7 * 2) When switching directions, the entire subtree in the new direction should be seen as one of the nodes in the original direction 8 * 3) Sister nodes are shown on the same line 9 * 4) Parent is centered at the middle of its children 10 * 5) Parent is above/to the left of all children 11 * 12 */ 13 14var node_radius = 4; //adjust this global variable to change the size of the drawn node 15 16//generates svg code for the given input parameters 17//the x, y coordinates are the upper left hand coordinate of the drawing. should start with (0,0) 18function getBoxTree(data, endtag, x, y) { 19 20 if(data[endtag] == undefined) 21 return; 22 23 var ret = ""; //the svg code to return 24 var numChildren = getNumChildren(data,endtag); 25 var pc_type = data[endtag].pc_type; 26 27 var total_size = data[endtag].total_size; 28 var text_size = getTextSize(data,endtag); 29 30 //draw the node itself (centering it properly) 31 var visualLoc = data[endtag].visual_loc; 32 33 var description = getSimpleDescription(data,endtag); 34 var numLines = countNumOccurances("<br>",description); 35 36 //recursively draw all the children (if any) 37 var elapsedDist = 0; 38 39 for(var i = 0; i<numChildren; i++) { 40 var childEndtag = endtag + "_" + i; 41 42 if(data[childEndtag] == undefined) 43 return; 44 45 var childTotalSize = data[childEndtag].total_size; 46 47 if(pc_type == "mg" || pc_type == "gamg") { 48 //draw the appropriate line from the parent to the child 49 ret += getCurve(x + visualLoc.x, y + visualLoc.y, x+text_size.width+data[endtag].indentations[i]+data[childEndtag].visual_loc.x, y+elapsedDist+data[childEndtag].visual_loc.y,"east"); 50 51 //draw the child 52 ret += getBoxTree(data, childEndtag, x+text_size.width+data[endtag].indentations[i], y+elapsedDist); //remember to indent !! 53 54 elapsedDist += childTotalSize.height; 55 } 56 else { 57 //draw the appropriate line from the parent to the child 58 ret += getCurve(x + visualLoc.x, y + visualLoc.y, x+elapsedDist+data[childEndtag].visual_loc.x, y+text_size.height+data[endtag].indentations[i]+data[childEndtag].visual_loc.y ,"south"); 59 60 //draw the child 61 ret += getBoxTree(data, childEndtag, x+elapsedDist, y+text_size.height+data[endtag].indentations[i]); //remember to indent !! 62 63 elapsedDist += childTotalSize.width; 64 } 65 } 66 67 //useful for debugging purposes (don't delete) 68 //ret += "<rect x=\"" + x + "\" y=\"" + y + "\" width=\"" + total_size.width + "\" height=\"" + total_size.height + "\" style=\"fill:black;fill-opacity:.1\" />"; 69 70 //draw the node itself last so that the text is on top of everything 71 var color = colors[getNumUnderscores(endtag) % colors.length]; 72 ret += "<circle id=\"" + "node" + endtag + "\" cx=\"" + (x + visualLoc.x) + "\" cy=\"" + (y + visualLoc.y) + "\" r=\"" + node_radius + "\" stroke=\"black\" stroke-width=\"1\" fill=\"" + color + "\" />"; 73 74 for(var i = 0; i<numLines; i++) { 75 var indx = description.indexOf("<br>"); 76 var chunk = description.substring(0,indx); 77 description = description.substring(indx+4,description.length); 78 ret += "<text x=\"" + (x + visualLoc.x + 1.2*node_radius) + "\" y=\"" + (y + visualLoc.y + 2*node_radius + 12*i) + "\" fill=\"black\" font-size=\"12px\">" + chunk + "</text>"; 79 } 80 81 return ret; 82} 83 84//this function should be pretty straightforward 85function getTextSize(data, endtag) { 86 87 var pc_type = data[endtag].pc_type; 88 var ret = new Object(); 89 ret.width = 100;//70 is enough for chrome, but svg font in safari/firefox shows up bigger so we need more space (although the font-size is always 12px) 90 91 var description = getSimpleDescription(data,endtag); 92 var height = 2*node_radius + 12 * countNumOccurances("<br>",description); //make each line 15 pixels tall 93 ret.height = height; 94 95 return ret; 96} 97 98/* 99 * This method recursively calculates each node's total-size (the total size the its subtree takes up) 100 * Children of mg and gamg are put to the east of the parent node and children of anything else are put to the south 101 * If the node has children, this method also calculates the data on how the child nodes should be indented (so that all sister nodes line up) 102 * Also calculates and records the location (the center coordinates) of the visual node 103 * 104 */ 105 106function calculateSizes(data, endtag) { 107 108 if(data[endtag] == undefined) 109 return; 110 var text_size = getTextSize(data,endtag); //return an object containing 'width' and 'height' 111 var numChildren = getNumChildren(data,endtag); 112 var pc_type = data[endtag].pc_type; 113 114 if(numChildren == 0) { 115 data[endtag].total_size = text_size; //simply set total_size to text_size 116 data[endtag].visual_loc = { 117 x: node_radius, 118 y: node_radius 119 }; //the location of the visual node 120 return; 121 } 122 123 //otherwise, first recursively calculate the properties of the child nodes 124 for(var i = 0; i<numChildren; i++) { 125 var childEndtag = endtag + "_" + i; 126 calculateSizes(data,childEndtag); //recursively calculate the data of all the children !! 127 } 128 129 if(pc_type == "mg" || pc_type == "gamg") { //put children to the east 130 131 var totalHeight = 0; //get the total heights of all the children. and the most extreme visual node location 132 var mostShifted = 0; //of the child nodes, find the most x_shifted visual node 133 134 for(var i=0; i<numChildren; i++) { //iterate thru the children to get the total height and most extreme visual node location 135 var childEndtag = endtag + "_" + i; 136 137 if(data[childEndtag] == undefined) 138 return; 139 140 var childSize = data[childEndtag].total_size; 141 var visualLoc = data[childEndtag].visual_loc; 142 143 totalHeight += childSize.height; 144 if(visualLoc.x > mostShifted) 145 mostShifted = visualLoc.x; 146 } 147 148 var indentations = new Array(); 149 var rightFrontier = 0; 150 151 for(var i=0; i<numChildren; i++) { //iterate through the children again and indent each child such that their visual nodes line up 152 var childEndtag = endtag + "_" + i; 153 var childSize = data[childEndtag].total_size; 154 var visualLoc = data[childEndtag].visual_loc; 155 156 indentations[i] = 0; 157 158 if(visualLoc.x < mostShifted) { 159 indentations[i] = mostShifted - visualLoc.x; //record to let the drawing algorithm know to indent these children 160 } 161 if(indentations[i] + childSize.width > rightFrontier) //at the same time, calculate how wide the total_size must be 162 rightFrontier = indentations[i] + childSize.width; 163 } 164 165 //find where the parent node must be (if there is an odd number of children, simply align it with the center child. for even, take average of the middle 2 children) 166 var visualLoc = new Object(); 167 visualLoc.x = node_radius; 168 169 if(numChildren % 2 == 0) { //even number of children (take avg of middle two visual nodes) 170 var elapsedDist = 0; 171 for(var i = 0; i<numChildren/2 - 1; i++) { 172 var childEndtag = endtag + "_" + i; 173 elapsedDist += data[childEndtag].total_size.height; 174 } 175 var child1 = numChildren/2 - 1; 176 var child2 = numChildren/2; 177 var child1_endtag = endtag + "_" + child1; 178 var child2_endtag = endtag + "_" + child2; 179 180 var child1_pos = elapsedDist + data[child1_endtag].visual_loc.y; 181 var child2_pos = elapsedDist + data[child1_endtag].total_size.height + data[child2_endtag].visual_loc.y; 182 183 var mid_y = (child1_pos + child2_pos)/2; 184 visualLoc.y = mid_y; 185 } 186 else { //odd number of children (simply take the visual y-coord of the middle child) 187 var elapsedDist = 0; 188 for(var i = 0; i<Math.floor(numChildren/2); i++) { 189 var childEndtag = endtag + "_" + i; 190 elapsedDist += data[childEndtag].total_size.height; 191 } 192 var child = Math.floor(numChildren/2); 193 var child_endtag = endtag + "_" + child; 194 195 var mid_y = elapsedDist + data[child_endtag].visual_loc.y; 196 visualLoc.y = mid_y; 197 } 198 199 var total_size = new Object(); 200 201 var southFrontier = visualLoc.y - node_radius + text_size.height; 202 if(southFrontier > totalHeight) //should be rare, but certainly possible. (this is when the parent node is absurdly long) 203 total_size.height = southFrontier; 204 else 205 total_size.height = totalHeight; 206 207 total_size.width = text_size.width + rightFrontier; //total width depends on how far the right frontier got pushed 208 209 data[endtag].total_size = total_size; 210 data[endtag].indentations = indentations; 211 data[endtag].visual_loc = visualLoc; 212 } 213 else { //put children to the south 214 215 var totalWidth = 0; //get the total widths of all the children. and the most extreme visual node location 216 var mostShifted = 0; //of the child nodes, find the most y_shifted visual node 217 218 for(var i=0; i<numChildren; i++) { //iterate thru the children to get the total width and most extreme visual node location 219 var childEndtag = endtag + "_" + i; 220 if(data[childEndtag] == undefined) 221 return; 222 223 var childSize = data[childEndtag].total_size; 224 var visualLoc = data[childEndtag].visual_loc; 225 226 totalWidth += childSize.width; 227 if(visualLoc.y > mostShifted) 228 mostShifted = visualLoc.y; 229 } 230 231 var indentations = new Array(); 232 var southFrontier = 0; 233 234 for(var i=0; i<numChildren; i++) { //iterate through the children again and indent each child such that their visual nodes line up 235 var childEndtag = endtag + "_" + i; 236 var childSize = data[childEndtag].total_size; 237 var visualLoc = data[childEndtag].visual_loc; 238 239 indentations[i] = 0; 240 241 if(visualLoc.y < mostShifted) { 242 indentations[i] = mostShifted - visualLoc.y; //record to let the drawing algorithm know to indent these children 243 } 244 if(indentations[i] + childSize.height > southFrontier) //at the same time, calculate how long the total_size must be 245 southFrontier = indentations[i] + childSize.height; 246 } 247 248 //find where the parent node must be (if there is an odd number of children, simply align it with the center child. for even, take average of the middle 2 children) 249 var visualLoc = new Object(); 250 visualLoc.y = node_radius; 251 252 if(numChildren % 2 == 0) { //even number of children (take avg of middle two visual nodes) 253 var elapsedDist = 0; 254 for(var i = 0; i<numChildren/2 - 1; i++) { 255 var childEndtag = endtag + "_" + i; 256 elapsedDist += data[childEndtag].total_size.width; 257 } 258 var child1 = numChildren/2 - 1; 259 var child2 = numChildren/2; 260 var child1_endtag = endtag + "_" + child1; 261 var child2_endtag = endtag + "_" + child2; 262 263 var child1_pos = elapsedDist + data[child1_endtag].visual_loc.x; 264 var child2_pos = elapsedDist + data[child1_endtag].total_size.width + data[child2_endtag].visual_loc.x; 265 266 var mid_x = (child1_pos + child2_pos)/2; 267 visualLoc.x = mid_x; 268 } 269 else { //odd number of children (simply take the visual y-coord of the middle child) 270 var elapsedDist = 0; 271 for(var i = 0; i<Math.floor(numChildren/2); i++) { 272 var childEndtag = endtag + "_" + i; 273 elapsedDist += data[childEndtag].total_size.width; 274 } 275 var child = Math.floor(numChildren/2); 276 var child_endtag = endtag + "_" + child; 277 278 var mid_x = elapsedDist + data[child_endtag].visual_loc.x; 279 visualLoc.x = mid_x; 280 } 281 282 var total_size = new Object(); 283 284 var rightFrontier = visualLoc.x - node_radius + text_size.width; 285 if(rightFrontier > totalWidth) //should be rare, but certainly possible. (this is when the parent node is absurdly wide) 286 total_size.width = rightFrontier; 287 else 288 total_size.width = totalWidth; 289 290 total_size.height = text_size.height + southFrontier; //total height depends on how far the south frontier got pushed 291 292 data[endtag].total_size = total_size; 293 data[endtag].indentations = indentations; 294 data[endtag].visual_loc = visualLoc; 295 } 296 return; 297} 298 299 300//use svg to generate a smooth Bézier curve from one point to another 301//this simple algorithm to find the 2 control points for the bezier curve to generate a logistic-looking curve is taken from the d3 graphics library 302function getCurve(x1,y1,x2,y2,direction) { 303 304 var ret = ""; 305 306 if(direction == "east") { 307 var mid_x = (x1+x2)/2.0; 308 309 var control1 = new Object(); 310 control1.x = mid_x; 311 control1.y = y1; 312 313 var control2 = new Object(); 314 control2.x = mid_x; 315 control2.y = y2; 316 317 ret = "<path d=\"M " + x1 + "," + y1 + " " + "C" + control1.x + "," + control1.y + " " + control2.x + "," + control2.y + " " + x2 + "," + y2 + "\" stroke =\"blue\" stroke-width=\"2\" stroke-opacity=\".5\" fill=\"none\" />"; 318 } 319 320 else if(direction == "south") { 321 var mid_y = (y1+y2)/2.0; 322 323 var control1 = new Object(); 324 control1.x = x1; 325 control1.y = mid_y; 326 327 var control2 = new Object(); 328 control2.x = x2; 329 control2.y = mid_y; 330 331 ret = "<path d=\"M " + x1 + "," + y1 + " " + "C" + control1.x + "," + control1.y + " " + control2.x + "," + control2.y + " " + x2 + "," + y2 + "\" stroke =\"blue\" stroke-width=\"2\" stroke-opacity=\".5\" fill=\"none\" />"; 332 } 333 334 return ret; 335} 336