chordless_cycles#

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

查找图中的简单无弦环。

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

请注意，如果 G 不是简单图或简单有向图，则需要特别注意。有些作者将无弦环的定义限制为具有指定的最小长度；我们不作此限制。

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

  2. 我们将有向二环解释为无弦环，但在多重有向图中，如果二环中的任何边具有平行副本，则除外。

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

  4. 概括上述情况，具有平行副本的边可能不会出现在无弦环中。

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

可选地，可以限制环的长度。

我们使用一种算法，它深受 Dias 等人 [1] 算法的启发。该算法已作如下修改：

  1. 根据 Python 的限制，避免使用递归

  2. 不需要标记函数，因为起始路径

    被选择（并从主图中删除）以防止同一路径多次出现

  3. 搜索长度可选地限制在指定值

  4. 通过沿以下方向扩展环来支持有向图：

    前向边，并沿前向和后向边阻塞节点

  5. 通过从集合中省略二元组来支持多重图：

    前向边

参数:
GNetworkX DiGraph

一个有向图

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

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

生成值:
节点列表

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

抛出:
ValueError

当 length_bound < 0 时。

另请参阅

simple_cycles

说明

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

参考文献

[1]

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

示例

>>> sorted(list(nx.chordless_cycles(nx.complete_graph(4))))
[[1, 0, 2], [1, 0, 3], [2, 0, 3], [2, 1, 3]]
在此页面上