Package flumotion :: Package common :: Module dag
[hide private]

Source Code for Module flumotion.common.dag

  1  # -*- Mode: Python; test-case-name: flumotion.test.test_dag -*- 
  2  # vi:si:et:sw=4:sts=4:ts=4 
  3  # 
  4  # Flumotion - a streaming media server 
  5  # Copyright (C) 2004,2005,2006,2007 Fluendo, S.L. (www.fluendo.com). 
  6  # All rights reserved. 
  7   
  8  # This file may be distributed and/or modified under the terms of 
  9  # the GNU General Public License version 2 as published by 
 10  # the Free Software Foundation. 
 11  # This file is distributed without any warranty; without even the implied 
 12  # warranty of merchantability or fitness for a particular purpose. 
 13  # See "LICENSE.GPL" in the source distribution for more information. 
 14   
 15  # Licensees having purchased or holding a valid Flumotion Advanced 
 16  # Streaming Server license may use this file in accordance with the 
 17  # Flumotion Advanced Streaming Server Commercial License Agreement. 
 18  # See "LICENSE.Flumotion" in the source distribution for more information. 
 19   
 20  # Headers in this file shall remain intact. 
 21   
 22  """ 
 23  Directed Acyclic Graph class and functionality 
 24  """ 
 25  from flumotion.common import log 
 26   
