algorithm – deceptively simple implementation of topological sorting in python

algorithm – deceptively simple implementation of topological sorting in python

Its not easy to turn an iterative implementation of DFS into Topological sort, since the change that needs to be done is more natural with a recursive implementation. But you can still do it, it just requires that you implement your own stack.

First off, heres a slightly improved version of your code (its much more efficient and not much more complicated):

def iterative_dfs_improved(graph, start):
    seen = set()  # efficient set to look up nodes in
    path = []     # there was no good reason for this to be an argument in your code
    q = [start]
    while q:
        v = q.pop()   # no reason not to pop from the end, where its fast
        if v not in seen:
            seen.add(v)
            path.append(v)
            q.extend(graph[v]) # this will add the nodes in a slightly different order
                               # if you want the same order, use reversed(graph[v])

    return path

Heres how Id modify that code to do a topological sort:

def iterative_topological_sort(graph, start):
    seen = set()
    stack = []    # path variable is gone, stack and order are new
    order = []    # order will be in reverse order at first
    q = [start]
    while q:
        v = q.pop()
        if v not in seen:
            seen.add(v) # no need to append to path any more
            q.extend(graph[v])

            while stack and v not in graph[stack[-1]]: # new stuff here!
                order.append(stack.pop())
            stack.append(v)

    return stack + order[::-1]   # new return value!

The part I commented with new stuff here is the part that figures out the order as you move up the stack. It checks if the new node thats been found is a child of the previous node (which is on the top of the stack). If not, it pops the top of the stack and adds the value to order. While were doing the DFS, order will be in reverse topological order, starting from the last values. We reverse it at the end of the function, and concatenate it with the remaining values on the stack (which conveniently are already in the correct order).

Because this code needs to check v not in graph[stack[-1]] a bunch of times, it will be much more efficient if the values in the graph dictionary are sets, rather than lists. A graph usually doesnt care about the order its edges are saved in, so making such a change shouldnt cause problems with most other algorithms, though code that produces or updates the graph might need fixing. If you ever intend to extend your graph code to support weighted graphs, youll probably end up changing the lists to dictionaries mapping from node to weight anyway, and that would work just as well for this code (dictionary lookups are O(1) just like set lookups). Alternatively, we could build the sets we need ourselves, if graph cant be modified directly.

For reference, heres a recursive version of DFS, and a modification of it to do a topological sort. The modification needed is very small indeed:

def recursive_dfs(graph, node):
    result = []
    seen = set()

    def recursive_helper(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                result.append(neighbor)     # this line will be replaced below
                seen.add(neighbor)
                recursive_helper(neighbor)

    recursive_helper(node)
    return result

def recursive_topological_sort(graph, node):
    result = []
    seen = set()

    def recursive_helper(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                recursive_helper(neighbor)
        result.insert(0, node)              # this line replaces the result.append line

    recursive_helper(node)
    return result

Thats it! One line gets removed and a similar one gets added at a different location. If you care about performance, you should probably do result.append in the second helper function too, and do return result[::-1] in the top level recursive_topological_sort function. But using insert(0, ...) is a more minimal change.

Its also worth noting that if you want a topological order of the whole graph, you shouldnt need to specify a starting node. Indeed, there may not be a single node that lets you traverse the entire graph, so you may need to do several traversals to get to everything. An easy way to make that happen in the iterative topological sort is to initialize q to list(graph) (a list of all the graphs keys) instead of a list with only a single starting node. For the recursive version, replace the call to recursive_helper(node) with a loop that calls the helper function on every node in the graph if its not yet in seen.

My idea is based on two key observations:

  1. Dont pop the next item from stack, keep it to emulate stack unwinding.
  2. Instead of pushing all children to stack, just push one.

Both of these help us to traverse the graph exactly like recursive dfs. As the other answer here noted, this is important for this particular problem. The rest should be easy.

def iterative_topological_sort(graph, start,path=set()):
    q = [start]
    ans = []
    while q:
        v = q[-1]                   #item 1,just access, dont pop
        path = path.union({v})  
        children = [x for x in graph[v] if x not in path]    
        if not children:              #no child or all of them already visited
            ans = [v]+ans 
            q.pop()
        else: q.append(children[0])   #item 2, push just one child

    return ans

q here is our stack. In the main loop, we access our current node v from the stack. access, not pop, because we need to be able to come back to this node again. We find out all unvisited children of our current node. and push only the first one to stack (q.append(children[0])), not all of them together. Again, this is precisely what we do with recursive dfs.

If no eligible child is found (if not children), we have visited the entire subtree under it. So its ready to be pushed into ans. And this is when we really pop it.

(Goes without saying, its not great performance-wise. Instead of generating all unvisited children in children variable, we should just generate the first one, generator style, maybe using filter. We should also reverse that ans = [v] + ans and call a reverse on ans at the end. But these things are omitted for OPs insistence on simplicity.)

algorithm – deceptively simple implementation of topological sorting in python

Im pretty new to this, but shouldnt topological sort based on DFS work no matter where in the graph you start? The current solutions (as of this writing) only traverse the entire graph for particular starting points in the example graph. (Although I havent completely thought it through, it seems the problem occurs when hitting a vertex that has no neighbors to visit. If the algorithm hits such a node before traversing all the other vertices in the graph, then the results are truncated.)

Although it is not as simple as the OP would probably like, the following is an iterative topological sort using DFS that works regardless of the order of vertices explored.

```
from collections import deque

def iterative_top_sort(graph):
    result = deque() #using deque because we want to append left
    visited = set()

    #the first entry to the stack is a list of the vertices in the 
    #graph. 

    stack = [[key for key in graph]] #we want the stack to hold lists

    while stack:
      for i in stack[-1]: 
        if i in visited and i not in result: 
          result.appendleft(i)
        if i not in visited:
          visited.add(i)
          #add the vertexs neighbors to the stack
          stack.append(graph[i]) 
          break
      else: 
        stack.pop() 

    return result
```

Leave a Reply

Your email address will not be published.