simple_cycles#

simple_cycles(G, length_bound=None)[source]#

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

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

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

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

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

Parameters:
GNetworkX 图

一个networkx图。无向图、有向图和多重图都支持。

length_boundint 或 None, 可选 (默认=None)

如果 length_bound 是int，生成 G 中长度最多为 length_bound 的所有简单环。否则，生成 G 中的所有简单环。

Yields:
节点列表

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

Raises:
ValueError

当` length_bound < 0`时。

See also

cycle_basis
chordless_cycles

Notes

当 length_bound 为None时，时间复杂度为:math:O((n+e)(c+1))，其中:math:n`是节点数，:math:`e`是边数，:math:`c`是简单环数。否则，当 `length_bound > 1 时，时间复杂度为:math:O((c+n)(k-1)d^k)，其中:math:d`是 `G 节点的平均度数，$k = length_bound `。

References

[1]

查找有向图的所有基本回路。 D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975. https://doi.org/10.1137/0204007

[2]

在有向图中查找所有有限长度的简单环 A. Gupta 和 T. Suzumura https://arxiv.org/abs/2105.10094

[3]

枚举有向图的回路：一种新的预处理策略。 G. Loizou 和 P. Thanish, Information Sciences, v. 27, 163-182, 1982.

[4]

有向图基本回路的搜索策略。 J.L. Szwarcfiter 和 P.E. Lauer, BIT NUMERICAL MATHEMATICS, v. 16, no. 2, 192-204, 1976.

[5]

无向图中循环和st路径的最优枚举 R. Ferreira 和 R. Grossi 和 A. Marino 和 N. Pisanti 和 R. Rizzi 和 G. Sacomoto https://arxiv.org/abs/1205.2766

Examples

>>> 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]]
On this page