Umar Gul Umar Gul - 3 months ago 11
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

def add(self, a, b):

if a in self.vertex_map:
av = self.vertex_map[a]
if b in self.vertex_map:
bv = self.vertex_map[b]
av.add(bv)
else:
bv = Vertex(b)
av.add(bv)
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]
av.add(bv)
else:
bv = Vertex(b)
av.add(bv)
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

def add(self, item):
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):
visited.add(v)
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()
graph.add(1, 2)
graph.add(1, 3)
graph.add(3, 4)
graph.add(3, 5)
graph.add(2, 6)
graph.add(2, 7)
graph.add(2, 8)

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.

Answer

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):
    visited.add(v)
    for n in v.neighbors:
        if n in visited:
            continue
        top_sort_util(n, visited, stack)
        stack.append(n)