Sort nodes based on ancestors

Question

I have a problem where I would like to sort a set of nodes {a, b, c, d}. For each node I know the ancestors, i.e. those nodes that need to come before that node. (e.g a: {b, c} means that a needs to be somewhere in the list but after b and c).

I could solve following example iteratively like that:

1. a: {b, c} --> b|c , a
2. b: {c} --> c , b , a
3. d: {b, c} --> c , b , d, a

Is there a known algorithm so solve this? Preferably in Python.

Answer 1

This problem is called Topological Sort. You can see the pseudocode here. Here is the python implementation:

import copy
def topological_sort(outcoming_edges):
    #outcoming_edges: Dict[str,Set[str]]
    # example: {'a': {'b', 'c'}, 'b': {'c'}, 'd': {'b','c'}}

    outcoming_edges = copy.deepcopy(outcoming_edges) #to make sure the original variable is not changed

    l = []

    #find outcoming_edges which has no incoming edge
    s = set(outcoming_edges.keys())
    for node in outcoming_edges:
        for ancestor in outcoming_edges[node]:
            s.discard(ancestor)

    incoming_edges = dict()

    for n, next_nodes in outcoming_edges.items():
        for m in next_nodes:
            if m in incoming_edges:
                incoming_edges[m].add(n)
            else:
                incoming_edges[m] = {n}

    while s:
        n = s.pop()
        l.append(n)

        next_nodes = outcoming_edges.get(n,set())
        while next_nodes:
            m = next_nodes.pop()
            incoming_edges[m].remove(n)
            if not incoming_edges[m]:
                s.add(m)

    if any(outcoming_edges.values()) or any(incoming_edges.values()):
        return None #graph has at least one cycle
    else:
        return l # a topologically sorted order