3

我有一个包含许多子图的图。我有一些边在两个方向上连接两个节点，即 A-->B 和 B-->A。双向性很重要，因为它代表我们缺乏关于 A 到 B 还是 B 到 A 的知识，而且我们没有简单的方法来确定哪个是正确的。

我想知道有多少子图，并将每个子图中的边输出到 Pandas DataFrame。但是，NetworkX 仅在提供的 connected_components_subgraph(G) 函数中接收无向图。当我将图转换为无向图时，我可以使用 connected_components_subgraph() 来获取每条边中的节点，但我失去了边的方向性。

有没有一种简单的方法来做我想要实现的目标？

4

2 回答 2

5

也许您正在寻找弱连接组件？

该算法将边缘视为无向并返回该图中的连通分量。

In [1]: import networkx as nx

In [2]: G = nx.DiGraph([(1,2),(2,1),(3,4)])

In [3]: for w in nx.weakly_connected_component_subgraphs(G):
   ...:     print(w.edges())
   ...:     
[(1, 2), (2, 1)]
[(3, 4)]
于 2013-09-07T13:57:01.490 回答
1

您正在寻找图形的SCC，它们是强 连通 分量。它们可以通过DFS的变体（深度优先搜索）找到。

你应该看看维基文章。

于 2013-09-05T18:55:33.813 回答