flumotion.common.dag

58 """ 59 I represent a Directed Acyclic Graph. 60 61 You can add objects to me as Nodes and then express dependency by 62 adding edges. 63 """

64 - def __init__(self):

65 self._nodes = {} # map of (object, type) -> NodeX 66 self._tainted = False # True after add/remove and no cycle check done 67 68 # topological sort stuff 69 self._count = 0 70 self._begin = {} # node -> begin count 71 self._end = {} # node -> end count 72 self._hasZeroEnd = [] # list of nodes that have end set to zero

73

74 - def _assertExists(self, object, type=0):

75 if not self.hasNode(object, type): 76 raise KeyError("No node for object %r, type %r" % (object, type))

77

78 - def addNode(self, object, type=0):

79 """ 80 I add a node to the DAG. 81 82 @param object: object to put in the DAG 83 @param type: optional type for the object 84 """ 85 if self.hasNode(object, type): 86 raise KeyError("Node for %r already exists with type %r" % ( 87 object, type)) 88 89 n = Node(object, type) 90 self._nodes[(object, type)] = n

91

92 - def hasNode(self, object, type=0):

93 """ 94 I check if a node exists in the DAG. 95 96 @param object: The object to check existence of. 97 @param type: An optional type for the object to check. 98 @type type: Integer 99 100 @rtype: Boolean 101 """ 102 if (object, type) in self._nodes.keys(): 103 return True 104 return False

105

106 - def removeNode(self, object, type=0):

107 """ 108 I remove a node that exists in the DAG. I also remove any edges 109 pointing to this node. 110 111 @param object: The object to remove. 112 @param type: The type of object to remove (optional). 113 """ 114 if not self.hasNode(object, type): 115 raise KeyError("Node for %r with type %r does not exist" % ( 116 object, type)) 117 node = self._getNode(object, type) 118 self.debug("Removing node (%r, %r)" % (object, type)) 119 # go through all the nodes and remove edges that end in this node 120 for somenodeobj,somenodetype in self._nodes: 121 somenode = self._nodes[(somenodeobj, somenodetype)] 122 if node in somenode.children: 123 self.removeEdge(somenodeobj, object, somenodetype, type) 124 125 del self._nodes[(object, type)]

126

127 - def _getNode(self, object, type=0):

128 value = self._nodes[(object, type)] 129 return value

130 131

132 - def addEdge(self, parent, child, parenttype=0, childtype=0):

133 """ 134 I add an edge between two nodes in the DAG. 135 136 @param parent: The object that is to be the parent. 137 @param child: The object that is to be the child. 138 @param parenttype: The type of the parent object (optional). 139 @param childtype: The type of the child object (optional). 140 """ 141 self._assertExists(parent, parenttype) 142 self._assertExists(child, childtype) 143 np = self._getNode(parent, parenttype) 144 nc = self._getNode(child, childtype) 145 146 if nc in np.children: 147 raise KeyError( 148 "%r of type %r is already a child of %r of type %r" % ( 149 child, childtype, parent, parenttype)) 150 151 self._tainted = True 152 np.children.append(nc) 153 nc.parents.append(np)

154

155 - def removeEdge(self, parent, child, parenttype=0, childtype=0):

156 """ 157 I remove an edge between two nodes in the DAG. 158 159 @param parent: The object that is the parent, 160 @param child: The object that is the child. 161 @param parenttype: The type of the parent object (optional). 162 @param childtype: The type of the child object (optional). 163 """ 164 self._assertExists(parent, parenttype) 165 self._assertExists(child, childtype) 166 np = self._nodes[(parent, parenttype)] 167 nc = self._nodes[(child, childtype)] 168 169 if nc not in np.children: 170 raise KeyError("%r is not a child of %r" % (child, parent)) 171 self.debug("Removing edge (%r ,%r) -> (%r, %r)" % (parent, parenttype, 172 child, childtype)) 173 self._tainted = True 174 np.children.remove(nc) 175 self.log("Children now: %r" % np.children) 176 nc.parents.remove(np)

177

178 - def getChildrenTyped(self, object, objtype=0, types=None):

179 """ 180 I return a list of (object, type) tuples that are direct children of 181 this object,objtype. 182 183 @param object: object to return children of 184 @param objtype: type of object (optional) 185 @param types: a list of types of children that you want. 186 None means all. 187 @type types: list 188 189 @rtype: list of (object, object) 190 """ 191 self._assertExists(object, objtype) 192 node = self._getNode(object, objtype) 193 194 l = node.children 195 if types: 196 l = [n for n in l if n.type in types] 197 198 return [(n.object, n.type) for n in l]

