找到简单路径的所有唯一组合

Question

考虑以下网络示例：

gg = nx.complete_graph(6)
paths = nx.all_simple_paths(gg, source=0, target=3, cutoff=5)
print(list(paths))

nx.draw(gg, with_labels = True)

all_simple_paths() 返回节点 (0, 3) 之间的所有可能路径。如果以前使用过节点，我需要一个替代函数来避免计算路径。

Answer 1

如果您想保留唯一的路径组合，即到达目标的唯一节点集，您可以构建 set 个 [=14] =] 从您的路径，然后返回到列表。

在这里使用 frozenset，您可以通过从生成的可迭代对象中构建 set 来删除重复项。然而，我们将不得不重新排列生成的路径，因为集合没有顺序。为此，我们可以使用列表理解，从那些 frozensets 构建列表并强制 source 和 target 节点分别位于开头和结尾：所以对于共享示例：

gg = nx.complete_graph(6)

source = 0
target = 3
paths = nx.all_simple_paths(gg, source=source, target=target, cutoff=5)

s = set(map(frozenset, paths))
# {frozenset({0, 3, 4}), frozenset({0, 2, 3})...
non_redundant_paths = [[source, *[*p-{source,target}],target] for p in s]

另一种方法可能更可取，因为您只需迭代一次，即迭代路径生成器，并使用 set:

跟踪看到的路径

non_redundant_paths = []
seen = []
for p in paths:
    if set(p) not in seen:
        non_redundant_paths.append(p)
        seen.append({*p})

print(non_redundant_paths)
[[0, 4, 3], [0, 2, 3], [0, 1, 2, 4, 3], [0, 1, 5, 3], [0, 2, 4, 3], 
 [0, 3], [0, 1, 4, 3], [0, 1, 2, 4, 5, 3], [0, 2, 4, 5, 3], [0, 2, 5, 3], 
 [0, 4, 5, 3], [0, 1, 2, 3], [0, 1, 4, 5, 3], [0, 5, 3], [0, 1, 2, 5, 3], [0, 1, 3]]

找到简单路径的所有唯一组合

Find all unique combinations of simple paths

python

graph-theory

networkx