Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree.
More...
template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>
class mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >
Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree.
For more information on the algorithm, see the following citation:
@inproceedings{
author = {March, W.B., Ram, P., and Gray, A.G.},
title = {{Fast Euclidean Minimum Spanning
Tree: Algorithm, Analysis,
Applications.}},
booktitle = {Proceedings of the 16th ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining}
series = {KDD 2010},
year = {2010}
}
General usage of this class might be like this:
DualTreeBoruvka<> dtb(data);
arma::mat mstResults;
dtb.ComputeMST(mstResults);
More advanced usage of the class can use different types of trees, pass in an already-built tree, or compute the MST using the O(n^2) naive algorithm.
- Template Parameters
-
MetricType | The metric to use. |
MatType | The type of data matrix to use. |
TreeType | Type of tree to use. This should follow the TreeType policy API. |
Definition at line 85 of file dtb.hpp.
template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>
Create the tree from the given dataset.
This copies the dataset to an internal copy, because tree-building modifies the dataset.
- Parameters
-
data | Dataset to build a tree for. |
naive | Whether the computation should be done in O(n^2) naive mode. |
leafSize | The leaf size to be used during tree construction. |
template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>
Create the DualTreeBoruvka object with an already initialized tree.
This will not copy the dataset, and can save a little processing power. Naive mode is not available as an option for this constructor; instead, to run naive computation, construct a tree with all the points in one leaf (i.e. leafSize = number of points).
- Note
- Because tree-building (at least with BinarySpaceTree) modifies the ordering of a matrix, be sure you pass the modified matrix to this object! In addition, mapping the points of the matrix back to their original indices is not done when this constructor is used.
- Parameters
-
tree | Pre-built tree. |
dataset | Dataset corresponding to the pre-built tree. |
template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>
Iteratively find the nearest neighbor of each component until the MST is complete.
The results will be a 3xN matrix (with N equal to the number of edges in the minimum spanning tree). The first row will contain the lesser index of the edge; the second row will contain the greater index of the edge; and the third row will contain the distance between the two edges.
- Parameters
-
results | Matrix which results will be stored in. |