[FIXED] How to iterate over defaultdict?

Issue

I have the following code which makes topological order:

from collections import defaultdict 

class Graph: 
    def __init__(self): 
        self.graph = defaultdict(list)
        self.V = 0  #number of nodes

    def addEdge(self,u,v): 
        self.graph[u].append(v) 
        self.V = self.V + 1

    def topologicalSortUtil(self,v,visited,stack): 

        visited[v] = True

        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 

        stack.insert(0,v) 

    # topologicalSortUtil() 
    def topologicalSort(self): 
        # Mark all the vertices as not visited 
        visited = [False]*self.V 
        stack =[] 

        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 

        print stack 

g= Graph() 
g.addEdge(5, 2); 
g.addEdge(5, 0); 
g.addEdge(4, 0); 
g.addEdge(4, 1); 
g.addEdge(2, 3); 
g.addEdge(3, 1); 

g.topologicalSort() 

It gives:

[5, 4, 3, 2, 1, 0]

Now, I want my code to be able to handle with strings as keys:

g.addEdge('f', 'c')
g.addEdge('f', 'a')
g.addEdge('e', 'a')
g.addEdge('e', 'b')
g.addEdge('c', 'd')
g.addEdge('d', 'b')

(just change the digits to letters... 0='a', 1='b' etc..) However this doesn't work.

It should give:

['f', 'e', 'd', 'c', 'b', 'a']

The problem is here:

for i in range(self.V):
    if visited[i] is False:
        self.topologicalSortUtil(i, visited, stack)

The code iterates over range and not over the actual node keys.

I tried to convert it to:

for i in self.graph.items():

but it doesn't work.

TypeError: list indices must be integers or slices, not tuple

How can I fix this?

Solution

There are a few things that could be generalized in your class Graph to accept both letters and numbers as names of the vertices.

Here is a suggestion:

class Graph:
    def __init__(self, name_of_vertices):
        self.graph = collections.defaultdict(list)
        self.name_of_vertices = name_of_vertices     # define all vertices by name

    def add_edge(self, v, other_v):
        self.graph[v].append(other_v)

    def _topological_sort(self, v, visited, stack):
        visited[v] = True

        for other_v in self.graph[v]:
            if not visited[other_v]:
                self._topological_sort(other_v, visited, stack)

        stack.insert(0, v)

    def topological_sort(self):
        # Mark all the vertices as not visited
        visited = {
            v: False
            for v in self.name_of_vertices}
        stack = []

        for v in self.name_of_vertices:
            if not visited[v]:
                self._topological_sort(v, visited, stack)

        print(stack)

Then you can use this:

g = Graph(['z', 'a', 'b', 'c', 'd', 'e'])
g.add_edge('e', 'b')
g.add_edge('e', 'z')
g.add_edge('d', 'z')
g.add_edge('d', 'a')
g.add_edge('b', 'c')
g.add_edge('c', 'a')
g.topological_sort()
# prints: ['e', 'd', 'b', 'c', 'a', 'z']

g = Graph(list(range(6)))
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)
g.topological_sort()
# prints: [5, 4, 2, 3, 1, 0]

Answered By - Ralf