python-3.x - Networkx:如何在未加权、无向、无标签、连通图中找到最大给定长度的所有唯一路径？

Question

假设我有以下未加权(所有边权重 = 1)、无向、未标记、连通图，并且我想找到最大给定长度的所有唯一路径。此外，节点不能在一条路径中出现两次。我找不到在 networkx atm 中执行此操作的例程。

有谁知道是否存在这样的东西？或者什么是解决此问题的好方法？

import networkx as nx
G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9])
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (2, 4), (6, 9), (8, 9), (9, 6)])

示例图如下所示

假设我需要最大长度 = 2，我想要这个输出

[1 2]
[2 3]
[2 4]
[3 4]
[4 5]
[5 6]
[6 7]
[7 8]
[8 9]
[6 9]
[1 2 3]
[1 2 4]
[2 3 4]
[2 4 5]
[3 4 5]
[4 5 6]
[5 6 7]
[5 6 9]
[6 7 9]
[6 7 8]
[7 8 9]
[6 9 8]

编辑:我正在寻找比使用 itertools 生成 required_max_path_length-1 个节点的所有节点组合 + 在组合组或类似的东西中使用 G.has_edge(node_1, node_2) 检查连通性更好的解决方案，这似乎是一个非常糟糕的解决方案。

Answer 1

所以现在我正在对@user3483203 执行此操作，它会产生预期的输出。可以避免使用 Itertools，但在我的具体情况下我不介意。

不过，对于较大的图，我仍然觉得它的缩放比例会比其他东西差一点，如果有人找到更好的解决方案，我会更改已接受的答案。

import networkx as nx
import itertools

required_max_path_length = 2 # (inferior or equal to)

G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9])
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (2, 4), (6, 9), (8, 9), (9, 6)])

all_paths = []
nodes_combs = itertools.combinations(G.nodes, 2)

for source, target in nodes_combs:
    paths = nx.all_simple_paths(G, source=source, target=target, cutoff=required_max_path_length)

    for path in paths:
        if path not in all_paths and path[::-1] not in all_paths:
            all_paths.append(path)

for path in all_paths:
    print(path)

如果您希望路径作为边列表，您可以这样做:

for path in map(nx.utils.pairwise, all_paths):
    print(list(path))

你会得到:

[(1, 2)]
[(1, 2), (2, 3)]
[(1, 2), (2, 4)]
[(2, 3)]
[(2, 3), (3, 4)]
[(2, 4)]
[(2, 4), (4, 5)]
[(3, 4)]
[(3, 4), (4, 5)]
[(4, 5)]
[(4, 5), (5, 6)]
[(5, 6)]
[(5, 6), (6, 7)]
[(5, 6), (6, 9)]
[(6, 7)]
[(6, 7), (7, 8)]
[(6, 8), (8, 9)]
[(6, 9)]
[(7, 8)]
[(6, 7), (7, 9)]
[(7, 8), (8, 9)]
[(8, 9)]