7

我有两个问题。

  1. 在无向图中，我想找到最大的连通分量。我阅读了networkX的API文档，找到了这个函数 nx.connected_component_subgraphs()。但我不知道如何使用它，因为它的返回值是一个生成器，我无法导出最大连通分量的子图。

  2. 它与一个相同。但是图是有向的。我想找到有向图的最大弱连接分量。因此，我使用nx.weakly_connected_component_subgraphs(), 这个函数。问题1也有同样的问题。

如何使用networkX中的内置函数找到无向图中的最大连通分量和有向图中的最大弱连通分量？

我使用 NetworkX 1.9.1。

4

2 回答 2

7

NetworkX 组件函数返回 Python 生成器。list您可以使用 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>]

max 运算符采用一个关键参数，您可以将其设置为 Python 函数，该函数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)]
于 2014-10-07T18:35:56.527 回答
1

目前，提供的解决方案不再有效，因为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.

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

max_wcc = max(nx.weakly_connected_components(G), key=len)
max_wcc = nx.subgraph(G, max_wcc)
于 2021-11-09T00:15:16.293 回答