I was studying Topological Sorting and came across GeeksforGeek's Python code.
# Python program to print topological sorting of a DAG
from collections import defaultdict
# Class to represent a graph
class Graph:
def __init__(self,vertices):
self.graph = defaultdict(list) # dictionary containing adjacency List
self.V = vertices #No. of vertices
# function to add an edge to graph
def addEdge(self,u,v):
self.graph[u].append(v)
# A recursive function used by topologicalSort
def topologicalSortUtil(self,v,visited,stack):
# Mark the current node as visited.
visited[v] = True
# Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
# Push current vertex to stack which stores result
stack.insert(0,v)
# The function to do Topological Sort. It uses recursive
# topologicalSortUtil()
def topologicalSort(self):
# Mark all the vertices as not visited
visited = [False]*self.V
stack =[]
# Call the recursive helper function to store Topological
# Sort starting from all vertices one by one
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
# Print contents of stack
print stack
# Driver Code
g = Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)
print "Following is a Topological Sort of the given graph"
g.topologicalSort()
However, I have changed the inputs because I wanted to test an actual case I need for my project.
g = Graph(5)
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
But I am getting a "list index out of range" exception in the recurrent function and cannot understand why.
IndexError Traceback (most recent call last)
<ipython-input-8-cb05f6defc6c> in <module>
54
55 print("Following is a Topological Sort of the given graph")
---> 56 g.topologicalSort()
<ipython-input-8-cb05f6defc6c> in topologicalSort(self)
37 for i in range(self.V):
38 if visited[i] == False:
---> 39 self.topologicalSortUtil(i,visited,stack)
40
41 # Print contents of stack
<ipython-input-8-cb05f6defc6c> in topologicalSortUtil(self, v, visited, stack)
21 for i in self.graph[v]:
22 if visited[i] == False:
---> 23 self.topologicalSortUtil(i,visited,stack)
24
25 # Push current vertex to stack which stores result
<ipython-input-8-cb05f6defc6c> in topologicalSortUtil(self, v, visited, stack)
21 for i in self.graph[v]:
22 if visited[i] == False:
---> 23 self.topologicalSortUtil(i,visited,stack)
24
25 # Push current vertex to stack which stores result
<ipython-input-8-cb05f6defc6c> in topologicalSortUtil(self, v, visited, stack)
21 for i in self.graph[v]:
22 if visited[i] == False:
---> 23 self.topologicalSortUtil(i,visited,stack)
24
25 # Push current vertex to stack which stores result
<ipython-input-8-cb05f6defc6c> in topologicalSortUtil(self, v, visited, stack)
20 # Recur for all the vertices adjacent to this vertex
21 for i in self.graph[v]:
---> 22 if visited[i] == False:
23 self.topologicalSortUtil(i,visited,stack)
24
IndexError: list index out of range
The IndexError: list index out of range is caused because this example code assumes that vertices are numbered starting with zero.
The list visited is initialized as:
visited = [False]*self.V
Hence, if the graph is initialized with 5 vertices, then the indices of visited will be 0, 1, 2, 3, 4.
Then later, the function topologicalSortUtil(self, v, visited, stack) executes line 22 below and vertex 5 is out of range, since the range goes from 0 to 4:
21 for i in self.graph[v]:
---> 22 if visited[i] == False:
23 self.topologicalSortUtil(i,visited,stack)
The following code using zero-based vertex indexing works as expected.
g = Graph(5)
g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(3, 4)
print("Following is a Topological Sort of the given graph")
g.topologicalSort()
Output:
Following is a Topological Sort of the given graph
[0, 1, 2, 3, 4]
The following implementation does not require you to specify the number of vertices, since the count automatically increases whenever a new vertex is added to the graph via the add_edge method.
In addition, the vertices do not need to start with any particular number. I went ahead and cleaned up the formatting to use standard snake-case naming conventions.
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list) #dictionary containing adjacency List
def add_edge(self,u,v):
self.graph[u].append(v)
def topological_sort(self) -> list:
visited = set()
reverse_topo = list()
vertices = set(self.graph.keys())
for vertex in vertices:
if vertex not in visited:
self._topological_sort_util(vertex, visited, reverse_topo)
return list(reversed(reverse_topo))
def _topological_sort_util(self, vertex, visited, reverse_topo):
visited.add(vertex)
for adj_vertex in self.graph[vertex]:
if adj_vertex not in visited:
self._topological_sort_util(adj_vertex, visited, reverse_topo)
reverse_topo.append(vertex)
g = Graph()
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 5)
print("Following is a Topological Sort of the given graph")
vertices_topo_sorted = g.topological_sort()
print(vertices_topo_sorted)
Following is a Topological Sort of the given graph
[1, 2, 3, 4, 5]