all_simple_paths

all_simple_paths(G, source, target, cutoff=None)

生成图 G 中从源节点到目标节点的所有简单路径。

简单路径是指没有重复节点的路径。

Parameters:

GNetworkX 图

source节点

路径的起始节点

target节点

单个节点或可迭代的节点，路径在此结束

cutoff整数, 可选

停止搜索的深度。仅返回长度 <= cutoff 的路径。

Returns:

path_generator: 生成器

生成简单路径列表的生成器。如果在给定的 cutoff 内源节点和目标节点之间没有路径，生成器不会产生输出。如果可以通过多条平行边以多种方式遍历相同的节点序列，则该节点序列将多次返回（每种可行的边组合一次）。

See also

all_shortest_paths, shortest_path, has_path

Notes

此算法使用修改后的深度优先搜索来生成路径 [1]。单条路径可以在 \(O(V+E)\) 时间内找到，但图中的简单路径数量可能非常大，例如在完全图 \(n\) 中为 \(O(n!)\)。

此函数不检查 source 和 target 之间是否存在路径。对于大型图，这可能导致非常长的运行时间。考虑在大型图上调用此函数之前使用 has_path 检查 source 和 target 之间是否存在路径。

References

[1]

R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison Wesley Professional, 3rd ed., 2001.

Examples

此迭代器生成节点列表:

>>> G = nx.complete_graph(4)
>>> for path in nx.all_simple_paths(G, source=0, target=3):
...     print(path)
...
[0, 1, 2, 3]
[0, 1, 3]
[0, 2, 1, 3]
[0, 2, 3]
[0, 3]

可以通过使用 cutoff 关键字参数生成仅短于特定长度的路径:

>>> paths = nx.all_simple_paths(G, source=0, target=3, cutoff=2)
>>> print(list(paths))
[[0, 1, 3], [0, 2, 3], [0, 3]]

要获取每条路径对应的边列表，可以使用 networkx.utils.pairwise() 辅助函数:

>>> paths = nx.all_simple_paths(G, source=0, target=3)
>>> for path in map(nx.utils.pairwise, paths):
...     print(list(path))
[(0, 1), (1, 2), (2, 3)]
[(0, 1), (1, 3)]
[(0, 2), (2, 1), (1, 3)]
[(0, 2), (2, 3)]
[(0, 3)]

将可迭代的节点作为目标，生成以多个节点中任意一个结束的所有路径:

>>> G = nx.complete_graph(4)
>>> for path in nx.all_simple_paths(G, source=0, target=[3, 2]):
...     print(path)
...
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 3]
[0, 1, 3, 2]
[0, 2]
[0, 2, 1, 3]
[0, 2, 3]
[0, 3]
[0, 3, 1, 2]
[0, 3, 2]

从 source 到自身的单一路径也被视为简单路径，并包含在结果中:

>>> G = nx.empty_graph(5)
>>> list(nx.all_simple_paths(G, source=0, target=0))
[[0]]

>>> G = nx.path_graph(3)
>>> list(nx.all_simple_paths(G, source=0, target={0, 1, 2}))
[[0], [0, 1], [0, 1, 2]]

使用函数式编程方法迭代有向无环图中从根节点到叶节点的每条路径:

>>> from itertools import chain
>>> from itertools import product
>>> from itertools import starmap
>>> from functools import partial
>>>
>>> chaini = chain.from_iterable
>>>
>>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
>>> roots = (v for v, d in G.in_degree() if d == 0)
>>> leaves = (v for v, d in G.out_degree() if d == 0)
>>> all_paths = partial(nx.all_simple_paths, G)
>>> list(chaini(starmap(all_paths, product(roots, leaves))))
[[0, 1, 2], [0, 3, 2]]

使用迭代方法计算相同列表:

>>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
>>> roots = (v for v, d in G.in_degree() if d == 0)
>>> leaves = (v for v, d in G.out_degree() if d == 0)
>>> all_paths = []
>>> for root in roots:
...     for leaf in leaves:
...         paths = nx.all_simple_paths(G, root, leaf)
...         all_paths.extend(paths)
>>> all_paths
[[0, 1, 2], [0, 3, 2]]

在有向无环图中迭代从根节点到叶节点的每条路径，将所有叶节点一起传递以避免不必要的计算:

>>> G = nx.DiGraph([(0, 1), (2, 1), (1, 3), (1, 4)])
>>> roots = (v for v, d in G.in_degree() if d == 0)
>>> leaves = [v for v, d in G.out_degree() if d == 0]
>>> all_paths = []
>>> for root in roots:
...     paths = nx.all_simple_paths(G, root, leaves)
...     all_paths.extend(paths)
>>> all_paths
[[0, 1, 3], [0, 1, 4], [2, 1, 3], [2, 1, 4]]

如果平行边提供了多种遍历给定节点序列的方式，则该节点序列将多次返回:

>>> G = nx.MultiDiGraph([(0, 1), (0, 1), (1, 2)])
>>> list(nx.all_simple_paths(G, 0, 2))
[[0, 1, 2], [0, 1, 2]]