Return all topological sort orderings in a graph using Kahn's algorithm?

Question

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

Answer 1

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]

Answer 2

Your problem statement matches the NetworkX all topo sorts function.

If you just want the result, I recommend calling their function as-is.

If you want to hack on an implementation, their source code might inform your own. In that case you might choose to switch from Kahn's algorithm to the one by Knuth that they cite.