1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 """
23 Directed Acyclic Graph class and functionality
24 """
25 from flumotion.common import log
26
28 """
29 A cycle was detected during execution of a function.
30 """
31
33 """
34 I represent a Node in a Graph.
35
36 I am private to the Graph.
37 """
39 self.object = object
40 self.type = type
41 self.parents = []
42 self.children = []
43
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 """
62 self._nodes = {}
63 self._tainted = False
64
65
66 self._count = 0
67 self._begin = {}
68 self._end = {}
69 self._hasZeroEnd = []
70
72 if not self.hasNode(object, type):
73 raise KeyError("No node for object %r, type %r" % (object, type))
74
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
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
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
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
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
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
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
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
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
271 if not node.children:
272 self.log("Returning nothing")
273 return []
274
275
276 sorted = self._sortPreferred()
277
278
279 list = [node]
280 offspring = []
281 expand = True
282
283 while expand:
284 expand = False
285 for n in list:
286 if n.children:
287
288
289 expand = True
290 list.remove(n)
291 list.extend(n.children)
292 offspring.extend(n.children)
293
294
295 if types:
296 offspring = filter(lambda n: n.type in types, offspring)
297
298
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
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
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
345 if not node.parents:
346 return []
347
348
349 sorted = self._sortPreferred()
350
351
352 list = [node]
353 ancestors = []
354 expand = True
355
356 while expand:
357 expand = False
358 for n in list:
359 if n.parents:
360
361
362 expand = True
363 list.remove(n)
364 list.extend(n.parents)
365 ancestors.extend(n.parents)
366
367
368 if types:
369 ancestors = filter(lambda n: n.type in types, ancestors)
370
371
372 ret = []
373 for n in sorted:
374 if n in ancestors:
375 ret.append((n.object, n.type))
376
377 return ret
378
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
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
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
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
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
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
468
469 self._count += 1
470
471 self._begin[node] = self._count
472
473
474
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
481
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
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
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