[mlpack-svn] r12693 - in mlpack/trunk/src/mlpack/core/tree: . traversers

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

Author: rcurtin
Date: 2012-05-16 14:57:39 -0400 (Wed, 16 May 2012)
New Revision: 12693

Added:
   mlpack/trunk/src/mlpack/core/tree/traversers/dual_cover_tree_traverser.hpp
Modified:
   mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt
   mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp
Log:
Add preferred traverser and dual cover tree traverser (which doesn't prune at
the moment).


Modified: mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt	2012-05-16 18:46:38 UTC (rev 12692)
+++ mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt	2012-05-16 18:57:39 UTC (rev 12693)
@@ -21,6 +21,7 @@
   traversers/single_tree_depth_first_traverser.hpp
   traversers/dual_tree_depth_first_traverser.hpp
   traversers/dual_tree_breadth_first_traverser.hpp
+  traversers/dual_cover_tree_traverser.hpp
 )
 
 # add directory name to sources

Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp	2012-05-16 18:46:38 UTC (rev 12692)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp	2012-05-16 18:57:39 UTC (rev 12693)
@@ -11,7 +11,11 @@
 #include "statistic.hpp"
 
 #include "traversers/single_tree_depth_first_traverser.hpp"
+#include "traversers/dual_tree_depth_first_traverser.hpp"
 
+// Bad!
+#include <mlpack/methods/neighbor_search/neighbor_search_rules.hpp>
+
 namespace mlpack {
 namespace tree /** Trees and tree-building procedures. */ {
 
@@ -74,6 +78,22 @@
     > Type;
   };
 
+  template<typename RuleType>
+  struct PreferredDualTraverser
+  {
+    typedef DualTreeDepthFirstTraverser<
+        BinarySpaceTree<BoundType, StatisticType, MatType>,
+        RuleType
+    > Type;
+  };
+
+  template<typename SortPolicy, typename MetricType, typename TreeType>
+  struct PreferredRules
+  {
+    typedef neighbor::NeighborSearchRules<SortPolicy, MetricType, TreeType>
+        Type;
+  };
+
   /**
    * Construct this as the root node of a binary space tree using the given
    * dataset.  This will modify the ordering of the points in the dataset!

Added: mlpack/trunk/src/mlpack/core/tree/traversers/dual_cover_tree_traverser.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/traversers/dual_cover_tree_traverser.hpp	                        (rev 0)
+++ mlpack/trunk/src/mlpack/core/tree/traversers/dual_cover_tree_traverser.hpp	2012-05-16 18:57:39 UTC (rev 12693)
@@ -0,0 +1,91 @@
+/**
+ * @file dual_cover_tree_traverser.hpp
+ * @author Ryan Curtin
+ *
+ * A dual-tree traverser for the cover tree.
+ */
+#ifndef __MLPACK_CORE_TREE_DUAL_COVER_TREE_TRAVERSER_HPP
+#define __MLPACK_CORE_TREE_DUAL_COVER_TREE_TRAVERSER_HPP
+
+#include <mlpack/core.hpp>
+#include <queue>
+
+namespace mlpack {
+namespace tree {
+
+template<typename TreeType, typename RuleType>
+class DualCoverTreeTraverser
+{
+ public:
+  DualCoverTreeTraverser(RuleType& rule) : rule(rule), numPrunes(0) { }
+
+  void Traverse(TreeType& queryNode, TreeType& referenceNode)
+  {
+    Traverse(queryNode, referenceNode, size_t() - 1);
+  }
+
+  void Traverse(TreeType& queryNode, TreeType& referenceNode, size_t parent)
+  {
+    std::queue<TreeType*> referenceQueue;
+    std::queue<size_t> referenceParents;
+
+    referenceQueue.push(&referenceNode);
+    referenceParents.push(parent);
+
+    while (!referenceQueue.empty())
+    {
+      TreeType& reference = *referenceQueue.front();
+      referenceQueue.pop();
+
+      size_t refParent = referenceParents.front();
+      referenceParents.pop();
+
+      // Do the base case, if we need to.
+      if (refParent != reference.Point())
+        rule.BaseCase(queryNode.Point(), reference.Point());
+
+      if (((queryNode.Scale() < reference.Scale()) &&
+           (reference.NumChildren() != 0)) ||
+           (queryNode.NumChildren() == 0))
+      {
+        // We must descend the reference node.  Pruning happens here.
+        for (size_t i = 0; i < reference.NumChildren(); ++i)
+        {
+          // Can we prune?
+  //        if (!rule.CanPrune(queryNode, reference.Child(i)))
+          {
+            referenceQueue.push(&(reference.Child(i)));
+            referenceParents.push(reference.Point());
+          }
+//          else
+          {
+            numPrunes++;
+          }
+        }
+      }
+      else
+      {
+        // We must descend the query node.  No pruning happens here.  For the
+        // self-child, we trick the recursion into thinking that the base case
+        // has already been done (which it has).
+        if (queryNode.NumChildren() >= 1)
+          Traverse(queryNode.Child(0), reference, reference.Point());
+
+        for (size_t i = 1; i < queryNode.NumChildren(); ++i)
+          Traverse(queryNode.Child(i), reference, size_t() - 1);
+      }
+    }
+  }
+
+  size_t NumPrunes() const { return numPrunes; }
+  size_t& NumPrunes() { return numPrunes; }
+
+ private:
+  RuleType& rule;
+  size_t numPrunes;
+};
+
+}; // namespace tree
+}; // namespace mlpack
+
+#endif