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,2008,2009 Fluendo, S.L. 
  6  # Copyright (C) 2010,2011 Flumotion Services, S.A. 
  7  # All rights reserved. 
  8  # 
  9  # This file may be distributed and/or modified under the terms of 
 10  # the GNU Lesser General Public License version 2.1 as published by 
 11  # the Free Software Foundation. 
 12  # This file is distributed without any warranty; without even the implied 
 13  # warranty of merchantability or fitness for a particular purpose. 
 14  # See "LICENSE.LGPL" in the source distribution for more information. 
 15  # 
 16  # Headers in this file shall remain intact. 
 17   
 18  """directed acyclic graph implementation. 
 19  Directed Acyclic Graph class and functionality 
 20  """ 
 21  from flumotion.common import log 
 22   
 23  __version__ = "$Rev$" 
 24   
 25   
26 -class CycleError(Exception):
27 """ 28 A cycle was detected during execution of a function. 29 """
30 31
32 -class Node:
33 """ 34 I represent a Node in a Graph. 35 36 I am private to the Graph. 37 """ 38
39 - def __init__(self, object, type=0):
40 self.object = object 41 self.type = type 42 self.parents = [] # FIXME: could be weakrefs to avoid cycles ? 43 self.children = []
44
45 - def isFloating(self):
46 """ 47 Returns whether the node is floating: no parents and no children. 48 """ 49 count = len(self.children) + len(self.parents) 50 if count: 51 return False 52 53 return True
54 55
56 -class DAG(log.Loggable):
57 """ 58 I represent a Directed Acyclic Graph. 59 60 You can add objects to me as Nodes and then express dependency by 61 adding edges. 62 """ 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 - def addEdge(self, parent, child, parenttype=0, childtype=0):
132 """ 133 I add an edge between two nodes in the DAG. 134 135 @param parent: The object that is to be the parent. 136 @param child: The object that is to be the child. 137 @param parenttype: The type of the parent object (optional). 138 @param childtype: The type of the child object (optional). 139 """ 140 self._assertExists(parent, parenttype) 141 self._assertExists(child, childtype) 142 np = self._getNode(parent, parenttype) 143 nc = self._getNode(child, childtype) 144 145 if nc in np.children: 146 raise KeyError( 147 "%r of type %r is already a child of %r of type %r" % ( 148 child, childtype, parent, parenttype)) 149 150 self._tainted = True 151 np.children.append(nc) 152 nc.parents.append(np)
153
154 - def removeEdge(self, parent, child, parenttype=0, childtype=0):
155 """ 156 I remove an edge between two nodes in the DAG. 157 158 @param parent: The object that is the parent, 159 @param child: The object that is the child. 160 @param parenttype: The type of the parent object (optional). 161 @param childtype: The type of the child object (optional). 162 """ 163 self._assertExists(parent, parenttype) 164 self._assertExists(child, childtype) 165 np = self._nodes[(parent, parenttype)] 166 nc = self._nodes[(child, childtype)] 167 168 if nc not in np.children: 169 raise KeyError("%r is not a child of %r" % (child, parent)) 170 self.debug("Removing edge (%r ,%r) -> (%r, %r)" % (parent, parenttype, 171 child, childtype)) 172 self._tainted = True 173 np.children.remove(nc) 174 self.log("Children now: %r" % np.children) 175 nc.parents.remove(np)
176
177 - def getChildrenTyped(self, object, objtype=0, types=None):
178 """ 179 I return a list of (object, type) tuples that are direct children of 180 this object,objtype. 181 182 @param object: object to return children of 183 @param objtype: type of object (optional) 184 @param types: a list of types of children that you want. 185 None means all. 186 @type types: list 187 188 @rtype: list of (object, object) 189 """ 190 self._assertExists(object, objtype) 191 node = self._getNode(object, objtype) 192 193 l = node.children 194 if types: 195 l = [n for n in l if n.type in types] 196 197 return [(n.object, n.type) for n in l]
198
199 - def getChildren(self, object, objtype=0, types=None):
200 """ 201 I return a list of objects that are direct children of this 202 object,objtype. 203 204 @param object: object to return children of. 205 @param objtype: type of object (optional). 206 @type objtype: Integer 207 @param types: a list of types of children that you want. 208 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 - def getOffspringTyped(self, object, objtype=0, *types):
257 """ 258 I return a list of (object, type) tuples that are offspring of 259 this object,objtype. 260 261 @param object: object to return children of. 262 @param objtype: type of object (optional). 263 @type objtype: Integer 264 @param types: a list of types of children that you want. 265 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 - def getAncestorsTyped(self, object, objtype=0, *types):
332 """ 333 I return a list of (object, type) tuples that are ancestors of 334 this object,objtype. 335 336 @param object: object to return ancestors of. 337 @param objtype: type of object (optional). 338 @type objtype: Integer 339 @param types: types of ancestors that you want ancestors of. 340 341 @rtype: list of (object,Integer) 342 """ 343 self._assertExists(object, objtype) 344 node = self._getNode(object, objtype) 345 346 # if we don't have children, don't bother trying 347 if not node.parents: 348 return [] 349 350 # catches CycleError as well 351 sortedNodes = self._sortPreferred() 352 353 # start by adding our node to our to be expanded list 354 nodeList = [node] 355 ancestors = [] 356 expand = True 357 # as long as we need to expand, loop over all offspring ... 358 while expand: 359 expand = False 360 for n in nodeList: 361 if n.parents: 362 # .. and for every item add all of its children 363 # which triggers requiring further expansion 364 expand = True 365 nodeList.remove(n) 366 nodeList.extend(n.parents) 367 ancestors.extend(n.parents) 368 369 # filter offspring by types 370 if types: 371 ancestors = [n for n in ancestors if n.type in types] 372 373 # now that we have all offspring, return a sorted list of them 374 ret = [] 375 for n in sortedNodes: 376 if n in ancestors: 377 ret.append((n.object, n.type)) 378 379 return ret
380
381 - def getAncestors(self, object, objtype=0, *types):
382 """ 383 I return a list of objects that are ancestors of this object,objtype. 384 385 @param object: object to return ancestors of. 386 @param objtype: type of object (optional). 387 @type objtype: Integer 388 @param types: types of ancestors that you want returned. 389 390 @rtype: list of objects 391 """ 392 typedancestors = self.getAncestorsTyped(object, objtype, *types) 393 394 ret = [] 395 ret = [n[0] for n in typedancestors] 396 397 return ret
398
399 - def isFloating(self, object, objtype=0):
400 """ 401 I return whether the object is floating: no parents and no children. 402 403 @param object: object to check if floating. 404 @param objtype: type of object (optional). 405 @type objtype: Integer 406 407 @rtype: Boolean 408 """ 409 self._assertExists(object, objtype) 410 node = self._getNode(object, objtype) 411 412 return node.isFloating()
413
414 - def hasCycle(self):
415 """ 416 I return whether or not the graph has a cycle. 417 418 If it has, some operations on it will fail and raise CycleError. 419 """ 420 self._sortPreferred()
421
422 - def sort(self):
423 """ 424 I return a topologically sorted list of objects. 425 426 @rtype: list of (object, type) 427 """ 428 return [(node.object, node.type) for node in self._sortPreferred()]
429
430 - def _sortPreferred(self, list=None, clearState=True):
431 """ 432 I return a topologically sorted list of nodes, using list as a 433 preferred order for the algorithm. 434 435 @param list: a list of (object, type) tuples in preference order 436 @type list: list of (object, type) 437 438 @rtype: list of {Node} 439 """ 440 self._count = 0 441 for n in self._nodes.values(): 442 self._begin[n] = 0 443 self._end[n] = 0 444 if list: 445 assert (n.object, n.type) in list 446 if list: 447 self._hasZeroEnd = [self._nodes[(n[0], n[1])] for n in list] 448 else: 449 self._hasZeroEnd = self._nodes.values() 450 451 while self._hasZeroEnd: 452 node = self._hasZeroEnd[0] 453 self._dfs(node) 454 455 # get a list of dictionary keys sorted in decreasing value order 456 l = [] 457 for node, count in self._end.items(): 458 l.append([count, node]) 459 460 l.sort() 461 l.reverse() 462 if clearState: 463 self._begin = {} 464 self._end = {} 465 self._hasZeroEnd = [] 466 return [node for count, node in l]
467
468 - def _dfs(self, node):
469 # perform depth first search 470 471 self._count += 1 472 473 self._begin[node] = self._count 474 475 # 2.3 476 # 2.3.b: detect cycle 477 nodes = [n for n in node.children 478 if self._begin[n] > 0 and self._end[n] == 0] 479 if nodes: 480 raise CycleError('nodes %r' % nodes) 481 482 # 2.3.a: perform dfs 483 # don't get a list of zerobegins first; do it step by step 484 485 for n in node.children: 486 if self._begin[n] > 0: 487 continue 488 self._dfs(n) 489 490 self._count += 1 491 self._end[node] = self._count 492 if node in self._hasZeroEnd: 493 self._hasZeroEnd.remove(node)
494
495 - def getAllNodesByType(self, type):
496 """ 497 I return all the objects with node type specified by type 498 499 @rtype: list of object 500 """ 501 ret = [] 502 for node in self._nodes.keys(): 503 if node[1] == type: 504 ret.append(self._nodes[node].object) 505 506 return ret
507 508
509 -def topological_sort(items, partial_order):
510 """ 511 Perform topological sort. 512 513 @param items: list of items 514 @param partial_order: list of pairs. If pair (a,b) is in it, it 515 means that item a should appear before item b. 516 @returns: list of the items in one of the possible orders. Raises 517 DAG.CycleError if partial_order contains a loop. 518 """ 519 520 graph = DAG() 521 for v in items: 522 graph.addNode(v) 523 for a, b in partial_order: 524 graph.addEdge(a, b) 525 526 return [v for v, t in graph.sort()]
527