Constructs weight decreasing hamiltonian paths

Returns a modified version of paths, where component paths/cycles are re-oriented so low weight edges occur first, and the component paths/cycles are then permuted so low-weight paths are first.

Usage

weighted_hpaths(d, path1 = NULL, paths=NULL, matrix=TRUE, cycle=NULL, 
path_weight=sum, path_dir = path_cor,...)

Arguments

d: A dist, used to provide edge weights.
path1: A vector giving a hamiltonian. This will be the first path of the returned hamiltonian. The default is obtained from order_tsp.
paths: A matrix where each row is a hamiltonian. Default comes from hpaths.
matrix: if TRUE, returns a matrix where each row is a hamiltonian path, otherwise concatenates the rows into a vector. For odd n, the starting node is appended to close the eulerian.
cycle: If TRUE, the weighted_hpaths algorithm evaluates path_weight on hamiltonian cycles, if FALSE, on open hamiltonian paths. Default is TRUE for odd n and FALSE for even n.
path_weight: A function used combine path weights into a single value. Default function is path_cor.
path_dir: A function used to evaluate a path start and orientation.
...: passed to path_weight

Details

If path is not provided, find the hamiltonian (path for even n, cycle for odd n) with the smallest total weight. Applying path_dir to edge weights, pick the starting and point orientation for path1 giving the largest path_dir value. (For open paths, there are only two possible starts, for cycles there are n). Apply this node labelling to the hamiltonians in the rows of paths. Use criterion path_dir again to find the best orientation for each of rows 2... of paths and permute these rows in order of increasing path_weight.

References

see overview

Author

C.B. Hurley and R.W. Oldford

Examples


require(PairViz)

weighted_hpaths(dist(rnorm(6)))
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    1    5    6    3    2    4
#> [2,]    5    3    1    4    6    2
#> [3,]    3    4    5    2    1    6

weighted_hpaths(dist(rnorm(7)))
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    5    2    6    3    1    7    4
#> [2,]    5    6    1    2    4    3    7
#> [3,]    5    1    4    6    7    2    3