12 #ifndef MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
13 #define MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
18 #include "../statistic.hpp"
95 template<
typename MetricType = metric::LMetric<2, true>,
96 typename StatisticType = EmptyStatistic,
97 typename MatType = arma::mat,
98 typename RootPo
intPolicy = FirstPo
intIsRoot>
119 MetricType* metric = NULL);
189 const size_t pointIndex,
193 arma::Col<size_t>& indices,
194 arma::vec& distances,
198 MetricType& metric = NULL);
218 const size_t pointIndex,
222 const ElemType furthestDescendantDistance,
223 MetricType* metric = NULL);
244 template<
typename Archive>
247 const typename boost::enable_if<typename Archive::is_loading>::type* = 0);
256 template<
typename RuleType>
260 template<
typename RuleType>
263 template<
typename RuleType>
267 const MatType&
Dataset()
const {
return *dataset; }
270 size_t Point()
const {
return point; }
272 size_t Point(
const size_t)
const {
return point; }
274 bool IsLeaf()
const {
return (children.size() == 0); }
288 const std::vector<CoverTree*>&
Children()
const {
return children; }
290 std::vector<CoverTree*>&
Children() {
return children; }
309 const StatisticType&
Stat()
const {
return stat; }
311 StatisticType&
Stat() {
return stat; }
317 template<
typename VecType>
319 const VecType& point,
326 template<
typename VecType>
328 const VecType& point,
402 {
return furthestDescendantDistance; }
414 center = arma::vec(dataset->col(point));
418 MetricType&
Metric()
const {
return *metric; }
422 const MatType* dataset;
426 std::vector<CoverTree*> children;
434 size_t numDescendants;
440 ElemType furthestDescendantDistance;
451 void CreateChildren(arma::Col<size_t>& indices,
452 arma::vec& distances,
455 size_t& usedSetSize);
468 void ComputeDistances(
const size_t pointIndex,
469 const arma::Col<size_t>& indices,
470 arma::vec& distances,
471 const size_t pointSetSize);
486 size_t SplitNearFar(arma::Col<size_t>& indices,
487 arma::vec& distances,
489 const size_t pointSetSize);
510 size_t SortPointSet(arma::Col<size_t>& indices,
511 arma::vec& distances,
512 const size_t childFarSetSize,
513 const size_t childUsedSetSize,
514 const size_t farSetSize);
516 void MoveToUsedSet(arma::Col<size_t>& indices,
517 arma::vec& distances,
521 arma::Col<size_t>& childIndices,
522 const size_t childFarSetSize,
523 const size_t childUsedSetSize);
524 size_t PruneFarSet(arma::Col<size_t>& indices,
525 arma::vec& distances,
527 const size_t nearSetSize,
528 const size_t pointSetSize);
534 void RemoveNewImplicitNodes();
546 friend class boost::serialization::access;
552 template<
typename Archive>
553 void Serialize(Archive& ar,
const unsigned int );
559 size_t distanceComps;
566 #include "cover_tree_impl.hpp"
569 #include "../cover_tree.hpp"
size_t DistanceComps() const
ElemType ParentDistance() const
Get the distance to the parent.
MatType Mat
So that other classes can access the matrix type.
A dual-tree cover tree traverser; see dual_tree_traverser.hpp.
size_t Point(const size_t) const
For compatibility with other trees; the argument is ignored.
CoverTree * Parent() const
Get the parent node.
void Center(arma::vec ¢er) const
Get the center of the node and store it in the given vector.
MatType::elem_type ElemType
The type held by the matrix type.
The core includes that mlpack expects; standard C++ includes and Armadillo.
const MatType & Dataset() const
Get a reference to the dataset.
ElemType & FurthestDescendantDistance()
Modify the distance from the center of the node to the furthest descendant.
MetricType & Metric() const
Get the instantiated metric.
size_t GetFurthestChild(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0)
Return the index of the furthest child node to the given query point.
int & Scale()
Modify the scale of this node. Be careful...
int Scale() const
Get the scale of this node.
ElemType FurthestDescendantDistance() const
Get the distance from the center of the node to the furthest descendant.
ElemType Base() const
Get the base.
StatisticType & Stat()
Modify the statistic for this node.
CoverTree()
A default constructor.
size_t NumDescendants() const
Get the number of descendant points.
size_t Descendant(const size_t index) const
Get the index of a particular descendant point.
CoverTree *& Parent()
Modify the parent node.
ElemType FurthestPointDistance() const
Get the distance to the furthest point. This is always 0 for cover trees.
const StatisticType & Stat() const
Get the statistic for this node.
size_t NumChildren() const
Get the number of children.
ElemType MaxDistance(const CoverTree &other) const
Return the maximum distance to another node.
std::vector< CoverTree * > & Children()
Modify the children manually (maybe not a great idea).
size_t GetNearestChild(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0)
Return the index of the nearest child node to the given query point.
size_t Point() const
Get the index of the point which this node represents.
~CoverTree()
Delete this cover tree node and its children.
math::RangeType< ElemType > RangeDistance(const CoverTree &other) const
Return the minimum and maximum distance to another node.
CoverTree *& ChildPtr(const size_t index)
A single-tree cover tree traverser; see single_tree_traverser.hpp for implementation.
ElemType MinimumBoundDistance() const
Get the minimum distance from the center to any bound edge (this is the same as furthestDescendantDis...
const CoverTree & Child(const size_t index) const
Get a particular child node.
ElemType & Base()
Modify the base; don't do this, you'll break everything.
const std::vector< CoverTree * > & Children() const
Get the children.
ElemType MinDistance(const CoverTree &other) const
Return the minimum distance to another node.
Definition of the Range class, which represents a simple range with a lower and upper bound...
CoverTree & Child(const size_t index)
Modify a particular child node.
A cover tree is a tree specifically designed to speed up nearest-neighbor computation in high-dimensi...
ElemType & ParentDistance()
Modify the distance to the parent.
If value == true, then VecType is some sort of Armadillo vector or subview.
void Serialize(Archive &ar, const unsigned int)
Serialize the tree.