\section{Dual\+Tree\+Boruvka$<$ Metric\+Type, Mat\+Type, Tree\+Type $>$ Class Template Reference}
\label{classmlpack_1_1emst_1_1DualTreeBoruvka}\index{Dual\+Tree\+Boruvka$<$ Metric\+Type, Mat\+Type, Tree\+Type $>$@{Dual\+Tree\+Boruvka$<$ Metric\+Type, Mat\+Type, Tree\+Type $>$}}


Performs the M\+ST calculation using the Dual-\/\+Tree Boruvka algorithm, using any type of tree.  


\subsection*{Public Types}
\begin{DoxyCompactItemize}
\item 
typedef Tree\+Type$<$ Metric\+Type, \textbf{ D\+T\+B\+Stat}, Mat\+Type $>$ \textbf{ Tree}
\begin{DoxyCompactList}\small\item\em Convenience typedef. \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item 
\textbf{ Dual\+Tree\+Boruvka} (const Mat\+Type \&dataset, const bool naive=false, const Metric\+Type metric=Metric\+Type())
\begin{DoxyCompactList}\small\item\em Create the tree from the given dataset. \end{DoxyCompactList}\item 
\textbf{ Dual\+Tree\+Boruvka} (\textbf{ Tree} $\ast$tree, const Metric\+Type metric=Metric\+Type())
\begin{DoxyCompactList}\small\item\em Create the \doxyref{Dual\+Tree\+Boruvka}{p.}{classmlpack_1_1emst_1_1DualTreeBoruvka} object with an already initialized tree. \end{DoxyCompactList}\item 
\textbf{ $\sim$\+Dual\+Tree\+Boruvka} ()
\begin{DoxyCompactList}\small\item\em Delete the tree, if it was created inside the object. \end{DoxyCompactList}\item 
void \textbf{ Compute\+M\+ST} (arma\+::mat \&results)
\begin{DoxyCompactList}\small\item\em Iteratively find the nearest neighbor of each component until the M\+ST is complete. \end{DoxyCompactList}\end{DoxyCompactItemize}


\subsection{Detailed Description}
\subsubsection*{template$<$typename Metric\+Type = metric\+::\+Euclidean\+Distance, typename Mat\+Type = arma\+::mat, template$<$ typename Tree\+Metric\+Type, typename Tree\+Stat\+Type, typename Tree\+Mat\+Type $>$ class Tree\+Type = tree\+::\+K\+D\+Tree$>$\newline
class mlpack\+::emst\+::\+Dual\+Tree\+Boruvka$<$ Metric\+Type, Mat\+Type, Tree\+Type $>$}

Performs the M\+ST calculation using the Dual-\/\+Tree Boruvka algorithm, using any type of tree. 

For more information on the algorithm, see the following citation\+:


\begin{DoxyCode}
@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\}
\}
\end{DoxyCode}


General usage of this class might be like this\+:


\begin{DoxyCode}
\textcolor{keyword}{extern} arma::mat data; \textcolor{comment}{// We want to find the MST of this dataset.}
DualTreeBoruvka<> dtb(data); \textcolor{comment}{// Create the tree with default options.}

\textcolor{comment}{// Find the MST.}
arma::mat mstResults;
dtb.ComputeMST(mstResults);
\end{DoxyCode}


More advanced usage of the class can use different types of trees, pass in an already-\/built tree, or compute the M\+ST using the O(n$^\wedge$2) naive algorithm.


\begin{DoxyTemplParams}{Template Parameters}
{\em Metric\+Type} & The metric to use. \\
\hline
{\em Mat\+Type} & The type of data matrix to use. \\
\hline
{\em Tree\+Type} & Type of tree to use. This should follow the Tree\+Type policy A\+PI. \\
\hline
\end{DoxyTemplParams}


Definition at line 83 of file dtb.\+hpp.



\subsection{Member Typedef Documentation}
\mbox{\label{classmlpack_1_1emst_1_1DualTreeBoruvka_add9de6c53980696f4a41e4d1d3b71942}} 
\index{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}!Tree@{Tree}}
\index{Tree@{Tree}!mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}}
\subsubsection{Tree}
{\footnotesize\ttfamily typedef Tree\+Type$<$Metric\+Type, \textbf{ D\+T\+B\+Stat}, Mat\+Type$>$ \textbf{ Tree}}



Convenience typedef. 



Definition at line 87 of file dtb.\+hpp.



\subsection{Constructor \& Destructor Documentation}
\mbox{\label{classmlpack_1_1emst_1_1DualTreeBoruvka_ace5bd00e87dc4694e14549f154aaef4e}} 
\index{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}!Dual\+Tree\+Boruvka@{Dual\+Tree\+Boruvka}}
\index{Dual\+Tree\+Boruvka@{Dual\+Tree\+Boruvka}!mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}}
\subsubsection{Dual\+Tree\+Boruvka()\hspace{0.1cm}{\footnotesize\ttfamily [1/2]}}
{\footnotesize\ttfamily \textbf{ Dual\+Tree\+Boruvka} (\begin{DoxyParamCaption}\item[{const Mat\+Type \&}]{dataset,  }\item[{const bool}]{naive = {\ttfamily false},  }\item[{const Metric\+Type}]{metric = {\ttfamily MetricType()} }\end{DoxyParamCaption})}



