igraph Reference Manual

For using the igraph C library

Chapter 18. Graph cycles

1. Finding cycles
2. Acyclic graphs and feedback sets
3. Eulerian cycles and paths
4. 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);

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; igraph_simple_cycles() to list all cycles in a graph.

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_int_t min_cycle_length, igraph_int_t max_cycle_length,
        igraph_int_t max_results);

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.
`min_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.
`max_results`:	At most this many cycles will be recorded. If negative, or `IGRAPH_UNLIMITED`, no limit is applied.

Returns:

Error code.

See also:

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

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_int_t min_cycle_length,
        igraph_int_t max_cycle_length,
        igraph_cycle_handler_t *callback,
        void *arg);

Warning

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

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.
`min_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`.

Returns:

Error code.

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.

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. Acyclic graphs and feedback sets

2.1. igraph_is_dag — Checks whether a graph is a directed acyclic graph (DAG).
2.2. igraph_is_acyclic — Checks whether a graph is acyclic or not.
2.3. igraph_topological_sorting — Calculate a possible topological sorting of the graph.
2.4. igraph_feedback_arc_set — Feedback arc set of a graph using exact or heuristic methods.
2.5. igraph_feedback_vertex_set — Feedback vertex set of a graph.

2.1. `igraph_is_dag` — Checks whether a graph is a directed acyclic graph (DAG).

igraph_error_t igraph_is_dag(const igraph_t* graph, igraph_bool_t *res);

A directed acyclic graph (DAG) is a directed graph with no cycles.

This function returns false for undirected graphs.

The return value of this function is cached in the graph itself; calling the function multiple times with no modifications to the graph in between will return a cached value in O(1) time.

Arguments:

`graph`:	The input graph.
`res`:	Pointer to a boolean constant, the result is stored here.

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_topological_sorting() to get a possible topological sorting of a DAG.

2.2. `igraph_is_acyclic` — Checks whether a graph is acyclic or not.

igraph_error_t igraph_is_acyclic(const igraph_t *graph, igraph_bool_t *res);

This function checks whether a graph has any cycles. Edge directions are considered, i.e. in directed graphs, only directed cycles are searched for.

The result of this function is cached in the graph itself; calling the function multiple times with no modifications to the graph in between will return a cached value in O(1) time.

Arguments:

`graph`:	The input graph.
`res`:	Pointer to a boolean constant, the result is stored here.

Returns:

Error code.

See also:

igraph_find_cycle() to find a cycle that demonstrates that the graph is not acyclic; igraph_is_forest() to look for undirected cycles even in directed graphs; igraph_is_dag() to test specifically for directed acyclic graphs.

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

2.3. `igraph_topological_sorting` — Calculate a possible topological sorting of the graph.

igraph_error_t igraph_topological_sorting(
        const igraph_t* graph, igraph_vector_int_t *res, igraph_neimode_t mode);

A topological sorting of a directed acyclic graph (DAG) is a linear ordering of its vertices where each vertex comes before all nodes to which it has edges. Every DAG has at least one topological sort, and may have many. This function returns one possible topological sort among them. If the graph contains any cycles that are not self-loops, an error is raised.

Arguments:

`graph`:	The input graph.
`res`:	Pointer to a vector, the result will be stored here. It will be resized if needed.
`mode`:	Specifies how to use the direction of the edges. For `IGRAPH_OUT`, the sorting order ensures that each vertex comes before all vertices to which it has edges, so vertices with no incoming edges go first. For `IGRAPH_IN`, it is quite the opposite: each vertex comes before all vertices from which it receives edges. Vertices with no outgoing edges go first.

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_dag() if you are only interested in whether a given graph is a DAG or not, or igraph_feedback_arc_set() to find a set of edges whose removal makes the graph acyclic.

Example 18.1. File examples/simple/igraph_topological_sorting.c

#include <igraph.h>
#include <stdio.h>

int main(void) {
    igraph_t graph;
    igraph_vector_int_t res;

    /* Initialize the library. */
    igraph_setup();

    /* Test graph taken from http://en.wikipedia.org/wiki/Topological_sorting
     * @ 05.03.2006 */
    igraph_small(&graph, 8, IGRAPH_DIRECTED,
                 0, 3, 0, 4, 1, 3, 2, 4, 2, 7, 3, 5, 3, 6, 3, 7, 4, 6,
                 -1);

    igraph_vector_int_init(&res, 0);

    /* Sort the vertices in "increasing" order. */
    igraph_topological_sorting(&graph, &res, IGRAPH_OUT);
    igraph_vector_int_print(&res);
    printf("\n");

    /* Sort the vertices in "decreasing" order. */
    igraph_topological_sorting(&graph, &res, IGRAPH_IN);
    igraph_vector_int_print(&res);

    /* Destroy data structures when done using them. */
    igraph_destroy(&graph);
    igraph_vector_int_destroy(&res);

    return 0;
}

2.4. `igraph_feedback_arc_set` — Feedback arc set of a graph using exact or heuristic methods.

igraph_error_t igraph_feedback_arc_set(
        const igraph_t *graph,
        igraph_vector_int_t *result,
        const igraph_vector_t *weights,
        igraph_fas_algorithm_t algo);

A feedback arc set is a set of edges whose removal makes the graph acyclic. We are usually interested in minimum feedback arc sets, i.e. sets of edges whose total weight is the smallest among all the feedback arc sets.

For undirected graphs, the solution is simple: one has to find a maximum weight spanning tree and then remove all the edges not in the spanning tree. For directed graphs, this is an NP-complete problem, and various heuristics are usually used to find an approximate solution to the problem. This function implements both exact methods and heuristics, selectable with the algo parameter.

References:

Eades P, Lin X and Smyth WF: A fast and effective heuristic for the feedback arc set problem. Information Processing Letters 47(6), pp 319-323 (1993). https://doi.org/10.1016/0020-0190(93)90079-O

Baharev A, Hermann S, Arnold N and Tobias A: An Exact Method for the Minimum Feedback Arc Set Problem. ACM Journal of Experimental Algorithmics 26, 1–28 (2021). https://doi.org/10.1145/3446429.

Arguments:

graph:

The graph object.

result:

An initialized vector, the result will be written here.

weights:

Weight vector or NULL if no weights are specified.

algo:

The algorithm to use to solve the problem if the graph is directed. Possible values:

`IGRAPH_FAS_EXACT_IP`	Finds a minimum feedback arc set using integer programming (IP), automatically selecting the best method of this type (currently always `IGRAPH_FAS_EXACT_IP_CG`). The complexity is of course at least exponential.
`IGRAPH_FAS_EXACT_IP_CG`	This is an integer programming approach based on a minimum set cover formulation and using incremental constraint generation (CG), added in igraph 0.10.14. We minimize `sum_e w_e b_e` subject to the constraints `sum_e c_e b_e >= 1` for all cycles `c`. Here `w_e` is the weight of edge `e`, `b_e` is a binary variable (0 or 1) indicating whether edge `e` is in the feedback set, and `c_e` is a binary coefficient indicating whether edge `e` is in cycle `c`. The constraint expresses the requirement that all cycles must intersect with (be broken by) the edge set represented by `b`. Since there are a very large number of cycles in the graph, constraints are generated incrementally, iteratively adding some cycles that do not intersect with the current edge set `b`, then solving for `b` again, until finally no unbroken cycles remain. This approach is similar to that described by Baharev et al (though with a simpler cycle generation scheme), and to what is implemented by SageMath's. `feedback_edge_set` function.
`IGRAPH_FAS_EXACT_IP_TI`	This is another integer programming approach based on finding a maximum (largest weight) edge set that adheres to a topological order. It uses the common formulation through triangle inequalities (TI), see Section 3.1 of Baharev et al (2021) for an overview. This method was used before igraph 0.10.14, and is typically much slower than `IGRAPH_FAS_EXACT_IP_CG`.
`IGRAPH_FAS_APPROX_EADES`	Finds a feedback arc set using the heuristic of Eades, Lin and Smyth (1993). This is guaranteed to be smaller than \|E\|/2 - \|V\|/6, and it is linear in the number of edges (i.e. O(\|E\|)) to compute.

Returns:

Error code: IGRAPH_EINVAL if an unknown method was specified or the weight vector is invalid.

Example 18.2. File examples/simple/igraph_feedback_arc_set.c

#include <igraph.h>
#include <string.h>

int main(void) {
    igraph_t g;
    igraph_vector_t weights;
    igraph_vector_int_t result;
    igraph_bool_t dag;

    /* Initialize the library. */
    igraph_setup();

    igraph_vector_int_init(&result, 0);

    /***********************************************************************/
    /* Approximation with Eades' method                                    */
    /***********************************************************************/

    /* Simple unweighted graph */
    igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, -1);
    igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_APPROX_EADES);
    igraph_vector_int_print(&result);
    igraph_delete_edges(&g, igraph_ess_vector(&result));
    igraph_is_dag(&g, &dag);
    if (!dag) {
        return 1;
    }
    igraph_destroy(&g);

    /* Simple weighted graph */
    igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, -1);
    igraph_vector_init_int_end(&weights, -1, 1, 1, 3, 1, 1, 1, 1, 1, 1, -1);
    igraph_feedback_arc_set(&g, &result, &weights, IGRAPH_FAS_APPROX_EADES);
    igraph_vector_int_print(&result);
    igraph_delete_edges(&g, igraph_ess_vector(&result));
    igraph_is_dag(&g, &dag);
    if (!dag) {
        return 2;
    }
    igraph_vector_destroy(&weights);
    igraph_destroy(&g);

    /* Simple unweighted graph with loops */
    igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, 1, 1, 4, 4, -1);
    igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_APPROX_EADES);
    igraph_vector_int_print(&result);
    igraph_delete_edges(&g, igraph_ess_vector(&result));
    igraph_is_dag(&g, &dag);
    if (!dag) {
        return 3;
    }
    igraph_destroy(&g);

    /* Null graph */
    igraph_empty(&g, 0, IGRAPH_DIRECTED);
    igraph_feedback_arc_set(&g, &result, NULL, IGRAPH_FAS_APPROX_EADES);
    if (igraph_vector_int_size(&result) != 0) {
        return 4;
    }
    igraph_destroy(&g);

    /* Singleton graph */
    igraph_empty(&g, 1, IGRAPH_DIRECTED);
    igraph_feedback_arc_set(&g, &result, NULL, IGRAPH_FAS_APPROX_EADES);
    if (igraph_vector_int_size(&result) != 0) {
        return 5;
    }
    igraph_destroy(&g);

    igraph_vector_int_destroy(&result);

    return 0;
}

Example 18.3. File examples/simple/igraph_feedback_arc_set_ip.c

#include <igraph.h>
#include <string.h>

int main(void) {
    igraph_setup();
    igraph_t g;
    igraph_vector_t weights;
    igraph_vector_int_t result;
    igraph_bool_t dag;
    igraph_error_t retval;

    /* Initialize the library. */
    igraph_setup();

    igraph_vector_int_init(&result, 0);

    igraph_set_error_handler(&igraph_error_handler_printignore);

    /***********************************************************************/
    /* Exact solution with integer programming                             */
    /***********************************************************************/

    /* Simple unweighted graph */
    igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, -1);
    retval = igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_EXACT_IP);
    if (retval == IGRAPH_UNIMPLEMENTED) {
        return 77;
    }
    igraph_vector_int_print(&result);
    igraph_delete_edges(&g, igraph_ess_vector(&result));
    igraph_is_dag(&g, &dag);
    if (!dag) {
        return 1;
    }
    igraph_destroy(&g);

    /* Simple weighted graph */
    igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, -1);
    igraph_vector_init_int_end(&weights, -1, 1, 1, 3, 1, 1, 1, 1, 1, 1, -1);
    igraph_feedback_arc_set(&g, &result, &weights, IGRAPH_FAS_EXACT_IP);
    igraph_vector_int_print(&result);
    igraph_delete_edges(&g, igraph_ess_vector(&result));
    igraph_is_dag(&g, &dag);
    if (!dag) {
        return 2;
    }
    igraph_vector_destroy(&weights);
    igraph_destroy(&g);

    /* Simple unweighted graph with loops */
    igraph_small(&g, 0, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 0, 2, 3, 2, 4, 0, 4, 4, 3, 5, 0, 6, 5, 1, 1, 4, 4, -1);
    igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_EXACT_IP);
    igraph_vector_int_print(&result);
    igraph_delete_edges(&g, igraph_ess_vector(&result));
    igraph_is_dag(&g, &dag);
    if (!dag) {
        return 3;
    }
    igraph_destroy(&g);

    /* Disjoint union of two almost identical graphs */
    igraph_small(&g, 0, IGRAPH_DIRECTED,
                 0, 1, 1, 2, 2, 0, 2, 3,  2, 4,  0, 4,  4, 3,    5, 0,  6, 5, 1, 1, 4, 4,
                 7, 8, 8, 9, 9, 7, 9, 10, 9, 11, 7, 11, 11, 10, 12, 7, 13, 12,
                 -1);
    igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_EXACT_IP);
    igraph_vector_int_print(&result);
    igraph_delete_edges(&g, igraph_ess_vector(&result));
    igraph_is_dag(&g, &dag);
    if (!dag) {
        return 4;
    }
    igraph_destroy(&g);

    /* Graph with lots of isolated vertices */
    igraph_small(&g, 10000, IGRAPH_DIRECTED, 0, 1, -1);
    igraph_feedback_arc_set(&g, &result, 0, IGRAPH_FAS_EXACT_IP);
    igraph_vector_int_print(&result);
    igraph_delete_edges(&g, igraph_ess_vector(&result));
    igraph_is_dag(&g, &dag);
    if (!dag) {
        return 5;
    }
    igraph_destroy(&g);

    /* Null graph */
    igraph_empty(&g, 0, IGRAPH_DIRECTED);
    igraph_feedback_arc_set(&g, &result, NULL, IGRAPH_FAS_EXACT_IP);
    if (igraph_vector_int_size(&result) != 0) {
        return 6;
    }
    igraph_destroy(&g);

    /* Singleton graph */
    igraph_empty(&g, 1, IGRAPH_DIRECTED);
    igraph_feedback_arc_set(&g, &result, NULL, IGRAPH_FAS_EXACT_IP);
    if (igraph_vector_int_size(&result) != 0) {
        return 7;
    }
    igraph_destroy(&g);

    igraph_vector_int_destroy(&result);

    return 0;
}

Time complexity: depends on algo, see the time complexities there.

2.5. `igraph_feedback_vertex_set` — Feedback vertex set of a graph.

igraph_error_t igraph_feedback_vertex_set(
    const igraph_t *graph, igraph_vector_int_t *result,
    const igraph_vector_t *vertex_weights, igraph_fvs_algorithm_t algo);

A feedback vertex set is a set of vertices whose removal makes the graph acyclic. Finding a minimum feedback vertex set is an NP-complete problem, both on directed and undirected graphs.

Arguments:

graph:

The graph.

result:

An initialized vector, the result will be written here.

vertex_weights:

Vertex weight vector or NULL if no weights are specified.

algo:

Algorithm to use. Possible values:

IGRAPH_FVS_EXACT_IP

Finds a miniumum feedback vertex set using integer programming (IP). The complexity is of course at least exponential. Currently this method uses an approach analogous to that of the IGRAPH_FAS_EXACT_IP_CG algorithm of igraph_feedback_arc_set().

Returns:

Error code.

Time complexity: depends on algo, see the time complexities there.

3. Eulerian cycles and paths

3.1. igraph_is_eulerian — Checks whether an Eulerian path or cycle exists.
3.2. igraph_eulerian_cycle — Finds an Eulerian cycle.
3.3. igraph_eulerian_path — Finds an Eulerian path.

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

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

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

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

4. Cycle bases

4.1. igraph_fundamental_cycles — Finds a fundamental cycle basis.
4.2. igraph_minimum_cycle_basis — Computes a minimum weight cycle basis.

4.1. `igraph_fundamental_cycles` — Finds a fundamental cycle basis.

igraph_error_t igraph_fundamental_cycles(
        const igraph_t *graph, const igraph_vector_t *weights,
        igraph_vector_int_list_t *result,
        igraph_int_t start_vid, igraph_real_t bfs_cutoff);

Warning

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.
`weights`:	Currently unused.
`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 `2bfs_cutoff + 1` or shorter are included. `bfs_cutoff`* is used to limit the depth of the BFS tree when searching for cycle edges.

