[mlpack-git] master: Add GreedySingleTreeTraverser. (dfa99cc)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/3274b05fcc545c3b36f783316fea2e22f79c3d03...1c77230c7d3b9c45fb102cd3c632d9c7248e085e

>---------------------------------------------------------------

commit dfa99cc9793c5ff8b9cd6671b290aa18a25d0df3
Author: MarcosPividori <marcos.pividori at gmail.com>
Date:   Tue Aug 16 00:54:41 2016 -0300

    Add GreedySingleTreeTraverser.


>---------------------------------------------------------------

dfa99cc9793c5ff8b9cd6671b290aa18a25d0df3
 .../core/tree/greedy_single_tree_traverser.hpp     | 52 ++++++++++++++++++++++
 .../tree/greedy_single_tree_traverser_impl.hpp     | 49 ++++++++++++++++++++
 2 files changed, 101 insertions(+)

diff --git a/src/mlpack/core/tree/greedy_single_tree_traverser.hpp b/src/mlpack/core/tree/greedy_single_tree_traverser.hpp
new file mode 100644
index 0000000..29bc697
--- /dev/null
+++ b/src/mlpack/core/tree/greedy_single_tree_traverser.hpp
@@ -0,0 +1,52 @@
+/**
+ * @file greedy_single_tree_traverser_impl.hpp
+ * @author Marcos Pividori
+ *
+ * A simple greedy traverser which always chooses the child with the best score
+ * and doesn't do backtracking.  The RuleType class must implement the method
+ * 'GetBestChild()'.
+ */
+#ifndef MLPACK_CORE_TREE_GREEDY_SINGLE_TREE_TRAVERSER_HPP
+#define MLPACK_CORE_TREE_GREEDY_SINGLE_TREE_TRAVERSER_HPP
+
+#include <mlpack/core.hpp>
+
+namespace mlpack {
+namespace tree {
+
+template<typename TreeType, typename RuleType>
+class GreedySingleTreeTraverser
+{
+ public:
+  /**
+   * Instantiate the greedy single tree traverser with the given rule set.
+   */
+  GreedySingleTreeTraverser(RuleType& rule);
+
+  /**
+   * Traverse the tree with the given point.
+   *
+   * @param queryIndex The index of the point in the query set which is being
+   *     used as the query point.
+   * @param referenceNode The tree node to be traversed.
+   */
+  void Traverse(const size_t queryIndex, TreeType& referenceNode);
+
+  //! Get the number of prunes.
+  size_t NumPrunes() const { return numPrunes; }
+
+ private:
+  //! Reference to the rules with which the tree will be traversed.
+  RuleType& rule;
+
+  //! The number of nodes which have been pruned during traversal.
+  size_t numPrunes;
+};
+
+} // namespace tree
+} // namespace mlpack
+
+// Include implementation.
+#include "greedy_single_tree_traverser_impl.hpp"
+
+#endif
diff --git a/src/mlpack/core/tree/greedy_single_tree_traverser_impl.hpp b/src/mlpack/core/tree/greedy_single_tree_traverser_impl.hpp
new file mode 100644
index 0000000..723efb5
--- /dev/null
+++ b/src/mlpack/core/tree/greedy_single_tree_traverser_impl.hpp
@@ -0,0 +1,49 @@
+/**
+ * @file greedy_single_tree_traverser_impl.hpp
+ * @author Marcos Pividori
+ *
+ * A simple greedy traverser which always chooses the child with the best score
+ * and doesn't do backtracking.  The RuleType class must implement the method
+ * 'GetBestChild()'.
+ */
+#ifndef MLPACK_CORE_TREE_GREEDY_SINGLE_TREE_TRAVERSER_IMPL_HPP
+#define MLPACK_CORE_TREE_GREEDY_SINGLE_TREE_TRAVERSER_IMPL_HPP
+
+// In case it hasn't been included yet.
+#include "greedy_single_tree_traverser.hpp"
+
+namespace mlpack {
+namespace tree {
+
+template<typename TreeType, typename RuleType>
+GreedySingleTreeTraverser<TreeType, RuleType>::GreedySingleTreeTraverser(
+    RuleType& rule) :
+    rule(rule),
+    numPrunes(0)
+{ /* Nothing to do. */ }
+
+template<typename TreeType, typename RuleType>
+GreedySingleTreeTraverser<TreeType, RuleType>::Traverse(
+    const size_t queryIndex,
+    TreeType& referenceNode)
+{
+  // If we have reached a leaf node, run the base case as necessary.
+  if (referenceNode.IsLeaf())
+  {
+    for (size_t i = 0; i < referenceNode.NumPoints(); ++i)
+      rule.BaseCase(queryIndex, referenceNode.Point(i));
+  }
+  else
+  {
+    // We are prunning all but one child.
+    numPrunes += referenceNode.NumChildren() - 1;
+    // Recurse the best child.
+    TreeTyp& bestChild = rule.GetBestChild(queryIndex, referenceNode);
+    Traverse(queryIndex, bestChild);
+  }
+}
+
+} // namespace tree
+} // namespace mlpack
+
+#endif