Umar Gul - 11 months ago 51

Python Question

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 Source

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)
```