199

200 - def getChildren(self, object, objtype=0, types=None):

201 """ 202 I return a list of objects that are direct children of this 203 object,objtype. 204 205 @param object: object to return children of. 206 @param objtype: type of object (optional). 207 @type objtype: Integer 208 @param types: a list of types of children that you want. None means all. 209 @type types: list of Integers 210 211 @rtype: list of objects 212 """ 213 typedchildren = self.getChildrenTyped(object, objtype, types) 214 215 ret = [n[0] for n in typedchildren] 216 return ret

217

218 - def getParentsTyped(self, object, objtype=0, types=None):

219 """ 220 I return a list of (object, type) tuples that are direct parents of 221 this object, objtype. 222 223 @param object: object to return parents of 224 @param objtype: type of object (optional) 225 @param types: A list of types of parents that you want. 226 None means all. 227 @type types: list or None 228 229 @rtype: list of (object, object) 230 """ 231 self._assertExists(object, objtype) 232 node = self._getNode(object,objtype) 233 234 l = node.parents 235 if types: 236 l = [n for n in l if n.type in types] 237 238 return [(n.object, n.type) for n in l]

239

240 - def getParents(self, object, objtype=0, types=None):

241 """ 242 I return a list of objects that are direct parents of this 243 object, objtype. 244 245 @param object: object to return parents of. 246 @param objtype: type of object (optional) 247 @param types: List of types of parents that you want. None means all. 248 @type types: list 249 250 @rtype: list of (object, object) 251 """ 252 typedparents = self.getParentsTyped(object, objtype, types) 253 ret = [n[0] for n in typedparents] 254 return ret

255 256

257 - def getOffspringTyped(self, object, objtype=0, *types):

258 """ 259 I return a list of (object, type) tuples that are offspring of 260 this object,objtype. 261 262 @param object: object to return children of. 263 @param objtype: type of object (optional). 264 @type objtype: Integer 265 @param types: a list of types of children that you want. None means all. 266 @type types: list of Integers 267 268 @rtype: list of (object,Integer) 269 """ 270 self._assertExists(object, objtype) 271 node = self._getNode(object, objtype) 272 self.log("Getting offspring for (%r, %r)" % (object, objtype)) 273 # if we don't have children, don't bother trying 274 if not node.children: 275 self.log("Returning nothing") 276 return [] 277 278 # catches CycleError as well 279 sortedNodes = self._sortPreferred() 280 281 # start by adding our node to our to be expanded list 282 nodeList = [node] 283 offspring = [] 284 expand = True 285 # as long as we need to expand, loop over all offspring ... 286 while expand: 287 expand = False 288 for n in nodeList: 289 if n.children: 290 # .. and for every item add all of its children 291 # which triggers requiring further expansion 292 expand = True 293 nodeList.remove(n) 294 nodeList.extend(n.children) 295 offspring.extend(n.children) 296 297 # filter offspring by types 298 if types: 299 offspring = [n for n in offspring if n.type in types] 300 301 # now that we have all offspring, return a sorted list of them 302 ret = [] 303 for n in sortedNodes: 304 if n in offspring: 305 ret.append((n.object, n.type)) 306 307 for node in ret: 308 self.log("Offspring: (%r, %r)" % (node[0], node[1])) 309 return ret

310

311 - def getOffspring(self, object, objtype=0, *types):

312 """ 313 I return a list of objects that are offspring of this 314 object,objtype. 315 316 @param object: object to return children of. 317 @param objtype: type of object (optional). 318 @type objtype: Integer 319 @param types: types of children that you want offspring returned of. 320 321 @rtype: list of objects 322 """ 323 324 typedoffspring = self.getOffspringTyped(object, objtype, *types) 325 326 ret = [] 327 ret = [n[0] for n in typedoffspring] 328 329 return ret

330 331

332 - def getAncestorsTyped(self, object, objtype=0, *types):

