simple_cycles#

simple_cycles(G, length_bound=None)[源码]#

寻找图中的简单环（基本回路）。

“简单环”或“基本回路”是一条闭合路径，其中没有节点出现两次。在有向图中，如果两个简单环不是彼此的循环排列，则它们是不同的。在无向图中，如果两个简单环不是彼此的循环排列或彼此的反向循环排列，则它们是不同的。

可以选择限制环的长度。在无界情况下，我们使用 Johnson 算法 [1] 的非递归、迭代器/生成器版本。在有界情况下，我们使用 Gupta 和 Suzumura 算法 [2] 的一个版本。在某些情况下，可能存在更好的算法 [3] [4] [5]。

Johnson 以及 Gupta 和 Suzumura 的算法通过一些众所周知的预处理技术得到了增强。当 G 是有向图时，我们将注意力限制在 G 的强连通分量上，生成包含特定节点的所有简单环，移除该节点，然后将剩余部分进一步分解为强连通分量。当 G 是无向图时，我们将注意力限制在双连通分量上，生成包含特定边的所有简单环，移除该边，然后将剩余部分进一步分解为双连通分量。

请注意，此函数支持多重图——在无向多重图中，一对平行边被视为长度为 2 的环。同样，自环被视为长度为 1 的环。我们将环定义为节点的序列；因此，循环和平行边的存在不会改变图中简单环的数量。

参数:

GNetworkX 图: 一个 networkx 图。支持无向图、有向图和多重图。
length_boundint 或 None，可选 (默认=None): 如果 length_bound 是一个 int，则生成 G 中长度至多为 length_bound 的所有简单环。否则，生成 G 中所有简单环。

产出:

节点列表: 每个环由沿环的节点列表表示。

引发:

ValueError: 当 length_bound < 0 时。

另请参阅

cycle_basis
chordless_cycles

注释

当 length_bound 为 None 时，对于 \(n\) 个节点、\(e\) 条边和 \(c\) 个简单回路，时间复杂度为 \(O((n+e)(c+1))\)。否则，当 length_bound > 1 时，时间复杂度为 \(O((c+n)(k-1)d^k)\)，其中 \(d\) 是 G 中节点的平均度，\(k\) = length_bound。

参考文献

[1]

Finding all the elementary circuits of a directed graph. D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975. https://doi.org/10.1137/0204007

[2]

Finding All Bounded-Length Simple Cycles in a Directed Graph A. Gupta and T. Suzumura https://arxiv.org/abs/2105.10094

[3]

Enumerating the cycles of a digraph: a new preprocessing strategy. G. Loizou and P. Thanish, Information Sciences, v. 27, 163-182, 1982.

[4]

A search strategy for the elementary cycles of a directed graph. J.L. Szwarcfiter and P.E. Lauer, BIT NUMERICAL MATHEMATICS, v. 16, no. 2, 192-204, 1976.

[5]

Optimal Listing of Cycles and st-Paths in Undirected Graphs R. Ferreira and R. Grossi and A. Marino and N. Pisanti and R. Rizzi and G. Sacomoto https://arxiv.org/abs/1205.2766

示例

>>> G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)])
>>> sorted(nx.simple_cycles(G))
[[0], [0, 1, 2], [0, 2], [1, 2], [2]]

要过滤环，使其不包含某些节点或边，请复制您的图并在调用此函数之前删除这些节点或边。例如，要从上面的示例中排除自环

>>> H = G.copy()
>>> H.remove_edges_from(nx.selfloop_edges(G))
>>> sorted(nx.simple_cycles(H))
[[0, 1, 2], [0, 2], [1, 2]]