I'm trying to solve a situation where I've implemented Kahn's algorithm to find and return one topological sorting in a graph. However, I want to try and implement this in order to return all topological orders. For example, if a graph had 4 nodes with the following edges:
(1 2)
(1 3)
(2 3)
(2 4)
it would return the following 2 possible topological orders:
[1 2 3 4]
[1 2 4 3]
Is there anyway I can go about doing this with my following code:
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)
# The function to do Topological Sort.
def topologicalSort(self):
# Create a vector to store indegrees of all
# vertices. Initialize all indegrees as 0.
in_degree = [0]*(self.V)
# Traverse adjacency lists to fill indegrees of
# vertices. This step takes O(V+E) time
for i in self.graph:
for j in self.graph[i]:
in_degree[j] += 1
# Create an queue and enqueue all vertices with
# indegree 0
queue = []
for i in range(self.V):
if in_degree[i] == 0:
queue.append(i)
#Initialize count of visited vertices
cnt = 0
# Create a vector to store result (A topological
# ordering of the vertices)
top_order = []
# One by one dequeue vertices from queue and enqueue
# adjacents if indegree of adjacent becomes 0
while queue:
# Extract front of queue (or perform dequeue)
# and add it to topological order
u = queue.pop(0)
top_order.append(u)
# Iterate through all neighbouring nodes
# of dequeued node u and decrease their in-degree
# by 1
for i in self.graph[u]:
in_degree[i] -= 1
# If in-degree becomes zero, add it to queue
if in_degree[i] == 0:
queue.append(i)
cnt += 1
# Check if there was a cycle
if cnt != self.V:
print "There exists a cycle in the graph"
else :
#Print topological order
print top_order
#Test scenario
g = Graph(4);
g.addEdge(1, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.topologicalSort()
Note that graph nodes indexes starts with 0:
g.addEdge(1, 2); # replace with 0, 1 and so on
With this modification this algorithm returns only one topological sorting, while graph can have more sortings, because we always select only first item from queue. To get all sortings you can use this modified code:
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)
# The function to do Topological Sort.
def topologicalSort(self):
# Create a vector to store indegrees of all
# vertices. Initialize all indegrees as 0.
in_degree = [0] * self.V
# Traverse adjacency lists to fill indegrees of
# vertices. This step takes O(V+E) time
for i in self.graph:
for j in self.graph[i]:
in_degree[j] += 1
# Create an queue and enqueue all vertices with
# indegree 0
queue = []
for i in range(self.V):
if in_degree[i] == 0:
queue.append(i)
self.process_queue(queue[:], in_degree[:], [], 0)
def process_queue(self, queue, in_degree, top_order, cnt):
if queue:
# We have multiple possible next nodes, generate all possbile variations
for u in queue:
# create temp copies for passing to process_queue
curr_top_order = top_order + [u]
curr_in_degree = in_degree[:]
curr_queue = queue[:]
curr_queue.remove(u)
# Iterate through all neighbouring nodes
# of dequeued node u and decrease their in-degree
# by 1
for i in self.graph[u]:
curr_in_degree[i] -= 1
# If in-degree becomes zero, add it to queue
if curr_in_degree[i] == 0:
curr_queue.append(i)
self.process_queue(curr_queue, curr_in_degree, curr_top_order, cnt + 1) # continue recursive
elif cnt != self.V:
print("There exists a cycle in the graph")
else:
#Print topological order
print(top_order)
g = Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.topologicalSort()
Output:
[0, 1, 2, 3]
[0, 1, 3, 2]