Create the tree from the given dataset. 

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


\begin{DoxyParams}{Parameters}
{\em data} & Dataset to build a tree for. \\
\hline
{\em naive} & Whether the computation should be done in O(n$^\wedge$2) naive mode. \\
\hline
{\em metric} & An optional instantiated metric to use. \\
\hline
\end{DoxyParams}
\mbox{\label{classmlpack_1_1emst_1_1DualTreeBoruvka_aa7be00b83431cd517b956c46913e6a72}} 
\index{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}!Dual\+Tree\+Boruvka@{Dual\+Tree\+Boruvka}}
\index{Dual\+Tree\+Boruvka@{Dual\+Tree\+Boruvka}!mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}}
\subsubsection{Dual\+Tree\+Boruvka()\hspace{0.1cm}{\footnotesize\ttfamily [2/2]}}
{\footnotesize\ttfamily \textbf{ Dual\+Tree\+Boruvka} (\begin{DoxyParamCaption}\item[{\textbf{ Tree} $\ast$}]{tree,  }\item[{const Metric\+Type}]{metric = {\ttfamily MetricType()} }\end{DoxyParamCaption})}



Create the \doxyref{Dual\+Tree\+Boruvka}{p.}{classmlpack_1_1emst_1_1DualTreeBoruvka} 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. leaf\+Size = number of points).

\begin{DoxyNote}{Note}
Because tree-\/building (at least with Binary\+Space\+Tree) 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. 
\end{DoxyNote}

\begin{DoxyParams}{Parameters}
{\em tree} & Pre-\/built tree. \\
\hline
{\em metric} & An optional instantiated metric to use. \\
\hline
\end{DoxyParams}
\mbox{\label{classmlpack_1_1emst_1_1DualTreeBoruvka_ae413c24d961195f2ae5fd856454900f0}} 
\index{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}!````~Dual\+Tree\+Boruvka@{$\sim$\+Dual\+Tree\+Boruvka}}
\index{````~Dual\+Tree\+Boruvka@{$\sim$\+Dual\+Tree\+Boruvka}!mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}}
\subsubsection{$\sim$\+Dual\+Tree\+Boruvka()}
{\footnotesize\ttfamily $\sim$\textbf{ Dual\+Tree\+Boruvka} (\begin{DoxyParamCaption}{ }\end{DoxyParamCaption})}



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



\subsection{Member Function Documentation}
\mbox{\label{classmlpack_1_1emst_1_1DualTreeBoruvka_a47d46f4bccd05a45cfe752c4630088ef}} 
\index{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}!Compute\+M\+ST@{Compute\+M\+ST}}
\index{Compute\+M\+ST@{Compute\+M\+ST}!mlpack\+::emst\+::\+Dual\+Tree\+Boruvka@{mlpack\+::emst\+::\+Dual\+Tree\+Boruvka}}
\subsubsection{Compute\+M\+S\+T()}
{\footnotesize\ttfamily void Compute\+M\+ST (\begin{DoxyParamCaption}\item[{arma\+::mat \&}]{results }\end{DoxyParamCaption})}



Iteratively find the nearest neighbor of each component until the M\+ST 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.


\begin{DoxyParams}{Parameters}
{\em results} & Matrix which results will be stored in. \\
\hline
\end{DoxyParams}


The documentation for this class was generated from the following file\+:\begin{DoxyCompactItemize}
\item 
/var/www/mlpack.\+ratml.\+org/mlpack.\+org/\+\_\+src/mlpack-\/3.\+3.\+0/src/mlpack/methods/emst/\textbf{ dtb.\+hpp}\end{DoxyCompactItemize}
