1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 """directed acyclic graph implementation.
23 Directed Acyclic Graph class and functionality
24 """
25 from flumotion.common import log
26
27 __version__ = "$Rev$"
28
29
31 """
32 A cycle was detected during execution of a function.
33 """
34
35
37 """
38 I represent a Node in a Graph.
39
40 I am private to the Graph.
41 """
42
44 self.object = object
45 self.type = type
46 self.parents = []
47 self.children = []
48
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
69 self._nodes = {}
70 self._tainted = False
71
72
73 self._count = 0
74 self._begin = {}
75 self._end = {}
76 self._hasZeroEnd = []
77
79 if not self.hasNode(object, type):
80 raise KeyError("No node for object %r, type %r" % (object, type))
81
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
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
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
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
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
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
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
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
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
278 if not node.children:
279 self.log("Returning nothing")
280 return []
281
282
283 sortedNodes = self._sortPreferred()
284
285
286 nodeList = [node]
287 offspring = []
288 expand = True
289
290 while expand:
291 expand = False
292 for n in nodeList:
293 if n.children:
294
295
296 expand = True
297 nodeList.remove(n)
298 nodeList.extend(n.children)
299 offspring.extend(n.children)
300
301
302 if types:
303 offspring = [n for n in offspring if n.type in types]
304
305
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
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
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
351 if not node.parents:
352 return []
353
354
355 sortedNodes = self._sortPreferred()
356
357
358 nodeList = [node]
359 ancestors = []
360 expand = True
361
362 while expand:
363 expand = False
364 for n in nodeList:
365 if n.parents:
366
367
368 expand = True
369 nodeList.remove(n)
370 nodeList.extend(n.parents)
371 ancestors.extend(n.parents)
372
373
374 if types:
375 ancestors = [n for n in ancestors if n.type in types]
376
377
378 ret = []
379 for n in sortedNodes:
380 if n in ancestors:
381 ret.append((n.object, n.type))
382
383 return ret
384
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
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
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
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
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
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
474
475 self._count += 1
476
477 self._begin[node] = self._count
478
479
480
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
487
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
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
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