dtb.hpp
Go to the documentation of this file.00001
00035 #ifndef __MLPACK_METHODS_EMST_DTB_HPP
00036 #define __MLPACK_METHODS_EMST_DTB_HPP
00037
00038 #include "dtb_stat.hpp"
00039 #include "edge_pair.hpp"
00040
00041 #include <mlpack/core.hpp>
00042 #include <mlpack/core/metrics/lmetric.hpp>
00043
00044 #include <mlpack/core/tree/binary_space_tree.hpp>
00045
00046 namespace mlpack {
00047 namespace emst {
00048
00087 template<
00088 typename MetricType = metric::EuclideanDistance,
00089 typename TreeType = tree::BinarySpaceTree<bound::HRectBound<2>, DTBStat>
00090 >
00091 class DualTreeBoruvka
00092 {
00093 private:
00095 typename TreeType::Mat dataCopy;
00097 typename TreeType::Mat& data;
00098
00100 TreeType* tree;
00102 bool ownTree;
00103
00105 bool naive;
00106
00108 std::vector<EdgePair> edges;
00109
00111 UnionFind connections;
00112
00114 std::vector<size_t> oldFromNew;
00116 arma::Col<size_t> neighborsInComponent;
00118 arma::Col<size_t> neighborsOutComponent;
00120 arma::vec neighborsDistances;
00121
00123 double totalDist;
00124
00126 MetricType metric;
00127
00129 struct SortEdgesHelper
00130 {
00131 bool operator()(const EdgePair& pairA, const EdgePair& pairB)
00132 {
00133 return (pairA.Distance() < pairB.Distance());
00134 }
00135 } SortFun;
00136
00137 public:
00146 DualTreeBoruvka(const typename TreeType::Mat& dataset,
00147 const bool naive = false,
00148 const size_t leafSize = 1,
00149 const MetricType metric = MetricType());
00150
00168 DualTreeBoruvka(TreeType* tree, const typename TreeType::Mat& dataset,
00169 const MetricType metric = MetricType());
00170
00174 ~DualTreeBoruvka();
00175
00185 void ComputeMST(arma::mat& results);
00186
00187 private:
00191 void AddEdge(const size_t e1, const size_t e2, const double distance);
00192
00196 void AddAllEdges();
00197
00201 void EmitResults(arma::mat& results);
00202
00207 void CleanupHelper(TreeType* tree);
00208
00212 void Cleanup();
00213
00214 };
00215
00216 };
00217 };
00218
00219 #include "dtb_impl.hpp"
00220
00221 #endif // __MLPACK_METHODS_EMST_DTB_HPP