MLPACK  1.0.10
dual_tree_traverser.hpp
Go to the documentation of this file.
1 
22 #ifndef __MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
23 #define __MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
24 
25 #include <mlpack/core.hpp>
26 #include <queue>
27 
28 namespace mlpack {
29 namespace tree {
30 
31 template<typename MetricType, typename RootPointPolicy, typename StatisticType>
32 template<typename RuleType>
33 class CoverTree<MetricType, RootPointPolicy, StatisticType>::DualTreeTraverser
34 {
35  public:
39  DualTreeTraverser(RuleType& rule);
40 
47  void Traverse(CoverTree& queryNode, CoverTree& referenceNode);
48 
50  size_t NumPrunes() const { return numPrunes; }
52  size_t& NumPrunes() { return numPrunes; }
53 
56  size_t NumVisited() const { return 0; }
57  size_t NumScores() const { return 0; }
58  size_t NumBaseCases() const { return 0; }
59 
60  private:
62  RuleType& rule;
63 
65  size_t numPrunes;
66 
69  {
73  double score;
75  double baseCase;
77  typename RuleType::TraversalInfoType traversalInfo;
78 
80  bool operator<(const DualCoverTreeMapEntry& other) const
81  {
82  if (score == other.score)
83  return (baseCase < other.baseCase);
84  else
85  return (score < other.score);
86  }
87  };
88 
92  void Traverse(CoverTree& queryNode,
93  std::map<int, std::vector<DualCoverTreeMapEntry> >&
94  referenceMap);
95 
97  void PruneMap(CoverTree& queryNode,
98  std::map<int, std::vector<DualCoverTreeMapEntry> >&
99  referenceMap,
100  std::map<int, std::vector<DualCoverTreeMapEntry> >&
101  childMap);
102 
103  void ReferenceRecursion(CoverTree& queryNode,
104  std::map<int, std::vector<DualCoverTreeMapEntry> >&
105  referenceMap);
106 };
107 
108 }; // namespace tree
109 }; // namespace mlpack
110 
111 // Include implementation.
112 #include "dual_tree_traverser_impl.hpp"
113 
114 #endif
bool operator<(const DualCoverTreeMapEntry &other) const
Comparison operator, for sorting within the map.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: load.hpp:31
size_t numPrunes
The number of pruned nodes.
CoverTree(const arma::mat &dataset, const double base=2.0, MetricType *metric=NULL)
Create the cover tree with the given dataset and given base.
size_t NumPrunes() const
Get the number of pruned nodes.
RuleType::TraversalInfoType traversalInfo
The traversal info associated with the call to Score() for this entry.
size_t & NumPrunes()
Modify the number of pruned nodes.
RuleType & rule
The instantiated rule set for pruning branches.
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
Definition: cover_tree.hpp:103
CoverTree< MetricType, RootPointPolicy, StatisticType > * referenceNode
The node this entry refers to.