mlpack
a scalable c++ machine learning library
docs
mlpack: src/mlpack/methods/emst/dtb.hpp Source File

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; // We must use vector with non-numerical types.
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 }; // class DualTreeBoruvka
00215 
00216 }; // namespace emst
00217 }; // namespace mlpack
00218 
00219 #include "dtb_impl.hpp"
00220 
00221 #endif // __mlpack_METHODS_EMST_DTB_HPP