使用networkx查找所有可能的路径

Question

如何使用网络找到图中两个节点之间的所有可能路径？

import networkx as nx

G = nx.Graph()
edges = ['start-A', 'start-b', 'A-c', 'A-b', 'b-d', 'A-end', 'b-end']

nodes = []
for node in edges:
    n1 = node.split('-')[0]
    n2 = node.split('-')[1]
    
    if n1 not in nodes:
        nodes.append(n1)
        
    if n2 not in nodes:
        nodes.append(n2)
for node in nodes:
    G.add_node(node)
for edge in edges:
    n1 = edge.split('-')[0]
    n2 = edge.split('-')[1]
    
    G.add_edge(n1, n2)


for path in nx.all_simple_paths(G, 'start', 'end'):
    print(path)

这是结果：

['start', 'A', 'b', 'end']
['start', 'A', 'end']
['start', 'b', 'A', 'end']
['start', 'b', 'end']

但是我想要所有可能的路径，例如：start,b,A,c,A,end

- Will

Answer 1

如果允许重复访问节点，则在至少有两个节点连接的路径上（不包括起点和终点），有效路径的数量没有上限。如果路径上有两个连接的节点，例如节点A和B，则可以通过将A->B->A插入在start和end之间的有效路径的适当部分中来形成任意数量的新路径。

如果限制了重复访问次数，则可以将all_simple_paths作为起点，并在两个节点之间插入任何有效路径，根据允许的重复访问次数多次重复此过程。

在您的示例中，这将获取all_simple_paths(G，'start'，'end')的第三个输出，即['start'，'b'，'A'，'end']，然后对于与b连接的所有节点，在X是迭代节点的情况下遍历all_simple_paths(G，X，'A')的结果。

以下是草图伪代码（它无法工作但建议算法）：

for path in nx.all_simple_paths(G, 'start', 'end'):
    print(path)
    for n, X, Y in enumerate(zip(path, path[1:])):
       if X is not 'start' and X is not 'end':
            for sub_path in nx.all_simple_paths(G, X, Y):
                print(path[:n] + sub_path + path[n+2:])

这种方法不太好，因为使用这种公式很难控制重复访问的次数。解决这个问题的一种方法是创建一个基于节点计数的附加过滤器。然而，对于任何现实世界的图形，由于路径和节点数量非常大，这都是不可行的...

- SultanOrazbayev