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

所以，多亏了评论和回答，我意识到“连接性”是我想要实现的目标的错误引导。要清楚：我想在有向无环图中获得所有起始节点到它们连接的结束节点之间的每条可能路径。

所以我最终编写了自己的解决方案，这很容易理解，但可能不是最好的，关于性能或风格（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有内置函数，我明显漏掉了）