Вернуть все топологические сортировки в графе, используя алгоритм Кана?

Question

Я пытаюсь разрешить ситуацию, когда я реализовал алгоритм Кана, чтобы найти и вернуть одну топологическую сортировку в графе. Однако я хочу попытаться реализовать это, чтобы вернуть все топологические заказы. Например, если граф имел 4 узла со следующими ребрами:

(1 2)
(1 3)
(2 3)
(2 4)

вернет 2 возможных топологических порядка:

[1 2 3 4] 
[1 2 4 3]

Могу ли я в любом случае сделать это с помощью следующего кода:

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

Обратите внимание, что индексы узлов графа начинаются с 0:

g.addEdge(1, 2);  # replace with 0, 1 and so on

С этой модификацией этот алгоритм возвращает только одну топологическую сортировку, тогда как у графа может быть больше сортировок, потому что мы всегда выбираем только первый элемент из очереди. Чтобы получить все сортировки вы можете использовать этот модифицированный код:

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

Выход:

[0, 1, 2, 3]

[0, 1, 3, 2]

Answer 2

Ваша постановка задачи соответствует функции NetworkX all topo sorts .

Если вы просто хотите получить результат, я рекомендую вызывать их функцию как есть.

Если выхочу взломать реализацию, их исходный код может сообщить ваш собственный.В этом случае вы можете переключиться с алгоритма Кана на алгоритм Кнута, который они цитируют.