1

我在 Python 3 中编写了 Kosaraju 的两遍算法，当前的实现找到 SCC 并根据每个 SCC 中的节点数确定每个 SCC 的大小。然后，确定最大的 SCC。如何更改代码，以便它可以根据每个 SCC 中的边数计算每个 SCC 的大小。

# Input : a directed graph, G
import sys, threading, time


# Increase recursion limit and stack size in windows environment
sys.setrecursionlimit(2 ** 20)
threading.stack_size(67108864)


# Source file has one directed edge per line
# e.g. "1 5" is one line. 1 is the tail and 5 is the head
source = "???.txt"
# Number of nodes
n = ???


def main():
    def Kosaraju(G,G_rev):
        global leader, finish
        # Set leader for strongly connected group
        leader = {}
        # Set finishing time for each element
        finish = {}
        # Run first DFS Loop
        DFS_Loop(G_rev)
        # Reorder graph with nodes numbered according to finish time
        G_reordered = {}
        g_values = list(G.values())
        for i in range(1,n+1):
            temp = g_values[i-1]
            G_reordered[finish[i]] = [finish[x] for x in temp]
        # Run second DFS Loop with reordered graph
        DFS_Loop(G_reordered)
        return leader

    def DFS_Loop(G):
        global t,s, explored
        t = 0 # Number of nodes processed so far (only useful for pass 1)
        s = 0 # Current source vertex (only useful for pass 2)
        # Initialize all nodes as unexplored
        explored = {}
        for i in range(1,n+1):
            explored[i] = 0 
        # Explore each adjacent node i (if unexplored)
        for i in range(n,0,-1):
            if explored[i] == 0:
                s = i
                DFS(G,i)
        return

    def DFS(G,i):
        # Run Depth First Search
        global t, leader, finish
        explored[i] = 1 # Mark node i as explored
        leader[i] = s # Sets leader as node s (useful for second pass only)
        # For each arc (i,j) in G, if j is not yet explored, recurse on j
        for j in G[i]:
            if explored[j] == 0:
                DFS(G,j)
        t = t + 1
        finish[i] = t
        return

    def get_graph():
        # Grabs graph from input file
        # Create dictionary with a key for each node
        G, G_rev = {}, {}
        for i in range(1,n+1):
            G[i], G_rev[i]  = [], []
        # Populate dictionary with information from file
        file = open(source)
        for line in file:
            list_line = line.split()
            i = int(list_line[0])
            j = int(list_line[1])
            G[i].append(j)
            G_rev[j].append(i)
        file.close()
        return G, G_rev

    def most_common(lst,x):
        # This functions returns the 'x' most common elements from 'lst' 
        from collections import Counter
        c = Counter(lst)
        output = []        
        for number,count in c.most_common(x):
            output.append(count)
        return output               

    if __name__=="__main__":
        G, G_rev = get_graph()
        leader = Kosaraju(G,G_rev)
        print(most_common(leader.values(),x))


thread = threading.Thread(target=main)
thread.start()

例如对于一个图（下面以列表的形式呈现，只是为了简单起见）：[[1,2],[2,3],[2,5],[3,4],[4 ,1],[5,6],[6,7],[7,5]] 第一个元素是尾部，第二个元素是头部。

上述代码的结果，包括按降序排列的 SCC 的大小，是 [4,3]

但是，当前的实现导致图的数字相同：[[1,2],[1,3],[2,3],[2,5],[3,4],[4,1 ],[5,6],[6,7],[7,5]] 有一个附加边 [1,3]。我想要 [5, 3] 作为结果。任何帮助深表感谢。

4

0 回答 0