networkX中的最大弱连通分量

Question

我有两个问题。

1. 在无向图中，我想要找到最大连通分量。我阅读了networkX的API文档，找到了这个函数nx.connected_component_subgraphs()。但是我不知道如何使用它，因为它的返回值是一个生成器，我不能导出最大连通组件的子图。
2. 它和一个一样。但是图是有向的。我想找出有向图的最大弱连通分量。因此，我使用nx.weakly_connected_component_subgraphs()这个函数。问题1也有同样的问题。

如何利用networkX中的内建函数求出无向图中最大连通分量和有向图中最大弱连通分量？

我使用NetworkX 1.9.1。

Answer 1

NetworkX组件函数返回Python生成器。可以使用Python函数在生成器中创建一个项目列表。这里有一个例子说明了这一点，同时也找到了最大的弱连通分量。

In [1]: import networkx as nx

In [2]: G = nx.DiGraph()

In [3]: G.add_path([1,2,3,4])

In [4]: G.add_path([10,11,12])

您可以使用例如list将生成器转换为子图列表：

In [5]: list(nx.weakly_connected_component_subgraphs(G))
Out[5]: 
[<networkx.classes.digraph.DiGraph at 0x278bc10>,
 <networkx.classes.digraph.DiGraph at 0x278ba90>]

最大运算符接受一个键参数，您可以将其设置为len函数，该函数调用每个子图上的len(g)来计算节点数。因此，要获得具有最多节点数量的组件，可以编写

In [6]: largest = max(nx.weakly_connected_component_subgraphs(G),key=len)

In [7]: largest.nodes()
Out[7]: [1, 2, 3, 4]

In [8]: largest.edges()
Out[8]: [(1, 2), (2, 3), (3, 4)]

Answer 2

目前，所提供的解决方案不再起作用，因为weakly_connected_component_subgraphs已在networkx上被废弃。

TLDR:使用subgraph(original_graph, weakly_connected_component_set)

与使用旧版本的networkx不同，可以通过执行以下操作获得最大的弱连接组件：

#create an example graph
import networkx as nx
G = nx.lollipop_graph(10, 5)
G = G.to_directed() #weakly connected component needs a directed graph.

您可以收集所有弱连通子图，也可以通过以下操作选择最大子图：

#list of all weakly connected subgraphs, each one is a set. 
#If you don't list them, you'll get a generator.
list_of_subgraphs = list(nx.weakly_connected_components(G))

list_of_digraphs = []

for subgraph in list_of_subgraphs:
    list_of_digraphs.append(nx.subgraph(G, subgraph)) #this is the relevant part.

这些子图中的每一个现在都是存储在list_of_digraphs中的nx有向图。

如果你想要最大弱连通子图，

max_wcc = max(nx.weakly_connected_components(G), key=len)
max_wcc = nx.subgraph(G, max_wcc)