18
18
"""Topological sorting routines."""
21
from bzrlib import errors
22
import bzrlib.revision as _mod_revision
24
revision as _mod_revision,
23
26
from collections import deque
44
47
topo_sort is faster when the whole list is needed, while when iterating
45
48
over a part of the list, TopoSorter.iter_topo_order should be used.
47
# store a dict of the graph.
49
# this is the stack storing on which the sorted nodes are pushed.
52
# count the number of children for every node in the graph
53
node_child_count = dict.fromkeys(graph.iterkeys(), 0)
54
for parents in graph.itervalues():
55
for parent in parents:
56
# don't count the parent if it's a ghost
57
if parent in node_child_count:
58
node_child_count[parent] += 1
59
# keep track of nodes without children in a separate list
60
nochild_nodes = deque([node for (node, n) in node_child_count.iteritems()
64
node_stack_append = node_stack.append
65
nochild_nodes_pop = nochild_nodes.pop
66
nochild_nodes_append = nochild_nodes.append
69
# pick a node without a child and add it to the stack.
70
node_name = nochild_nodes_pop()
71
node_stack_append(node_name)
73
# the parents of the node lose it as a child; if it was the last
74
# child, add the parent to the list of childless nodes.
75
parents = graph_pop(node_name)
76
for parent in parents:
77
if parent in node_child_count:
78
node_child_count[parent] -= 1
79
if node_child_count[parent] == 0:
80
nochild_nodes_append(parent)
82
# if there are still nodes left in the graph,
83
# that means that there is a cycle
85
raise errors.GraphCycleError(graph)
87
# the nodes where pushed on the stack child first, so this list needs to be
88
# reversed before returning it.
50
kg = _mod_graph.KnownGraph(graph)
93
54
class TopoSorter(object):
added
removed
bzrlib/tsort.py
