[mlpack-svn] r15036 - mlpack/trunk/src/mlpack/tests

fastlab-svn at coffeetalk-1.cc.gatech.edu fastlab-svn at coffeetalk-1.cc.gatech.edu
Wed May 8 17:22:43 EDT 2013


Author: rcurtin
Date: 2013-05-08 17:22:42 -0400 (Wed, 08 May 2013)
New Revision: 15036

Modified:
   mlpack/trunk/src/mlpack/tests/tree_test.cpp
Log:
Test the Descendant() and NumDescendants() functions.  These tests were
surprisingly difficult to write but should be rather comprehensive.


Modified: mlpack/trunk/src/mlpack/tests/tree_test.cpp
===================================================================
--- mlpack/trunk/src/mlpack/tests/tree_test.cpp	2013-05-08 21:22:19 UTC (rev 15035)
+++ mlpack/trunk/src/mlpack/tests/tree_test.cpp	2013-05-08 21:22:42 UTC (rev 15036)
@@ -2188,4 +2188,120 @@
   BOOST_REQUIRE_EQUAL(b.Right()->Right(), c.Right()->Right());
 }
 
+//! Count the number of leaves under this node.
+template<typename TreeType>
+size_t NumLeaves(TreeType* node)
+{
+  if (node->NumChildren() == 0)
+    return 1;
+
+  size_t count = 0;
+  for (size_t i = 0; i < node->NumChildren(); ++i)
+    count += NumLeaves(&node->Child(i));
+
+  return count;
+}
+
+//! Returns true if the index is contained somewhere under this node.
+template<typename TreeType>
+bool FindIndex(TreeType* node, const size_t index)
+{
+  for (size_t i = 0; i < node->NumPoints(); ++i)
+    if (node->Point(i) == index)
+      return true;
+
+  for (size_t i = 0; i < node->NumChildren(); ++i)
+    if (FindIndex(&node->Child(i), index))
+      return true;
+
+  return false;
+}
+
+//! Check that the points in the given node are accessible through the
+//! Descendant() function of the root node.
+template<typename TreeType>
+bool CheckAccessibility(TreeType* childNode, TreeType* rootNode)
+{
+  for (size_t i = 0; i < childNode->NumPoints(); ++i)
+  {
+    bool found = false;
+    for (size_t j = 0; j < rootNode->NumDescendants(); ++j)
+    {
+      if (childNode->Point(i) == rootNode->Descendant(j))
+      {
+        found = true;
+        break;
+      }
+    }
+
+    if (!found)
+    {
+      Log::Debug << "Did not find descendant " << childNode->Point(i) << ".\n";
+      return false;
+    }
+  }
+
+  // Now check the children.
+  for (size_t i = 0; i < childNode->NumChildren(); ++i)
+    if (!CheckAccessibility(&childNode->Child(i), rootNode))
+      return false;
+
+  return true;
+}
+
+//! Check that Descendant() and NumDescendants() is right for this node.
+template<typename TreeType>
+void CheckDescendants(TreeType* node)
+{
+  // In a cover tree, the number of leaves should be the number of descendant
+  // points.
+  const size_t numLeaves = NumLeaves(node);
+  BOOST_REQUIRE_EQUAL(numLeaves, node->NumDescendants());
+
+  // Now check that each descendant is somewhere in the tree.
+  for (size_t i = 0; i < node->NumDescendants(); ++i)
+  {
+    Log::Debug << "Check for descendant " << node->Descendant(i) << " (i " <<
+        i << ").\n";
+    BOOST_REQUIRE_EQUAL(FindIndex(node, node->Descendant(i)), true);
+  }
+
+  // Now check that every actual descendant is accessible through the
+  // Descendant() function.
+  BOOST_REQUIRE_EQUAL(CheckAccessibility(node, node), true);
+
+  // Now check that there are no duplicates in the list of descendants.
+  std::vector<size_t> descendants;
+  descendants.resize(node->NumDescendants());
+  for (size_t i = 0; i < node->NumDescendants(); ++i)
+    descendants[i] = node->Descendant(i);
+
+  // Sort the list.
+  std::sort(descendants.begin(), descendants.end());
+
+  // Check that there are no duplicates (this is easy because it's sorted).
+  for (size_t i = 1; i < descendants.size(); ++i)
+    BOOST_REQUIRE_NE(descendants[i], descendants[i - 1]);
+
+  // Now perform these same checks for the children.
+  for (size_t i = 0; i < node->NumChildren(); ++i)
+    CheckDescendants(&node->Child(i));
+}
+
+/**
+ * Make sure Descendant() and NumDescendants() works properly for the cover
+ * tree.
+ */
+BOOST_AUTO_TEST_CASE(CoverTreeDescendantTest)
+{
+  arma::mat dataset;
+  dataset.randu(3, 100);
+
+  CoverTree<> tree(dataset);
+
+  // Now check that the NumDescendants() count and each Descendant() is right
+  // using the recursive function above.
+  CheckDescendants(&tree);
+}
+
 BOOST_AUTO_TEST_SUITE_END();




More information about the mlpack-svn mailing list