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

Что вам не хватает, так это определение сильно связного :

[Направленный граф] сильно связан, разделен или просто силен, если содержит направленный путьот u до v и направленный путь от v до u для каждой пары вершин u, v. Сильные компоненты - это максимальные сильносвязанные подграфы.

У вас есть нет сильныйсвязь между любыми двумя узлами показанного графа, не говоря уже о 3-узловом подграфе, который вы перечисляете.Вы действительно можете пройти 3 -> 41 -> 39, но пути назад к 41, не говоря уже о том, что нет, не существует. Следовательно, этот граф не сильно связан.

Answer 2

Итак, благодаря комментариям и ответам, я понял, что «подключение» было ложным руководством к тому, чего я хочу достичь. Для ясности: Я хочу получить все возможные пути между всеми начальными узлами к их связанным конечным узлам в направленном ациклическом графе .

Так что я закончил тем, что написал свое собственное решение, которое довольно просто для понимания, но, вероятно, не самое лучшее в отношении производительности или стиля (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 есть встроенная функция, я явно ее пропустил)

Answer 3

Согласно определению сильно связного графа, вы получите правильный результат.

ОПРЕДЕЛЕНИЕ: сильно связный граф

Направленный граф G = (V,E) называется сильно связной, если каждая вершина v в V достижима из любой другой вершины в V.