chordless_cycles#

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

查找图中的简单无弦环。

一个 简单环 是一个闭合路径，其中没有节点出现两次。在简单环中， 弦 是环中两个节点之间的额外边。一个 无弦环 是一个没有弦的简单环。换句话说，一个无弦环是一个图G中的环C，其中诱导图G[C]中的边数等于环C的长度。

需要注意的是，在G不是简单图或简单有向图的情况下，必须小心处理。一些作者限制无弦环的定义，要求其具有规定的最小长度；我们没有这样做。

  1. 我们将自环解释为无弦环，除非在具有多个平行环的多图中。同样，在长度大于1的无弦环中，不能有带自环的节点。

  2. 我们将有向的双环解释为无弦环，除非在多有向图中，双环中的任何边都有平行副本。

  3. 我们将无向边的平行对解释为双环，除非在两个节点之间存在第三个（或更多）平行边。

  4. 推广上述情况，带有平行副本的边不能出现在无弦环中。

在有向图中，两个无弦环是不同的，如果它们不是彼此的循环排列。在无向图中，两个无弦环是不同的，如果它们不是彼此的循环排列，也不是彼此的反转。

可选地，环的长度是有限的。

我们使用一个深受Dias等人[1]算法启发的算法。它已经进行了以下修改：

  1. 避免了递归，因为Python的限制。

  2. 不需要标记函数，因为起始路径被选择（并从宿主图中删除）以防止相同路径的多次出现。

  3. 搜索可选地在指定长度处被限制。

  4. 通过沿前向边扩展环，并通过沿前向和反向边阻塞节点，提供了对有向图的支持。

  5. 通过从前向边集合中省略双边，提供了对多图的支持。

Parameters:
GNetworkX DiGraph

一个有向图

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

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

Yields:
节点列表

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

Raises:
ValueError

当length_bound < 0时。

See also

simple_cycles

Notes

当length_bound为None，且图是简单图时，时间复杂度为:math:O((n+e)(c+1))，其中:math:`n`是节点数，:math:`e`是边数，:math:`c`是无弦环数。

References

[1]

高效枚举无弦环 E. Dias 和 D. Castonguay 和 H. Longo 和 W.A.R. Jradi https://arxiv.org/abs/1309.1051

Examples

>>> sorted(list(nx.chordless_cycles(nx.complete_graph(4))))
[[1, 0, 2], [1, 0, 3], [2, 0, 3], [2, 1, 3]]
On this page