Arthur de Jong

Open Source / Free Software developer

summaryrefslogtreecommitdiffstats
path: root/django/db/migrations/topological_sort.py
blob: 560091c754fa5d7e578de10abaf487da5b8de745 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def topological_sort_as_sets(dependency_graph):
    """Variation of Kahn's algorithm (1962) that returns sets.

    Takes a dependency graph as a dictionary of node => dependencies.

    Yields sets of items in topological order, where the first set contains
    all nodes without dependencies, and each following set contains all
    nodes that depend on the nodes in the previously yielded sets.
    """
    todo = dependency_graph.copy()
    while todo:
        current = {node for node, deps in todo.items() if len(deps) == 0}

        if not current:
            raise ValueError('Cyclic dependency in graph: {}'.format(
                ', '.join(repr(x) for x in todo.items())))

        yield current

        # remove current from todo's nodes & dependencies
        todo = {node: (dependencies - current) for node, dependencies in
                todo.items() if node not in current}


def stable_topological_sort(l, dependency_graph):
    result = []
    for layer in topological_sort_as_sets(dependency_graph):
        for node in l:
            if node in layer:
                result.append(node)
    return result