visgraph.graphcore

10 11 ''' 12 The base Graph object implements a simple nodes and edges graph. 13 14 Nodes - 15 Nodes consist of a dicionary of properties about that node and 16 a unique id which identifies the node in the current graph. From 17 API perspective a node is a tuple of (nodeid, nodeprops). 18 19 Edges - 20 Edges are directional sets of a from node-id and to node-id and 21 a piece of arbitrary edge information. 22 ''' 23

24 - def __init__(self):

25 self.wipeGraph() 26 self.nidgen = itertools.count() 27 self.eidgen = itertools.count() 28 self.metadata = {}

29

30 - def setMeta(self, mprop, mval):

31 self.metadata[mprop] = mval

32

33 - def getMeta(self, mprop, default=None):

34 return self.metadata.get(mprop, default)

35

36 - def wipeGraph(self):

37 ''' 38 Re-initialize the graph structures and start clean again. 39 ''' 40 self.edges = {} 41 self.nodes = {} 42 self.edge_by_from = {} 43 self.edge_by_to = {}

44

45 - def getEdges(self):

46 ''' 47 Get the list of edges in the graph. Edges are defined 48 as (eid, fromid, toid, einfo) tuples. 49 50 Example: for eid, fromid, toid, einfo in g.getEdges(): 51 ''' 52 return list(self.edges.values())

53

54 - def getEdge(self, eid):

55 ''' 56 Get the (eid, fromid, toid, einfo) tuple for the specified 57 edge. 58 59 Example: e = g.getEdge(eid) 60 ''' 61 return self.edges.get(eid, None)

62

63 - def getEdgeInfo(self, eid, key, default=None):

64 ''' 65 Get a property about an edge specified by from/to id. 66 67 Example: n = g.getEdgeInfo(eid 'name', 'Default Name') 68 ''' 69 edge = self.edges.get(eid) 70 if edge == None: 71 raise EdgeNonExistant(eid) 72 eid, fromid, toid, einfo = edge 73 return einfo.get(key, default)

74

75 - def setEdgeInfo(self, eid, key, value):

76 ''' 77 Set a key/value pair about a given edge by 78 it's from/to id. 79 80 Example: g.setEdgeInfo(eid, 'awesomeness', 99) 81 ''' 82 edge = self.edges.get(eid) 83 if edge == None: 84 raise EdgeNonExistant(eid) 85 eid, fromid, toid, einfo = edge 86 einfo[key] = value

87

88 - def setNodeInfo(self, nodeid, key, value):

89 ''' 90 Store a piece of information (by key:value) about a given node. 91 92 Example g.setNodeInfo(nid, 'Description', 'My Node Is Awesome!') 93 ''' 94 d = self.nodes.get(nodeid) 95 if d == None: 96 raise NodeNonExistant(nodeid) 97 d[key] = value

98

99 - def getNodeInfo(self, nodeid, key, default=None):

100 ''' 101 Retrieve a piece of information about a given node by key. 102 103 Example: descr = g.getNodeInfo(nid, 'Description', default='OH HAI') 104 ''' 105 d = self.nodes.get(nodeid) 106 if d == None: 107 raise NodeNonExistant(nodeid) 108 return d.get(key, default)

109

110 - def getNodeProps(self, nodeid):

111 ''' 112 Get the node info dictionary for the specified node. 113 114 Example: d = g.getNodeProps(nid) 115 ''' 116 return self.nodes.get(nodeid)

117

118 - def addNode(self, nodeid=None, ninfo=None, **kwargs):

119 ''' 120 Add a Node object to the graph. Returns the nodeid. 121 122 Example: nid = g.addNode() 123 g.addNode('woot', {'height':20, 'width':20}) 124 125 NOTE: If nodeid is unspecified, it is considered an 'anonymous' 126 node and will have an ID automagically assigned. 127 ''' 128 if nodeid == None: 129 nodeid = self.nidgen.next() 130 p = self.nodes.get(nodeid) 131 if p != None: 132 raise DuplicateNode(nodeid) 133 if ninfo == None: 134 ninfo = {} 135 ninfo.update(kwargs) 136 ninfo['nodeid'] = nodeid 137 self.nodes[nodeid] = ninfo 138 return nodeid

139

140 - def delNode(self, nid):

141 for eid,nfrom,nto,einfo in self.getRefsFrom(nid): 142 self.delEdge(eid) 143 for eid,nfrom,nto,einfo in self.getRefsTo(nid): 144 self.delEdge(eid) 145 return self.nodes.pop(nid)

146

147 - def getNode(self, nodeid):

148 ''' 149 Return the dictionary of properties for the specified node id. 150 ''' 151 return self.nodes.get(nodeid)

152

153 - def getNodes(self):

154 ''' 155 Return a list of (nodeid, nodeinfo) tuples. 156 ''' 157 return self.nodes.items()

158

