mlpack  2.0.1
dtb.hpp
Go to the documentation of this file.
1 
27 #ifndef __MLPACK_METHODS_EMST_DTB_HPP
28 #define __MLPACK_METHODS_EMST_DTB_HPP
29 
30 #include "dtb_stat.hpp"
31 #include "edge_pair.hpp"
32 
33 #include <mlpack/core.hpp>
35 
37 
38 namespace mlpack {
39 namespace emst {
40 
78 template<
79  typename MetricType = metric::EuclideanDistance,
80  typename MatType = arma::mat,
81  template<typename TreeMetricType,
82  typename TreeStatType,
83  typename TreeMatType> class TreeType = tree::KDTree
84 >
86 {
87  public:
89  typedef TreeType<MetricType, DTBStat, MatType> Tree;
90 
91  private:
93  std::vector<size_t> oldFromNew;
95  Tree* tree;
97  const MatType& data;
99  bool ownTree;
100 
102  bool naive;
103 
105  std::vector<EdgePair> edges; // We must use vector with non-numerical types.
106 
109 
111  arma::Col<size_t> neighborsInComponent;
113  arma::Col<size_t> neighborsOutComponent;
116 
118  double totalDist;
119 
121  MetricType metric;
122 
125  {
126  bool operator()(const EdgePair& pairA, const EdgePair& pairB)
127  {
128  return (pairA.Distance() < pairB.Distance());
129  }
130  } SortFun;
131 
132  public:
141  DualTreeBoruvka(const MatType& dataset,
142  const bool naive = false,
143  const MetricType metric = MetricType());
144 
162  DualTreeBoruvka(Tree* tree,
163  const MetricType metric = MetricType());
164 
169 
179  void ComputeMST(arma::mat& results);
180 
181  private:
185  void AddEdge(const size_t e1, const size_t e2, const double distance);
186 
190  void AddAllEdges();
191 
195  void EmitResults(arma::mat& results);
196 
201  void CleanupHelper(Tree* tree);
202 
206  void Cleanup();
207 
208 }; // class DualTreeBoruvka
209 
210 } // namespace emst
211 } // namespace mlpack
212 
213 #include "dtb_impl.hpp"
214 
215 #endif // __MLPACK_METHODS_EMST_DTB_HPP
bool naive
Indicates whether or not O(n^2) naive mode will be used.
Definition: dtb.hpp:102
A Union-Find data structure.
Definition: union_find.hpp:32
An edge pair is simply two indices and a distance.
Definition: edge_pair.hpp:30
const MatType & data
Reference to the data (this is what should be used for accessing data).
Definition: dtb.hpp:97
Linear algebra utility functions, generally performed on matrices or vectors.
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:113
std::vector< EdgePair > edges
Edges.
Definition: dtb.hpp:105
struct mlpack::emst::DualTreeBoruvka::SortEdgesHelper SortFun
void Cleanup()
The values stored in the tree must be reset on each iteration.
MetricType metric
The instantiated metric.
Definition: dtb.hpp:121
bool ownTree
Indicates whether or not we "own" the tree.
Definition: dtb.hpp:99
A binary space partitioning tree, such as a KD-tree or a ball tree.
double Distance() const
Get the distance.
Definition: edge_pair.hpp:65
void ComputeMST(arma::mat &results)
Iteratively find the nearest neighbor of each component until the MST is complete.
arma::Col< size_t > neighborsOutComponent
List of edge nodes.
Definition: dtb.hpp:113
bool operator()(const EdgePair &pairA, const EdgePair &pairB)
Definition: dtb.hpp:126
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
DualTreeBoruvka(const MatType &dataset, const bool naive=false, const MetricType metric=MetricType())
Create the tree from the given dataset.
void EmitResults(arma::mat &results)
Unpermute the edge list and output it to results.
double totalDist
Total distance of the tree.
Definition: dtb.hpp:118
~DualTreeBoruvka()
Delete the tree, if it was created inside the object.
std::vector< size_t > oldFromNew
Permutations of points during tree building.
Definition: dtb.hpp:93
TreeType< MetricType, DTBStat, MatType > Tree
Convenience typedef.
Definition: dtb.hpp:89
For sorting the edge list after the computation.
Definition: dtb.hpp:124
arma::vec neighborsDistances
List of edge distances.
Definition: dtb.hpp:115
void CleanupHelper(Tree *tree)
This function resets the values in the nodes of the tree nearest neighbor distance, and checks for fully connected nodes.
UnionFind connections
Connections.
Definition: dtb.hpp:108
arma::Col< size_t > neighborsInComponent
List of edge nodes.
Definition: dtb.hpp:111
Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree...
Definition: dtb.hpp:85
Tree * tree
Pointer to the root of the tree.
Definition: dtb.hpp:95
void AddEdge(const size_t e1, const size_t e2, const double distance)
Adds a single edge to the edge list.
void AddAllEdges()
Adds all the edges found in one iteration to the list of neighbors.