igraph Reference Manual

For using the igraph C library

Search the manual:
Previous Home Next

Chapter 14. Graph cycles

1. Eulerian cycles and paths
2. Cycle bases

1. Eulerian cycles and paths

1.1. igraph_is_eulerian — Checks whether an Eulerian path or cycle exists.
1.2. igraph_eulerian_cycle — Finds an Eulerian cycle.
1.3. igraph_eulerian_path — Finds an Eulerian path.

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

1.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.

1.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. 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.

1.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.

2. Cycle bases

2.1. igraph_fundamental_cycles — Finds a fundamental cycle basis.
2.2. igraph_minimum_cycle_basis — Computes a minimum weight cycle basis.

2.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|).

2.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 →