Topological ordering

topological_sort.py

def topological_sort(graph):
    """
    :param graph: an adjacency list representing an acyclic digraph
    :type graph: dict
    :return: a list of vertices in order of decreasing finish times
    :rtype: list

    >>> G = {'w': ['t'], 's': ['v', 'w'], 'v': ['t'], 't': []}
    >>> order = topological_sort(G)
    >>> order in (['s', 'w', 'v', 't'], ['s', 'v', 'w', 't'])
    True
    >>> from collections import OrderedDict
    >>> G = OrderedDict()
    >>> G['w'] = ['t']
    >>> G['s'] = ['v', 'w']
    >>> G['v'] = ['t']
    >>> G['t'] = []
    >>> topological_sort(G)
    ['s', 'v', 'w', 't']
    """
    explored_nodes = set()
    current_label = len(graph)
    f = {}  # times

    def dfs(s):
        explored_nodes.add(s)
        for v in graph[s]:
            if v not in explored_nodes:
                dfs(v)
        nonlocal current_label
        f[s] = current_label
        current_label = current_label - 1

    for v in graph:
        if v not in explored_nodes:
            dfs(v)

    return sorted(f, key=f.get)


if __name__ == '__main__':
    import doctest
    doctest.testmod()