如何创建最大强连通分量图

Question

我想创建一个有向图的最大强连通分量图。 Networkx 有一个函数 (components.strongly_connected_components) 可以提取最大的强连通分量，但它只是 returns 节点集的生成器。但这不包含节点之间的连接。

有没有函数可以创建最大强连通分量的有向图？

Answer 1

请参阅docs for extracting a subgraph。

您可以获得包含这些节点的子图的边。

在这个简单的例子中，节点 2、3 和 4 是强连接的，但节点 5 是断开的（完全）。

import networkx as nx
G = nx.DiGraph()
G.add_nodes_from([2, 3, 4, 5])

G.add_edge(2, 3)
G.add_edge(4, 3)
G.add_edge(4, 2)
G.add_edge(3, 2)
G.add_edge(3, 4)
G.add_edge(2, 4)

# following results in [{2, 3, 4}, {5}]
strongs = sorted(nx.strongly_connected_components(G), key=len, reverse=True)
for strong in strongs:
    print(G.subgraph(strong).edges())

结果（第一行是{2, 3, 4}，第二行是{5}没有边）：

[(2, 3), (2, 4), (3, 2), (3, 4), (4, 3), (4, 2)]
[]

如何创建最大强连通分量图

How to create a graph of largest strongly connected component

python

networkx