Skip to contents

Find Eulerian paths or cycles in a graph

Source: R/eulerian.R
has_eulerian_path.Rd

has_eulerian_path() and has_eulerian_cycle() checks whether there is an Eulerian path or cycle in the input graph. eulerian_path() and eulerian_cycle() return such a path or cycle if it exists, and throws an error otherwise.

Usage

has_eulerian_path(graph)

has_eulerian_cycle(graph)

eulerian_path(graph)

eulerian_cycle(graph)

Arguments

graph

An igraph graph object

Value

For has_eulerian_path() and has_eulerian_cycle(), a logical value that indicates whether the graph contains an Eulerian path or cycle. For eulerian_path() and eulerian_cycle(), a named list with two entries:

epath

A vector containing the edge IDs along the Eulerian path or cycle.

vpath

A vector containing the vertex IDs along the Eulerian path or cycle.

Details

has_eulerian_path() decides whether the input graph has an Eulerian path, i.e. a path that passes through every edge of the graph exactly once, and returns a logical value as a result. eulerian_path() returns a possible Eulerian path, described with its edge and vertex sequence, or throws an error if no such path exists.

has_eulerian_cycle() decides whether the input graph has an Eulerian cycle, i.e. a path that passes through every edge of the graph exactly once and that returns to its starting point, and returns a logical value as a result. eulerian_cycle() returns a possible Eulerian cycle, described with its edge and vertex sequence, or throws an error if no such cycle exists.

is_eulerian(), eulerian_path(), ecount(), vcount(), edges(), get_eids(), eulerian_cycle()

See also

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

Examples


g <- make_graph(~ A - B - C - D - E - A - F - D - B - F - E)

has_eulerian_path(g)
#> [1] TRUE
eulerian_path(g)
#> $epath
#> ── <edge sequence> 10/10 · vertex names · from 8ca76da ─────────────────────────
#>  [1] A ─ B  B ─ C  C ─ D  B ─ D  B ─ F  A ─ F  A ─ E  D ─ E  D ─ F  E ─ F 
#> 
#> $vpath
#> ── <vertex sequence> 11/6 · named · from 8ca76da ───────────────────────────────
#>  [1] A B C D B F A E D F E
#> 

has_eulerian_cycle(g)
#> [1] FALSE
try(eulerian_cycle(g))
#> Error in eulerian_cycle_impl(graph = graph) : 
#>   The graph does not have an Eulerian cycle. Input problem has no solution
#> Source: paths/eulerian.c:615