用于使用 igraph C 库
igraph_error_t igraph_find_cycle(const igraph_t *graph,
igraph_vector_int_t *vertices,
igraph_vector_int_t *edges,
igraph_neimode_t mode);
此函数是实验性的，其签名尚未被视为最终签名。我们保留更改函数签名的权利，而无需更改 igraph 的主要版本。使用它需要您自担风险。
如果图中存在环，则此函数返回图的一个环。如果图是无环的，则返回空向量。
参数：
|
输入图。 |
|
指向整数向量的指针。如果找到环，其顶点将存储在此处。否则，该向量将为空。 |
|
指向整数向量的指针。如果找到环，其边将存储在此处。否则，该向量将为空。 |
|
一个常量，用于指定在有向图中如何考虑边的方向。有效的模式为： |
返回值：
错误代码。 |
时间复杂度：O(|V|+|E|)，其中 |V| 和 |E| 是原始输入图中顶点和边的数量。
另请参阅：
|
igraph_error_t igraph_simple_cycles(
const igraph_t *graph,
igraph_vector_int_list_t *vertices,
igraph_vector_int_list_t *edges,
igraph_neimode_t mode,
igraph_integer_t min_cycle_length,
igraph_integer_t max_cycle_length);
此函数是实验性的，其签名尚未被视为最终签名。我们保留更改函数签名的权利，而无需更改 igraph 的主要版本。使用它需要您自担风险。
此函数使用 Johnson 的环检测算法搜索所有简单环，并将它们存储在提供的向量列表中。简单环是没有重复顶点的环（即闭合路径）。
参考
Johnson DB: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4(1):77-84. https://doi.org/10.1137/0204007
参数：
|
要搜索环的图。 |
|
每个环的顶点 ID 将存储在此处。 |
|
每个环的边 ID 将存储在此处。 |
|
一个常量，用于指定在有向图中如何考虑边的方向。有效的模式为： |
|
限制要搜索的环的最小长度。传递一个负值以搜索所有环。 |
|
限制要搜索的环的最大长度。传递一个负值以搜索所有环。 |
另请参阅：
|
返回值：
错误代码。 |
igraph_error_t igraph_simple_cycles_callback(
const igraph_t *graph,
igraph_neimode_t mode,
igraph_integer_t min_cycle_length,
igraph_integer_t max_cycle_length,
igraph_cycle_handler_t *callback,
void *arg);
此函数是实验性的，其签名尚未被视为最终签名。我们保留更改函数签名的权利，而无需更改 igraph 的主要版本。使用它需要您自担风险。
此函数使用 Johnson 的环检测算法搜索所有简单环，并为每个环调用一个函数。简单环是没有重复顶点的环（即闭合路径）。
参考
Johnson DB: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4(1):77-84. https://doi.org/10.1137/0204007 See also: igraph_simple_cycles_callback()
参数：
|
要搜索的图 |
|
一个常量，用于指定在有向图中如何考虑边的方向。有效的模式为： |
|
限制要搜索的环的最小长度。传递一个负值以搜索所有环。 |
|
限制要搜索的环的最大长度。传递一个负值以搜索所有环。 |
|
为找到的每个环调用的函数。另请参见 |
|
此参数将传递给 |
另请参阅：
|
返回值：
错误代码。 |
typedef igraph_error_t igraph_cycle_handler_t(
const igraph_vector_int_t *vertices,
const igraph_vector_int_t *edges,
void *arg);
回调类型，在找到环时由 igraph_simple_cycles_callback() 调用。
参数：
|
当前环的顶点。不得修改。 |
|
当前环的边。不得修改。 |
|
传递给 |
返回值：
错误代码； |
igraph_error_t igraph_is_acyclic(const igraph_t *graph, igraph_bool_t *res);
此函数检查图是否具有任何环。考虑边的方向，即在有向图中，仅搜索有向环。
参数：
|
输入图。 |
|
指向布尔常量的指针，结果存储在此处。 |
返回值：
错误代码。 |
另请参阅：
|
时间复杂度：O(|V|+|E|)，其中 |V| 和 |E| 是原始输入图中顶点和边的数量。
这些函数计算是否存在欧拉路径或环，如果存在，则可以找到它们。
igraph_error_t igraph_is_eulerian(const igraph_t *graph, igraph_bool_t *has_path, igraph_bool_t *has_cycle);
欧拉路径精确地遍历图的每条边一次。闭合欧拉路径称为欧拉环。
参数：
|
图对象。 |
|
指向布尔值的指针，如果存在欧拉路径，则设置为 true。不得为 |
|
指向布尔值的指针，如果存在欧拉环，则设置为 true。不得为 |
返回值：
错误代码： |
时间复杂度：O(|V|+|E|)，顶点数加上边数。
igraph_error_t igraph_eulerian_cycle(
const igraph_t *graph, igraph_vector_int_t *edge_res, igraph_vector_int_t *vertex_res);
查找欧拉环（如果存在）。欧拉环是一条闭合路径，精确地遍历每条边一次。
如果图没有边，则返回零长度环。
此函数使用 Hierholzer 算法。
参数：
|
图对象。 |
|
指向初始化的向量的指针。属于环的边的索引将存储在此处。如果调用者不需要，可以为 |
|
指向初始化的向量的指针。属于环的顶点的索引将存储在此处。向量中的第一个和最后一个顶点将相同。如果调用者不需要，可以为 |
返回值：
|
错误代码
|
时间复杂度：O(|V|+|E|)，顶点数加上边数。
igraph_error_t igraph_eulerian_path(
const igraph_t *graph, igraph_vector_int_t *edge_res, igraph_vector_int_t *vertex_res);
查找欧拉路径（如果存在）。欧拉路径精确地遍历每条边一次。
如果图没有边，则返回零长度路径。
此函数使用 Hierholzer 算法。
参数：
|
图对象。 |
|
指向初始化的向量的指针。属于路径的边的索引将存储在此处。如果调用者不需要，可以为 |
|
指向初始化的向量的指针。属于路径的顶点的索引将存储在此处。如果调用者不需要，可以为 |
返回值：
|
错误代码
|
时间复杂度：O(|V|+|E|)，顶点数加上边数。
igraph_error_t igraph_fundamental_cycles(const igraph_t *graph,
igraph_vector_int_list_t *result,
igraph_integer_t start_vid,
igraph_integer_t bfs_cutoff,
const igraph_vector_t *weights);
此函数是实验性的，其签名尚未被视为最终签名。我们保留更改函数签名的权利，而无需更改 igraph 的主要版本。使用它需要您自担风险。
此函数计算与图的广度优先搜索树关联的基本环基。
忽略边的方向。支持多重边和自环。
参数：
|
图对象。 |
|
一个初始化的整数向量列表。结果将存储在此处，每个向量包含一个基元素的边 ID。 |
|
如果为负数，则返回一个完整的基本环基。如果为顶点 ID，则返回与以该顶点为根的 BFS 树关联的基本环，仅用于包含该顶点的弱连通分量。 |
|
如果为负数，则返回一个完整的环基。否则，仅包括长度小于等于 |
|
当前未使用。 |
返回值：
错误代码。 |
另请参阅：
时间复杂度：O(|V| + |E|)。
igraph_error_t igraph_minimum_cycle_basis(const igraph_t *graph,
igraph_vector_int_list_t *result,
igraph_integer_t bfs_cutoff,
igraph_bool_t complete,
igraph_bool_t use_cycle_order,
const igraph_vector_t *weights);
此函数是实验性的，其签名尚未被视为最终签名。我们保留更改函数签名的权利，而无需更改 igraph 的主要版本。使用它需要您自担风险。
此函数计算图的最小权重环基。当前，使用了 Horton 算法的修改版本，该版本允许截止。
忽略边的方向。支持多重边和自环。
参考
Horton, J. D. (1987) A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM Journal on Computing, 16 (2): 358–366. https://doi.org/10.1137%2F0216026
参数：
|
图对象。 |
|
一个初始化的整数向量列表，环基的元素将作为边 ID 的向量存储在此处。 |
|
如果为负数，则返回一个精确的最小环基。否则，只有结果中的那些环才是某个最小环基的一部分，其大小小于等于 |
|
布尔值。仅当给出了 |
|
如果为 true，则每个环都以自然顺序返回：边 ID 将沿环按顺序出现。这会带来很小的性能成本。如果为 false，则不保证周期内边 ID 的排序。此参数的存在仅仅是为了控制性能权衡。 |
|
当前未使用。 |
返回值：
错误代码。 |
另请参阅：
时间复杂度：待定。
| ← 第 13 章 图的结构属性 | 第 15 章 图访问者 → |