mlpack_emst_DualTreeBoruvka (3)

Performs the mst calculation using the dual-tree boruvka algorithm, using any type of tree.

  1. Carta.tech
  2. Man Pages
  3. Library calls
  4. mlpack_emst_DualTreeBoruvka: Performs the mst calculation using the dual-tree boruvka algorithm, using any type of tree.
  1. Carta.tech
  2. Packages
  3. mlpack-doc
  4. mlpack_emst_DualTreeBoruvka: Performs the mst calculation using the dual-tree boruvka algorithm, using any type of tree.

SYNOPSIS

Classes

struct SortEdgesHelper

For sorting the edge list after the computation.

Public Member Functions

DualTreeBoruvka (const typename TreeType::Mat &dataset, const bool naive=false, 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. std::string ToString () const

Returns a string representation of this object.

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. const 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 instantiated 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.

Detailed Description

template<typename MetricType = metric::EuclideanDistance, 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; // We want to find the MST of this dataset.
DualTreeBoruvka<> dtb(data); // Create the tree with default options.

// Find the MST.
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 91 of file dtb.hpp.

Constructor & Destructor Documentation

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::\fBDualTreeBoruvka\fP (const typename TreeType::Mat &dataset, const boolnaive = \fCfalse\fP, const MetricTypemetric = \fCMetricType()\fP)

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 TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::\fBDualTreeBoruvka\fP (TreeType *tree, const typename TreeType::Mat &dataset, const MetricTypemetric = \fCMetricType()\fP)

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 TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::~\fBDualTreeBoruvka\fP ()

Delete the tree, if it was created inside the object.

Member Function Documentation

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> void \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::AddAllEdges ()\fC [private]\fP

Adds all the edges found in one iteration to the list of neighbors.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> void \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::AddEdge (const size_te1, const size_te2, const doubledistance)\fC [private]\fP

Adds a single edge to the edge list.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> void \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::Cleanup ()\fC [private]\fP

The values stored in the tree must be reset on each iteration.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> void \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::CleanupHelper (TreeType *tree)\fC [private]\fP

This function resets the values in the nodes of the tree nearest neighbor distance, and checks for fully connected nodes.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> void \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::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.

Parameters:

results Matrix which results will be stored in.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> void \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::EmitResults (arma::mat &results)\fC [private]\fP

Unpermute the edge list and output it to results.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> std::string \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::ToString () const

Returns a string representation of this object.

Member Data Documentation

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> \fBUnionFind\fP \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::connections\fC [private]\fP

Connections.

Definition at line 111 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> const TreeType::Mat& \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::data\fC [private]\fP

Reference to the data (this is what should be used for accessing data).

Definition at line 97 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> TreeType::Mat \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::dataCopy\fC [private]\fP

Copy of the data (if necessary).

Definition at line 95 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> std::vector<\fBEdgePair\fP> \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::edges\fC [private]\fP

Edges.

Definition at line 108 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> MetricType \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::metric\fC [private]\fP

The instantiated metric.

Definition at line 126 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> bool \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::naive\fC [private]\fP

Indicates whether or not O(n^2) naive mode will be used.

Definition at line 105 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> arma::vec \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::neighborsDistances\fC [private]\fP

List of edge distances.

Definition at line 120 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> arma::Col<size_t> \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::neighborsInComponent\fC [private]\fP

List of edge nodes.

Definition at line 116 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> arma::Col<size_t> \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::neighborsOutComponent\fC [private]\fP

List of edge nodes.

Definition at line 118 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> std::vector<size_t> \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::oldFromNew\fC [private]\fP

Permutations of points during tree building.

Definition at line 114 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> bool \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::ownTree\fC [private]\fP

Indicates whether or not we 'own' the tree.

Definition at line 102 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> struct \fBmlpack::emst::DualTreeBoruvka::SortEdgesHelper\fP \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::SortFun\fC [private]\fP

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> double \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::totalDist\fC [private]\fP

Total distance of the tree.

Definition at line 123 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>> TreeType* \fBmlpack::emst::DualTreeBoruvka\fP< MetricType, TreeType >::tree\fC [private]\fP

Pointer to the root of the tree.

Definition at line 100 of file dtb.hpp.

Author

Generated automatically by Doxygen for MLPACK from the source code.