igraph Reference Manual

For using the igraph C library

Search the manual:
Previous Home Next

Chapter 14. Graph cycles

1. Finding cycles
2. Eulerian cycles and paths
3. Cycle bases

1. Finding cycles

1.1. igraph_find_cycle — Finds a single cycle in the graph.
1.2. igraph_simple_cycles — Finds all simple cycles.
1.3. igraph_simple_cycles_callback — Finds all simple cycles (callback version).
1.4. igraph_cycle_handler_t — Type of cycle handler functions.

1.1. igraph_find_cycle — Finds a single cycle in the graph.

igraph_error_t igraph_find_cycle(const igraph_t *graph,
                                 igraph_vector_int_t *vertices,
                                 igraph_vector_int_t *edges,
                                 igraph_neimode_t mode);

Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

This function returns a cycle of the graph, if there is one. If the graph is acyclic, it returns empty vectors.

Arguments: 

graph:

The input graph.

vertices:

Pointer to an integer vector. If a cycle is found, its vertices will be stored here. Otherwise the vector will be empty.

edges:

Pointer to an integer vector. If a cycle is found, its edges will be stored here. Otherwise the vector will be empty.

mode:

A constant specifying how edge directions are considered in directed graphs. Valid modes are: IGRAPH_OUT, follows edge directions; IGRAPH_IN, follows the opposite directions; and IGRAPH_ALL, ignores edge directions. This argument is ignored for undirected graphs.

Returns: 

Error code.

Time complexity: O(|V|+|E|), where |V| and |E| are the number of vertices and edges in the original input graph.

See also: 

igraph_is_acyclic() to determine if a graph is acyclic, without returning a specific cycle.

1.2. igraph_simple_cycles — Finds all simple cycles.

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);

Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

This function searches for all simple cycles using Johnson's cycle detection algorithm, and stores them in the provided vector lists. A simple cycle is a cycle (i.e. closed path) without repeated vertices.

Reference:

Johnson DB: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4(1):77-84. https://doi.org/10.1137/0204007

Arguments: 

graph:

The graph to search for cycles in.

vertices:

The vertex IDs of each cycle will be stored here.

edges:

The edge IDs of each cycle will be stored here.

mode:

A constant specifying how edge directions are considered in directed graphs. Valid modes are: IGRAPH_OUT, follows edge directions; IGRAPH_IN, follows the opposite directions; and IGRAPH_ALL, ignores edge directions. This argument is ignored for undirected graphs.

max_cycle_length:

Limit the minimum length of cycles to search for. Pass a negative value to search for all cycles.

max_cycle_length:

Limit the maximum length of cycles to search for. Pass a negative value to search for all cycles.

See also: 

igraph_simple_cycles() to call a function for each found cycle; igraph_find_cycle() to find a single cycle; igraph_fundamental_cycles() and igraph_minimum_cycle_basis() to find a cycle basis, a compact representation of the cycle structure of the graph.

Returns: 

Error code.

1.3. igraph_simple_cycles_callback — Finds all simple cycles (callback version).

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);

Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

This function searches for all simple cycles using Johnson's cycle detection algorithm, and calls a function for each. A simple cycle is a cycle (i.e. closed path) without repeated vertices.

Reference:

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()

Arguments: 

graph:

The graph to search for

mode:

A constant specifying how edge directions are considered in directed graphs. Valid modes are: IGRAPH_OUT, follows edge directions; IGRAPH_IN, follows the opposite directions; and IGRAPH_ALL, ignores edge directions. This argument is ignored for undirected graphs.

max_cycle_length:

Limit the minimum length of cycles to search for. Pass a negative value to search for all cycles.

max_cycle_length:

Limit the maximum length of cycles to search for. Pass a negative value to search for all cycles.

callback:

A function to call for each cycle that is found. See also igraph_cycle_handler_t

arg:

This parameter will be passed to callback.

See also: 

igraph_simple_cycles() to store the found cycles; igraph_find_cycle() to find a single cycle; igraph_fundamental_cycles() and igraph_minimum_cycle_basis() to find a cycle basis, a compact representation of the cycle structure of the graph.

Returns: 

Error code.

1.4. igraph_cycle_handler_t — Type of cycle handler functions.

typedef igraph_error_t igraph_cycle_handler_t(
        const igraph_vector_int_t *vertices,
        const igraph_vector_int_t *edges,
        void *arg);

Callback type, called by igraph_simple_cycles_callback() when a cycle is found.

Arguments: 

vertices:

The vertices of the current cycle. Must not be modified.

edges:

The edges of the current cycle. Must not be modified.

arg:

The extra parameter passed to igraph_simple_cycles_callback()

Returns: 

Error code; IGRAPH_SUCCESS to continue the search or IGRAPH_STOP to stop the search without signaling an error.

2. Eulerian cycles and paths

2.1. igraph_is_eulerian — Checks whether an Eulerian path or cycle exists.
2.2. igraph_eulerian_cycle — Finds an Eulerian cycle.
2.3. igraph_eulerian_path — Finds an Eulerian path.

These functions calculate whether an Eulerian path or cycle exists and if so, can find them.

2.1. igraph_is_eulerian — Checks whether an Eulerian path or cycle exists.

