python - 使用 Kosaraju 算法的图中强连通分量 (SCC) 的大小(边数)
问题描述
我在 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] 作为结果。任何帮助深表感谢。
解决方案
推荐阅读
- python - 根据每个分数对预测池中的样本进行排名
- c++ - 有没有办法以特定方式显示 cpp 图
- javascript - 在 vb.net 中使用 Ajax 时找不到具有给定 url 的资源错误
- python - 运行带有输入/输出参数的 bash 命令,但将它们作为不在磁盘中的变量提供
- windows - 无法在 Vim 上制作 Dracula 主题 [os: W10]
- c# - .NET Core 从无法返回重定向的方法将用户发送到页面
- sql-server - 了解具有高安全模式和手动故障转移的数据库镜像会话设置。为什么会有人选择这种组合?
- google-cloud-platform - googleapi: 错误 400: Precondition check failed., failedPrecondition while create Cloud Composer Environment through Terraform
- c# - 如何将 FirestoreProperty 与 DocumentReference 结合使用?
- kotlin - Intellij Kotlin - 缺少错误继续