如何在有向图中查找子图而不转换为无向图？

Question

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

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

有没有一种简单的方法可以完成我想要实现的目标？

Answer 1

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

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

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