igraph Reference Manual

For using the igraph C library

Search the manual:

Chapter 14. Graph cycles

1. Eulerian cycles and paths

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.

has_cycle:

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

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.

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_EINVVID

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.

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_EINVVID

graph does not have an Eulerian path.

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