Finds a cycle in a graph, if there is one

This function returns a cycle of the graph, in terms of both its vertices and edges. If the graph is acyclic, it returns empty vertex and edge sequences.

Use is_acyclic() to determine if a graph has cycles, without returning a specific cycle.

Usage

find_cycle(graph, mode = c("out", "in", "all", "total"))

Arguments

graph

The input graph.

mode

Character constant specifying how to handle directed graphs. out follows edge directions, in follows edges in the reverse direction, and all ignores edge directions. Ignored in undirected graphs.

Value

A list of integer vectors, each integer vector is a path from the source vertex to one of the target vertices. A path is given by its vertex IDs.

Related documentation in the C library

find_cycle(), ecount(), vcount(), edges(), get_eids()

See also

Graph cycles: feedback_arc_set(), feedback_vertex_set(), girth(), has_eulerian_path(), is_acyclic(), is_dag(), simple_cycles()

Examples

g <- make_lattice(c(3, 3))
find_cycle(g)
#> $vertices
#> ── <vertex sequence> 4/9 · from 95602da ────────────────────────────────────────
#> [1] 9 6 5 8
#> 
#> $edges
#> ── <edge sequence> 4/12 · from 95602da ─────────────────────────────────────────
#> [1] 8 ─ 9  6 ─ 9  5 ─ 6  5 ─ 8 
#> 

# Empty results are returned for acyclic graphs
find_cycle(sample_tree(5))
#> $vertices
#> ── <vertex sequence> 0/5 · from 14850d9 ────────────────────────────────────────
#> 
#> $edges
#> ── <edge sequence> 0/4 · from 14850d9 ──────────────────────────────────────────
#>