[mlpack-svn] r14105 - in mlpack/trunk/src/mlpack/core/tree: . binary_space_tree cover_tree

fastlab-svn at coffeetalk-1.cc.gatech.edu fastlab-svn at coffeetalk-1.cc.gatech.edu
Thu Jan 10 13:21:11 EST 2013


Author: rcurtin
Date: 2013-01-10 13:21:10 -0500 (Thu, 10 Jan 2013)
New Revision: 14105

Added:
   mlpack/trunk/src/mlpack/core/tree/binary_space_tree/traits.hpp
   mlpack/trunk/src/mlpack/core/tree/cover_tree/traits.hpp
   mlpack/trunk/src/mlpack/core/tree/tree_traits.hpp
Modified:
   mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt
   mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp
   mlpack/trunk/src/mlpack/core/tree/cover_tree.hpp
Log:
Add traits for trees.


Modified: mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt	2013-01-10 15:53:08 UTC (rev 14104)
+++ mlpack/trunk/src/mlpack/core/tree/CMakeLists.txt	2013-01-10 18:21:10 UTC (rev 14105)
@@ -9,6 +9,7 @@
   binary_space_tree/dual_tree_traverser_impl.hpp
   binary_space_tree/single_tree_traverser.hpp
   binary_space_tree/single_tree_traverser_impl.hpp
+  binary_space_tree/traits.hpp
   bounds.hpp
   cover_tree/cover_tree.hpp
   cover_tree/cover_tree_impl.hpp
@@ -17,6 +18,7 @@
   cover_tree/single_tree_traverser_impl.hpp
   cover_tree/dual_tree_traverser.hpp
   cover_tree/dual_tree_traverser_impl.hpp
+  cover_tree/traits.hpp
   hrectbound.hpp
   hrectbound_impl.hpp
   mrkd_statistic.hpp
@@ -25,6 +27,7 @@
   periodichrectbound.hpp
   periodichrectbound_impl.hpp
   statistic.hpp
+  tree_traits.hpp
 )
 
 # add directory name to sources

Added: mlpack/trunk/src/mlpack/core/tree/binary_space_tree/traits.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree/traits.hpp	                        (rev 0)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree/traits.hpp	2013-01-10 18:21:10 UTC (rev 14105)
@@ -0,0 +1,45 @@
+/**
+ * @file traits.hpp
+ * @author Ryan Curtin
+ *
+ * Specialization of the TreeTraits class for the BinarySpaceTree type of tree.
+ */
+#ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_TRAITS_HPP
+#define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_TRAITS_HPP
+
+#include <mlpack/core/tree/tree_traits.hpp>
+
+namespace mlpack {
+namespace tree {
+
+/**
+ * This is a specialization of the TreeType class to the BinarySpaceTree tree
+ * type.  It defines characteristics of the binary space tree, and is used to
+ * help write tree-independent (but still optimized) tree-based algorithms.  See
+ * mlpack/core/tree/tree_traits.hpp for more information.
+ */
+template<>
+template<typename BoundType,
+         typename StatisticType,
+         typename MatType>
+class TreeTraits<BinarySpaceTree<BoundType, StatisticType, MatType> >
+{
+ public:
+  /**
+   * The binary space tree cannot easily calculate the distance from a node to
+   * its parent; so BinarySpaceTree<...>::ParentDistance() does not exist.
+   */
+  static const bool HasParentDistance = false;
+
+  /**
+   * Each binary space tree node has two children which represent
+   * non-overlapping subsets of the space which the node represents.  Therefore,
+   * children are not overlapping.
+   */
+  static const bool HasOverlappingChildren = false;
+};
+
+}; // namespace tree
+}; // namespace mlpack
+
+#endif

Modified: mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp	2013-01-10 15:53:08 UTC (rev 14104)
+++ mlpack/trunk/src/mlpack/core/tree/binary_space_tree.hpp	2013-01-10 18:21:10 UTC (rev 14105)
@@ -11,5 +11,6 @@
 #include "binary_space_tree/binary_space_tree.hpp"
 #include "binary_space_tree/single_tree_traverser.hpp"
 #include "binary_space_tree/dual_tree_traverser.hpp"
+#include "binary_space_tree/traits.hpp"
 
 #endif

