36
36
node identifiers can be any hashable object, and are typically strings.
38
This function has the same purpose as the TopoSorter class, but uses a
39
different algorithm to sort the graph. That means that while both return a list
40
with parents before their child nodes, the exact ordering can be different.
42
topo_sort is faster when the whole list is needed, while when iterating over a
43
part of the list, TopoSorter.iter_topo_order should be used.
38
return TopoSorter(graph).sorted()
45
# store a dict of the graph.
47
# this is the stack storing on which the sorted nodes are pushed.
50
# count the number of children for every node in the graph
51
nchildren = dict.fromkeys(graph.iterkeys(), 0)
52
for parents in graph.itervalues():
53
for parent in parents:
54
if parent in nchildren:
55
nchildren[parent] += 1
56
# keep track of nodes without children in a separate list
57
nochildnodes = [node for (node, n) in nchildren.iteritems() if n == 0]
60
# pick a node without a child and add it to the stack.
61
node_name = nochildnodes.pop()
62
node_name_stack.append(node_name)
64
# the parents of the node lose it as a child; if it was the last
65
# child, add the parent to the list of childless nodes.
66
parents = graph.pop(node_name)
67
for parent in parents:
68
if parent in nchildren:
69
nchildren[parent] -= 1
70
if nchildren[parent] == 0:
71
nochildnodes.append(parent)
73
# if there are still nodes left in the graph,
74
# that means that there is a cycle
76
raise errors.GraphCycleError(graph)
78
# the nodes where pushed on the stack child first, so this list needs to be
79
# reversed before returning it.
80
node_name_stack.reverse()
81
return node_name_stack
41
84
class TopoSorter(object):
added
removed
bzrlib/tsort.py