Returns:

Error code.

See also:

igraph_minimum_cycle_basis()

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

4.2. `igraph_minimum_cycle_basis` — Computes a minimum weight cycle basis.

igraph_error_t igraph_minimum_cycle_basis(
        const igraph_t *graph, const igraph_vector_t *weights,
        igraph_vector_int_list_t *result,
        igraph_real_t bfs_cutoff,
        igraph_bool_t complete, igraph_bool_t use_cycle_order);

Warning

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.
`weights`:	Currently unused.
`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 `2bfs_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.

Returns:

Error code.

See also:

igraph_fundamental_cycles()

Time complexity: TODO.

igraph Reference Manual

Chapter 18. Graph cycles

1. Finding cycles

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

1.2. igraph_simple_cycles — Finds all simple cycles.

Warning

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

Warning

1.4. igraph_cycle_handler_t — Type of cycle handler functions.

2. Acyclic graphs and feedback sets

2.1. igraph_is_dag — Checks whether a graph is a directed acyclic graph (DAG).

2.2. igraph_is_acyclic — Checks whether a graph is acyclic or not.

2.3. igraph_topological_sorting — Calculate a possible topological sorting of the graph.

2.4. igraph_feedback_arc_set — Feedback arc set of a graph using exact or heuristic methods.

2.5. igraph_feedback_vertex_set — Feedback vertex set of a graph.

