# hpaths: Hamiltonian paths on the complete graph on 1..n, using... In PairViz: Visualization using Graph Traversal

## Description

`zigzag` - Constructs hamiltonian paths where each pair (i,j) appears in at least one of the hamiltonians.

`hpaths` - Returns a hamiltonian decomposition on the complete graph with n nodes. See Details.

`permute_hpaths` - Returns a modified version of `paths`, where vertices are re-labelled so that the first hamiltonian is `path1`.

## Usage

 ```1 2 3``` ```zigzag(n) hpaths(n, matrix=TRUE,cycle=NULL,...) permute_hpaths(path1,paths= hpaths(length(path1)), matrix=TRUE,...) ```

## Arguments

 `n` a positive integer. For `hpaths`, `n` may also be a vector specifying the first hamiltonian. `matrix` if `TRUE`, returns a matrix where each row is a hamiltonian path, otherwise concatenates the rows into a vector. `cycle` If `TRUE`, returns hamiltonian cycles, i.e. every hamiltonian starts at the same node. If `FALSE`, returned paths are open. Defaults to `TRUE` for odd n,`FALSE` for even n. `path1` A vector- This will be the first hamiltonian of the returned hamiltonian decomposition. `paths` A matrix where each row is a hamiltonian. `...` Ignored.

## Details

`hpaths` - From graph theory we know that for odd n, the complete graph decomposes into (n-1)/2 edge distinct hamiltonian cycles, while for even n the graph decomposes into n/2 edge distinct hamiltonian paths. The default behaviour of the function `hpaths` is to produce the cycle decomposition for odd n and the path decomposition for even n.

However, if a `TRUE` value is supplied as argument cycle, the returned paths are cycles, and the result is a true decomposition for odd n, but for even n the last hamiltonian has some duplicate edges. If a `FALSE` value is supplied as argument cycle, the returned paths are open, and the result is a true decomposition for even n, but for odd n the last hamiltonian has some duplicate edges.

## Value

A numeric matrix where each row contains a permutation of 1..n, or these rows concatenated into a vector if `matrix=FALSE`.

## Author(s)

C.B. Hurley and R.W. Oldford

## References

D.E. Lucas (1892), Recreations Matematiques, Vol II. Gauthier Villars, Paris.

Also see overview

`weighted_hpaths`, `eseq`.
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22``` ```require(PairViz) zigzag(7) hpaths(7) # the rows form a decomp. into hamiltonian cycles # Now concatenate the rows and close the path hpaths(7,matrix=FALSE) # Form a decomposition into hamiltonian cycles- # this decomposition is not exact, as the last row duplicates edges hpaths(7,cycle=FALSE) # For even n, the default is a decomposition into hamiltonian paths, not cycles. hpaths(6) # If cycles are required for even n, # the decomposition will not be exact and the last row duplicates edges hpaths(6,cycle=TRUE) # If you want to specify the first hamiltonian of the decomposition, use hpaths(1:7) ```