sort_direct_acyclic_graph

topological_sort.py

import collections


def topological_sort(edge_list):
    graph = collections.defaultdict(set)
    for node, child in edge_list:
        graph[node].add(child)
    nodes = set(graph)
    visited = set()
    ordered = set()
    order = []

    def dfs(node):
        for ch in graph[node]:
            if ch in ordered:
                continue
            if ch in visited:
                raise ValueError('Invalid')
            visited.add(ch)
            nodes.discard(ch)
            dfs(ch)
        ordered.add(node)
        order.append(node)

    while nodes:
        dfs(nodes.pop())
    return order


u = [
    ['a', 'b'],  # a -> b, etc.
    ['a', 'c'],
    ['b', 'e'],
    ['c', 'd'],
    ['b', 'd'],
    ['e', 'f'],
    ['c', 'f'],
]
assert topological_sort(u) == ['a', 'c', 'b', 'e', 'd', 'f']