3. Eulerian cycles and paths

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

3.2. igraph_eulerian_cycle — Finds an Eulerian cycle.

3.3. igraph_eulerian_path — Finds an Eulerian path.

4. Cycle bases

4.1. igraph_fundamental_cycles — Finds a fundamental cycle basis.

Warning

4.2. igraph_minimum_cycle_basis — Computes a minimum weight cycle basis.

Warning

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.

2.1. `igraph_is_dag` — Checks whether a graph is a directed acyclic graph (DAG).

2.2. `igraph_is_acyclic` — Checks whether a graph is acyclic or not.

2.3. `igraph_topological_sorting` — Calculate a possible topological sorting of the graph.

2.4. `igraph_feedback_arc_set` — Feedback arc set of a graph using exact or heuristic methods.

2.5. `igraph_feedback_vertex_set` — Feedback vertex set of a graph.

3.1. `igraph_is_eulerian` — Checks whether an Eulerian path or cycle exists.

3.2. `igraph_eulerian_cycle` — Finds an Eulerian cycle.

3.3. `igraph_eulerian_path` — Finds an Eulerian path.

4.1. `igraph_fundamental_cycles` — Finds a fundamental cycle basis.

4.2. `igraph_minimum_cycle_basis` — Computes a minimum weight cycle basis.