Topologial Sort in Python

Question

I am trying to self study algorithms and this is my attempt at topological sort using Tarjan's version of DFS. It runs correctly for the graph I included. Can someone tell me if this is correct and if/what optimizations I can make?

graph = {
'A':['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['F'],
'F': ['G'],
'G': [],
}

def topological_sort(graph):
    visited, stack = set(), []

    for vertex in graph:
        handle_vertex(graph, vertex, visited, stack) 

    print(stack)

def handle_vertex(graph, vertex, visited, stack):
    if vertex not in visited:
        visited.add(vertex)

    for neighbors in graph[vertex]:
        if neighbors not in visited:
            handle_vertex(graph, neighbors, visited, stack)

    if vertex not in stack:
       stack.insert(0, vertex)
    return stack

print(topological_sort(graph))

Answer 1

1. I don't get the point of returning the stack from the handle_vertex function. The return value is never used (and the stack which is passed as an argument is modified in place).

2. The topological_sort functions prints the stack, doesn't return anything and then it's returned value is printed: print(topological_sort(graph)). There're two reasonable options here:

   • not printing the returned value of the topological_sort and just calling it instead
   • Returning the stack from it instead of printing it inside the function.

3. The neighbors name here: for neighbors in graph[vertex] is misleading. This variable represent just one neighbor at a time. I don't see why would you make it plural.