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

以下代码应该可以解决您的任务，但它输出的路径比您提供的路径多（例如 [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]]

Answer 2

所以现在我正在对@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)]

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

Networkx: How to find all unique paths of max given length in an unweighted, undirected, unlabeled, connected graph?

enumeration

networkx

python-3.x