Added: mlpack/trunk/src/mlpack/core/tree/cover_tree/traits.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree/traits.hpp	                        (rev 0)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree/traits.hpp	2013-01-10 18:21:10 UTC (rev 14105)
@@ -0,0 +1,46 @@
+/**
+ * @file traits.hpp
+ * @author Ryan Curtin
+ *
+ * This file contains the specialization of the TreeTraits class for the
+ * CoverTree type of tree.
+ */
+#ifndef __MLPACK_CORE_TREE_COVER_TREE_TRAITS_HPP
+#define __MLPACK_CORE_TREE_COVER_TREE_TRAITS_HPP
+
+#include <mlpack/core/tree/tree_traits.hpp>
+
+namespace mlpack {
+namespace tree {
+
+/**
+ * The specialization of the TreeTraits class for the CoverTree tree type.  It
+ * defines characteristics of the cover tree, and is used to help write
+ * tree-independent (but still optimized) tree-based algorithms.  See
+ * mlpack/core/tree/tree_traits.hpp for more information.
+ */
+template<>
+template<typename MetricType,
+         typename RootPointPolicy,
+         typename StatisticType>
+class TreeTraits<CoverTree<MetricType, RootPointPolicy, StatisticType> >
+{
+ public:
+  /**
+   * The cover tree calculates the distance between parent and child during
+   * construction, so that value is saved and CoverTree<...>::ParentDistance()
+   * does exist.
+   */
+  static const bool HasParentDistance = true;
+
+  /**
+   * The cover tree (or, this implementation of it) does not require that
+   * children represent non-overlapping subsets of the parent node.
+   */
+  static const bool HasOverlappingChildren = true;
+};
+
+}; // namespace tree
+}; // namespace mlpack
+
+#endif

Modified: mlpack/trunk/src/mlpack/core/tree/cover_tree.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/cover_tree.hpp	2013-01-10 15:53:08 UTC (rev 14104)
+++ mlpack/trunk/src/mlpack/core/tree/cover_tree.hpp	2013-01-10 18:21:10 UTC (rev 14105)
@@ -11,5 +11,6 @@
 #include "cover_tree/cover_tree.hpp"
 #include "cover_tree/single_tree_traverser.hpp"
 #include "cover_tree/dual_tree_traverser.hpp"
+#include "cover_tree/traits.hpp"
 
 #endif

Added: mlpack/trunk/src/mlpack/core/tree/tree_traits.hpp
===================================================================
--- mlpack/trunk/src/mlpack/core/tree/tree_traits.hpp	                        (rev 0)
+++ mlpack/trunk/src/mlpack/core/tree/tree_traits.hpp	2013-01-10 18:21:10 UTC (rev 14105)
@@ -0,0 +1,92 @@
+/**
+ * @file tree_traits.hpp
+ * @author Ryan Curtin
+ *
+ * This file implements the basic, unspecialized TreeTraits class, which
+ * provides information about tree types.  If you create a tree class, you
+ * should specialize this class with the characteristics of your tree.
+ */
+#ifndef __MLPACK_CORE_TREE_TREE_TRAITS_HPP
+#define __MLPACK_CORE_TREE_TREE_TRAITS_HPP
+
+namespace mlpack {
+namespace tree {
+
+/**
+ * The TreeTraits class provides compile-time information on the characteristics
+ * of a given tree type.  These include traits such as whether or not a node
+ * knows the distance to its parent node, or whether or not the subspaces
+ * represented by children can overlap.
+ *
+ * These traits can be used for static compile-time optimization:
+ *
+ * @code
+ * // This if statement will be optimized out at compile time!
+ * if (TreeTraits<TreeType>::HasOverlappingChildren == false)
+ * {
+ *   // Do a simpler computation because no children overlap.
+ * }
+ * else
+ * {
+ *   // Do the full, complex calculation.
+ * }
+ * @endcode
+ *
+ * The traits can also be used in conjunction with SFINAE to write specialized
+ * versions of functions:
+ *
+ * @code
+ * template<typename TreeType>
+ * void Compute(TreeType& node,
+ *              boost::enable_if<
+ *                  TreeTraits<TreeType>::HasParentDistance>::type*)
+ * {
+ *   // Computation with TreeType::ParentDistance().
+ * }
+ *
+ * template<typename TreeType>
+ * void Compute(TreeType& node,
+ *              boost::enable_if<
+ *                  !TreeTraits<TreeType>::HasParentDistance>::type*)
+ * {
+ *   // Computation without TreeType::ParentDistance().
+ * }
+ * @endcode
+ *
+ * In those two examples, the boost::enable_if<> class takes a boolean template
+ * parameter which allows that function to be called when the boolean is true.
+ *
+ * Each trait must be a static const value and not a function; only const values
+ * can be used as template parameters (with the exception of constexprs, which
+ * are a C++11 feature; but MLPACK is not using C++11).  By default (the
+ * unspecialized implementation of TreeTraits), each parameter is set to make as
+ * few assumptions about the tree as possible; so, even if TreeTraits is not
+ * specialized for a particular tree type, tree-based algorithms should still
+ * work.
+ *
+ * When you write your own tree, you must specialize the TreeTraits class to
+ * your tree type and set the corresponding values appropriately.  See
+ * mlpack/core/tree/binary_space_tree/traits.hpp for an example.
+ */
+template<typename TreeType>
+class TreeTraits
+{
+ public:
+  /**
+   * This is true if TreeType::ParentDistance() exists and works.  The
+   * ParentDistance() function returns the distance between the center of a node
+   * and the center of its parent.
+   */
+  static const bool HasParentDistance = false;
+
+  /**
+   * This is true if the subspaces represented by the children of a node can
+   * overlap.
+   */
+  static const bool HasOverlappingChildren = true;
+};
+
+}; // namespace tree
+}; // namespace mlpack
+
+#endif




More information about the mlpack-svn mailing list