MLPACK  1.0.10
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  const 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 MetricType metric = MetricType());
149 
167  DualTreeBoruvka(TreeType* tree,
168  const typename TreeType::Mat& dataset,
169  const MetricType metric = MetricType());
170 
175 
185  void ComputeMST(arma::mat& results);
186 
190  std::string ToString() const;
191 
192  private:
196  void AddEdge(const size_t e1, const size_t e2, const double distance);
197 
201  void AddAllEdges();
202 
206  void EmitResults(arma::mat& results);
207 
212  void CleanupHelper(TreeType* tree);
213 
217  void Cleanup();
218 
219 }; // class DualTreeBoruvka
220 
221 }; // namespace emst
222 }; // namespace mlpack
223 
224 #include "dtb_impl.hpp"
225 
226 #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:105
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
DualTreeBoruvka(const typename TreeType::Mat &dataset, const bool naive=false, const MetricType metric=MetricType())
Create the tree from the given dataset.
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
std::string ToString() const
Returns a string representation of this object.
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
const 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