mst {nnclust}R Documentation

Minimum spanning trees

Description

Minimum spanning tree by Prim's algorithm, using a fast nearest-neighbour search to find candidate points. The variant mst_restart stops when the link length is greater than a specified threshold.

Usage

mst(X, rebuild = sqrt(nrow(X))/4)
mst_restart(X,rebuild=sqrt(nrow(X))/4,threshold=Inf,start=NULL)

Arguments

X Matrix of data points
rebuild How often to rebuild the k-d tree for nearest neighbour lookup.
threshold Return when the next link is longer than this
start Start here rather than at the first row of X

Value

from,to Row numbers of X for each link
dist Squared length of link
n For mst_restart only, the number of links added

Author(s)

Thomas Lumley

References

Bentley JL, Friedman JH. "Fast algorithms for constructing minimal spanning trees in coordinate spaces" IEEE Transactions on Computers C27(2) Feb 1978

See Also

nncluster for a wrapper for mst_restart to do clustering.

Examples

x<-scale(faithful)
a<-mst(x)
plot(faithful)
segments(faithful[a$from,1], faithful[a$from,2], faithful[a$to,1],
faithful[a$to,2],col="blue")

## restarting 
plot(a$dist)
a<-mst_restart(x,threshold=0.04,start=0)
plot(faithful)
segments(faithful[a$from,1], faithful[a$from,2], faithful[a$to,1],
faithful[a$to,2],col="red")

b<-mst_restart(x[-a$to,],threshold=0.04)
ff<-faithful[-a$to,]
segments(ff[b$from,1], ff[b$from,2], ff[b$to,1],ff[b$to,2],col="purple")



[Package nnclust version 2.2 Index]