DualTreeBoruvka< MetricType, MatType, TreeType > Class Template Reference

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

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

Tree

typedef TreeType<MetricType, DTBStat, MatType> Tree

Convenience typedef.

Definition at line 87 of file dtb.hpp.

Constructor & Destructor Documentation

DualTreeBoruvka() [1/2]

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

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() [2/2]

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.

~DualTreeBoruvka()

~DualTreeBoruvka

(

)

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

Member Function Documentation

ComputeMST()

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.

Parameters

results

Matrix which results will be stored in.

---

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

• /home/ryan/src/mlpack.org/_src/mlpack-git/src/mlpack/methods/emst/dtb.hpp