159 - def hasNode(self, nodeid):

160 ''' 161 Check if a given node is present within the graph. 162 163 Example: if g.hasNode('yermom'): print 'woot' 164 ''' 165 return self.getNode(nodeid) != None

166

167 - def addEdge(self, fromid, toid, eid=None, einfo=None, **kwargs):

168 ''' 169 Add an edge to the graph. Edges are directional. 170 171 Example: g.addEdge(node_1, node_2, einfo={'name':'Woot Edge'}) 172 ''' 173 if einfo == None: 174 einfo = {} 175 einfo.update(kwargs) 176 if eid == None: 177 eid = self.eidgen.next() 178 e = (eid, fromid, toid, einfo) 179 self.edges[eid] = e 180 xlist = self.edge_by_from.get(fromid) 181 if xlist == None: 182 xlist = [] 183 self.edge_by_from[fromid] = xlist 184 ylist = self.edge_by_to.get(toid) 185 if ylist == None: 186 ylist = [] 187 self.edge_by_to[toid] = ylist 188 xlist.append(e) 189 ylist.append(e) 190 return eid

191

192 - def delEdge(self, eid):

193 ''' 194 Delete an edge from the graph (by eid). 195 196 Example: g.delEdge(eid) 197 ''' 198 e = self.edges.pop(eid, None) 199 if e == None: 200 raise EdgeNonExistant(eid) 201 202 eid, fromid, toid, einfo = e 203 self.edge_by_to[toid] = [ x for x in self.edge_by_to[toid] if x[0] != eid ] 204 self.edge_by_from[fromid] = [ x for x in self.edge_by_from[fromid] if x[0] != eid ]

205

206 - def getRefsFrom(self, nodeid):

207 ''' 208 Return a list of edges which originate with us. 209 210 Example: for eid, fromid, toid, einfo in g.getRefsFrom(id) 211 ''' 212 ret = self.edge_by_from.get(nodeid) 213 if ret == None: 214 ret = [] 215 return ret

216

217 - def getRefsTo(self, nodeid):

218 ''' 219 Return a list of edges which terminate at us. 220 221 Example: for eid, fromid, toid, einfo in g.getRefsFrom(id) 222 ''' 223 ret = self.edge_by_to.get(nodeid) 224 if ret == None: 225 ret = [] 226 return ret

227

228 - def getClusterGraphs(self):

229 ''' 230 Return a list of the subgraph clusters (as graphs) contained 231 within this graph. A subgraph "cluster" is defined as a 232 group of interconnected nodes. This can be used to split 233 out grouped subgraphs from within a larger graph. 234 ''' 235 ret = [] 236 nodes = self.getNodes() 237 done = {} 238 while len(nodes): 239 nid, ninfo = nodes.pop() 240 if done.get(nid): 241 continue 242 243 # Generate the cluster subgraph 244 todo = [ (nid, ninfo), ] 245 g = Graph() 246 247 while len(todo): 248 gnid, gninfo = todo.pop() 249 250 done[gnid] = True 251 252 if not g.getNode(gnid): 253 g.addNode(nodeid=gnid, ninfo=gninfo) 254 255 for eid,n1,n2,einfo in self.getRefsFrom(gnid): 256 257 if not g.getNode(n2): 258 n2info = self.getNodeProps(n2) 259 g.addNode(nodeid=n2, ninfo=n2info) 260 todo.append((n2, n2info)) 261 262 if not g.getEdge(eid): 263 g.addEdge(n1, n2, eid=eid, einfo=einfo) 264 265 for eid,n1,n2,einfo in self.getRefsTo(gnid): 266 267 if not g.getNode(n1): 268 n1info = self.getNodeProps(n1) 269 g.addNode(nodeid=n1, ninfo=n1info) 270 todo.append((n1, n1info)) 271 272 if not g.getEdge(eid): 273 g.addEdge(n1, n2, eid=eid, einfo=einfo) 274 275 ret.append(g) 276 277 return ret

278 279

280 - def pathSearchOne(self, *args, **kwargs):

281 for p in self.pathSearch(*args, **kwargs): 282 return p

283

284 - def pathSearch(self, fromid, toid=None, edgecb=None, tocb=None):

