MLPACK  1.0.7
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 "edge_pair.hpp"
39 
40 #include <mlpack/core.hpp>
42 
44 
45 namespace mlpack {
46 namespace emst {
47 
52 class DTBStat
53 {
54  private:
58 
62 
64  double bound;
65 
71 
72  public:
77  DTBStat();
78 
86  template<typename TreeType>
87  DTBStat(const TreeType& node);
88 
90  double MaxNeighborDistance() const { return maxNeighborDistance; }
93 
95  double MinNeighborDistance() const { return minNeighborDistance; }
98 
100  double Bound() const { return bound; }
102  double& Bound() { return bound; }
103 
105  int ComponentMembership() const { return componentMembership; }
108 
109 }; // class DTBStat
110 
149 template<
150  typename MetricType = metric::EuclideanDistance,
151  typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>
152 >
154 {
155  private:
157  typename TreeType::Mat dataCopy;
159  typename TreeType::Mat& data;
160 
162  TreeType* tree;
164  bool ownTree;
165 
167  bool naive;
168 
170  std::vector<EdgePair> edges; // We must use vector with non-numerical types.
171 
174 
176  std::vector<size_t> oldFromNew;
178  arma::Col<size_t> neighborsInComponent;
180  arma::Col<size_t> neighborsOutComponent;
183 
185  double totalDist;
186 
188  MetricType metric;
189 
192  {
193  bool operator()(const EdgePair& pairA, const EdgePair& pairB)
194  {
195  return (pairA.Distance() < pairB.Distance());
196  }
197  } SortFun;
198 
199  public:
208  DualTreeBoruvka(const typename TreeType::Mat& dataset,
209  const bool naive = false,
210  const size_t leafSize = 1,
211  const MetricType metric = MetricType());
212 
230  DualTreeBoruvka(TreeType* tree, const typename TreeType::Mat& dataset,
231  const MetricType metric = MetricType());
232 
237 
247  void ComputeMST(arma::mat& results);
248 
249  private:
253  void AddEdge(const size_t e1, const size_t e2, const double distance);
254 
258  void AddAllEdges();
259 
263  void EmitResults(arma::mat& results);
264 
269  void CleanupHelper(TreeType* tree);
270 
274  void Cleanup();
275 
276 }; // class DualTreeBoruvka
277 
278 }; // namespace emst
279 }; // namespace mlpack
280 
281 #include "dtb_impl.hpp"
282 
283 #endif // __MLPACK_METHODS_EMST_DTB_HPP
double minNeighborDistance
Lower bound on the distance to the nearest neighbor of any point in this node.
Definition: dtb.hpp:61
void AddEdge(const size_t e1, const size_t e2, const double distance)
Adds a single edge to the edge list.
double MaxNeighborDistance() const
Get the maximum neighbor distance.
Definition: dtb.hpp:90
A Union-Find data structure.
Definition: union_find.hpp:40
double & Bound()
Modify the total bound for pruning.
Definition: dtb.hpp:102
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:162
arma::Col< size_t > neighborsInComponent
List of edge nodes.
Definition: dtb.hpp:178
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.
int componentMembership
The index of the component that all points in this node belong to.
Definition: dtb.hpp:70
arma::vec neighborsDistances
List of edge distances.
Definition: dtb.hpp:182
bool naive
Indicates whether or not O(n^2) naive mode will be used.
Definition: dtb.hpp:167
double & MaxNeighborDistance()
Modify the maximum neighbor distance.
Definition: dtb.hpp:92
UnionFind connections
Connections.
Definition: dtb.hpp:173
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 &quot;own&quot; the tree.
Definition: dtb.hpp:164
DTBStat()
A generic initializer.
int ComponentMembership() const
Get the component membership of this node.
Definition: dtb.hpp:105
double maxNeighborDistance
Upper bound on the distance to the nearest neighbor of any point in this node.
Definition: dtb.hpp:57
MetricType metric
The instantiated metric.
Definition: dtb.hpp:188
double totalDist
Total distance of the tree.
Definition: dtb.hpp:185
bool operator()(const EdgePair &pairA, const EdgePair &pairB)
Definition: dtb.hpp:193
arma::Col< size_t > neighborsOutComponent
List of edge nodes.
Definition: dtb.hpp:180
double MinNeighborDistance() const
Get the minimum neighbor distance.
Definition: dtb.hpp:95
int & ComponentMembership()
Modify the component membership of this node.
Definition: dtb.hpp:107
double bound
Total bound for pruning.
Definition: dtb.hpp:64
std::vector< EdgePair > edges
Edges.
Definition: dtb.hpp:170
TreeType::Mat dataCopy
Copy of the data (if necessary).
Definition: dtb.hpp:157
double & MinNeighborDistance()
Modify the minimum neighbor distance.
Definition: dtb.hpp:97
A statistic for use with MLPACK trees, which stores the upper bound on distance to nearest neighbors ...
Definition: dtb.hpp:52
For sorting the edge list after the computation.
Definition: dtb.hpp:191
TreeType::Mat & data
Reference to the data (this is what should be used for accessing data).
Definition: dtb.hpp:159
Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree...
Definition: dtb.hpp:153
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:176
double Bound() const
Get the total bound for pruning.
Definition: dtb.hpp:100