Topological Sort not behaving as expected
<p>Here's my graph implementation in Python. This is a directed graph.</p>

<pre><code>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='-&gt;')
            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
</code></pre>

<p>This is my code for topological sort</p>

<pre><code>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)
</code></pre>

<p>This is the caller graph.</p>

<pre><code>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()
</code></pre>

<p>This is the error message that I get,</p>

<pre><code>stack.append(n)
UnboundLocalError: local variable 'n' referenced before assignment
</code></pre>

<p>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.</p>

<p>If <code>v.neighbors</code> is empty, <code>n</code> is never set, so the <code>stack.append(n)</code> <em>outside</em> the <code>for n in v.neighbors:</code> fails.</p>

<p>If all <code>n</code> must be added to the stack (and not just the last), indent <code>stack.append()</code> properly to be inside the loop:</p>

<pre><code>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)
</code></pre>

python graph topological-sort