← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

Improved topological sort

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
16
16
 
17
17
import pdb
18
18
 
19
 
def topo_sort(nodes, pairs):
 
19
from bzrlib.errors import GraphCycleError
 
20
 
 
21
def topo_sort(graph):
20
22
    """Topological sort a graph.
21
23
 
22
 
    nodes -- list of all nodes in the graph
23
 
    pairs -- list of (a, b) pairs, meaning a is a predecessor of b. 
24
 
        both a and b must occur in the node list.
 
24
    graph -- sequence of pairs of node->parents_list.
 
25
 
 
26
    The result is a list of node names, such that all parents come before
 
27
    their children.
 
28
 
 
29
    Nodes at the same depth are returned in sorted order.
25
30
 
26
31
    node identifiers can be any hashable object, and are typically strings.
27
32
    """
28
33
    parents = {}  # node -> list of parents
29
34
    children = {} # node -> list of children
30
 
    for n in nodes:
31
 
        parents[n] = set()
32
 
        children[n] = set()
33
 
    for p, c in pairs:
34
 
        parents[c].add(p)
35
 
        children[p].add(c)
 
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)
 
44
            else:
 
45
                children[parent] = set([node])
36
46
    result = []
37
47
    while parents:
38
48
        # find nodes with no parents, and take them now
39
 
        ready = [n for n in parents if len(parents[n]) == 0]
40
 
        if not ready:
41
 
            raise AssertionError('cycle in graph?')
42
 
        for n in ready:
 
49
        no_parents = [n for n in parents if len(parents[n]) == 0]
 
50
        no_parents.sort()
 
51
        if not no_parents:
 
52
            raise GraphCycleError(parents)
 
53
        for n in no_parents:
43
54
            result.append(n)
44
55
            for child in children[n]:
45
56
                assert n in parents[child]