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.

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

int igraph_eulerian_cycle(const igraph_t *graph, igraph_vector_t *edge_res, igraph_vector_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.

int igraph_eulerian_path(const igraph_t *graph, igraph_vector_t *edge_res, igraph_vector_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.