1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
27 """
28 A cycle was detected during execution of a function.
29 """
30
31
33 """
34 I represent a Node in a Graph.
35
36 I am private to the Graph.
37 """
38
40 self.object = object
41 self.type = type
42 self.parents = []
43 self.children = []
44
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
65 self._nodes = {}
66 self._tainted = False
67
68
69 self._count = 0
70 self._begin = {}
71 self._end = {}
72 self._hasZeroEnd = []
73
75 if not self.hasNode(object, type):
76 raise KeyError("No node for object %r, type %r" % (object, type))
77
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
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
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
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
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
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
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
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
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
274 if not node.children:
275 self.log("Returning nothing")
276 return []
277
278
279 sortedNodes = self._sortPreferred()
280
281
282 nodeList = [node]
283 offspring = []
284 expand = True
285
286 while expand:
287 expand = False
288 for n in nodeList:
289 if n.children:
290
291
292 expand = True
293 nodeList.remove(n)
294 nodeList.extend(n.children)
295 offspring.extend(n.children)
296
297
298 if types:
299 offspring = [n for n in offspring if n.type in types]
300
301
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
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
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
347 if not node.parents:
348 return []
349
350
351 sortedNodes = self._sortPreferred()
352
353
354 nodeList = [node]
355 ancestors = []
356 expand = True
357
358 while expand:
359 expand = False
360 for n in nodeList:
361 if n.parents:
362
363
364 expand = True
365 nodeList.remove(n)
366 nodeList.extend(n.parents)
367 ancestors.extend(n.parents)
368
369
370 if types:
371 ancestors = [n for n in ancestors if n.type in types]
372
373
374 ret = []
375 for n in sortedNodes:
376 if n in ancestors:
377 ret.append((n.object, n.type))
378
379 return ret
380
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
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
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
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
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
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
470
471 self._count += 1
472
473 self._begin[node] = self._count
474
475
476
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
483
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
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
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