查找强连接组件上的边数

Question

我有一个名为 Gmedium 的网络图，我通过以下代码找到了最大的强连通分量：

maxstmed = max(nx.strongly_connected_components(Gmedium), key=len)

我的问题是，你如何找到这个连接网络的边数？如果您尝试查找节点数，我是这样的：

newGm = nx.Graph()
newGm.add_nodes_from(list(maxstmed))
newGm.number_of_nodes()

但是你不能将它应用于边缘，因为当我使用 add_edges_from 和 number_of_edges 时它是 returns 0。我试着用这个手动计数：

count = 0
for u in list(newGm.nodes):
    for v in list(newGm.nodes):
        if u == v:
            continue
        if nx.has_path(Gmedium,u,v) == True:
            count += 1
print(count)

但是，对于一个大型网络（拥有超过 10.000 个节点）来说，这需要很长时间。任何人都知道有效处理它的算法或功能？我正在使用 Python 版本。 3 在 Spyder 环境中。谢谢。

Answer 1

您可以使用 subgraph 函数从原始图中提取具有给定节点的子图。您发送一组节点作为属性，它 returns 您是原始图的子图，其中包含这些节点和它们之间的边：

G = nx.fast_gnp_random_graph(30, 0.04, directed=True, seed=1)
nx.draw(G)

C = max(nx.strongly_connected_components(G), key=len)
print(C)

{0, 3, 4, 6, 8, 10, 11, 15, 21, 22, 24, 25}

S = G.subgraph(C)
nx.draw(S)

print(list(nx.edges(S)))

[(0, 3), (3, 4), (3, 21), (4, 6), (6, 11), (6, 15), (8, 0), (10, 6), (11, 8), (11, 15), (15, 24), (15, 25), (21, 8), (21, 22), (21, 15), (22, 24), (22, 25), (22, 15), (24, 10), (25, 0)]

查找强连接组件上的边数

Finding Number of Edges on Strongly Connected Component

python

graph

networkx

edges

connected-components