31
34
node identifiers can be any hashable object, and are typically strings.
33
parents = {} # node -> list of parents
34
children = {} # node -> list of children
35
for node, node_parents in graph:
36
assert node not in parents, \
37
('node %r repeated in graph' % node)
38
parents[node] = set(node_parents)
39
if node not in children:
40
children[node] = set()
41
for parent in node_parents:
42
if parent in children:
43
children[parent].add(node)
45
children[parent] = set([node])
48
# find nodes with no parents, and take them now
49
no_parents = [n for n in parents if len(parents[n]) == 0]
52
raise GraphCycleError(parents)
55
for child in children[n]:
56
assert n in parents[child]
57
parents[child].remove(n)
36
return TopoSorter(graph).sorted()
39
class TopoSorter(object):
41
def __init__(self, graph):
42
"""Topological sorting of a graph.
44
:param graph: sequence of pairs of node_name->parent_names_list.
45
i.e. [('C', ['B']), ('B', ['A']), ('A', [])]
46
For this input the output from the sort or
47
iter_topo_order routines will be:
50
node identifiers can be any hashable object, and are typically strings.
52
If you have a graph like [('a', ['b']), ('a', ['c'])] this will only use
53
one of the two values for 'a'.
55
The graph is sorted lazily: until you iterate or sort the input is
56
not processed other than to create an internal representation.
58
iteration or sorting may raise GraphCycleError if a cycle is present
61
# a dict of the graph.
62
self._graph = dict(graph)
64
# self._original_graph = dict(graph)
66
# this is a stack storing the depth first search into the graph.
67
self._node_name_stack = []
68
# at each level of 'recursion' we have to check each parent. This
69
# stack stores the parents we have not yet checked for the node at the
70
# matching depth in _node_name_stack
71
self._pending_parents_stack = []
72
# this is a set of the completed nodes for fast checking whether a
73
# parent in a node we are processing on the stack has already been
74
# emitted and thus can be skipped.
75
self._completed_node_names = set()
78
"""Sort the graph and return as a list.
80
After calling this the sorter is empty and you must create a new one.
82
return list(self.iter_topo_order())
84
### Useful if fiddling with this code.
86
### sorted_names = list(self.iter_topo_order())
87
### for index in range(len(sorted_names)):
88
### rev = sorted_names[index]
89
### for left_index in range(index):
90
### if rev in self.original_graph[sorted_names[left_index]]:
91
### print "revision in parent list of earlier revision"
92
### import pdb;pdb.set_trace()
94
def iter_topo_order(self):
95
"""Yield the nodes of the graph in a topological order.
97
After finishing iteration the sorter is empty and you cannot continue
101
# now pick a random node in the source graph, and transfer it to the
102
# top of the depth first search stack.
103
node_name, parents = self._graph.popitem()
104
self._push_node(node_name, parents)
105
while self._node_name_stack:
106
# loop until this call completes.
107
parents_to_visit = self._pending_parents_stack[-1]
108
# if all parents are done, the revision is done
109
if not parents_to_visit:
110
# append the revision to the topo sorted list
111
# all the nodes parents have been added to the output, now
112
# we can add it to the output.
113
yield self._pop_node()
115
while self._pending_parents_stack[-1]:
116
# recurse depth first into a single parent
117
next_node_name = self._pending_parents_stack[-1].pop()
118
if next_node_name in self._completed_node_names:
119
# this parent was completed by a child on the
120
# call stack. skip it.
122
# otherwise transfer it from the source graph into the
123
# top of the current depth first search stack.
125
parents = self._graph.pop(next_node_name)
127
# if the next node is not in the source graph it has
128
# already been popped from it and placed into the
129
# current search stack (but not completed or we would
130
# have hit the continue 4 lines up.
131
# this indicates a cycle.
132
raise errors.GraphCycleError(self._node_name_stack)
133
self._push_node(next_node_name, parents)
134
# and do not continue processing parents until this 'call'
138
def _push_node(self, node_name, parents):
139
"""Add node_name to the pending node stack.
141
Names in this stack will get emitted into the output as they are popped
145
self._node_name_stack.append(node_name)
146
self._pending_parents_stack.append(list(parents))
149
"""Pop the top node off the stack
151
The node is appended to the sorted output.
153
# we are returning from the flattened call frame:
154
# pop off the local variables
155
node_name = self._node_name_stack.pop()
156
self._pending_parents_stack.pop()
158
self._completed_node_names.add(node_name)
added
removed
bzrlib/tsort.py