igraph_error_t igraph_is_eulerian(const igraph_t *graph, igraph_bool_t *has_path, igraph_bool_t *has_cycle);

An Eulerian path traverses each edge of the graph precisely once. A closed Eulerian path is referred to as an Eulerian cycle.

Arguments: 

graph:

The graph object.

has_path:

Pointer to a Boolean, will be set to true if an Eulerian path exists. Must not be NULL.

has_cycle:

Pointer to a Boolean, will be set to true if an Eulerian cycle exists. Must not be NULL.

Returns: 

Error code: IGRAPH_ENOMEM, not enough memory for temporary data.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

2.2. igraph_eulerian_cycle — Finds an Eulerian cycle.

igraph_error_t igraph_eulerian_cycle(
        const igraph_t *graph, igraph_vector_int_t *edge_res, igraph_vector_int_t *vertex_res);

Finds an Eulerian cycle, if it exists. An Eulerian cycle is a closed path that traverses each edge precisely once.

If the graph has no edges, a zero-length cycle is returned.

This function uses Hierholzer's algorithm.

Arguments: 

graph:

The graph object.

edge_res:

Pointer to an initialised vector. The indices of edges belonging to the cycle will be stored here. May be NULL if it is not needed by the caller.

vertex_res:

Pointer to an initialised vector. The indices of vertices belonging to the cycle will be stored here. The first and last vertex in the vector will be the same. May be NULL if it is not needed by the caller.

Returns: 

Error code:

IGRAPH_ENOMEM

not enough memory for temporary data.

IGRAPH_ENOSOL

graph does not have an Eulerian cycle.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

2.3. igraph_eulerian_path — Finds an Eulerian path.

igraph_error_t igraph_eulerian_path(
        const igraph_t *graph, igraph_vector_int_t *edge_res, igraph_vector_int_t *vertex_res);

Finds an Eulerian path, if it exists. An Eulerian path traverses each edge precisely once.

If the graph has no edges, a zero-length path is returned.

This function uses Hierholzer's algorithm.

Arguments: 

graph:

The graph object.

edge_res:

Pointer to an initialised vector. The indices of edges belonging to the path will be stored here. May be NULL if it is not needed by the caller.

vertex_res:

Pointer to an initialised vector. The indices of vertices belonging to the path will be stored here. May be NULL if it is not needed by the caller.

Returns: 

Error code:

IGRAPH_ENOMEM

not enough memory for temporary data.

IGRAPH_ENOSOL

graph does not have an Eulerian path.

Time complexity: O(|V|+|E|), the number of vertices plus the number of edges.

3. Cycle bases

3.1. igraph_fundamental_cycles — Finds a fundamental cycle basis.
3.2. igraph_minimum_cycle_basis — Computes a minimum weight cycle basis.

3.1. igraph_fundamental_cycles — Finds a fundamental cycle basis.

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);

Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

This function computes a fundamental cycle basis associated with a breadth-first search tree of the graph.

Edge directions are ignored. Multi-edges and self-loops are supported.

Arguments: 

graph:

The graph object.

result:

An initialized integer vector list. The result will be stored here, each vector containing the edge IDs of a basis element.

start_vid:

If negative, a complete fundamental cycle basis is returned. If a vertex ID, the fundamental cycles associated with the BFS tree rooted in that vertex will be returned, only for the weakly connected component containing that vertex.

bfs_cutoff:

If negative, a complete cycle basis is returned. Otherwise, only cycles of length 2*bfs_cutoff + 1 or shorter are included. bfs_cutoff is used to limit the depth of the BFS tree when searching for cycle edges.

weights:

Currently unused.

Returns: 

Error code.

Time complexity: O(|V| + |E|).

3.2. igraph_minimum_cycle_basis — Computes a minimum weight cycle basis.

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);

Warning

This function is experimental and its signature is not considered final yet. We reserve the right to change the function signature without changing the major version of igraph. Use it at your own risk.

This function computes a minimum weight cycle basis of a graph. Currently, a modified version of Horton's algorithm is used that allows for cutoffs.

Edge directions are ignored. Multi-edges and self-loops are supported.

References:

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

Arguments: 

graph:

The graph object.

result:

An initialized integer vector list, the elements of the cycle basis will be stored here as vectors of edge IDs.

bfs_cutoff:

If negative, an exact minimum cycle basis is returned. Otherwise only those cycles in the result will be part of some minimum cycle basis which are of size 2*bfs_cutoff + 1 or smaller. Cycles longer than this limit may not be of the smallest possible size. bfs_cutoff is used to limit the depth of the BFS tree when computing candidate cycles. Specifying a bfs_cutoff can speed up the computation substantially.

complete:

Boolean value. Used only when bfs_cutoff was given. If true, a complete basis is returned. If false, only cycles not greater than 2*bfs_cutoff + 1 are returned. This may save computation time, however, the result will not span the entire cycle space.

use_cycle_order:

If true, each cycle is returned in natural order: the edge IDs will appear ordered along the cycle. This comes at a small performance cost. If false, no guarantees are given about the ordering of edge IDs within cycles. This parameter exists solely to control performance tradeoffs.

weights:

Currently unused.

Returns: 

Error code.

Time complexity: TODO.

← Chapter 13. Structural properties of graphs Chapter 15. Graph visitors →