Networkx：获取 DAG 中的所有可能路径

Question

我正在尝试根据 连通性 将有向（非循环）图拆分为方向连接的路径：

当我测试弱连接子图和强连接子图时，这是我得到的：

Weak connectivity :
['16', '17'], ['3', '41', '39', '42']
Strong connectivity :
['17'], ['16'], ['39'], ['41'], ['3'], ['42']

我理解弱连接结果，但不理解强连接结果，正如我所期望的 3 个子图：[16, 17]、[42, 39] 和 [3, 41, 39]。

我在这里错过了什么，为什么那些单节点列表？如何得到预期的结果？

代码如下：

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([('16', '17'), ('3', '41'), ('41', '39'), ('42', '39')])

print("Weak connectivity : ")
for subgraph in (G.subgraph(c).copy() for c in nx.weakly_connected_components(G)) :
    print(subgraph.nodes)
print("Strong connectivity : ")
for subgraph in (G.subgraph(c).copy() for c in nx.strongly_connected_components(G)) :
    print(subgraph.nodes)

nx.draw_networkx(G, pos=nx.circular_layout(G))
plt.show()

Answer 1

根据强连通图的定义，你得到的结果是正确的。

定义：强连通图

如果 V 中的每个顶点 v 都可以从 V 中的每个其他顶点到达，则称有向图 G=(V,E) 是强连通的。

Answer 2

您缺少的是 strongly connected 的定义：

[A directed graph] is strongly connected, diconnected, or simply strong if it contains a directed path from u to v and a directed path from v to u for every pair of vertices u, v. The strong components are the maximal strongly connected subgraphs.

您在图中显示的任意两个节点之间没有强连接，更不用说您列出的 3 节点子图了。实际上，您可以遍历 3 -> 41 -> 39，但没有返回 41 的路径，更不用说 3 了。因此，该图不是强连通。

Answer 3

所以，感谢评论和回答，我意识到 "connectivity" 是我想要实现的目标的错误线索。要清楚：我想在有向无环图中获取所有起始节点到它们连接的结束节点之间的所有可能路径。

所以我最终编写了自己的解决方案，它很容易理解，但在性能或风格（pythonic / networkx）方面可能不是最好的。欢迎提出改进建议:)

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([('16', '17'), ('3', '41'), ('41', '39'), ('42', '39')])

roots = []
leaves = []
for node in G.nodes :
  if G.in_degree(node) == 0 : # it's a root
    roots.append(node)
  elif G.out_degree(node) == 0 : # it's a leaf
    leaves.append(node)

for root in roots :
  for leaf in leaves :
    for path in nx.all_simple_paths(G, root, leaf) :
      print(path)

nx.draw_networkx(G, pos=nx.circular_layout(G))
plt.show()

（如果networkx有内置函数，我明明漏了）

Networkx：获取 DAG 中的所有可能路径

Networkx : getting all possible paths in DAG

python

graph

directed-graph

networkx