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

Classes
struct	SortEdgesHelper
	For sorting the edge list after the computation. 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...

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 (Tree *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...

const MatType &	data
	Reference to the data (this is what should be used for accessing data). More...

std::vector< EdgePair >	edges
	Edges. More...

MetricType	metric
	The instantiated 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...

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

Detailed Description

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:

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.
MatType	The type of data matrix to use.
TreeType	Type of tree to use. This should follow the TreeType policy API.

Definition at line 83 of file dtb.hpp.

Member Typedef Documentation

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

typedef TreeType<MetricType, DTBStat, MatType> mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::Tree

Convenience typedef.

Definition at line 87 of file dtb.hpp.

Constructor & Destructor Documentation

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::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.

Parameters

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

Referenced by mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortEdgesHelper::operator()().

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::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).

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.
metric	An optional instantiated metric to use.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::~DualTreeBoruvka ( )

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

Referenced by mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortEdgesHelper::operator()().

Member Function Documentation

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

void mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::AddAllEdges ( )

private

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

Referenced by mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortEdgesHelper::operator()().

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

void mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::AddEdge	(	const size_t	e1,
		const size_t	e2,
		const double	distance
	)

private

Adds a single edge to the edge list.

Referenced by mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortEdgesHelper::operator()().

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

void mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::Cleanup ( )

private

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

Referenced by mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortEdgesHelper::operator()().

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

void mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::CleanupHelper ( Tree * tree )

private

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

Referenced by mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortEdgesHelper::operator()().

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

void mlpack::emst::DualTreeBoruvka< MetricType, MatType, 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.

Referenced by mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortEdgesHelper::operator()().

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

void mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::EmitResults ( arma::mat & results )

private

Unpermute the edge list and output it to results.

Referenced by mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortEdgesHelper::operator()().

Member Data Documentation

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

UnionFind mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::connections

private

Connections.

Definition at line 106 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

const MatType& mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::data

private

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

Definition at line 95 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

std::vector<EdgePair> mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::edges

private

Edges.

Definition at line 103 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

MetricType mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::metric

private

The instantiated metric.

Definition at line 119 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

bool mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::naive

private

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

Definition at line 100 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

arma::vec mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::neighborsDistances

private

List of edge distances.

Definition at line 113 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

arma::Col<size_t> mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::neighborsInComponent

private

List of edge nodes.

Definition at line 109 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

arma::Col<size_t> mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::neighborsOutComponent

private

List of edge nodes.

Definition at line 111 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

std::vector<size_t> mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::oldFromNew

private

Permutations of points during tree building.

Definition at line 91 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

bool mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::ownTree

private

Indicates whether or not we "own" the tree.

Definition at line 97 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

struct mlpack::emst::DualTreeBoruvka::SortEdgesHelper mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortFun

private

Referenced by mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::SortEdgesHelper::operator()().

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

double mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::totalDist

private

Total distance of the tree.

Definition at line 116 of file dtb.hpp.

template<typename MetricType = metric::EuclideanDistance, typename MatType = arma::mat, template< typename TreeMetricType, typename TreeStatType, typename TreeMatType > class TreeType = tree::KDTree>

Tree* mlpack::emst::DualTreeBoruvka< MetricType, MatType, TreeType >::tree

private

Pointer to the root of the tree.

Definition at line 93 of file dtb.hpp.

The documentation for this class was generated from the following file:

src/mlpack/methods/emst/dtb.hpp

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

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 >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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 >