Umar Gul -4 years ago 176
Python Question

# Topological Sort not behaving as expected

Here's my graph implementation in Python. This is a directed graph.

``````class DiGraph:
def __init__(self):
self.all_vertices = []
self.vertex_map = {}
self.size = 0

if a in self.vertex_map:
av = self.vertex_map[a]
if b in self.vertex_map:
bv = self.vertex_map[b]
else:
bv = Vertex(b)
self.vertex_map[b] = bv
self.all_vertices.append(bv)
self.size += 1
else:
av = Vertex(a)
self.size += 1
if b in self.vertex_map:
bv = self.vertex_map[b]
else:
bv = Vertex(b)
self.vertex_map[b] = bv
self.all_vertices.append(bv)
self.size += 1
self.vertex_map[a] = av
self.all_vertices.append(av)

def __sizeof__(self):
return self.size

def print(self):
for v in self.all_vertices:
print(v.data, end='->')
for n in v.neighbors:
print(n.data, end=', ')
print()

class Vertex:
def __init__(self, data):
self.data = data
self.neighbors = []
self.connections = 0

self.neighbors.append(item)
self.connections += 1
``````

This is my code for topological sort

``````def top_sort(g):
stack = []
visited = set()

for v in g.all_vertices:
if v not in visited:
top_sort_util(v, visited, stack)

for ele in stack:
print(ele, end=' ')
print()

def top_sort_util(v, visited, stack):
for n in v.neighbors:
if n in visited:
continue
top_sort_util(n, visited, stack)
stack.append(n)
``````

This is the caller graph.

``````def main():
graph = DiGraph()

top_sort(graph)

if __name__ == '__main__':
main()
``````

This is the error message that I get,

``````stack.append(n)
UnboundLocalError: local variable 'n' referenced before assignment
``````

On debugging the code I can see that on the line stack.append(n) nothing gets appended and though the recursion folds out the call stack doesn't go to the next iteration of traversing the neighbors inside the top_sort_util.
Can't seem to understand what is logically incorrect here.
Any help appreciated.

If `v.neighbors` is empty, `n` is never set, so the `stack.append(n)` outside the `for n in v.neighbors:` fails.

If all `n` must be added to the stack (and not just the last), indent `stack.append()` properly to be inside the loop:

``````def top_sort_util(v, visited, stack):