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