visgraph.layouts.dynadag

1 2 ''' 3 A dynadag-ish graph layout calculator... 4 ''' 5 6 import itertools 7 8 import visgraph 9 import visgraph.layouts as vg_layout 10 import visgraph.graphcore as vg_graphcore 11 import visgraph.drawing.bezier as vg_bezier 12 import visgraph.drawing.catmullrom as vg_catmullrom 13 14 zero_zero = (0,0) 15

16 -def revenumerate(l):

17 return itertools.izip(xrange(len(l)-1, -1, -1), reversed(l))

18 19 SCOOCH_LEFT = 0 20 SCOOCH_RIGHT = 1 21

22 -class DynadagLayout(vg_layout.GraphLayout):

23

24 - def __init__(self, graph):

25 26 vg_layout.GraphLayout.__init__(self, graph) 27 28 self._addGhostNodes() 29 30 self.width_pad = 20 31 self.height_pad = 40

32

33 - def getLayoutSize(self):

34 ''' 35 Return the width,height of this layout. 36 ''' 37 height = 0 38 width = 0 39 for layer in self.layers: 40 41 lheight = 0 42 lwidth = 0 43 44 for nid,ninfo in layer: 45 xsize, ysize = ninfo.get('size', zero_zero) 46 lheight = max(lheight, ysize + self.height_pad) 47 lwidth += xsize + self.width_pad 48 49 height += lheight 50 width = max(lwidth, width) 51 52 return width, height

53

54 - def _baryCenter(self, nid, ninfo):

55 tot = 0 56 cnt = 0 57 for eid, fnode, tnode, einfo in self.graph.getRefsFrom(nid): 58 tot += self.graph.getNodeInfo(tnode, 'layerpos') 59 cnt += 1 60 for eid, fnode, tnode, einfo in self.graph.getRefsTo(nid): 61 tot += self.graph.getNodeInfo(fnode, 'layerpos') 62 cnt += 1 63 b = tot / float(cnt) 64 ninfo['barycenter'] = b

65

66 - def _cmpBaryCenter(self, node1, node2):

67 n1bary = node1[1].get('barycenter') 68 n2bary = node2[1].get('barycenter') 69 return cmp(n1bary, n2bary)

70 71 # Try out "barycenter" averaging and re-ordering.

72 - def _orderNodesByBary(self):

73 # Go through the layers and do barycenter calcs first. 74 # FIXME how do we tell when we're done? 75 for i in xrange(10): 76 for layer in self.layers: 77 for nid,ninfo in layer: 78 self._baryCenter(nid, ninfo) 79 80 for layer in self.layers: 81 layer.sort(cmp=self._cmpBaryCenter) 82 for i,(nid,ninfo) in enumerate(layer): 83 ninfo['layerpos'] = i

84

85 - def _getNodeRelPos(self, nid, ninfo):

86 87 weight = ninfo['weight'] 88 89 abovepos = [] 90 for eid, fromid, toid, einfo in self.graph.getRefsTo(nid): 91 fprops = self.graph.getNodeProps(fromid) 92 if fprops['weight'] != weight-1: 93 continue 94 abovepos.append(fprops['layerpos']) 95 abovepos.sort() 96 97 belowpos = [] 98 for eid, fromid, toid, einfo in self.graph.getRefsFrom(nid): 99 tprops = self.graph.getNodeProps(toid) 100 if tprops['weight'] != weight+1: 101 continue 102 belowpos.append(tprops['layerpos']) 103 belowpos.sort() 104 105 return abovepos, belowpos

106

107 - def _getLayerCross(self, layernum):

108 ccount = 0 109 110 layer = self.layers[layernum] 111 for i in xrange(1, len(layer)): 112 113 myabove, mybelow = self._getNodeRelPos(*layer[i]) 114 hisabove, hisbelow = self._getNodeRelPos(*layer[i-1]) 115 116 # If I have any nodes above with position lower 117 # than any of his, those are cross overs... 118 for mya in myabove: 119 for hisa in hisabove: 120 if mya < hisa: 121 ccount += 1 122 123 # If I have any nodes below with position lower 124 # than any of his, those acre cross overs... 125 for myb in mybelow: 126 for hisb in hisbelow: 127 if myb < hisb: 128 ccount += 1 129 130 return ccount

131

132 - def _bubSortNodes(self):

