all_simple_paths

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

生成图 G 中从 source 到 target 的所有简单路径。

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

参数:

GNetworkX 图

source节点

路径的起始节点

target节点

路径的结束节点（单个节点或节点的可迭代对象）

cutoff整数，可选

停止搜索的深度。仅返回长度小于等于 cutoff 的路径。

返回:

path_generator: 生成器

一个生成器，产生简单路径的列表。如果在给定截止深度内 source 和 target 之间没有路径，生成器不会产生任何输出。如果可以通过多种方式遍历相同的节点序列，即通过平行边，那么它将被多次返回（每种可行的边组合一次）。

另请参阅

all_shortest_paths, shortest_path, has_path

注意

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

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

参考文献

[1]

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

示例

此迭代器生成节点列表

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

将节点的迭代对象作为 target 传递，以生成所有以多个节点中任意一个为结束的路径

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