Topological sort python

algorithm, graph, python

Solution

FWIW, here is some code I worked up for a non-recursive topological sort.

from collections import defaultdict, namedtuple
from itertools import islice

Results = namedtuple('Results', ['sorted', 'cyclic'])

def topological_sort(dependency_pairs):
    'Sort values subject to dependency constraints'
    num_heads = defaultdict(int)   # num arrows pointing in
    tails = defaultdict(list)      # list of arrows going out
    heads = []                     # unique list of heads in order first seen
    for h, t in dependency_pairs:
        num_heads[t] += 1
        if h in tails:
            tails[h].append(t)
        else:
            tails[h] = [t]
            heads.append(h)

    ordered = [h for h in heads if h not in num_heads]
    for h in ordered:
        for t in tails[h]:
            num_heads[t] -= 1
            if not num_heads[t]:
                ordered.append(t)
    cyclic = [n for n, heads in num_heads.items() if heads]
    return Results(ordered, cyclic)

if __name__ == '__main__':
    print( topological_sort('aa'.split()) )
    print( topological_sort('ah bg cf ch di ed fb fg hd he ib'.split()) )

Problem

I coded a solution for DFS non-recursive, but i can't modify it to make a topological sort: ``` def dfs(graph,start): path = [] stack = [start] while stack != []: v = stack.pop() if v not in path: path.append(v) for w in reversed(graph[v]): if w not in path and not w in stack: stack.append(w) return path ``` Any ideas how to modify it? With the recursive version i can easy have the sorting: ``` def dfs_rec(graph,start,path): path = path + [start] for edge in graph[start]: if edge not in path: path = dfs_rec(graph, edge,path) print start return path ``` Input: ``` >>> graph = { 1: [2, 3], 2: [4, 5, 6], 3: [4,6], 4: [5,6], 5: [6], 6: [] } >>> dfs_rec(graph,1,[]) 6 5 4 2 3 1 [1, 2, 4, 5, 6, 3] >>> dfs(graph,1) [1, 2, 4, 5, 6, 3] >>> graph = { 1: [3], 3: [5,6], 5: [4], 4: [7], 7: [], 6: [] } >>> print dfs_rec(graph,1,[]) 7 4 5 6 3 1 [1, 3, 5, 4, 7, 6] >>> print dfs(graph,1) [1, 3, 5, 4, 7, 6] ``` so i need to get this ordering in the non-recursive also. Non-recursive solution: I think that this also could be the solution, mark me if i am wrong. ``` def dfs(graph,start): path = [] stack = [start] label = len(graph) result = {} while stack != []: #this for loop could be done in other ways also for element in stack: if element not in result: result[element] = label label = label - 1 v = stack.pop() if v not in path: path.append(v) for w in reversed(graph[v]): if w not in path and not w in stack: stack.append(w) result = {v:k for k, v in result.items()} return path,result ``` Input: ``` graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]} print dfs(graph,1) ``` Output: ``` ([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1}) 1 / 3 /\ 5 6 / 4 / 7 ```

Original source