133 134 # Go through nodes and see if we can re-order children to 135 # reduce crossovers... 136 137 for i in xrange(len(self.layers)): 138 139 layer = self.layers[i] 140 141 reduced = True 142 while reduced: 143 144 reduced = False 145 146 # Get the current crossover count for this layer 147 score = self._getLayerCross(i) 148 149 # TODO should we do this multipliciative rather than 150 # neighbors only? 151 for j in xrange(len(layer)-1): 152 153 n1 = layer[j] 154 n2 = layer[j+1] 155 156 layer[j] = n2 157 layer[j+1] = n1 158 159 newscore = self._getLayerCross(i) 160 # If this was optimal, keep it and continue 161 if newscore < score: 162 reduced = True 163 n1[1]['layerpos'] = j+1 164 n2[1]['layerpos'] = j 165 break 166 167 # Nope, put it back... 168 layer[j] = n1 169 layer[j+1] = n2

170

171 - def _addGhostNodes(self):

172 ''' 173 Translate the hierarchical graph we are given into dynadag 174 friendly graph with ghost nodes.... 175 ''' 176 weights = self.graph.getNodeWeights() 177 178 # First lets take care of any loop edges 179 # (These will be nodes in the graph which are marked "reverse=True" 180 # but have been added with src/dst swapped to make graphing easier) 181 for eid, fromid, toid, einfo in self.graph.getEdges(): 182 183 if not einfo.get('reverse'): 184 continue 185 186 topweight = weights.get(fromid) 187 botweight = weights.get(toid) 188 189 # In the case of a single block loop, add one ghost and 190 # connect them all 191 #if fromid == toid: 192 if topweight == botweight: 193 bridgenode = self.graph.addNode(ghost=True, weight=topweight) 194 weights[bridgenode] = topweight 195 196 self.graph.delEdge(eid) 197 self.graph.addEdge(fromid, bridgenode, looptop=True) 198 self.graph.addEdge(bridgenode, toid, loopbot=True) 199 continue 200 201 # For a "reverse" edge, add a node in the weight for each 202 # and connect them. 203 topnode = self.graph.addNode(ghost=True, weight=topweight) 204 weights[topnode] = topweight 205 botnode = self.graph.addNode(ghost=True, weight=botweight) 206 weights[botnode] = botweight 207 208 self.graph.addEdge(topnode, botnode) # For rendering, these will be normal! 209 210 # Now, remove the "reverse" edge, and add a 'looptop' and 'loopbot' edge 211 self.graph.delEdge(eid) 212 self.graph.addEdge(fromid, topnode, looptop=True) 213 self.graph.addEdge(botnode, toid, loopbot=True) 214 215 # Create ghost nodes for edges which pass through a weight layer 216 for eid, fromid, toid, einfo in self.graph.getEdges(): 217 xweight = weights.get(fromid, 0) 218 yweight = weights.get(toid) 219 if xweight + 1 < yweight: 220 self.graph.delEdge(eid) 221 while xweight + 1 < yweight: 222 xweight += 1 223 ghostid = self.graph.addNode(ghost=True, weight=xweight) 224 self.graph.addEdge(fromid, ghostid) 225 #print 'ADDED GHOST %d (%d -> %d)' % (ghostid,fromid,toid) 226 fromid = ghostid 227 self.graph.addEdge(fromid, toid)

228

229 - def layoutGraph(self):

230 231 self.maxweight = 0 232 233 for nid, ninfo in self.graph.getNodes(): 234 self.maxweight = max(ninfo.get('weight', 0), self.maxweight) 235 #print 'Max Weight: %d' % self.maxweight 236 237 self.layers = [ [] for i in xrange(self.maxweight + 1) ] 238 239 doit_done = {} 240 def doit(nid, ninfo): 241 242 if doit_done.get(nid): 243 return 244 245 doit_done[nid] = True 246 247 for eid, fromid, toid, einfo in self.graph.getRefsFrom(nid): 248 doit(toid, self.graph.getNodeProps(toid)) 249 250 w = ninfo.get('weight', 0) 251 252 layer = self.layers[w] 253 ninfo['layerpos'] = len(layer) 254 layer.append((nid,ninfo))

