dual_tree_traverser.hpp
Go to the documentation of this file.
1 
12 #ifndef MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
13 #define MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
14 
15 #include <mlpack/prereqs.hpp>
16 #include <queue>
17 
18 namespace mlpack {
19 namespace tree {
20 
21 template<
22  typename MetricType,
23  typename StatisticType,
24  typename MatType,
25  typename RootPointPolicy
26 >
27 template<typename RuleType>
28 class CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>::
29  DualTreeTraverser
30 {
31  public:
35  DualTreeTraverser(RuleType& rule);
36 
43  void Traverse(CoverTree& queryNode, CoverTree& referenceNode);
44 
46  size_t NumPrunes() const { return numPrunes; }
48  size_t& NumPrunes() { return numPrunes; }
49 
52  size_t NumVisited() const { return 0; }
53  size_t NumScores() const { return 0; }
54  size_t NumBaseCases() const { return 0; }
55 
56  private:
58  RuleType& rule;
59 
61  size_t numPrunes;
62 
64  struct DualCoverTreeMapEntry
65  {
68  referenceNode;
70  double score;
72  double baseCase;
74  typename RuleType::TraversalInfoType traversalInfo;
75 
77  bool operator<(const DualCoverTreeMapEntry& other) const
78  {
79  if (score == other.score)
80  return (baseCase < other.baseCase);
81  else
82  return (score < other.score);
83  }
84  };
85 
89  void Traverse(
90  CoverTree& queryNode,
91  std::map<int, std::vector<DualCoverTreeMapEntry>,
92  std::greater<int>>& referenceMap);
93 
95  void PruneMap(
96  CoverTree& queryNode,
97  std::map<int, std::vector<DualCoverTreeMapEntry>,
98  std::greater<int>>& referenceMap,
99  std::map<int, std::vector<DualCoverTreeMapEntry>,
100  std::greater<int>>& childMap);
101 
102  void ReferenceRecursion(
103  CoverTree& queryNode,
104  std::map<int, std::vector<DualCoverTreeMapEntry>,
105  std::greater<int>>& referenceMap);
106 };
107 
108 } // namespace tree
109 } // namespace mlpack
110 
111 // Include implementation.
112 #include "dual_tree_traverser_impl.hpp"
113 
114 #endif
Linear algebra utility functions, generally performed on matrices or vectors.
The core includes that mlpack expects; standard C++ includes and Armadillo.
size_t & NumPrunes()
Modify the number of pruned nodes.
size_t NumPrunes() const
Get the number of pruned nodes.
CoverTree()
A default constructor.
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
Definition: cover_tree.hpp:99
bool operator<(basic_string_view< CharT, Traits > lhs, basic_string_view< CharT, Traits > rhs) noexcept