MLPACK  1.0.8
dtb.hpp
Go to the documentation of this file.
1 
35 #ifndef __MLPACK_METHODS_EMST_DTB_HPP
36 #define __MLPACK_METHODS_EMST_DTB_HPP
37 
38 #include "dtb_stat.hpp"
39 #include "edge_pair.hpp"
40 
41 #include <mlpack/core.hpp>
43 
45 
46 namespace mlpack {
47 namespace emst {
48 
87 template<
88  typename MetricType = metric::EuclideanDistance,
90 >
92 {
93  private:
95  typename TreeType::Mat dataCopy;
97  typename TreeType::Mat& data;
98 
100  TreeType* tree;
102  bool ownTree;
103 
105  bool naive;
106 
108  std::vector<EdgePair> edges; // We must use vector with non-numerical types.
109 
112 
114  std::vector<size_t> oldFromNew;
116  arma::Col<size_t> neighborsInComponent;
118  arma::Col<size_t> neighborsOutComponent;
121 
123  double totalDist;
124 
126  MetricType metric;
127 
130  {
131  bool operator()(const EdgePair& pairA, const EdgePair& pairB)
132  {
133  return (pairA.Distance() < pairB.Distance());
134  }
135  } SortFun;
136 
137  public:
146  DualTreeBoruvka(const typename TreeType::Mat& dataset,
147  const bool naive = false,
148  const size_t leafSize = 1,
149  const MetricType metric = MetricType());
150 
168  DualTreeBoruvka(TreeType* tree, const typename TreeType::Mat& dataset,
169  const MetricType metric = MetricType());
170 
175 
185  void ComputeMST(arma::mat& results);
186 
187  private:
191  void AddEdge(const size_t e1, const size_t e2, const double distance);
192 
196  void AddAllEdges();
197 
201  void EmitResults(arma::mat& results);
202 
207  void CleanupHelper(TreeType* tree);
208 
212  void Cleanup();
213 
214 }; // class DualTreeBoruvka
215 
216 }; // namespace emst
217 }; // namespace mlpack
218 
219 #include "dtb_impl.hpp"
220 
221 #endif // __MLPACK_METHODS_EMST_DTB_HPP
void AddEdge(const size_t e1, const size_t e2, const double distance)
Adds a single edge to the edge list.
A Union-Find data structure.
Definition: union_find.hpp:40
An edge pair is simply two indices and a distance.
Definition: edge_pair.hpp:38
TreeType * tree
Pointer to the root of the tree.
Definition: dtb.hpp:100
arma::Col< size_t > neighborsInComponent
List of edge nodes.
Definition: dtb.hpp:116
void ComputeMST(arma::mat &results)
Iteratively find the nearest neighbor of each component until the MST is complete.
LMetric< 2, true > EuclideanDistance
Definition: lmetric.hpp:104
void AddAllEdges()
Adds all the edges found in one iteration to the list of neighbors.
arma::vec neighborsDistances
List of edge distances.
Definition: dtb.hpp:120
bool naive
Indicates whether or not O(n^2) naive mode will be used.
Definition: dtb.hpp:105
UnionFind connections
Connections.
Definition: dtb.hpp:111
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.
struct mlpack::emst::DualTreeBoruvka::SortEdgesHelper SortFun
A binary space partitioning tree, such as a KD-tree or a ball tree.
~DualTreeBoruvka()
Delete the tree, if it was created inside the object.
void CleanupHelper(TreeType *tree)
This function resets the values in the nodes of the tree nearest neighbor distance, and checks for fully connected nodes.
void Cleanup()
The values stored in the tree must be reset on each iteration.
void EmitResults(arma::mat &results)
Unpermute the edge list and output it to results.
bool ownTree
Indicates whether or not we "own" the tree.
Definition: dtb.hpp:102
MetricType metric
The instantiated metric.
Definition: dtb.hpp:126
double totalDist
Total distance of the tree.
Definition: dtb.hpp:123
bool operator()(const EdgePair &pairA, const EdgePair &pairB)
Definition: dtb.hpp:131
arma::Col< size_t > neighborsOutComponent
List of edge nodes.
Definition: dtb.hpp:118
std::vector< EdgePair > edges
Edges.
Definition: dtb.hpp:108
TreeType::Mat dataCopy
Copy of the data (if necessary).
Definition: dtb.hpp:95
A statistic for use with MLPACK trees, which stores the upper bound on distance to nearest neighbors ...
Definition: dtb_stat.hpp:34
For sorting the edge list after the computation.
Definition: dtb.hpp:129
TreeType::Mat & data
Reference to the data (this is what should be used for accessing data).
Definition: dtb.hpp:97
Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree...
Definition: dtb.hpp:91
double Distance() const
Get the distance.
Definition: edge_pair.hpp:73
std::vector< size_t > oldFromNew
Permutations of points during tree building.
Definition: dtb.hpp:114