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

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

Author: rcurtin
Date: 2012-05-02 12:47:27 -0400 (Wed, 02 May 2012)
New Revision: 12603

Added:
   mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_breadth_first_traverser.hpp
Modified:
   mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt
Log:
Add the very similar SingleTreeBreadthFirstTraverser, meant to be used with the
CoverTree.


Modified: mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt	2012-05-02 16:42:18 UTC (rev 12602)
+++ mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt	2012-05-02 16:47:27 UTC (rev 12603)
@@ -17,6 +17,7 @@
   periodichrectbound_impl.hpp
   statistic.hpp
   mrkd_statistic.hpp
+  traversers/single_tree_breadth_first_traverser.hpp
   traversers/single_tree_depth_first_traverser.hpp
 )
 

Added: mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_breadth_first_traverser.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_breadth_first_traverser.hpp	                        (rev 0)
+++ mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_breadth_first_traverser.hpp	2012-05-02 16:47:27 UTC (rev 12603)
@@ -0,0 +1,70 @@
+/**
+ * @file single_tree_breadth_first_traverser.hpp
+ * @author Ryan Curtin
+ *
+ * Defines the SingleTreeBreadthFirstTraverser, an extensible class which allows
+ * a single-tree breadth-first recursion with a pruning rule and a base case
+ * (two point) rule.  This is similar to the SingleTreeDepthFirstTraverser.
+ */
+#ifndef __MLPACK_CORE_TREE_TRAVERSERS_SINGLE_TREE_BREADTH_FIRST_TRAVERSER_HPP
+#define __MLPACK_CORE_TREE_TRAVERSERS_SINGLE_TREE_BREADTH_FIRST_TRAVERSER_HPP
+
+#include <mlpack/core.hpp>
+#include <queue>
+
+namespace mlpack {
+namespace tree {
+
+template<typename TreeType, typename RuleType>
+class SingleTreeBreadthFirstTraverser
+{
+ public:
+  SingleTreeBreadthFirstTraverser(RuleType& rule) :
+      rule(rule),
+      numPrunes(0)
+  { /* Nothing to do. */ }
+
+  void Traverse(const size_t queryIndex, TreeType& referenceNode)
+  {
+    // This is a non-recursive implementation (which should be faster than a
+    // recursive implementation).
+    std::queue<TreeType*> pointQueue;
+    pointQueue.push(&referenceNode);
+
+    while (!pointQueue.empty())
+    {
+      TreeType* node = pointQueue.front();
+      pointQueue.pop();
+
+      // Check if we can prune this node.
+      if (rule.CanPrune(queryIndex, *node))
+      {
+        ++numPrunes;
+        continue;
+      }
+
+      // First run the base case for any points this node might hold.
+      for (size_t i = 0; i < node->NumPoints(); ++i)
+        rule.BaseCase(queryIndex, node->Point(i));
+
+      // Now push children into the FIFO.
+      for (size_t i = 0; i < node->NumChildren(); ++i)
+        pointQueue.push(&(node->Child(i)));
+    }
+  }
+
+  //! Get the number of prunes so far.
+  size_t NumPrunes() const { return numPrunes; }
+  //! Set the number of prunes (good for a reset to 0).
+  size_t& NumPrunes() { return numPrunes; }
+
+ private:
+  RuleType& rule;
+
+  size_t numPrunes;
+};
+
+}; // namespace tree
+}; // namespace mlpack
+
+#endif