255 256 # FIXME support more than one root! 257 rootnode = self.graph.getRootNodes()[0] 258 doit(rootnode, self.graph.getNodeProps(rootnode)) 259 260 # Now lets use positional averaging to order nodes in the layer 261 self._orderNodesByBary() 262 self._bubSortNodes() 263 264 self.maxwidth = 0 265 266 # Calculate the width / height of each layer... 267 lwidths = [] # The width of this total layer 268 self.lheights = [] # The tallest node in this layer 269 for layer in self.layers: 270 x = self.width_pad 271 y = 0 272 273 heightmax = 0 274 for nid,ninfo in layer: 275 size = ninfo.get('size', zero_zero) 276 xx,yy = size 277 278 heightmax = max(heightmax, yy) 279 280 x += xx 281 y += yy 282 283 lwidths.append(x) 284 self.lheights.append(heightmax) 285 286 self.maxwidth = max(self.maxwidth, x) 287 288 # Now that we have them sorted, lets set their individual positions... 289 vpad = 0 290 for i,layer in enumerate(self.layers): 291 hpad = (self.maxwidth - lwidths[i]) / 2 292 hpad += self.width_pad 293 for nid,ninfo in layer: 294 xpos = hpad 295 ypos = vpad 296 297 xsize, ysize = ninfo.get('size', zero_zero) 298 299 ninfo['position'] = (xpos,ypos) 300 ninfo['vert_pad'] = self.lheights[i] - ysize 301 302 hpad += xsize 303 304 hpad += self.width_pad 305 306 vpad += self.lheights[i] 307 vpad += self.height_pad 308 309 310 # Optimize the positions of nodes by moving them outward to align 311 312 # First from top to bottom 313 for i, layer in enumerate(self.layers): 314 315 layermid = len(layer) / 2 316 317 # From the left side, scooch kids out... 318 for j, (nid,ninfo) in enumerate(layer): 319 320 if not ninfo.get('ghost'): 321 break 322 323 self._scoochXKids(nid, ninfo, SCOOCH_LEFT) 324 325 # From the right side, scooch kids out... 326 for j, (nid, ninfo) in revenumerate(layer): 327 328 if not ninfo.get('ghost'): 329 break 330 331 self._scoochXKids(nid, ninfo, SCOOCH_RIGHT) 332 333 # From the bottom to the top! 334 for i, layer in revenumerate(self.layers): 335 336 layermid = len(layer) / 2 337 338 # From the left side, scooch kids out... 339 for j, (nid,ninfo) in enumerate(layer): 340 341 if not ninfo.get('ghost'): 342 break 343 344 self._scoochXParents(nid, ninfo, SCOOCH_LEFT) 345 346 # From the right side, scooch kids out... 347 for j, (nid, ninfo) in revenumerate(layer): 348 349 if not ninfo.get('ghost'): 350 break 351 352 self._scoochXParents(nid, ninfo, SCOOCH_RIGHT) 353 354 # Finally, we calculate the drawing for the edge lines 355 self._calcEdgeLines()

356

357 - def _scoochXParents(self, nid, ninfo, lr=None):

358 359 weight = ninfo['weight'] 360 361 for eid, n1, n2, einfo in self.graph.getRefsTo(nid): 362 363 pinfo = self.graph.getNodeProps(n1) 364 365 # Only do ghost nodes (for now...) 366 if not pinfo.get('ghost'): 367 continue 368 369 # Only do this to parents in the layer above us... 370 if pinfo['weight'] != weight-1: 371 continue 372 373 self._scoochXAlign(ninfo, pinfo, lr=lr)

374

375 - def _scoochXKids(self, nid, ninfo, lr=None):

376 377 weight = ninfo['weight'] 378 379 for eid, n1, n2, einfo in self.graph.getRefsFrom(nid): 380 381 kinfo = self.graph.getNodeProps(n2) 382 383 # Only do ghost nodes (for now...) 384 if not kinfo.get('ghost'): 385 continue 386 387 # Only do this to kids in the layer beneath us... 388 if kinfo['weight'] != weight+1: 389 continue 390 391 self._scoochXAlign(ninfo, kinfo, lr=lr)

392

393 - def _scoochXAlign(self, ninfo, kinfo, lr=None):

394 ''' 395 If possible, move the "kidinfo" node toward ninfo 396 along the X axis... If "lr" is specified, only move 397 the "kidnode" (which may be "above" you...) if it is 398 moving either SCOOCH_LEFT or SCOOCH_RIGHT as specified. 399 ''' 400 xpos, ypos = ninfo['position'] 401 xsize, ysize = ninfo.get('size', zero_zero) 402 xmid = xpos + ( xsize / 2 ) 403 404 kxpos, kypos = kinfo['position'] 405 kxsize, kysize = kinfo.get('size', zero_zero) 406 kxmid = kxpos + ( kxsize / 2 ) 407 408 xdelta = xmid - kxmid 409 410 # If they only want us to go left, and the delta 411 # is right, bail... 412 if lr == SCOOCH_LEFT and xdelta >= 0: 413 return 414 415 # If they only want us to go right, and the delta 416 # is left, bail... 417 if lr == SCOOCH_RIGHT and xdelta <= 0: 418 return 419 420 self._scoochX(kinfo, xdelta)

