all_simple_edge_paths

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

生成从源节点到目标节点的所有简单路径的边列表。

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

Parameters:

GNetworkX 图

source节点

路径的起始节点

target节点

单个节点或可迭代的节点，作为路径的终点

cutoff整数, 可选

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

Returns:

path_generator: 生成器

生成简单路径列表的生成器。如果在给定的 cutoff 内源节点和目标节点之间没有路径，生成器不产生输出。 对于多图，边列表中的元素形式为 (u,v,k) ，其中 k 对应于边键。

See also

all_shortest_paths, shortest_path, all_simple_paths

Notes

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

References

[1]

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

Examples

打印图的简单路径边:

>>> g = nx.Graph([(1, 2), (2, 4), (1, 3), (3, 4)])
>>> for path in sorted(nx.all_simple_edge_paths(g, 1, 4)):
...     print(path)
[(1, 2), (2, 4)]
[(1, 3), (3, 4)]

打印多图的简单路径边。返回的边带有其关联的键:

>>> mg = nx.MultiGraph()
>>> mg.add_edge(1, 2, key="k0")
'k0'
>>> mg.add_edge(1, 2, key="k1")
'k1'
>>> mg.add_edge(2, 3, key="k0")
'k0'
>>> for path in sorted(nx.all_simple_edge_paths(mg, 1, 3)):
...     print(path)
[(1, 2, 'k0'), (2, 3, 'k0')]
[(1, 2, 'k1'), (2, 3, 'k0')]

当 source 是目标之一时，不经过任何边的从 source 开始并结束的空路径被视为有效的简单边路径，并包含在结果中:

>>> G = nx.Graph()
>>> G.add_node(0)
>>> paths = list(nx.all_simple_edge_paths(G, 0, 0))
>>> for path in paths:
...     print(path)
[]
>>> len(paths)
1