mlpack  2.0.1
dual_tree_traverser.hpp
Go to the documentation of this file.
1 
14 #ifndef __MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
15 #define __MLPACK_CORE_TREE_COVER_TREE_DUAL_TREE_TRAVERSER_HPP
16 
17 #include <mlpack/core.hpp>
18 #include <queue>
19 
20 namespace mlpack {
21 namespace tree {
22 
23 template<
24  typename MetricType,
25  typename StatisticType,
26  typename MatType,
27  typename RootPointPolicy
28 >
29 template<typename RuleType>
30 class CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>::
32 {
33  public:
37  DualTreeTraverser(RuleType& rule);
38 
45  void Traverse(CoverTree& queryNode, CoverTree& referenceNode);
46 
48  size_t NumPrunes() const { return numPrunes; }
50  size_t& NumPrunes() { return numPrunes; }
51 
54  size_t NumVisited() const { return 0; }
55  size_t NumScores() const { return 0; }
56  size_t NumBaseCases() const { return 0; }
57 
58  private:
60  RuleType& rule;
61 
63  size_t numPrunes;
64 
67  {
72  double score;
74  double baseCase;
76  typename RuleType::TraversalInfoType traversalInfo;
77 
79  bool operator<(const DualCoverTreeMapEntry& other) const
80  {
81  if (score == other.score)
82  return (baseCase < other.baseCase);
83  else
84  return (score < other.score);
85  }
86  };
87 
91  void Traverse(CoverTree& queryNode,
92  std::map<int, std::vector<DualCoverTreeMapEntry> >&
93  referenceMap);
94 
96  void PruneMap(CoverTree& queryNode,
97  std::map<int, std::vector<DualCoverTreeMapEntry> >&
98  referenceMap,
99  std::map<int, std::vector<DualCoverTreeMapEntry> >&
100  childMap);
101 
102  void ReferenceRecursion(CoverTree& queryNode,
103  std::map<int, std::vector<DualCoverTreeMapEntry> >&
104  referenceMap);
105 };
106 
107 } // namespace tree
108 } // namespace mlpack
109 
110 // Include implementation.
111 #include "dual_tree_traverser_impl.hpp"
112 
113 #endif
A dual-tree cover tree traverser; see dual_tree_traverser.hpp.
Definition: cover_tree.hpp:249
Linear algebra utility functions, generally performed on matrices or vectors.
size_t NumPrunes() const
Get the number of pruned nodes.
RuleType & rule
The instantiated rule set for pruning branches.
RuleType::TraversalInfoType traversalInfo
The traversal info associated with the call to Score() for this entry.
size_t numPrunes
The number of pruned nodes.
CoverTree< MetricType, StatisticType, MatType, RootPointPolicy > * referenceNode
The node this entry refers to.
bool operator<(const DualCoverTreeMapEntry &other) const
Comparison operator, for sorting within the map.
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
size_t & NumPrunes()
Modify the number of pruned nodes.
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
Definition: cover_tree.hpp:98