[mlpack-svn] r12615 - mlpack/trunk/src/mlpack/core/tree

[fastlab-svn at coffeetalk-1.cc.gatech.edu]

Author: rcurtin
Date: 2012-05-03 20:12:44 -0400 (Thu, 03 May 2012)
New Revision: 12615

Modified:
   mlpack/trunk/src/mlpack/core/tree/cover_tree.hpp
   mlpack/trunk/src/mlpack/core/tree/cover_tree_impl.hpp
Log:
Modify CoverTree API towards a more standard API.  It can be used with
NeighborSearch now... although it probably will fail miserably.


Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree.hpp	2012-05-04 00:09:22 UTC (rev 12614)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree.hpp	2012-05-04 00:12:44 UTC (rev 12615)
@@ -10,6 +10,7 @@
 #include <mlpack/core.hpp>
 #include <mlpack/core/metrics/lmetric.hpp>
 #include "first_point_is_root.hpp"
+#include "traversers/single_tree_breadth_first_traverser.hpp"
 
 namespace mlpack {
 namespace tree {
@@ -87,6 +88,8 @@
 class CoverTree
 {
  public:
+  typedef arma::mat Mat;
+
   /**
    * Create the cover tree with the given dataset and given expansion constant.
    * The dataset will not be modified during the building procedure (unlike
@@ -144,12 +147,33 @@
    */
   ~CoverTree();
 
+  //! Define this tree's preferred traverser.
+  template<typename RuleType>
+  struct PreferredTraverser
+  {
+    typedef SingleTreeBreadthFirstTraverser<
+        CoverTree<MetricType, RootPointPolicy, StatisticType>,
+        RuleType
+    > Type;
+  };
+
   //! Get a reference to the dataset.
   const arma::mat& Dataset() const { return dataset; }
 
   //! Get the index of the point which this node represents.
   size_t Point() const { return point; }
+  //! For compatibility with other trees; the argument is ignored.
+  size_t Point(const size_t) const { return point; }
 
+  // Fake
+  CoverTree* Left() const { return NULL; }
+  CoverTree* Right() const { return NULL; }
+  size_t Begin() const { return 0; }
+  size_t Count() const { return 0; }
+  size_t End() const { return 0; }
+  bool IsLeaf() const { return (children.size() == 0); }
+  size_t NumPoints() const { return 1; }
+
   //! Get a particular child node.
   const CoverTree& Child(const size_t index) const { return *children[index]; }
   //! Modify a particular child node.
@@ -168,6 +192,26 @@
   //! Modify the expansion constant; don't do this, you'll break everything.
   double& ExpansionConstant() { return expansionConstant; }
 
+  //! Get the statistic for this node.
+  const StatisticType& Stat() const { return stat; }
+  //! Modify the statistic for this node.
+  StatisticType& Stat() { return stat; }
+
+  //! Return the minimum distance to another node.
+  double MinDistance(const CoverTree* other) const;
+
+  //! Return the minimum distance to another point.
+  double MinDistance(const arma::vec& other) const;
+
+  //! Return the maximum distance to another node.
+  double MaxDistance(const CoverTree* other) const;
+
+  //! Return the maximum distance to another point.
+  double MaxDistance(const arma::vec& other) const;
+
+  //! Returns true: this tree does have self-children.
+  static bool HasSelfChildren() { return true; }
+
  private:
   //! Reference to the matrix which this tree is built on.
   const arma::mat& dataset;

Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree_impl.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree_impl.hpp	2012-05-04 00:09:22 UTC (rev 12614)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree_impl.hpp	2012-05-04 00:12:44 UTC (rev 12615)
@@ -318,6 +318,43 @@
 }
 
 template<typename MetricType, typename RootPointPolicy, typename StatisticType>
+double CoverTree<MetricType, RootPointPolicy, StatisticType>::MinDistance(
+    const CoverTree<MetricType, RootPointPolicy, StatisticType>* other) const
+{
+  // Every cover tree node will contain points up to EC^(scale + 1) away.
+  return MetricType::Evaluate(dataset.col(point),
+      other->Dataset().col(other->Point())) -
+      std::pow(expansionConstant, scale + 1) -
+      std::pow(other->ExpansionConstant(), other->Scale() + 1);
+}
+
+template<typename MetricType, typename RootPointPolicy, typename StatisticType>
+double CoverTree<MetricType, RootPointPolicy, StatisticType>::MinDistance(
+    const arma::vec& other) const
+{
+  return MetricType::Evaluate(dataset.unsafe_col(point), other) -
+      std::pow(expansionConstant, scale + 1);
+}
+
+template<typename MetricType, typename RootPointPolicy, typename StatisticType>
+double CoverTree<MetricType, RootPointPolicy, StatisticType>::MaxDistance(
+    const CoverTree<MetricType, RootPointPolicy, StatisticType>* other) const
+{
+  return MetricType::Evaluate(dataset.col(point),
+      other->Dataset().col(other->Point())) +
+      std::pow(expansionConstant, scale + 1) +
+      std::pow(other->ExpansionConstant(), other->Scale() + 1);
+}
+
+template<typename MetricType, typename RootPointPolicy, typename StatisticType>
+double CoverTree<MetricType, RootPointPolicy, StatisticType>::MaxDistance(
+    const arma::vec& other) const
+{
+  return MetricType::Evaluate(dataset.unsafe_col(point), other) +
+      std::pow(expansionConstant, scale + 1);
+}
+
+template<typename MetricType, typename RootPointPolicy, typename StatisticType>
 size_t CoverTree<MetricType, RootPointPolicy, StatisticType>::SplitNearFar(
     arma::Col<size_t>& indices,
     arma::vec& distances,