Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree.
More...
Classes |
struct | SortEdgesHelper |
Public Member Functions |
| DualTreeBoruvka (const typename TreeType::Mat &dataset, const bool naive=false, const size_t leafSize=1, const MetricType metric=MetricType()) |
| Create the tree from the given dataset.
|
| DualTreeBoruvka (TreeType *tree, const typename TreeType::Mat &dataset, const MetricType metric=MetricType()) |
| Create the DualTreeBoruvka object with an already initialized tree.
|
| ~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.
|
Private Member Functions |
void | AddAllEdges () |
| Adds all the edges found in one iteration to the list of neighbors.
|
void | AddEdge (const size_t e1, const size_t e2, const double distance) |
| Adds a single edge to the edge list.
|
void | Cleanup () |
| The values stored in the tree must be reset on each iteration.
|
void | CleanupHelper (TreeType *tree) |
| This function resets the values in the nodes of the tree nearest neighbor distance, and checks for fully connected nodes.
|
void | EmitResults (arma::mat &results) |
| Unpermute the edge list and output it to results.
|
Private Attributes |
UnionFind | connections |
| Connections.
|
TreeType::Mat & | data |
| Reference to the data (this is what should be used for accessing data).
|
TreeType::Mat | dataCopy |
| Copy of the data (if necessary).
|
std::vector< EdgePair > | edges |
| Edges.
|
MetricType | metric |
| The metric.
|
bool | naive |
| Indicates whether or not O(n^2) naive mode will be used.
|
arma::vec | neighborsDistances |
| List of edge distances.
|
arma::Col< size_t > | neighborsInComponent |
| List of edge nodes.
|
arma::Col< size_t > | neighborsOutComponent |
| List of edge nodes.
|
std::vector< size_t > | oldFromNew |
| Permutations of points during tree building.
|
bool | ownTree |
| Indicates whether or not we "own" the tree.
|
struct
mlpack::emst::DualTreeBoruvka::SortEdgesHelper | SortFun |
double | totalDist |
| Total distance of the tree.
|
TreeType * | tree |
| Pointer to the root of the tree.
|
template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
class mlpack::emst::DualTreeBoruvka< MetricType, 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:
extern arma::mat data;
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. IMPORTANT: this hasn't really been tested with anything other than the L2 metric, so user beware. Note that the tree type needs to compute bounds using the same metric as the type specified here. |
TreeType | Type of tree to use. Should use DTBStat as a statistic. |
Definition at line 137 of file dtb.hpp.
template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
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. |