CODEWITHSUNDEEP
pythontopological-sort
Lookout
Lookout

Reputation: 241

errors in my implement of topological sort using python

UPDATE

I did not use nested function in the following code,but the answer is wrong: {'s': 4, 't': 4, 'w': 4, 'v': 4}

I think the problem is in the recursive call,where n does not decrease when the functions call back,but I don't know how to revise it.

import unittest
#dfs
def dfs(graph,start,visited,n,topo_order):
        visited.add(start)
        for w in graph[start]:
            if w not in visited:
                dfs(graph,w,visited,n,topo_order)
        topo_order[start]=n
        n-=1
def topological_sort(graph):
    visited=set()
    n=len(graph)
    topo_order={}
    for v in graph:
        if v not in visited:
            dfs(graph,v,visited,n,topo_order)
    print(topo_order)
class topological_sort_test(unittest.TestCase):
    def test(self):
        file=[]
        with open('topological_test.txt') as f:
            data=f.read()
        data=data.split('\n')
        data=[i.split() for i in data]        
        G={}
        for lst in data:
            G[lst[0]]=lst[1:]
        topological_sort(G)
if __name__=='__main__':
    unittest.main()

Upvotes: 0

Views: 145

Answers (1)

Łukasz Rogalski
Łukasz Rogalski

Reputation: 23203

def dfs(graph,start)

Function declaration creates local scope for variables. To access any variable from outside you'll need to pass it as an argument to this function.

Upvotes: 1

Related Questions