mlpack 3.4.2
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
18namespace mlpack {
19namespace tree {
20
21template<
22 typename MetricType,
23 typename StatisticType,
24 typename MatType,
25 typename RootPointPolicy
26>
27template<typename RuleType>
28class CoverTree<MetricType, StatisticType, MatType, RootPointPolicy>::
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(CoverTree& queryNode,
90 std::map<int, std::vector<DualCoverTreeMapEntry> >&
91 referenceMap);
92
94 void PruneMap(CoverTree& queryNode,
95 std::map<int, std::vector<DualCoverTreeMapEntry> >&
96 referenceMap,
97 std::map<int, std::vector<DualCoverTreeMapEntry> >&
98 childMap);
99
100 void ReferenceRecursion(CoverTree& queryNode,
101 std::map<int, std::vector<DualCoverTreeMapEntry> >&
102 referenceMap);
103};
104
105} // namespace tree
106} // namespace mlpack
107
108// Include implementation.
109#include "dual_tree_traverser_impl.hpp"
110
111#endif
A dual-tree cover tree traverser; see dual_tree_traverser.hpp.
void Traverse(CoverTree &queryNode, CoverTree &referenceNode)
Traverse the two specified trees.
DualTreeTraverser(RuleType &rule)
Initialize the dual tree traverser with the given rule type.
size_t NumPrunes() const
Get the number of pruned nodes.
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:100
CoverTree()
A default constructor.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: cv.hpp:1
The core includes that mlpack expects; standard C++ includes and Armadillo.