285 ''' 286 Search for the shortest path from one node to another 287 with the option to filter based on edges using 288 edgecb. edgecb should be a function: 289 290 def myedgecb(graph, eid, fromid, toid, depth) 291 292 which returns True if it's OK to traverse this node 293 in the search. 294 295 Additionally, toid may be None and the caller may specify 296 tocb with a function such as: 297 298 def mytocb(graph, nid) 299 300 which must return True on finding the target node 301 302 Returns a list of edge ids... 303 ''' 304 305 if toid == None and tocb == None: 306 raise Exception('You must use either toid or tocb!') 307 308 root = vg_pathcore.newPathNode(nid=fromid, eid=None) 309 310 todo = [(root, 0),] 311 312 # FIXME make this a deque so it can be FIFO 313 while len(todo): 314 315 pnode,depth = todo.pop() # popleft() 316 ppnode, pkids, pprops = pnode 317 318 nid = pprops.get('nid') 319 for edge in self.getRefsFrom(nid): 320 321 eid, srcid, dstid, einfo = edge 322 323 if vg_pathcore.isPathLoop(pnode, 'nid', dstid): 324 continue 325 326 # Check if the callback is present and likes us... 327 if edgecb != None: 328 if not edgecb(self, edge, depth): 329 continue 330 331 # Are we the match? 332 match = False 333 if dstid == toid: 334 match = True 335 336 if tocb and tocb(self, dstid): 337 match = True 338 339 if match: 340 341 m = vg_pathcore.newPathNode(pnode, nid=dstid, eid=eid) 342 path = vg_pathcore.getPathToNode(m) 343 344 ret = [] 345 for ppnode, pkids, pprops in path: 346 eid = pprops.get('eid') 347 if eid != None: 348 ret.append(eid) 349 350 yield ret 351 352 # Add the next set of choices to evaluate. 353 branch = vg_pathcore.newPathNode(pnode, nid=dstid, eid=eid) 354 todo.append((branch, depth+1))

355 356 #return [] 357

358 - def pathSearchFrom(self, fromid, nodecb, edgecb=None):

359 ''' 360 Search from the specified node (breadth first) until you 361 find a node where nodecb(graph, nid) == True. See 362 pathSearchFromTo for docs on edgecb... 363 '''

366 ''' 367 An extension to the graph base which implements the idea of hierarchy 368 keeping a weight relationship based on the added edges. 369 Edges are directional from X to y. 370 371 You must add nodes with the property "rootnode" to know where the 372 hierarchy begins! 373 '''

374 - def __init__(self):

375 Graph.__init__(self)

376

377 - def getRootNodes(self):

378 ''' 379 Get all the node id's in this graph which are weight 0 (meaning 380 they have no parents)... 381 ''' 382 ret = [] 383 for nid, nprops in self.nodes.items(): 384 if nprops.get('rootnode', False): 385 ret.append(nid) 386 return ret

387

388 - def getNodeWeights(self):

389 ''' 390 Calculate the node weights for the given nodes in the hierarchical 391 graph based on the added "rootnode" nodes. This will return a dict 392 of { nodeid: weight, } key-pairs. 393 394 # NOTE: This will also set the 'weight' property on the nodes 395 ''' 396 weights = {} 397 todo = [ (r, []) for r in self.getRootNodes() ] 398 while len(todo): 399 400 nid, path = todo.pop() 401 402 cweight = weights.get(nid, 0) 403 weights[nid] = max(cweight, len(path)) 404 405 path.append(nid) 406 407 for eid, fromid, toid, einfo in self.getRefsFrom(nid): 408 if weights.get(toid, -1) >= len(path): 409 continue 410 if toid not in path: 411 todo.append((toid, list(path))) 412 413 for nid,weight in weights.items(): 414 self.setNodeInfo(nid, 'weight', weight) 415 416 return weights

417

418 - def getPathCount(self):

419 ''' 420 Return the number of non-looped paths through this function. 421 422 NOTE: one small issue, "spiral" functions where the leaf node 423 has a lower weight than a block which must reach it by a 424 looped path will be a few total paths short... 425 ''' 426 427 nodes = [] 428 leafnodes = [] 429 430 # We must put all nodes into weight order 431 weights = self.getNodeWeights() 432 433 # Initialize all nodes to 0 434 # (and populate leafnodes list...) 435 for nid,ninfo in self.getNodes(): 436 437 nodes.append( (weights.get(nid), nid, ninfo) ) 438 ninfo['pathcount'] = 0 439 440 # No refs from means leaf 441 xrfcnt = len(self.getRefsFrom(nid)) 442 if xrfcnt == 0: 443 leafnodes.append((nid,ninfo)) 444 445 # Seed root nodes with a path 446 if ninfo.get('rootnode'): 447 ninfo['pathcount'] = 1 448 continue 449 450 # Lets make the list of nodes *ordered* by weight 451 nodes.sort() 452 453 # Now tally ho! 454 for weight, nid, ninfo in nodes: 455 456 # Here's the magic... In *hierarchy order* each node 457 # gets the sum of the paths of his parents. 458 for eid, fromid, toid, einfo in self.getRefsFrom(nid): 459 props = self.getNodeProps(toid) 460 # A reference to somebody at our weight (probably self) 461 # is considered a loop... 462 if weights[toid] == weight: 463 continue 464 props['pathcount'] += ninfo['pathcount'] 465 466 totcount = 0 467 for nid,ninfo in leafnodes: 468 totcount += ninfo['pathcount'] 469 470 return totcount

Source Code for Module visgraph.graphcore