[mlpack-svn] r12616 - mlpack/trunk/src/mlpack/core/tree/traversers

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

Author: rcurtin
Date: 2012-05-03 20:13:55 -0400 (Thu, 03 May 2012)
New Revision: 12616

Modified:
   mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_breadth_first_traverser.hpp
   mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_depth_first_traverser.hpp
Log:
Update our traversers so that they don't consider self-children.  I am not too
happy with how unclean it is, but I expect it'll get cleaned later.


Modified: 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	2012-05-04 00:12:44 UTC (rev 12615)
+++ mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_breadth_first_traverser.hpp	2012-05-04 00:13:55 UTC (rev 12616)
@@ -29,8 +29,12 @@
     // This is a non-recursive implementation (which should be faster than a
     // recursive implementation).
     std::queue<TreeType*> pointQueue;
+    std::queue<size_t> parentPoints; // For if this tree has self-children.
     pointQueue.push(&referenceNode);
 
+    if (TreeType::HasSelfChildren())
+      parentPoints.push(size_t() - 1); // Invalid value.
+
     while (!pointQueue.empty())
     {
       TreeType* node = pointQueue.front();
@@ -39,17 +43,38 @@
       // Check if we can prune this node.
       if (rule.CanPrune(queryIndex, *node))
       {
+        if (TreeType::HasSelfChildren())
+          parentPoints.pop(); // Pop the parent point off.
+
         ++numPrunes;
         continue;
       }
 
+      // If this tree type has self-children, we need to make sure we don't run
+      // the base case if the parent already had it run.
+      size_t baseCaseStart = 0;
+      if (TreeType::HasSelfChildren())
+      {
+        if (parentPoints.front() == node->Point(0))
+          baseCaseStart = 1; // Skip base case we've already evaluated.
+
+        parentPoints.pop();
+      }
+
       // First run the base case for any points this node might hold.
-      for (size_t i = 0; i < node->NumPoints(); ++i)
+      for (size_t i = baseCaseStart; 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)));
+
+      // Push parent points if we need to.
+      if (TreeType::HasSelfChildren())
+      {
+        for (size_t i = 0; i < node->NumChildren(); ++i)
+          parentPoints.push(node->Point(0));
+      }
     }
   }
 

Modified: mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_depth_first_traverser.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_depth_first_traverser.hpp	2012-05-04 00:12:44 UTC (rev 12615)
+++ mlpack/trunk/src/mlpack/core/tree/traversers/single_tree_depth_first_traverser.hpp	2012-05-04 00:13:55 UTC (rev 12616)
@@ -30,8 +30,12 @@
 
     // The stack of points to look at.
     std::stack<TreeType*> pointStack;
+    std::stack<size_t> parentPoints; // For if this tree has self-children.
     pointStack.push(&referenceNode);
 
+    if (TreeType::HasSelfChildren())
+      parentPoints.push(size_t() - 1); // Invalid value.
+
     while (!pointStack.empty())
     {
       TreeType* node = pointStack.top();
@@ -40,16 +44,38 @@
       // Check if we can prune this node.
       if (rule.CanPrune(queryIndex, *node))
       {
+        if (TreeType::HasSelfChildren())
+          parentPoints.pop(); // Pop the parent point off.
+
         ++numPrunes;
         continue;
       }
 
+      // If this tree type has self-children, we need to make sure we don't run
+      // the base case if the parent already had it run.
+      Log::Debug << "Node is " << node->Point(0) << std::endl;
+      size_t baseCaseStart = 0;
+      if (TreeType::HasSelfChildren())
+      {
+        if (parentPoints.top() == node->Point(0))
+          baseCaseStart = 1; // Skip base case we've already evaluated.
+
+        parentPoints.pop();
+      }
+
       // First run the base case for any points this node might hold.
-      for (size_t i = 0; i < node->NumPoints(); ++i)
+      for (size_t i = baseCaseStart; i < node->NumPoints(); ++i)
         rule.BaseCase(queryIndex, node->Point(i));
 
       for (size_t i = 0; i < node->NumChildren(); ++i)
         pointStack.push(&(node->Child(i)));
+
+      // Push parent points if we need to.
+      if (TreeType::HasSelfChildren())
+      {
+        for (size_t i = 0; i < node->NumChildren(); ++i)
+          parentPoints.push(node->Point(0));
+      }
     }
   }