mlpack  1.0.12
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 
79 template<
80  typename MetricType = metric::EuclideanDistance,
82 >
84 {
85  private:
87  typename TreeType::Mat dataCopy;
89  const typename TreeType::Mat& data;
90 
92  TreeType* tree;
94  bool ownTree;
95 
97  bool naive;
98 
100  std::vector<EdgePair> edges; // We must use vector with non-numerical types.
101 
104 
106  std::vector<size_t> oldFromNew;
108  arma::Col<size_t> neighborsInComponent;
110  arma::Col<size_t> neighborsOutComponent;
113 
115  double totalDist;
116 
118  MetricType metric;
119 
122  {
123  bool operator()(const EdgePair& pairA, const EdgePair& pairB)
124  {
125  return (pairA.Distance() < pairB.Distance());
126  }
127  } SortFun;
128 
129  public:
138  DualTreeBoruvka(const typename TreeType::Mat& dataset,
139  const bool naive = false,
140  const MetricType metric = MetricType());
141 
159  DualTreeBoruvka(TreeType* tree,
160  const typename TreeType::Mat& dataset,
161  const MetricType metric = MetricType());
162 
167 
177  void ComputeMST(arma::mat& results);
178 
182  std::string ToString() const;
183 
184  private:
188  void AddEdge(const size_t e1, const size_t e2, const double distance);
189 
193  void AddAllEdges();
194 
198  void EmitResults(arma::mat& results);
199 
204  void CleanupHelper(TreeType* tree);
205 
209  void Cleanup();
210 
211 }; // class DualTreeBoruvka
212 
213 }; // namespace emst
214 }; // namespace mlpack
215 
216 #include "dtb_impl.hpp"
217 
218 #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:32
An edge pair is simply two indices and a distance.
Definition: edge_pair.hpp:30
TreeType * tree
Pointer to the root of the tree.
Definition: dtb.hpp:92
arma::Col< size_t > neighborsInComponent
List of edge nodes.
Definition: dtb.hpp:108
void ComputeMST(arma::mat &results)
Iteratively find the nearest neighbor of each component until the MST is complete.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: load.hpp:23
LMetric< 2, true > EuclideanDistance
Definition: lmetric.hpp:97
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:112
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:97
UnionFind connections
Connections.
Definition: dtb.hpp:103
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:94
MetricType metric
The instantiated metric.
Definition: dtb.hpp:118
double totalDist
Total distance of the tree.
Definition: dtb.hpp:115
bool operator()(const EdgePair &pairA, const EdgePair &pairB)
Definition: dtb.hpp:123
arma::Col< size_t > neighborsOutComponent
List of edge nodes.
Definition: dtb.hpp:110
std::vector< EdgePair > edges
Edges.
Definition: dtb.hpp:100
TreeType::Mat dataCopy
Copy of the data (if necessary).
Definition: dtb.hpp:87
A statistic for use with MLPACK trees, which stores the upper bound on distance to nearest neighbors ...
Definition: dtb_stat.hpp:26
For sorting the edge list after the computation.
Definition: dtb.hpp:121
const TreeType::Mat & data
Reference to the data (this is what should be used for accessing data).
Definition: dtb.hpp:89
Performs the MST calculation using the Dual-Tree Boruvka algorithm, using any type of tree...
Definition: dtb.hpp:83
double Distance() const
Get the distance.
Definition: edge_pair.hpp:65
std::vector< size_t > oldFromNew
Permutations of points during tree building.
Definition: dtb.hpp:106