421

422 - def _scoochX(self, ninfo, xdelta):

423 424 layerpos = ninfo.get('layerpos') 425 x, y = ninfo['position'] 426 xsize, ysize = ninfo.get('size', zero_zero) 427 layer = self.layers[ninfo['weight']] 428 layermax = len(layer) - 1 429 430 # There's always room on the left if we're the first... 431 if layerpos == 0 and xdelta < 0: 432 ninfo['position'] = (x+xdelta, y) 433 return 434 435 # Always room on the right if we're last! 436 if layerpos == layermax and xdelta > 0: 437 ninfo['position'] = (x+xdelta, y) 438 return 439 440 # Sigh... now we have to get fancy... 441 442 # If they're asking us to go left, find out about our 443 # left sibling 444 if xdelta < 0: 445 snid, sinfo = layer[layerpos - 1] 446 sx, sy = sinfo['position'] 447 sxsize, sysize = sinfo.get('size', zero_zero) 448 449 sright = (sx + sxsize) + self.width_pad 450 451 #leftroom = sright - x 452 # "greater" is less movement here... 453 xdelta = max(xdelta, sright - x) 454 ninfo['position'] = (x+xdelta, y) 455 return 456 457 # If they're asking us to go right, find out about our 458 # right sibling 459 if xdelta > 0: 460 snid, sinfo = layer[layerpos + 1] 461 sx, sy = sinfo['position'] 462 sxsize, sysize = sinfo.get('size', zero_zero) 463 464 myright = x + xsize + self.width_pad 465 466 xdelta = min(xdelta, sx-myright) 467 ninfo['position'] = (x+xdelta, y) 468 return

469

470 - def _calcEdgeLines(self):

471 472 h_hpad = self.width_pad / 2 473 h_vpad = self.height_pad / 2 474 475 for eid, fromid, toid, einfo in self.graph.getEdges(): 476 477 pre_lines = [] 478 post_lines = [] 479 480 pinfo = self.graph.getNodeProps(fromid) 481 kinfo = self.graph.getNodeProps(toid) 482 483 pwidth, pheight = pinfo.get('size', (0,0)) 484 pweight = pinfo.get('weight') 485 lheight = self.lheights[pweight] 486 voffset = lheight - pheight 487 488 if einfo.get('looptop'): 489 490 x1, y1 = vg_layout.entry_pos(pinfo) 491 x2, y2 = vg_layout.entry_pos(kinfo) 492 493 xhalf = (x1 - x2) / 2 494 495 b = [ (x1, y1), 496 (x1, y1 - h_vpad), 497 (x2, y2 - h_vpad), 498 (x2, y2), 499 ] 500 501 elif einfo.get('loopbot'): 502 503 x1, y1 = vg_layout.exit_pos(pinfo) 504 x2, y2 = vg_layout.exit_pos(kinfo) 505 506 kwidth, kheight = kinfo.get('size', (0,0)) 507 kweight = kinfo.get('weight') 508 klheight = self.lheights[kweight] 509 510 kvoffset = klheight - kheight 511 512 pre_lines = [(x1, y1), (x1, y1 + voffset)] 513 post_lines = [(x2, y2), (x2, y2 + kvoffset)] 514 515 b = [ (x1, y1 + voffset), 516 (x1, y1 + voffset + h_vpad), 517 (x2, y2 + kvoffset + h_vpad), 518 (x2, y2 + kvoffset), 519 ] 520 521 else: 522 523 x1, y1 = vg_layout.exit_pos(pinfo) 524 x2, y2 = vg_layout.entry_pos(kinfo) 525 526 pre_lines = [(x1,y1), (x1, y1 + voffset)] 527 528 b = [ (x1, y1 + voffset), 529 (x1, y1 + voffset + h_vpad), 530 (x2, y2 - h_vpad), 531 (x2, y2), 532 ] 533 534 bez_lines = vg_bezier.calculate_bezier(b, 20) 535 536 einfo['edge_points'] = pre_lines + bez_lines + post_lines

537 #einfo['edge_points'] = bez_lines 538

Source Code for Module visgraph.layouts.dynadag