在 DIRECTED networkx 图中查找多条路径

Question

我有一个有向图如下：

我用 networkx 创建了它并用 ipycytoscape 绘制了它。该图是有向图。所有边只有一个方向。

问题是如何从特定节点找到该节点与节点一之间的所有路径。由于图是有向的，因此只有边的所有方向都相同的路径才是有效的。在图中，6 和 1 之间有两条路径。乍一看可能会注意到蓝色路径，但在这种情况下，边缘 4-6 的方向与其他方向不同。

nodes = [1,2,3,4,5,6,7,8]
children = [[2],[3,4],[5,6],[6,7],[8],[],[8],[]]
G2 = nx.Graph()
G2.add_nodes_from(nodes)
for i,child in enumerate(children):
    for c in child:
        G2.add_edge(i+1, c)
cyto = CytoscapeWidget()
cyto.graph.add_graph_from_networkx(G2, directed=True)
cyto.set_layout(name='dagre', nodeSpacing=10, edgeLengthVal=10)
display(cyto)

我正在寻找的是网络方法，它为我提供了两个节点之间的路径列表。伪代码：

for node1 in G.nodes:
for node2 in G.nodes:
list_of_paths = networks_method???(node1,node2)

注意：图表中的箭头（方向性）总是从较小的数字指向较大的数字。 2 可以是 3 的父代，但不能反过来。

Answer 1

通常，寻找“所有路径”的问题可能是一项指数任务，会产生无限多的路径。但是，您描述了一个来自有向图的特殊子类的图：有向无环图 (DAG)。 DAG 是无环的有向图 G，即对于 G 中的节点 u 不存在路径 u->v_1...v_n- >你。由于您说所有边都从较小的数字到较大的数字，因此您的图形是 DAG。

在这种情况下，修改后的 DFS 搜索将为您提供所有可能的路径。 “DAG 中的所有路径”主题已在以下问题中讨论

list of all paths from source to sink in directed acyclic graph
Enumerating all paths in a directed acyclic graph

在 DIRECTED networkx 图中查找多条路径

finding multiple paths in a DIRECTED networkx graph

python

graph

networkx

ipycytoscape