python - 查找强连通分量上的边数

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 时它返回 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函数从原始图中提取具有给定节点的子图。您发送节点集合作为属性，它会返回原始图的子图，其中包含这些节点和它们之间的边:

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