[mlpack-svn] r15826 - mlpack/trunk/src/mlpack/tests
fastlab-svn at coffeetalk-1.cc.gatech.edu
fastlab-svn at coffeetalk-1.cc.gatech.edu
Sun Sep 22 09:21:52 EDT 2013
Author: muditrajgupta
Date: Sun Sep 22 09:21:52 2013
New Revision: 15826
Log:
Removed an older version of tree test and added a new one
Modified:
mlpack/trunk/src/mlpack/tests/tree_test.cpp
Modified: mlpack/trunk/src/mlpack/tests/tree_test.cpp
==============================================================================
--- mlpack/trunk/src/mlpack/tests/tree_test.cpp (original)
+++ mlpack/trunk/src/mlpack/tests/tree_test.cpp Sun Sep 22 09:21:52 2013
@@ -2,32 +2,17 @@
* @file tree_test.cpp
*
* Tests for tree-building methods.
- *
- * This file is part of MLPACK 1.0.4.
- *
- * MLPACK is free software: you can redistribute it and/or modify it under the
- * terms of the GNU Lesser General Public License as published by the Free
- * Software Foundation, either version 3 of the License, or (at your option) any
- * later version.
- *
- * MLPACK is distributed in the hope that it will be useful, but WITHOUT ANY
- * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
- * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
- * details (LICENSE.txt).
- *
- * You should have received a copy of the GNU General Public License along with
- * MLPACK. If not, see <http://www.gnu.org/licenses/>.
*/
-#include <mlpack/core.hpp>
-#include <mlpack/core/tree/bounds.hpp>
-#include <mlpack/core/tree/binary_space_tree/binary_space_tree.hpp>
-#include <mlpack/core/metrics/lmetric.hpp>
-#include <mlpack/core/tree/cover_tree/cover_tree.hpp>
-#include <mlpack/core/tree/cosine_tree/cosine_tree.hpp>
-#include <mlpack/core/tree/cosine_tree/cosine_tree_builder.hpp>
+include <mlpack/core.hpp>
+include <mlpack/core/tree/bounds.hpp>
+include <mlpack/core/tree/binary_space_tree/binary_space_tree.hpp>
+include <mlpack/core/metrics/lmetric.hpp>
+include <mlpack/core/tree/cover_tree/cover_tree.hpp>
+include <mlpack/core/tree/cosine_tree/cosine_tree.hpp>
+include <mlpack/core/tree/cosine_tree/cosine_tree_builder.hpp>
-#include <boost/test/unit_test.hpp>
-#include "old_boost_test_definitions.hpp"
+include <boost/test/unit_test.hpp>
+include "old_boost_test_definitions.hpp"
using namespace mlpack;
using namespace mlpack::math;
@@ -42,9 +27,9 @@
*/
BOOST_AUTO_TEST_CASE(HRectBoundEmptyConstructor)
{
- HRectBound<2> b;
+ HRectBound<2> b;
- BOOST_REQUIRE_EQUAL((int) b.Dim(), 0);
+ BOOST_REQUIRE_EQUAL((int) b.Dim(), 0);
}
/**
@@ -53,20 +38,20 @@
*/
BOOST_AUTO_TEST_CASE(HRectBoundDimConstructor)
{
- HRectBound<2> b(2); // We'll do this with 2 and 5 dimensions.
-
- BOOST_REQUIRE_EQUAL(b.Dim(), 2);
- BOOST_REQUIRE_SMALL(b[0].Width(), 1e-5);
- BOOST_REQUIRE_SMALL(b[1].Width(), 1e-5);
+ HRectBound<2> b(2); // We'll do this with 2 and 5 dimensions.
- b = HRectBound<2>(5);
-
- BOOST_REQUIRE_EQUAL(b.Dim(), 5);
- BOOST_REQUIRE_SMALL(b[0].Width(), 1e-5);
- BOOST_REQUIRE_SMALL(b[1].Width(), 1e-5);
- BOOST_REQUIRE_SMALL(b[2].Width(), 1e-5);
- BOOST_REQUIRE_SMALL(b[3].Width(), 1e-5);
- BOOST_REQUIRE_SMALL(b[4].Width(), 1e-5);
+ BOOST_REQUIRE_EQUAL(b.Dim(), 2);
+ BOOST_REQUIRE_SMALL(b[0].Width(), 1e-5);
+ BOOST_REQUIRE_SMALL(b[1].Width(), 1e-5);
+
+ b = HRectBound<2>(5);
+
+ BOOST_REQUIRE_EQUAL(b.Dim(), 5);
+ BOOST_REQUIRE_SMALL(b[0].Width(), 1e-5);
+ BOOST_REQUIRE_SMALL(b[1].Width(), 1e-5);
+ BOOST_REQUIRE_SMALL(b[2].Width(), 1e-5);
+ BOOST_REQUIRE_SMALL(b[3].Width(), 1e-5);
+ BOOST_REQUIRE_SMALL(b[4].Width(), 1e-5);
}
/**
@@ -74,17 +59,17 @@
*/
BOOST_AUTO_TEST_CASE(HRectBoundCopyConstructor)
{
- HRectBound<2> b(2);
- b[0] = Range(0.0, 2.0);
- b[1] = Range(2.0, 3.0);
-
- HRectBound<2> c(b);
-
- BOOST_REQUIRE_EQUAL(c.Dim(), 2);
- BOOST_REQUIRE_SMALL(c[0].Lo(), 1e-5);
- BOOST_REQUIRE_CLOSE(c[0].Hi(), 2.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c[1].Lo(), 2.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c[1].Hi(), 3.0, 1e-5);
+ HRectBound<2> b(2);
+ b[0] = Range(0.0, 2.0);
+ b[1] = Range(2.0, 3.0);
+
+ HRectBound<2> c(b);
+
+ BOOST_REQUIRE_EQUAL(c.Dim(), 2);
+ BOOST_REQUIRE_SMALL(c[0].Lo(), 1e-5);
+ BOOST_REQUIRE_CLOSE(c[0].Hi(), 2.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(c[1].Lo(), 2.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(c[1].Hi(), 3.0, 1e-5);
}
/**
@@ -92,19 +77,19 @@
*/
BOOST_AUTO_TEST_CASE(HRectBoundAssignmentOperator)
{
- HRectBound<2> b(2);
- b[0] = Range(0.0, 2.0);
- b[1] = Range(2.0, 3.0);
-
- HRectBound<2> c(4);
-
- c = b;
-
- BOOST_REQUIRE_EQUAL(c.Dim(), 2);
- BOOST_REQUIRE_SMALL(c[0].Lo(), 1e-5);
- BOOST_REQUIRE_CLOSE(c[0].Hi(), 2.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c[1].Lo(), 2.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c[1].Hi(), 3.0, 1e-5);
+ HRectBound<2> b(2);
+ b[0] = Range(0.0, 2.0);
+ b[1] = Range(2.0, 3.0);
+
+ HRectBound<2> c(4);
+
+ c = b;
+
+ BOOST_REQUIRE_EQUAL(c.Dim(), 2);
+ BOOST_REQUIRE_SMALL(c[0].Lo(), 1e-5);
+ BOOST_REQUIRE_CLOSE(c[0].Hi(), 2.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(c[1].Lo(), 2.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(c[1].Hi(), 3.0, 1e-5);
}
/**
@@ -138,7 +123,6 @@
arma::vec centroid;
-
b.Centroid(centroid);
BOOST_REQUIRE_EQUAL(centroid.n_elem, 3);
@@ -167,8 +151,8 @@
arma::vec point = "-2.0 0.0 10.0 3.0 3.0";
- // This will be the Euclidean squared distance.
- BOOST_REQUIRE_CLOSE(b.MinDistance(point), 95.0, 1e-5);
+ // This will be the Euclidean distance.
+ BOOST_REQUIRE_CLOSE(b.MinDistance(point), sqrt(95.0), 1e-5);
point = "2.0 5.0 2.0 -5.0 1.0";
@@ -207,8 +191,8 @@
c[3] = Range(2.0, 5.0);
c[4] = Range(3.0, 4.0);
- BOOST_REQUIRE_CLOSE(b.MinDistance(c), 22.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c.MinDistance(b), 22.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MinDistance(c), sqrt(22.0), 1e-5);
+ BOOST_REQUIRE_CLOSE(c.MinDistance(b), sqrt(22.0), 1e-5);
// The other bound is on the edge of the bound.
c[0] = Range(-2.0, 0.0);
@@ -270,16 +254,16 @@
arma::vec point = "-2.0 0.0 10.0 3.0 3.0";
- // This will be the Euclidean squared distance.
- BOOST_REQUIRE_CLOSE(b.MaxDistance(point), 253.0, 1e-5);
+ // This will be the Euclidean distance.
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(point), sqrt(253.0), 1e-5);
point = "2.0 5.0 2.0 -5.0 1.0";
- BOOST_REQUIRE_CLOSE(b.MaxDistance(point), 46.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(point), sqrt(46.0), 1e-5);
point = "1.0 2.0 0.0 -2.0 1.5";
- BOOST_REQUIRE_CLOSE(b.MaxDistance(point), 23.25, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(point), sqrt(23.25), 1e-5);
}
/**
@@ -310,8 +294,8 @@
c[3] = Range(2.0, 5.0);
c[4] = Range(3.0, 4.0);
- BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 210.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c.MaxDistance(b), 210.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), sqrt(210.0), 1e-5);
+ BOOST_REQUIRE_CLOSE(c.MaxDistance(b), sqrt(210.0), 1e-5);
// The other bound is on the edge of the bound.
c[0] = Range(-2.0, 0.0);
@@ -320,8 +304,8 @@
c[3] = Range(-10.0, -5.0);
c[4] = Range(2.0, 3.0);
- BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 134.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c.MaxDistance(b), 134.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), sqrt(134.0), 1e-5);
+ BOOST_REQUIRE_CLOSE(c.MaxDistance(b), sqrt(134.0), 1e-5);
// The other bound partially overlaps the bound.
c[0] = Range(-2.0, 1.0);
@@ -330,12 +314,12 @@
c[3] = Range(-8.0, -4.0);
c[4] = Range(0.0, 4.0);
- BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 102.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c.MaxDistance(b), 102.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), sqrt(102.0), 1e-5);
+ BOOST_REQUIRE_CLOSE(c.MaxDistance(b), sqrt(102.0), 1e-5);
// The other bound fully overlaps the bound.
- BOOST_REQUIRE_CLOSE(b.MaxDistance(b), 46.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c.MaxDistance(c), 61.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(b), sqrt(46.0), 1e-5);
+ BOOST_REQUIRE_CLOSE(c.MaxDistance(c), sqrt(61.0), 1e-5);
// The other bound is entirely inside the bound / the other bound entirely
// envelops the bound.
@@ -345,13 +329,13 @@
c[3] = Range(-7.0, 0.0);
c[4] = Range(0.0, 5.0);
- BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 100.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c.MaxDistance(b), 100.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), sqrt(100.0), 1e-5);
+ BOOST_REQUIRE_CLOSE(c.MaxDistance(b), sqrt(100.0), 1e-5);
// Identical bounds. This will be the sum of the squared widths in each
// dimension.
- BOOST_REQUIRE_CLOSE(b.MaxDistance(b), 46.0, 1e-5);
- BOOST_REQUIRE_CLOSE(c.MaxDistance(c), 162.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(b), sqrt(46.0), 1e-5);
+ BOOST_REQUIRE_CLOSE(c.MaxDistance(c), sqrt(162.0), 1e-5);
// One last additional case. If the bound encloses only one point, the
// maximum distance between it and itself is 0.
@@ -365,7 +349,7 @@
/**
* Ensure that the ranges returned by RangeDistance() are equal to the minimum
- * and maximum distance. We will perform this test by creating bounds
+ * and maximum distance. We will perform this test by creating random bounds
* and comparing the behavior to MinDistance() and MaxDistance() -- so this test
* is assuming that those passed and operate correctly.
*/
@@ -957,6 +941,34 @@
}
/**
+ * Ensure that HRectBound::Diameter() works properly.
+ */
+BOOST_AUTO_TEST_CASE(HRectBoundDiameter)
+{
+ HRectBound<3> b(4);
+ b[0] = math::Range(0.0, 1.0);
+ b[1] = math::Range(-1.0, 0.0);
+ b[2] = math::Range(2.0, 3.0);
+ b[3] = math::Range(7.0, 7.0);
+
+ BOOST_REQUIRE_CLOSE(b.Diameter(), std::pow(3.0, 1.0 / 3.0), 1e-5);
+
+ HRectBound<2, false> c(4);
+ c[0] = math::Range(0.0, 1.0);
+ c[1] = math::Range(-1.0, 0.0);
+ c[2] = math::Range(2.0, 3.0);
+ c[3] = math::Range(0.0, 0.0);
+
+ BOOST_REQUIRE_CLOSE(c.Diameter(), 3.0, 1e-5);
+
+ HRectBound<5> d(2);
+ d[0] = math::Range(2.2, 2.2);
+ d[1] = math::Range(1.0, 1.0);
+
+ BOOST_REQUIRE_SMALL(d.Diameter(), 1e-5);
+}
+
+/**
* Ensure that a bound, by default, is empty and has no dimensionality, and the
* box size vector is empty.
*/
@@ -1079,11 +1091,11 @@
/**
* Ensure that we get the correct centroid for our bound.
*
-BOOST_AUTO_TEST_CASE(PeriodicHRectBoundCentroid) {
+ BOOST_AUTO_TEST_CASE(PeriodicHRectBoundCentroid) {
// Create a simple 3-dimensional bound. The centroid is not affected by the
// periodic coordinates.
PeriodicHRectBound<2> b(arma::vec("100 100 100"));
-
+
b[0] = Range(0.0, 5.0);
b[1] = Range(-2.0, -1.0);
b[2] = Range(-10.0, 50.0);
@@ -1240,7 +1252,7 @@
// Overlapping the bound.
c[0] = Range(3.0, 6.0);
c[1] = Range(1.0, 3.0);
-
+
BOOST_REQUIRE_SMALL(b.MinDistance(c), 1e-5);
// One range entirely covering the other
@@ -1285,7 +1297,7 @@
a[0] = Range(-1.0, 1.0); // Crosses over an edge.
d[0] = Range(11.9, 12.5); // The first right image of the bound starts at 4.0.
BOOST_REQUIRE_CLOSE(a.MinDistance(d), 0.81, 1e-5);
-
+
a[0] = Range(2.0, 3.0);
d[0] = Range(9.5, 11);
BOOST_REQUIRE_CLOSE(a.MinDistance(d), 1.0, 1e-5);
@@ -1307,7 +1319,7 @@
b[0] = Range(0.0, 5.0);
b[1] = Range(2.0, 4.0);
-
+
// Inside the bound.
arma::vec point = "2.5 3.0";
@@ -1337,7 +1349,7 @@
point[0] = 7.5; // Inside first right image of the box.
BOOST_REQUIRE_CLOSE(a.MaxDistance(point), 2.25, 1e-5);
-
+
a[0] = Range(0.0, 5.0); // Fills box fully.
point[1] = 19.3; // Inside the box, which covers everything.
@@ -1360,7 +1372,7 @@
a[0] = Range(0.0, 2.0); // On edge of box.
point[0] = 7.1; // 2.1 away from the first left image of the bound.
-
+
BOOST_REQUIRE_CLOSE(a.MaxDistance(point), 4.41, 1e-5);
PeriodicHRectBound<2> d(arma::vec("0.0"));
@@ -1372,13 +1384,13 @@
PeriodicHRectBound<2> e(arma::vec("-5.0"));
e[0] = Range(2.0, 4.0); // Box size of -5 should function the same as 5.
point[0] = -10.8; // Should alias to 4.2.
-
+
BOOST_REQUIRE_CLOSE(e.MaxDistance(point), 4.84, 1e-5);
// Switch our bound to a higher dimensionality. This should ensure that the
// dimensions are independent like they should be.
PeriodicHRectBound<2> c(arma::vec("5.0 5.0 5.0 5.0 5.0 5.0 0.0 -5.0"));
-
+
c[0] = Range(2.0, 4.0); // Entirely inside box.
c[1] = Range(0.0, 5.0); // Fills box fully.
c[2] = Range(-10.0, 10.0); // Larger than the box.
@@ -1397,10 +1409,9 @@
point[5] = 7.1; // 0.1 away from the first right image of the bound.
point[6] = 810.0; // 800 away from the only image of the box.
point[7] = -10.8; // Should alias to 4.2.
-
+
BOOST_REQUIRE_CLOSE(c.MaxDistance(point), 672630.65, 1e-10);
}*/
-
/**
* Correctly calculate the maximum distance between the bound and another bound in
* periodic coordinates. We have to account for the shifts necessary in
@@ -1432,7 +1443,7 @@
c[1] = Range(4.0, 6.0);
BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 80.0, 1e-5);
-
+
// Overlapping the bound.
c[0] = Range(3.0, 6.0);
@@ -1445,11 +1456,11 @@
c[0] = Range(0.0, 6.0);
c[1] = Range(1.0, 7.0);
- BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 61.0, 1e-5);
+ BOOST_REQUIRE_CLOSE(b.MaxDistance(c), 61.0, 1e-5);
// Now we start to invoke the periodicity. Thess bounds "alias" to (-3.0,
// -1.0) and (5,0,6.0).
-
+
c[0] = Range(97.0, 99.0);
c[1] = Range(105.0, 106.0);
@@ -1508,6 +1519,53 @@
BOOST_REQUIRE(rootNode.Right()->Right()->Count() == 1);
}
+BOOST_AUTO_TEST_CASE(CheckParents)
+{
+ arma::mat dataset = "2.0 5.0 9.0 4.0 8.0 7.0;"
+ "3.0 4.0 6.0 7.0 1.0 2.0 ";
+
+ // Leaf size of 1.
+ BinarySpaceTree<HRectBound<2> > rootNode(dataset, 1);
+
+ BOOST_REQUIRE_EQUAL(rootNode.Parent(),
+ (BinarySpaceTree<HRectBound<2> >*) NULL);
+ BOOST_REQUIRE_EQUAL(&rootNode, rootNode.Left()->Parent());
+ BOOST_REQUIRE_EQUAL(&rootNode, rootNode.Right()->Parent());
+ BOOST_REQUIRE_EQUAL(rootNode.Left(), rootNode.Left()->Left()->Parent());
+ BOOST_REQUIRE_EQUAL(rootNode.Left(), rootNode.Left()->Right()->Parent());
+ BOOST_REQUIRE_EQUAL(rootNode.Left()->Left(),
+ rootNode.Left()->Left()->Left()->Parent());
+ BOOST_REQUIRE_EQUAL(rootNode.Left()->Left(),
+ rootNode.Left()->Left()->Right()->Parent());
+ BOOST_REQUIRE_EQUAL(rootNode.Right(), rootNode.Right()->Left()->Parent());
+ BOOST_REQUIRE_EQUAL(rootNode.Right(), rootNode.Right()->Right()->Parent());
+ BOOST_REQUIRE_EQUAL(rootNode.Right()->Left(),
+ rootNode.Right()->Left()->Left()->Parent());
+ BOOST_REQUIRE_EQUAL(rootNode.Right()->Left(),
+ rootNode.Right()->Left()->Right()->Parent());
+}
+
+BOOST_AUTO_TEST_CASE(CheckDataset)
+{
+ arma::mat dataset = "2.0 5.0 9.0 4.0 8.0 7.0;"
+ "3.0 4.0 6.0 7.0 1.0 2.0 ";
+
+ // Leaf size of 1.
+ BinarySpaceTree<HRectBound<2> > rootNode(dataset, 1);
+
+ BOOST_REQUIRE_EQUAL(&rootNode.Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Left()->Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Right()->Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Left()->Left()->Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Left()->Right()->Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Right()->Left()->Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Right()->Right()->Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Left()->Left()->Left()->Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Left()->Left()->Right()->Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Right()->Left()->Left()->Dataset(), &dataset);
+ BOOST_REQUIRE_EQUAL(&rootNode.Right()->Left()->Right()->Dataset(), &dataset);
+}
+
// Ensure FurthestDescendantDistance() works.
BOOST_AUTO_TEST_CASE(FurthestDescendantDistanceTest)
{
@@ -1520,7 +1578,7 @@
// Both points are contained in the one node.
BinarySpaceTree<HRectBound<2> > twoPoint(dataset);
- BOOST_REQUIRE_CLOSE(twoPoint.FurthestDescendantDistance(), 2, 1e-5);
+ BOOST_REQUIRE_CLOSE(twoPoint.FurthestDescendantDistance(), sqrt(2.0), 1e-5);
}
// Forward declaration of methods we need for the next test.
@@ -1557,7 +1615,6 @@
size_t maxRuns = 10; // Ten total tests.
size_t pointIncrements = 1000; // Range is from 2000 points to 11000.
-
// We use the default leaf size of 20.
for(size_t run = 0; run < maxRuns; run++)
{
@@ -1591,8 +1648,7 @@
BOOST_REQUIRE_EQUAL(dataset(j, oldToNew[i]), datacopy(j, i));
}
}
-
- // Now check that each point is contained inside of all bounds above it.
+ // Now check that each point is contained inside of all bounds above it.
CheckPointBounds(&root, dataset);
// Now check that no peers overlap.
@@ -1636,12 +1692,9 @@
TreeType* left = node->Left();
TreeType* right = node->Right();
- size_t begin = node->Begin();
- size_t count = node->Count();
-
// Check that each point which this tree claims is actually inside the tree.
- for (size_t index = begin; index < begin + count; index++)
- if (!node->Bound().Contains(data.col(index)))
+ for (size_t index = 0; index < node->NumDescendants(); index++)
+ if (!node->Bound().Contains(data.col(node->Descendant(index))))
return false;
return CheckPointBounds(left, data) && CheckPointBounds(right, data);
@@ -1690,6 +1743,11 @@
}
#ifdef ARMA_HAS_SPMAT
+// Only run sparse tree tests if we are using Armadillo 3.6. Armadillo 3.4 has
+// some bugs that cause the kd-tree splitting procedure to fail terribly. Soon,
+// that version will be obsolete, though.
+#if !((ARMA_VERSION_MAJOR == 3) && (ARMA_VERSION_MINOR == 4))
+
/**
* Exhaustive sparse kd-tree test based on #125.
*
@@ -1778,6 +1836,8 @@
// Check the tree depth.
BOOST_REQUIRE_EQUAL(root.TreeDepth(), 7);
}
+
+#endif // Using Armadillo 3.4.
#endif // ARMA_HAS_SPMAT
template<typename TreeType>
@@ -1929,7 +1989,6 @@
// of sqrt(50). This means the scale of the root node should be 3 (because
// 2^3 = 8).
BOOST_REQUIRE_EQUAL(tree.Scale(), 3);
-
// Now loop through the tree and ensure that each leaf is only created once.
arma::vec counts;
counts.zeros(20);
@@ -1988,12 +2047,13 @@
arma::mat dataset;
dataset.zeros(10, 10);
- CoverTree<> node(dataset, 1.3, 3, 2, 1.5, 2.75);
+ CoverTree<> node(dataset, 1.3, 3, 2, NULL, 1.5, 2.75);
BOOST_REQUIRE_EQUAL(&node.Dataset(), &dataset);
BOOST_REQUIRE_EQUAL(node.Base(), 1.3);
BOOST_REQUIRE_EQUAL(node.Point(), 3);
BOOST_REQUIRE_EQUAL(node.Scale(), 2);
+ BOOST_REQUIRE_EQUAL(node.Parent(), (CoverTree<>*) NULL);
BOOST_REQUIRE_EQUAL(node.ParentDistance(), 1.5);
BOOST_REQUIRE_EQUAL(node.FurthestDescendantDistance(), 2.75);
}
@@ -2029,6 +2089,221 @@
}
/**
+ * Make sure copy constructor works for the cover tree.
+ */
+BOOST_AUTO_TEST_CASE(CoverTreeCopyConstructor)
+{
+ arma::mat dataset;
+ dataset.randu(10, 10); // dataset is irrelevant.
+ CoverTree<> c(dataset, 1.3, 0, 5, NULL, 1.45, 5.2); // Random parameters.
+ c.Children().push_back(new CoverTree<>(dataset, 1.3, 1, 4, &c, 1.3, 2.45));
+ c.Children().push_back(new CoverTree<>(dataset, 1.5, 2, 3, &c, 1.2, 5.67));
+
+ CoverTree<> d = c;
+
+ // Check that everything is the same.
+ BOOST_REQUIRE_EQUAL(c.Dataset().memptr(), d.Dataset().memptr());
+ BOOST_REQUIRE_CLOSE(c.Base(), d.Base(), 1e-50);
+ BOOST_REQUIRE_EQUAL(c.Point(), d.Point());
+ BOOST_REQUIRE_EQUAL(c.Scale(), d.Scale());
+ BOOST_REQUIRE_EQUAL(c.Parent(), d.Parent());
+ BOOST_REQUIRE_EQUAL(c.ParentDistance(), d.ParentDistance());
+ BOOST_REQUIRE_EQUAL(c.FurthestDescendantDistance(),
+ d.FurthestDescendantDistance());
+ BOOST_REQUIRE_EQUAL(c.NumChildren(), d.NumChildren());
+ BOOST_REQUIRE_NE(&c.Child(0), &d.Child(0));
+ BOOST_REQUIRE_NE(&c.Child(1), &d.Child(1));
+
+ BOOST_REQUIRE_EQUAL(c.Child(0).Parent(), &c);
+ BOOST_REQUIRE_EQUAL(c.Child(1).Parent(), &c);
+ BOOST_REQUIRE_EQUAL(d.Child(0).Parent(), &d);
+ BOOST_REQUIRE_EQUAL(d.Child(1).Parent(), &d);
+
+ // Check that the children are okay.
+ BOOST_REQUIRE_EQUAL(c.Child(0).Dataset().memptr(),
+ d.Child(0).Dataset().memptr());
+ BOOST_REQUIRE_CLOSE(c.Child(0).Base(), d.Child(0).Base(), 1e-50);
+ BOOST_REQUIRE_EQUAL(c.Child(0).Point(), d.Child(0).Point());
+ BOOST_REQUIRE_EQUAL(c.Child(0).Scale(), d.Child(0).Scale());
+ BOOST_REQUIRE_EQUAL(c.Child(0).ParentDistance(), d.Child(0).ParentDistance());
+ BOOST_REQUIRE_EQUAL(c.Child(0).FurthestDescendantDistance(),
+ d.Child(0).FurthestDescendantDistance());
+ BOOST_REQUIRE_EQUAL(c.Child(0).NumChildren(), d.Child(0).NumChildren());
+
+ BOOST_REQUIRE_EQUAL(c.Child(1).Dataset().memptr(),
+ d.Child(1).Dataset().memptr());
+ BOOST_REQUIRE_CLOSE(c.Child(1).Base(), d.Child(1).Base(), 1e-50);
+ BOOST_REQUIRE_EQUAL(c.Child(1).Point(), d.Child(1).Point());
+ BOOST_REQUIRE_EQUAL(c.Child(1).Scale(), d.Child(1).Scale());
+ BOOST_REQUIRE_EQUAL(c.Child(1).ParentDistance(), d.Child(1).ParentDistance());
+ BOOST_REQUIRE_EQUAL(c.Child(1).FurthestDescendantDistance(),
+ d.Child(1).FurthestDescendantDistance());
+ BOOST_REQUIRE_EQUAL(c.Child(1).NumChildren(), d.Child(1).NumChildren());
+}
+
+/**
+ * Make sure copy constructor works right for the binary space tree.
+ */
+BOOST_AUTO_TEST_CASE(BinarySpaceTreeCopyConstructor)
+{
+ arma::mat data("1");
+ BinarySpaceTree<HRectBound<2> > b(data);
+ b.Begin() = 10;
+ b.Count() = 50;
+ b.Left() = new BinarySpaceTree<HRectBound<2> >(data);
+ b.Left()->Begin() = 10;
+ b.Left()->Count() = 30;
+ b.Right() = new BinarySpaceTree<HRectBound<2> >(data);
+ b.Right()->Begin() = 40;
+ b.Right()->Count() = 20;
+
+ // Copy the tree.
+ BinarySpaceTree<HRectBound<2> > c(b);
+
+ // Ensure everything copied correctly.
+ BOOST_REQUIRE_EQUAL(b.Begin(), c.Begin());
+ BOOST_REQUIRE_EQUAL(b.Count(), c.Count());
+ BOOST_REQUIRE_NE(b.Left(), c.Left());
+ BOOST_REQUIRE_NE(b.Right(), c.Right());
+
+ // Check the children.
+ BOOST_REQUIRE_EQUAL(b.Left()->Begin(), c.Left()->Begin());
+ BOOST_REQUIRE_EQUAL(b.Left()->Count(), c.Left()->Count());
+ BOOST_REQUIRE_EQUAL(b.Left()->Left(),
+ (BinarySpaceTree<HRectBound<2> >*) NULL);
+ BOOST_REQUIRE_EQUAL(b.Left()->Left(), c.Left()->Left());
+ BOOST_REQUIRE_EQUAL(b.Left()->Right(),
+ (BinarySpaceTree<HRectBound<2> >*) NULL);
+ BOOST_REQUIRE_EQUAL(b.Left()->Right(), c.Left()->Right());
+
+ BOOST_REQUIRE_EQUAL(b.Right()->Begin(), c.Right()->Begin());
+ BOOST_REQUIRE_EQUAL(b.Right()->Count(), c.Right()->Count());
+ BOOST_REQUIRE_EQUAL(b.Right()->Left(),
+ (BinarySpaceTree<HRectBound<2> >*) NULL);
+ BOOST_REQUIRE_EQUAL(b.Right()->Left(), c.Right()->Left());
+ BOOST_REQUIRE_EQUAL(b.Right()->Right(),
+ (BinarySpaceTree<HRectBound<2> >*) NULL);
+ 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);
+}
+
+
+/**
* Make sure that constructor for cosine tree is working
*/
BOOST_AUTO_TEST_CASE(CosineTreeConstructorTest)
More information about the mlpack-svn
mailing list