Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree. More...
Public Types | |
typedef TreeType< MetricType, DTBStat, MatType > | Tree |
Convenience typedef. More... | |
Public Member Functions | |
DualTreeBoruvka (const MatType &dataset, const bool naive=false, const MetricType metric=MetricType()) | |
Create the tree from the given dataset. More... | |
DualTreeBoruvka (Tree *tree, const MetricType metric=MetricType()) | |
Create the DualTreeBoruvka object with an already initialized tree. More... | |
~DualTreeBoruvka () | |
Delete the tree, if it was created inside the object. More... | |
void | ComputeMST (arma::mat &results) |
Iteratively find the nearest neighbor of each component until the MST is complete. More... | |
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:
General usage of this class might be like this:
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.
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. |
DualTreeBoruvka | ( | const MatType & | dataset, |
const bool | naive = false , |
||
const MetricType | metric = MetricType() |
||
) |
Create the tree from the given dataset.
This copies the dataset to an internal copy, because tree-building modifies the dataset.
dataset | Dataset to build a tree for. |
naive | Whether the computation should be done in O(n^2) naive mode. |
metric | An optional instantiated metric to use. |
DualTreeBoruvka | ( | Tree * | tree, |
const MetricType | metric = MetricType() |
||
) |
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).
tree | Pre-built tree. |
metric | An optional instantiated metric to use. |
~DualTreeBoruvka | ( | ) |
Delete the tree, if it was created inside the object.
void ComputeMST | ( | arma::mat & | results | ) |
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.
results | Matrix which results will be stored in. |