A directed acyclic graph of objects and their dependencies. Supports a robust topological sort to detect the order in which they must be handled. Takes an optional iterator of ``(obj, dependencies)`` tuples to build the graph from. Warning: Does not support cycle detec
| 27 | |
| 28 | |
| 29 | class DependencyGraph: |
| 30 | """A directed acyclic graph of objects and their dependencies. |
| 31 | |
| 32 | Supports a robust topological sort |
| 33 | to detect the order in which they must be handled. |
| 34 | |
| 35 | Takes an optional iterator of ``(obj, dependencies)`` |
| 36 | tuples to build the graph from. |
| 37 | |
| 38 | Warning: |
| 39 | Does not support cycle detection. |
| 40 | """ |
| 41 | |
| 42 | def __init__(self, it=None, formatter=None): |
| 43 | self.formatter = formatter or GraphFormatter() |
| 44 | self.adjacent = {} |
| 45 | if it is not None: |
| 46 | self.update(it) |
| 47 | |
| 48 | def add_arc(self, obj): |
| 49 | """Add an object to the graph.""" |
| 50 | self.adjacent.setdefault(obj, []) |
| 51 | |
| 52 | def add_edge(self, A, B): |
| 53 | """Add an edge from object ``A`` to object ``B``. |
| 54 | |
| 55 | I.e. ``A`` depends on ``B``. |
| 56 | """ |
| 57 | self[A].append(B) |
| 58 | |
| 59 | def connect(self, graph): |
| 60 | """Add nodes from another graph.""" |
| 61 | self.adjacent.update(graph.adjacent) |
| 62 | |
| 63 | def topsort(self): |
| 64 | """Sort the graph topologically. |
| 65 | |
| 66 | Returns: |
| 67 | List: of objects in the order in which they must be handled. |
| 68 | """ |
| 69 | graph = DependencyGraph() |
| 70 | components = self._tarjan72() |
| 71 | |
| 72 | NC = { |
| 73 | node: component for component in components for node in component |
| 74 | } |
| 75 | for component in components: |
| 76 | graph.add_arc(component) |
| 77 | for node in self: |
| 78 | node_c = NC[node] |
| 79 | for successor in self[node]: |
| 80 | successor_c = NC[successor] |
| 81 | if node_c != successor_c: |
| 82 | graph.add_edge(node_c, successor_c) |
| 83 | return [t[0] for t in graph._khan62()] |
| 84 | |
| 85 | def valency_of(self, obj): |
| 86 | """Return the valency (degree) of a vertex in the graph.""" |
no outgoing calls