3
\$\begingroup\$

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))
\$\endgroup\$
  • 2
    \$\begingroup\$ Do you only have one test case? Does the code work correctly for other test cases? \$\endgroup\$ – Phrancis Dec 2 '16 at 23:27
  • \$\begingroup\$ @Phrancis it also works for the test case: graph2={ 0 : [], 1: [], 2: [3], 3: [1], 4: [0, 1], 5: [2, 0] } \$\endgroup\$ – driftdrift Dec 2 '16 at 23:36
  • 1
    \$\begingroup\$ Excuse my ignorance, but can you please explain what's the output you expect for the graph in the code ? More, could you please add more context to what your code does ? Having some recursion going on there doesn't help :). PS: for example, when I'm testing you're first graph, I receive different outputs at every run, so I suspect your code as being broken. \$\endgroup\$ – Grajdeanu Alex. Dec 3 '16 at 6:11
  • \$\begingroup\$ @Dex'ter A topological sort returns things in order, where given an edge U->V in a graph, U always comes before V. \$\endgroup\$ – driftdrift Dec 3 '16 at 15:48
1
\$\begingroup\$
  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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.