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  """directed acyclic graph implementation. 
 23  Directed Acyclic Graph class and functionality 
 24  """ 
 25  from flumotion.common import log 
 26   
 27  __version__ = "$Rev: 6982 $" 
 28   
 29   
30 -class CycleError(Exception):
31 """ 32 A cycle was detected during execution of a function. 33 """
34
35 -class Node:
36 """ 37 I represent a Node in a Graph. 38 39 I am private to the Graph. 40 """
41 - def __init__(self, object, type=0):
42 self.object = object 43 self.type = type 44 self.parents = [] # FIXME: could be weakrefs to avoid cycles ? 45 self.children = []
46
47 - def isFloating(self):
48 """ 49 Returns whether the node is floating: no parents and no children. 50 """ 51 count = len(self.children) + len(self.parents) 52 if count: 53 return False 54 55 return True
56
57 -class DAG(log.Loggable):
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
508 509
510 -def topological_sort(items, partial_order):
511 """ 512 Perform topological sort. 513 514 @param items: list of items 515 @param partial_order: list of pairs. If pair (a,b) is in it, it 516 means that item a should appear before item b. 517 @returns: list of the items in one of the possible orders. Raises 518 DAG.CycleError if partial_order contains a loop. 519 """ 520 521 graph = DAG() 522 for v in items: 523 graph.addNode(v) 524 for a,b in partial_order: 525 graph.addEdge(a, b) 526 527 return [v for v, t in graph.sort()]
528