mst: Minimum Spanning Tree

Description Usage Arguments Details Value Note Author(s) References Examples

View source: R/mst.r

Description

Identifies the minimum spanning tree connecting the set of points using their spatial distances.

Usage

1
  mst(x) 

Arguments

x

Distance matrix between points

Details

Certainly, a single vector could be used to capture the topology of a MST, indicating the index of the parent node for each child node. However, I have decided to indicate the endpoints for each MST arc into two separate vectors.

Value

This function returns a list with the following elements:

path

Length of the MST in the given metric units.

wght

Mean leangth of MST arcs incident to each vertex. Values are normalized so that they sum to unity.

xy0

Indices for one of the endpoints of MST arcs.

xy1

Indices for the other endpoints correspondingly ordered.

Note

The algorithm to obtain the MST is valid for distance matrices with metric properties. Consequently, both Euclidean and orthodromic distances can be used.

Author(s)

Daniel A. Dos Santos <[email protected]>

References

Prim R.C. 1957. Shortest Connecting Networks and Some Generalizations. Bell Syst. Tech. J 36:1389-1401.

Examples

1
2
3
4
  xy <- matrix(rnorm(100), ncol = 2) # Sample a random set of points
  plot(xy, xlab = "", ylab = "", main = "MINIMUM SPANNING TREE")
  aux <- mst(as.matrix(dist(xy))) # Find the Euclidean minimum spanning tree
  segments(xy[aux$xy0,1], xy[aux$xy0,2], xy[aux$xy1,1], xy[aux$xy1,2]) # Plot the MST

SyNet documentation built on May 30, 2017, 4:21 a.m.