simple_cycles

simple_cycles(G)

求有向图的简单环（基本电路）。

A simple cycle 或 elementary circuit ，是一个封闭路径，其中没有节点出现两次。如果两个基本电路彼此不是循环排列，则它们是不同的。

这是Johnson算法的非递归、迭代器/生成器版本 [1]. 对于某些情况，可能会有更好的算法 [2] [3] 。

参数

G网络X有向图

有向图

返回

周期生成器：生成器

生成图的基本圈的生成器。每个周期由沿周期的节点列表表示。

参见

cycle_basis

笔记

该实施遵循第79-80页 [1].

时间复杂性是 \(O((n+e)(c+1))\) 为 \(n\) 节点， \(e\) 边和 \(c\) 初级电路。

工具书类

1(1,2)

求有向图的所有基本电路。D.B.Johnson，《暹罗计算杂志》，第4期，第1期，第77-84页，1975年。网址：https://doi.org/10.1137/0204007

2

枚举有向图的循环：一种新的预处理策略。G.Loizou和P.Thanish，信息科学，v.27，163-1821982。

3

有向图初等环的搜索策略。J.L.Szwarcfiter和P.E.Lauer，《位数字数学》，第16卷，第2期，192-204页，1976年。

实例

>>> edges = [(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]
>>> G = nx.DiGraph(edges)
>>> len(list(nx.simple_cycles(G)))
5

要过滤循环以使它们不包含某些节点或边，请复制图形并在调用之前消除这些节点或边

>>> copyG = G.copy()
>>> copyG.remove_nodes_from([1])
>>> copyG.remove_edges_from([(0, 1)])
>>> len(list(nx.simple_cycles(copyG)))
3