333 """ 334 I return a list of (object, type) tuples that are ancestors of 335 this object,objtype. 336 337 @param object: object to return ancestors of. 338 @param objtype: type of object (optional). 339 @type objtype: Integer 340 @param types: types of ancestors that you want ancestors of. 341 342 @rtype: list of (object,Integer) 343 """ 344 self._assertExists(object, objtype) 345 node = self._getNode(object, objtype) 346 347 # if we don't have children, don't bother trying 348 if not node.parents: 349 return [] 350 351 # catches CycleError as well 352 sortedNodes = self._sortPreferred() 353 354 # start by adding our node to our to be expanded list 355 nodeList = [node] 356 ancestors = [] 357 expand = True 358 # as long as we need to expand, loop over all offspring ... 359 while expand: 360 expand = False 361 for n in nodeList: 362 if n.parents: 363 # .. and for every item add all of its children 364 # which triggers requiring further expansion 365 expand = True 366 nodeList.remove(n) 367 nodeList.extend(n.parents) 368 ancestors.extend(n.parents) 369 370 # filter offspring by types 371 if types: 372 ancestors = [n for n in ancestors if n.type in types] 373 374 # now that we have all offspring, return a sorted list of them 375 ret = [] 376 for n in sortedNodes: 377 if n in ancestors: 378 ret.append((n.object, n.type)) 379 380 return ret

381

382 - def getAncestors(self, object, objtype=0, *types):

383 """ 384 I return a list of objects that are ancestors of this object,objtype. 385 386 @param object: object to return ancestors of. 387 @param objtype: type of object (optional). 388 @type objtype: Integer 389 @param types: types of ancestors that you want returned. 390 391 @rtype: list of objects 392 """ 393 typedancestors = self.getAncestorsTyped(object, objtype, *types) 394 395 ret = [] 396 ret = [n[0] for n in typedancestors] 397 398 return ret

399 400

401 - def isFloating(self, object, objtype=0):

402 """ 403 I return whether the object is floating: no parents and no children. 404 405 @param object: object to check if floating. 406 @param objtype: type of object (optional). 407 @type objtype: Integer 408 409 @rtype: Boolean 410 """ 411 self._assertExists(object, objtype) 412 node = self._getNode(object, objtype) 413 414 return node.isFloating()

415

416 - def hasCycle(self):

417 """ 418 I return whether or not the graph has a cycle. 419 420 If it has, some operations on it will fail and raise CycleError. 421 """ 422 self._sortPreferred()

423

424 - def sort(self):

425 """ 426 I return a topologically sorted list of objects. 427 428 @rtype: list of (object, type) 429 """ 430 return [(node.object, node.type) for node in self._sortPreferred()]

431

432 - def _sortPreferred(self, list=None, clearState=True):

433 """ 434 I return a topologically sorted list of nodes, using list as a 435 preferred order for the algorithm. 436 437 @param list: a list of (object, type) tuples in preference order 438 @type list: list of (object, type) 439 440 @rtype: list of {Node} 441 """ 442 self._count = 0 443 for n in self._nodes.values(): 444 self._begin[n] = 0 445 self._end[n] = 0 446 if list: assert (n.object, n.type) in list 447 if list: 448 self._hasZeroEnd = [self._nodes[(n[0], n[1])] for n in list] 449 else: 450 self._hasZeroEnd = self._nodes.values() 451 452 while self._hasZeroEnd: 453 node = self._hasZeroEnd[0] 454 self._dfs(node) 455 456 # get a list of dictionary keys sorted in decreasing value order 457 l = [] 458 for node, count in self._end.items(): 459 l.append([count, node]) 460 461 l.sort() 462 l.reverse() 463 if clearState: 464 self._begin = {} 465 self._end = {} 466 self._hasZeroEnd = [] 467 return [node for count, node in l]

468

469 - def _dfs(self, node):

470 # perform depth first search 471 472 self._count += 1 473 474 self._begin[node] = self._count 475 476 # 2.3 477 # 2.3.b: detect cycle 478 nodes = [n for n in node.children 479 if self._begin[n] > 0 and self._end[n] == 0] 480 if nodes: 481 raise CycleError('nodes %r' % nodes) 482 483 # 2.3.a: perform dfs 484 # don't get a list of zerobegins first; do it step by step 485 486 for n in node.children: 487 if self._begin[n] > 0: 488 continue 489 self._dfs(n) 490 491 self._count += 1 492 self._end[node] = self._count 493 if node in self._hasZeroEnd: 494 self._hasZeroEnd.remove(node)

495

496 - def getAllNodesByType(self, type):

497 """ 498 I return all the objects with node type specified by type 499 500 @rtype: list of object 501 """ 502 ret = [] 503 for node in self._nodes.keys(): 504 if node[1] == type: 505 ret.append(self._nodes[node].object) 506 507 return ret

Source Code for Module flumotion.common.dag