27 -class CycleError(Exception):
28 """ 29 A cycle was detected during execution of a function. 30 """
31
32 -class Node:
33 """ 34 I represent a Node in a Graph. 35 36 I am private to the Graph. 37 """
38 - def __init__(self, object, type=0):
39 self.object = object 40 self.type = type 41 self.parents = [] # FIXME: could be weakrefs to avoid cycles ? 42 self.children = []
43
44 - def isFloating(self):
45 """ 46 Returns whether the node is floating: no parents and no children. 47 """ 48 count = len(self.children) + len(self.parents) 49 if count: 50 return False 51 52 return True
53
54 -class DAG(log.Loggable):
55 """ 56 I represent a Directed Acyclic Graph. 57 58 You can add objects to me as Nodes and then express dependency by 59 adding edges. 60 """
61 - def __init__(self):
62 self._nodes = {} # map of (object, type) -> NodeX 63 self._tainted = False # True after add/remove and no cycle check done 64 65 # topological sort stuff 66 self._count = 0 67 self._begin = {} # node -> begin count 68 self._end = {} # node -> end count 69 self._hasZeroEnd = [] # list of nodes that have end set to zero
70
71 - def _assertExists(self, object, type=0):
72 if not self.hasNode(object, type): 73 raise KeyError("No node for object %r, type %r" % (object, type))
74
75 - def addNode(self, object, type=0):
76 """ 77 I add a node to the DAG. 78 79 @param object: object to put in the DAG 80 @param type: optional type for the object 81 """ 82 if self.hasNode(object, type): 83 raise KeyError("Node for %r already exists with type %r" % ( 84 object, type)) 85 86 n = Node(object, type) 87 self._nodes[(object, type)] = n
88
89 - def hasNode(self, object, type=0):
90 """ 91 I check if a node exists in the DAG. 92 93 @param object: The object to check existence of. 94 @param type: An optional type for the object to check. 95 @type type: Integer 96 97 @rtype: Boolean 98 """ 99 if (object, type) in self._nodes.keys(): 100 return True 101 return False
102
103 - def removeNode(self, object, type=0):
104 """ 105 I remove a node that exists in the DAG. I also remove any edges 106 pointing to this node. 107 108 @param object: The object to remove. 109 @param type: The type of object to remove (optional). 110 """ 111 if not self.hasNode(object, type): 112 raise KeyError("Node for %r with type %r does not exist" % ( 113 object, type)) 114 node = self._getNode(object, type) 115 self.debug("Removing node (%r, %r)" % (object, type)) 116 # go through all the nodes and remove edges that end in this node 117 for somenodeobj,somenodetype in self._nodes: 118 somenode = self._nodes[(somenodeobj, somenodetype)] 119 if node in somenode.children: 120 self.removeEdge(somenodeobj, object, somenodetype, type) 121 122 del self._nodes[(object, type)]
123
124 - def _getNode(self, object, type=0):
125 value = self._nodes[(object, type)] 126 return value
127 128
129 - def addEdge(self, parent, child, parenttype=0, childtype=0):
130 """ 131 I add an edge between two nodes in the DAG. 132 133 @param parent: The object that is to be the parent. 134 @param child: The object that is to be the child. 135 @param parenttype: The type of the parent object (optional). 136 @param childtype: The type of the child object (optional). 137 """ 138 self._assertExists(parent, parenttype) 139 self._assertExists(child, childtype) 140 np = self._getNode(parent, parenttype) 141 nc = self._getNode(child, childtype) 142 143 if nc in np.children: 144 raise KeyError( 145 "%r of type %r is already a child of %r of type %r" % ( 146 child, childtype, parent, parenttype)) 147 148 self._tainted = True 149 np.children.append(nc) 150 nc.parents.append(np)
151
152 - def removeEdge(self, parent, child, parenttype=0, childtype=0):
153 """ 154 I remove an edge between two nodes in the DAG. 155 156 @param parent: The object that is the parent, 157 @param child: The object that is the child. 158 @param parenttype: The type of the parent object (optional). 159 @param childtype: The type of the child object (optional). 160 """ 161 self._assertExists(parent, parenttype) 162 self._assertExists(child, childtype) 163 np = self._nodes[(parent, parenttype)] 164 nc = self._nodes[(child, childtype)] 165 166 if nc not in np.children: 167 raise KeyError("%r is not a child of %r" % (child, parent)) 168 self.debug("Removing edge (%r ,%r) -> (%r, %r)" % (parent, parenttype, 169 child, childtype)) 170 self._tainted = True 171 np.children.remove(nc) 172 self.log("Children now: %r" % np.children) 173 nc.parents.remove(np)
174
175 - def getChildrenTyped(self, object, objtype=0, types=None):
176 """ 177 I return a list of (object, type) tuples that are direct children of 178 this object,objtype. 179 180 @param object: object to return children of 181 @param objtype: type of object (optional) 182 @param types: a list of types of children that you want. 183 None means all. 184 @type types: list 185 186 @rtype: list of (object, object) 187 """ 188 self._assertExists(object, objtype) 189 node = self._getNode(object, objtype) 190 191 l = node.children 192 if types: 193 l = filter(lambda n: n.type in types, l) 194 195 return [(n.object, n.type) for n in l]
196
197 - def getChildren(self, object, objtype=0, types=None):
198 """ 199 I return a list of objects that are direct children of this 200 object,objtype. 201 202 @param object: object to return children of. 203 @param objtype: type of object (optional). 204 @type objtype: Integer 205 @param types: a list of types of children that you want. None means all. 206 @type types: list of Integers 207 208 @rtype: list of objects 209 """ 210 typedchildren = self.getChildrenTyped(object, objtype, types) 211 212 ret = [n[0] for n in typedchildren] 213 return ret
214
215 - def getParentsTyped(self, object, objtype=0, types=None):
216 """ 217 I return a list of (object, type) tuples that are direct parents of 218 this object, objtype. 219 220 @param object: object to return parents of 221 @param objtype: type of object (optional) 222 @param types: A list of types of parents that you want. 223 None means all. 224 @type types: list or None 225 226 @rtype: list of (object, object) 227 """ 228 self._assertExists(object, objtype) 229 node = self._getNode(object,objtype) 230 231 l = node.parents 232 if types: 233 l = filter(lambda n: n.type in types, l) 234 235 return [(n.object, n.type) for n in l]
236
237 - def getParents(self, object, objtype=0, types=None):
238 """ 239 I return a list of objects that are direct parents of this 240 object, objtype. 241 242 @param object: object to return parents of. 243 @param objtype: type of object (optional) 244 @param types: List of types of parents that you want. None means all. 245 @type types: list 246 247 @rtype: list of (object, object) 248 """ 249 typedparents = self.getParentsTyped(object, objtype, types) 250 ret = [n[0] for n in typedparents] 251 return ret
252 253
254 - def getOffspringTyped(self, object, objtype=0, *types):
255 """ 256 I return a list of (object, type) tuples that are offspring of 257 this object,objtype. 258 259 @param object: object to return children of. 260 @param objtype: type of object (optional). 261 @type objtype: Integer 262 @param types: a list of types of children that you want. None means all. 263 @type types: list of Integers 264 265 @rtype: list of (object,Integer) 266 """ 267 self._assertExists(object, objtype) 268 node = self._getNode(object, objtype) 269 self.log("Getting offspring for (%r, %r)" % (object, objtype)) 270 # if we don't have children, don't bother trying 271 if not node.children: 272 self.log("Returning nothing") 273 return [] 274 275 # catches CycleError as well 276 sorted = self._sortPreferred() 277 278 # start by adding our node to our to be expanded list 279 list = [node] 280 offspring = [] 281 expand = True 282 # as long as we need to expand, loop over all offspring ... 283 while expand: 284 expand = False 285 for n in list: 286 if n.children: 287 # .. and for every item add all of its children 288 # which triggers requiring further expansion 289 expand = True 290 list.remove(n) 291 list.extend(n.children) 292 offspring.extend(n.children) 293 294 # filter offspring by types 295 if types: 296 offspring = filter(lambda n: n.type in types, offspring) 297 298 # now that we have all offspring, return a sorted list of them 299 ret = [] 300 for n in sorted: 301 if n in offspring: 302 ret.append((n.object, n.type)) 303 304 for node in ret: 305 self.log("Offspring: (%r, %r)" % (node[0], node[1])) 306 return ret
307
308 - def getOffspring(self, object, objtype=0, *types):
309 """ 310 I return a list of objects that are offspring of this 311 object,objtype. 312 313 @param object: object to return children of. 314 @param objtype: type of object (optional). 315 @type objtype: Integer 316 @param types: types of children that you want offspring returned of. 317 318 @rtype: list of objects 319 """ 320 321 typedoffspring = self.getOffspringTyped(object, objtype, *types) 322 323 ret = [] 324 ret = [n[0] for n in typedoffspring] 325 326 return ret
327 328
329 - def getAncestorsTyped(self, object, objtype=0, *types):
330 """ 331 I return a list of (object, type) tuples that are ancestors of 332 this object,objtype. 333 334 @param object: object to return ancestors of. 335 @param objtype: type of object (optional). 336 @type objtype: Integer 337 @param types: types of ancestors that you want ancestors of. 338 339 @rtype: list of (object,Integer) 340 """ 341 self._assertExists(object, objtype) 342 node = self._getNode(object, objtype) 343 344 # if we don't have children, don't bother trying 345 if not node.parents: 346 return [] 347 348 # catches CycleError as well 349 sorted = self._sortPreferred() 350 351 # start by adding our node to our to be expanded list 352 list = [node] 353 ancestors = [] 354 expand = True 355 # as long as we need to expand, loop over all offspring ... 356 while expand: 357 expand = False 358 for n in list: 359 if n.parents: 360 # .. and for every item add all of its children 361 # which triggers requiring further expansion 362 expand = True 363 list.remove(n) 364 list.extend(n.parents) 365 ancestors.extend(n.parents) 366 367 # filter offspring by types 368 if types: 369 ancestors = filter(lambda n: n.type in types, ancestors) 370 371 # now that we have all offspring, return a sorted list of them 372 ret = [] 373 for n in sorted: 374 if n in ancestors: 375 ret.append((n.object, n.type)) 376 377 return ret
378
379 - def getAncestors(self, object, objtype=0, *types):
380 """ 381 I return a list of objects that are ancestors of this object,objtype. 382 383 @param object: object to return ancestors of. 384 @param objtype: type of object (optional). 385 @type objtype: Integer 386 @param types: types of ancestors that you want returned. 387 388 @rtype: list of objects 389 """ 390 typedancestors = self.getAncestorsTyped(object, objtype, *types) 391 392 ret = [] 393 ret = [n[0] for n in typedancestors] 394 395 return ret
396 397
398 - def isFloating(self, object, objtype=0):
399 """ 400 I return whether the object is floating: no parents and no children. 401 402 @param object: object to check if floating. 403 @param objtype: type of object (optional). 404 @type objtype: Integer 405 406 @rtype: Boolean 407 """ 408 self._assertExists(object, objtype) 409 node = self._getNode(object, objtype) 410 411 return node.isFloating()
412
413 - def hasCycle(self):
414 """ 415 I return whether or not the graph has a cycle. 416 417 If it has, some operations on it will fail and raise CycleError. 418 """ 419 self._sortPreferred()
420
421 - def sort(self):
422 """ 423 I return a topologically sorted list of objects. 424 425 @rtype: list of (object, type) 426 """ 427 return [(node.object, node.type) for node in self._sortPreferred()]
428
429 - def _sortPreferred(self, list=None, clearState=True):
430 """ 431 I return a topologically sorted list of nodes, using list as a 432 preferred order for the algorithm. 433 434 @param list: a list of (object, type) tuples in preference order 435 @type list: list of (object, type) 436 437 @rtype: list of {Node} 438 """ 439 self._count = 0 440 for n in self._nodes.values(): 441 self._begin[n] = 0 442 self._end[n] = 0 443 if list: assert (n.object, n.type) in list 444 if list: 445 self._hasZeroEnd = [self._nodes[(n[0], n[1])] for n in list] 446 else: 447 self._hasZeroEnd = self._nodes.values() 448 449 while self._hasZeroEnd: 450 node = self._hasZeroEnd[0] 451 self._dfs(node) 452 453 # get a list of dictionary keys sorted in decreasing value order 454 l = [] 455 for node, count in self._end.items(): 456 l.append([count, node]) 457 458 l.sort() 459 l.reverse() 460 if clearState: 461 self._begin = {} 462 self._end = {} 463 self._hasZeroEnd = [] 464 return [node for count, node in l]
465
466 - def _dfs(self, node):
467 # perform depth first search 468 469 self._count += 1 470 471 self._begin[node] = self._count 472 473 # 2.3 474 # 2.3.b: detect cycle 475 hasCycle = lambda n: self._begin[n] > 0 and self._end[n] == 0 476 nodes = filter(hasCycle, node.children) 477 if nodes: 478 raise CycleError('nodes %r' % nodes) 479 480 # 2.3.a: perform dfs 481 # don't get a list of zerobegins first; do it step by step 482 483 for n in node.children: 484 if self._begin[n] > 0: 485 continue 486 self._dfs(n) 487 488 self._count += 1 489 self._end[node] = self._count 490 if node in self._hasZeroEnd: 491 self._hasZeroEnd.remove(node)
492
493 - def getAllNodesByType(self, type):
494 """ 495 I return all the objects with node type specified by type 496 497 @rtype: list of object 498 """ 499 ret = [] 500 for node in self._nodes.keys(): 501 if node[1] == type: 502 ret.append(self._nodes[node].object) 503 504 return ret
505 506
507 -def topological_sort(items, partial_order):
508 """ 509 Perform topological sort. 510 511 @param items: list of items 512 @param partial_order: list of pairs. If pair (a,b) is in it, it 513 means that item a should appear before item b. 514 @returns: list of the items in one of the possible orders. Raises 515 DAG.CycleError if partial_order contains a loop. 516 """ 517 518 graph = DAG() 519 for v in items: 520 graph.addNode(v) 521 for a,b in partial_order: 522 graph.addEdge(a, b) 523 524 return [v for v, t in graph.sort()]
525