mlpack: a scalable c++ machine learning library
mlpack  1.0.6
mlpack::emst::DualTreeBoruvka< MetricType, TreeType > Class Template Reference

Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree. More...

Collaboration diagram for mlpack::emst::DualTreeBoruvka< MetricType, TreeType >:

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. More...

 
 DualTreeBoruvka (TreeType *tree, const typename TreeType::Mat &dataset, 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...

 

Private Member Functions

void AddAllEdges ()
 Adds all the edges found in one iteration to the list of neighbors. More...

 
void AddEdge (const size_t e1, const size_t e2, const double distance)
 Adds a single edge to the edge list. More...

 
void Cleanup ()
 The values stored in the tree must be reset on each iteration. More...

 
void CleanupHelper (TreeType *tree)
 This function resets the values in the nodes of the tree nearest neighbor distance, and checks for fully connected nodes. More...

 
void EmitResults (arma::mat &results)
 Unpermute the edge list and output it to results. More...

 

Private Attributes

UnionFind connections
 Connections. More...

 
TreeType::Mat & data
 Reference to the data (this is what should be used for accessing data). More...

 
TreeType::Mat dataCopy
 Copy of the data (if necessary). More...

 
std::vector< EdgePairedges
 Edges. More...

 
MetricType metric
 The metric. More...

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

 
arma::vec neighborsDistances
 List of edge distances. More...

 
arma::Col< size_t > neighborsInComponent
 List of edge nodes. More...

 
arma::Col< size_t > neighborsOutComponent
 List of edge nodes. More...

 
std::vector< size_t > oldFromNew
 Permutations of points during tree building. More...

 
bool ownTree
 Indicates whether or not we "own" the tree. More...

 
struct mlpack::emst::DualTreeBoruvka::SortEdgesHelper SortFun
 
double totalDist
 Total distance of the tree. More...

 
TreeType * tree
 Pointer to the root of the tree. More...

 

Detailed Description


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; // 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
MetricTypeThe 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.
TreeTypeType of tree to use. Should use DTBStat as a statistic.

Definition at line 135 of file dtb.hpp.

Constructor & Destructor Documentation

◆ DualTreeBoruvka() [1/2]

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::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.

This copies the dataset to an internal copy, because tree-building modifies the dataset.

Parameters
dataDataset to build a tree for.
naiveWhether the computation should be done in O(n^2) naive mode.
leafSizeThe leaf size to be used during tree construction.

◆ DualTreeBoruvka() [2/2]

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::DualTreeBoruvka ( TreeType *  tree,
const typename TreeType::Mat &  dataset,
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).

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
treePre-built tree.
datasetDataset corresponding to the pre-built tree.

◆ ~DualTreeBoruvka()

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::~DualTreeBoruvka ( )

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

Member Function Documentation

◆ AddAllEdges()

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
void mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::AddAllEdges ( )
private

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

◆ AddEdge()

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
void mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::AddEdge ( const size_t  e1,
const size_t  e2,
const double  distance 
)
private

Adds a single edge to the edge list.

◆ Cleanup()

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
void mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::Cleanup ( )
private

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

◆ CleanupHelper()

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
void mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::CleanupHelper ( TreeType *  tree)
private

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

◆ ComputeMST()

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
void mlpack::emst::DualTreeBoruvka< 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
resultsMatrix which results will be stored in.

◆ EmitResults()

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
void mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::EmitResults ( arma::mat &  results)
private

Unpermute the edge list and output it to results.

Member Data Documentation

◆ connections

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
UnionFind mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::connections
private

Connections.

Definition at line 155 of file dtb.hpp.

◆ data

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
TreeType::Mat& mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::data
private

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

Definition at line 141 of file dtb.hpp.

◆ dataCopy

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
TreeType::Mat mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::dataCopy
private

Copy of the data (if necessary).

Definition at line 139 of file dtb.hpp.

◆ edges

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
std::vector<EdgePair> mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::edges
private

Edges.

Definition at line 152 of file dtb.hpp.

◆ metric

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
MetricType mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::metric
private

The metric.

Definition at line 170 of file dtb.hpp.

◆ naive

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
bool mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::naive
private

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

Definition at line 149 of file dtb.hpp.

◆ neighborsDistances

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
arma::vec mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::neighborsDistances
private

List of edge distances.

Definition at line 164 of file dtb.hpp.

◆ neighborsInComponent

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
arma::Col<size_t> mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::neighborsInComponent
private

List of edge nodes.

Definition at line 160 of file dtb.hpp.

◆ neighborsOutComponent

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
arma::Col<size_t> mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::neighborsOutComponent
private

List of edge nodes.

Definition at line 162 of file dtb.hpp.

◆ oldFromNew

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
std::vector<size_t> mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::oldFromNew
private

Permutations of points during tree building.

Definition at line 158 of file dtb.hpp.

◆ ownTree

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
bool mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::ownTree
private

Indicates whether or not we "own" the tree.

Definition at line 146 of file dtb.hpp.

◆ SortFun

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
struct mlpack::emst::DualTreeBoruvka::SortEdgesHelper mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::SortFun
private

◆ totalDist

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
double mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::totalDist
private

Total distance of the tree.

Definition at line 167 of file dtb.hpp.

◆ tree

template<typename MetricType = metric::SquaredEuclideanDistance, typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>>
TreeType* mlpack::emst::DualTreeBoruvka< MetricType, TreeType >::tree
private

Pointer to the root of the tree.

Definition at line 144 of file dtb.hpp.


The documentation for this class was generated from the following file:
  • /var/www/www.mlpack.org/mlpack-1.0.6/src/mlpack/methods/emst/dtb.hpp