emst: Fast Euclidean Minimum Spanning Tree

In mlpack: 'Rcpp' Integration for the 'mlpack' Library

Fast Euclidean Minimum Spanning Tree

Description

An implementation of the Dual-Tree Boruvka algorithm for computing the Euclidean minimum spanning tree of a set of input points.

Usage

emst(
  input,
  leaf_size = NA,
  naive = FALSE,
  verbose = getOption("mlpack.verbose", FALSE)
)

Arguments

input	Input data matrix (numeric matrix).
leaf_size	Leaf size in the kd-tree. One-element leaves give the empirically best performance, but at the cost of greater memory requirements. Default value "1" (integer).
naive	Compute the MST using O(n^2) naive algorithm. Default value "FALSE" (logical).
verbose	Display informational messages and the full list of parameters and timers at the end of execution. Default value "getOption("mlpack.verbose", FALSE)" (logical).

Details

This program can compute the Euclidean minimum spanning tree of a set of input points using the dual-tree Boruvka algorithm.

The set to calculate the minimum spanning tree of is specified with the "input" parameter, and the output may be saved with the "output" output parameter.

The "leaf_size" parameter controls the leaf size of the kd-tree that is used to calculate the minimum spanning tree, and if the "naive" option is given, then brute-force search is used (this is typically much slower in low dimensions). The leaf size does not affect the results, but it may have some effect on the runtime of the algorithm.

Value

A list with several components:

output

Output data. Stored as an edge list (numeric matrix).

Author(s)

mlpack developers

Examples

# For example, the minimum spanning tree of the input dataset "data" can be
# calculated with a leaf size of 20 and stored as "spanning_tree" using the
# following command:

## Not run: 
output <- emst(input=data, leaf_size=20)
spanning_tree <- output$output

## End(Not run)

# The output matrix is a three-dimensional matrix, where each row indicates
# an edge.  The first dimension corresponds to the lesser index of the edge;
# the second dimension corresponds to the greater index of the edge; and the
# third column corresponds to the distance between the two points.

mlpack documentation built on Oct. 5, 2024, 9:08 a.m.