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.

See also

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

Related documentation in the C library

find_cycle().

Examples

g <- make_lattice(c(3,3))
find_cycle(g)
#> $vertices
#> + 4/9 vertices, from bc9ab35:
#> [1] 9 6 5 8
#> 
#> $edges
#> + 4/12 edges from bc9ab35:
#> [1] 8--9 6--9 5--6 5--8
#> 

# Empty results are returned for acyclic graphs
find_cycle(sample_tree(5))
#> $vertices
#> + 0/5 vertices, from ed6c20f:
#> 
#> $edges
#> + 0/4 edges from ed6c20f:
#>