find_cycle#

find_cycle(G, source=None, orientation=None)[source]#

返回通过深度优先遍历找到的循环。

循环是由表示循环路径的边列表组成。 有向边的方向由 orientation 控制。

Parameters:
G图

一个有向/无向图/多重图。

source节点, 节点列表

遍历开始的节点。如果为 None，则任意选择一个源节点，并重复直到图中每个节点的所有边都被搜索。

orientationNone | ‘original’ | ‘reverse’ | ‘ignore’ (默认: None)

对于有向图和有向多重图，边的遍历不需要遵循边的原始方向。 当设置为 ‘reverse’ 时，每条边都以反方向遍历。 当设置为 ‘ignore’ 时，每条边都被视为无向。 当设置为 ‘original’ 时，每条边都被视为有向。 在这三种情况下，生成的边元组会添加一个最后一个条目，以指示该边被遍历的方向。 如果 orientation 为 None，则生成的边不指示方向。 方向被尊重，但不报告。

Returns:
edges有向边

一个有向边列表，指示循环的路径。 如果没有找到循环，则抛出异常。 对于图，边为 (u, v) 形式，其中 u 和 v 是根据遍历确定的边的尾部和头部。 对于多重图，边为 (u, v, key) 形式，其中 key 是边的键。当图是有向的时， u 和 v 总是实际有向边的顺序。 如果 orientation 不是 None，则边元组会扩展以包括该边上的遍历方向（’forward’ 或 ‘reverse’）。

Raises:
NetworkXNoCycle

如果没有找到循环。

See also

simple_cycles

Examples

在这个例子中，我们构建了一个有向无环图（DAG），并在第一次调用中，发现没有有向循环，因此抛出异常。在第二次调用中，我们忽略边的方向，发现有一个无向循环。 注意，第二次调用发现了一个有向循环，而实际上遍历了一个无向图，因此，我们发现了一个“无向循环”。 这意味着这个DAG结构没有形成一个有向树（也称为多树）。

>>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2)])
>>> nx.find_cycle(G, orientation="original")
Traceback (most recent call last):
    ...
networkx.exception.NetworkXNoCycle: No cycle found.
>>> list(nx.find_cycle(G, orientation="ignore"))
[(0, 1, 'forward'), (1, 2, 'forward'), (0, 2, 'reverse')]
On this page