Networkx：如何在一个无权、无向、无标记、连通的图中找到所有长度不超过给定最大长度的唯一路径？

Question

假设我有以下无权（所有边的权重均为1）、无向、未标记的连通图，并且我想要查找最大给定长度的所有唯一路径。同时，路径中节点不能重复出现。我目前在networkx中找不到这样的常规操作。

请问是否有任何类似的方法存在？ 或者这个问题有什么好的解决方案吗？

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生成所需最大路径长度减1个节点的所有节点组合并在组合内检查连通性（例如使用G.has_edge(node_1, node_2)）等更好的解决方案，这似乎是一个超级糟糕的解决方案。

- Charly Empereur-mot

---

小于2的路径怎么办？ - user3483203

还需要说明的是，我正在编辑我的示例，谢谢。 - Charly Empereur-mot

看看 all_simple_paths。它允许您指定一个截止点。由于您需要指定每个起始和结束节点，因此仍然是n^2。 - user3483203

我正在考虑使用 all_simple_paths，但不得不指定起点和终点，让我觉得这是一个不好的解决方案。但你建议使用 itertools 来获取所有成对节点组合 + 最大长度截止点之间的 all_simple_paths，并过滤所有生成的路径以确保唯一性，对吗？ 我想这可以起作用，但我仍然在思考是否可能有更好的解决方案。 - Charly Empereur-mot

你不需要使用itertools。 - user3483203

所以，只需使用经典的Python循环来生成节点对，也可以少加载一个库。 - Charly Empereur-mot

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)]

- Charly Empereur-mot

Answer 2

以下代码应该可以解决您的问题，但它会输出比您给出的路径更多的路径（例如[1,2]和[2,1]）：

def find_all_simple_paths(graph, cutoff):

    if cutoff == 0:
        return [[node] for node in graph]
    else:
        all_paths = []
        current_paths = [[node] for node in graph]
        # If you want to include paths of length 0
        # all_paths.extend(current_paths)
        for _ in range(min(cutoff, len(graph))):
            next_paths = []
            for path in current_paths:
                #print(path)
                for neighbor in graph.neighbors(path[-1]):
                    if neighbor not in path:
                        new_path = path[:] + [neighbor]
                        next_paths.append(new_path)
                        all_paths.append(new_path)
            current_paths = next_paths

        return all_paths
find_all_simple_paths(G,2)

输出

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

- Sparky05