Topological sort for python 3.6

topological.py

def topological(nodes:set, get_successors) -> deque:
    """
    Returs a topologically sorted queue using DFS and gray/black colors.
    get_successors(node) an accessor function for the successors of each node.
    
    Code based on https://gist.github.com/kachayev/5910538
    """
    GRAY, BLACK = 0, 1
    order, state = deque(), {}

    def dfs(node):
        state[node] = GRAY
        for k in get_successors(node):
            sk = state.get(k, None)
            if sk == GRAY: raise ValueError("cycle")
            if sk == BLACK: continue
            nodes.discard(k)
            dfs(k)
        order.appendleft(node)
        state[node] = BLACK

    while nodes: dfs(nodes.pop())
    return order
    
def test_topological():
    graph = {
        "a": ["b", "c", "d"],
        "b": [],
        "c": ["d"],
        "d": [],
        "e": ["g", "f", "q"],
        "g": [],
        "f": [],
        "q": []
    }

    def get_successors(node):
        return graph.get(node)

    assert topological(set(graph), get_successors) == deque(['a', 'b', 'c', 'd', 'e', 'q', 'f', 'g'])

test_topological()

Based on https://gist.github.com/kachayev/5910538 with the following improvements:

• Port to python 3.6
• Generalized for arbitrary graph representation