tdi._graph

41 """ 42 Dependency Graph Container 43 44 This is a simple directed acyclic graph. The graph starts empty, and new 45 nodes (and edges) are added using the `add` method. If the newly added 46 create a cycle, an exception is thrown. 47 48 Finally, the graph is resolved using the `resolve` method. The method will 49 return topologically ordered nodes and destroy the graph. The topological 50 order is *stable*, meaning, the same graph will always produce the same 51 output. 52 53 :IVariables: 54 `_outgoing` : ``defaultdict`` 55 Mapping of outgoing nodes (node -> set(outgoing neighbours)) 56 57 `_incoming` : ``defaultdict`` 58 Mapping of incoming nodes (node -> set(incoming neighbours)) 59 """ 60 __slots__ = ('_outgoing', '_incoming') 61

62 - def __init__(self):

63 """ Initialization """ 64 self._outgoing = _collections.defaultdict(set) 65 self._incoming = _collections.defaultdict(set)

66

67 - def add(self, start, end):

68 """ 69 Add a new nodes with edge to the graph 70 71 The edge is directed from `start` to `end`. 72 73 :Parameters: 74 `start` : ``str`` 75 Node 76 77 `end` : ``str`` 78 Node 79 """ 80 self._outgoing[start].add(end) 81 self._incoming[end].add(start) 82 self._check_cycle(end)

83

84 - def resolve(self):

85 """ 86 Resolve graph and return nodes in topological order 87 88 The graph is defined by outgoing and incoming dicts (mapping nodes to 89 their outgoing or incoming neighbours). The graph is destroyed in the 90 process. 91 92 :Return: Sorted node list. The output is stable, because nodes on 93 the same level are sorted alphabetically. Furthermore all 94 leaf nodes are put at the end. 95 :Rtype: ``list`` 96 """ 97 result, outgoing, incoming = [], self._outgoing, self._incoming 98 roots = list(set(outgoing.iterkeys()) - set(incoming.iterkeys())) 99 leaves = set(incoming.iterkeys()) - set(outgoing.iterkeys()) 100 101 roots.sort() # ensure stable output 102 roots = _collections.deque(roots) 103 roots_push, roots_pop = roots.appendleft, roots.pop 104 result_push, opop, ipop = result.append, outgoing.pop, incoming.pop 105 while roots: 106 node = roots_pop() 107 if node not in leaves: 108 result_push(node) 109 children = list(opop(node, ())) 110 children.sort() # ensure stable output 111 for child in children: 112 parents = incoming[child] 113 parents.remove(node) 114 if not parents: 115 roots_push(child) 116 ipop(child) 117 118 if outgoing or incoming: # pragma: no cover 119 raise AssertionError("Graph not resolved (this is a bug).") 120 121 leaves = list(leaves) 122 leaves.sort() # ensure stable output 123 return result + leaves

124

125 - def _check_cycle(self, node):

126 """ 127 Find a cycle containing `node` 128 129 This assumes, that there's no other possible cycle in the graph. This 130 assumption is valid, because the graph is checked whenever a new 131 edge is added. 132 133 :Parameters: 134 `node` : ``str`` 135 Node which may be part of a cycle. 136 137 :Exceptions: 138 - `DependencyCycle` : Raised, if there is, indeed, a cycle in the 139 graph. The cycling nodes are passed as a list to the exception. 140 """ 141 # run a DFS for each child node until we find 142 # a) a leaf (then backtrack) 143 # b) node (cycle) 144 outgoing = self._outgoing 145 if node in outgoing: 146 iter_ = iter 147 stack = [(node, iter_(outgoing[node]).next)] 148 exhausted, push, pop = StopIteration, stack.append, stack.pop 149 150 while stack: 151 try: 152 child = stack[-1][1]() 153 except exhausted: 154 pop() 155 else: 156 if child == node: 157 raise DependencyCycle(map(_op.itemgetter(0), stack)) 158 elif child in outgoing: 159 push((child, iter_(outgoing[child]).next))

Source Code for Module tdi._graph