all_simple_paths#

all_simple_paths(G, source, target, cutoff=None)[源代码]#

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

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

参数
G网络X图表
source结点

路径的起始节点

target节点

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

cutoff整数,可选

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

返回
路径生成器:生成器

生成简单路径列表的生成器。如果在给定的截止范围内源和目标之间没有路径,则生成器不会生成任何输出。

参见

all_shortest_paths, shortest_path, has_path

笔记

该算法使用改进的深度优先搜索来生成路径 [1]. 只有一条路径可以在 \(O(V+E)\) 但图中简单路径的数量可能非常大,例如 \(O(n!)\) 在完整的有序图中 \(n\)

此函数不检查之间是否存在路径 sourcetarget 。对于大型图表,这可能会导致非常长的运行时间。考虑使用 has_path 检查之间是否存在路径的步骤 sourcetarget 在大图形上调用此函数之前。

工具书类

1

R.Sedgewick,“C中的算法,第5部分:图形算法”,Addison-Wesley Professional,第3版,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)]

传递一个iterable of nodes作为目标,以生成以任意多个节点结尾的所有路径::

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

使用函数编程方法在有向非循环图中迭代从根节点到叶节点的每个路径:

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