order.length {cba}

Conciseness of Presentation Measures

Description

Compute the length of a Hamilton path through a distance matrix.

Usage

order.length(dist, order)

Arguments

dist

an object of class dist.

order

an optional permutation of the row (column) indexes.

Details

Ordering a distance matrix such that low distance values are placed close to the diagonal may improve its presentation. The length of an order is the corresponding objective measure.

The order corresponds to a path through a graph where each node is visited only once, i.e. a Hamilton path. The length of a path is defined as the sum of the edge weights, i.e. distances.

If order is missing the identity order is used.

If order is not unique NA is returned.

If there are non-finite distance values NA is returned.

Value

A scalar real value.

Author(s)

Christian Buchta

References

R. Sedgewick. (2002). Algorithms in C. Part 5. Graph Algorithms. 3rd Edition, Addison-Wesley.

Examples

d <- dist(matrix(runif(10),ncol=2))
order.length(d)
o <- sample(5,5) # random order
order.length(d, o)