Constructs eulerian tours on a graph.
etour.Rd
etour
-- Constructs an eulerian tour on a graph using Hierholzer's algorithm. Returns a vector of node labels. If weighted
is TRUE
constructs a weight-decreasing eulerian using the modified Hierholzer's algorithm. Usually etour
is not called directly, rather the generic function eulerian
is used.
Arguments
- g
a graph satisfying
is_even_graph
- start
an optional starting node for the tour.
- weighted
whether tour uses weights
Details
The supplied graph should satisfyis_even_graph
. If weighted
is TRUE
the lowest weight edge is found, and the tour starts at the
one of its nodes, picking the node with the bigger second-smallest edge weight.
After that the tour follows weight-increasing edges.
If weighted
is FALSE
weights are ignored. The returned tour is typically a closed path. However, if the last edge is a duplicated edge added to make the graph even, this edge is omitted and the result is an open path.
References
see overview
Examples
require(PairViz)
g <- mk_even_graph(5)
etour(g)
#> [1] "1" "2" "3" "1" "4" "2" "5" "3" "4" "5" "1"
g <- mk_even_graph(6) # adds 3 extra edges to g, so all nodes are even
etour(g)
#> [1] "1" "2" "3" "1" "4" "2" "3" "4" "5" "1" "6" "2" "5" "3" "6" "4" "5" "6"
etour(g, start= "4") # modifies the starting node
#> [1] "4" "1" "2" "3" "1" "5" "2" "3" "4" "2" "6" "1" "6" "3" "5" "4" "6" "5"
eulerian(6) # The eulerian wrapper looks after making even graph,
#> [1] 1 2 3 1 4 2 3 4 5 1 6 2 5 3 6 4 5 6
#also returns numbers rather than nodes
# On a general graph.
v <- LETTERS[1:4]
g <- new("graphNEL",nodes=v)
g <- addEdge(v[1],v[3:4],g,1:2)
g <- addEdge(v[2],v[3:4],g,3:4)
etour(g)
#> [1] "C" "A" "D" "B" "C"
eulerian(g) # Equivalently, use eulerian wrapper
#> [1] "C" "A" "D" "B" "C"
n <- LETTERS[1:5]
g <- new("graphNEL",nodes=n)
g <- addEdge(n[1],n[2:3],g)
g <-addEdge(n[2],n[3:5],g)
g <-addEdge(n[4],n[3],g)
is_even_graph(g)
#> [1] FALSE
etour(mk_even_graph(g))
#> [1] "B" "A" "C" "B" "D" "C" "E" "B"
eulerian(g) # Equivalently, use eulerian wrapper
#> [1] "B" "A" "C" "B" "D" "C" "E" "B"