Tests for tree-building methods. More...
#include <mlpack/core.hpp>#include <mlpack/core/tree/bounds.hpp>#include <mlpack/core/tree/binary_space_tree.hpp>#include <mlpack/core/metrics/lmetric.hpp>#include <mlpack/core/metrics/mahalanobis_distance.hpp>#include <mlpack/core/tree/cover_tree/cover_tree.hpp>#include <mlpack/core/tree/rectangle_tree.hpp>#include <queue>#include <stack>#include "catch.hpp"#include "test_catch_tools.hpp"
Functions | |
| TEST_CASE ("HRectBoundEmptyConstructor", "[TreeTest]") | |
| Ensure that a bound, by default, is empty and has no dimensionality. | |
| TEST_CASE ("HRectBoundDimConstructor", "[TreeTest]") | |
| Ensure that when we specify the dimensionality in the constructor, it is correct, and the bounds are all the empty set. | |
| TEST_CASE ("HRectBoundCopyConstructor", "[TreeTest]") | |
| Test the copy constructor. | |
| TEST_CASE ("HRectBoundAssignmentOperator", "[TreeTest]") | |
| Test the assignment operator. | |
| TEST_CASE ("HRectBoundClear", "[TreeTest]") | |
| Test that clearing the dimensions resets the bound to empty. | |
| TEST_CASE ("HRectBoundMoveConstructor", "[TreeTest]") | |
| TEST_CASE ("HRectBoundCenter", "[TreeTest]") | |
| Ensure that we get the correct center for our bound. | |
| TEST_CASE ("HRectBoundVolume", "[TreeTest]") | |
| Ensure the volume calculation is correct. | |
| TEST_CASE ("HRectBoundMinDistancePoint", "[TreeTest]") | |
| Ensure that we calculate the correct minimum distance between a point and a bound. | |
| TEST_CASE ("HRectBoundMinDistanceBound", "[TreeTest]") | |
| Ensure that we calculate the correct minimum distance between a bound and another bound. | |
| TEST_CASE ("HRectBoundMaxDistancePoint", "[TreeTest]") | |
| Ensure that we calculate the correct maximum distance between a bound and a point. More... | |
| TEST_CASE ("HRectBoundMaxDistanceBound", "[TreeTest]") | |
| Ensure that we calculate the correct maximum distance between a bound and another bound. More... | |
| TEST_CASE ("HRectBoundRangeDistanceBound", "[TreeTest]") | |
| Ensure that the ranges returned by RangeDistance() are equal to the minimum and maximum distance. More... | |
| TEST_CASE ("HRectBoundRangeDistancePoint", "[TreeTest]") | |
| Ensure that the ranges returned by RangeDistance() are equal to the minimum and maximum distance. More... | |
| TEST_CASE ("HRectBoundOrOperatorPoint", "[TreeTest]") | |
| Test that we can expand the bound to include a new point. | |
| TEST_CASE ("HRectBoundOrOperatorBound", "[TreeTest]") | |
| Test that we can expand the bound to include another bound. | |
| TEST_CASE ("HRectBoundContains", "[TreeTest]") | |
| Test that the Contains() function correctly figures out whether or not a point is in a bound. | |
| TEST_CASE ("TestBallBound", "[TreeTest]") | |
| TEST_CASE ("BallBoundMoveConstructor", "[TreeTest]") | |
| TEST_CASE ("HRectBoundRootMinDistancePoint", "[TreeTest]") | |
| Ensure that we calculate the correct minimum distance between a point and a bound. | |
| TEST_CASE ("HRectBoundRootMinDistanceBound", "[TreeTest]") | |
| Ensure that we calculate the correct minimum distance between a bound and another bound. | |
| TEST_CASE ("HRectBoundRootMaxDistancePoint", "[TreeTest]") | |
| Ensure that we calculate the correct maximum distance between a bound and a point. More... | |
| TEST_CASE ("HRectBoundRootMaxDistanceBound", "[TreeTest]") | |
| Ensure that we calculate the correct maximum distance between a bound and another bound. More... | |
| TEST_CASE ("HRectBoundRootRangeDistanceBound", "[TreeTest]") | |
| Ensure that the ranges returned by RangeDistance() are equal to the minimum and maximum distance. More... | |
| TEST_CASE ("HRectBoundRootRangeDistancePoint", "[TreeTest]") | |
| Ensure that the ranges returned by RangeDistance() are equal to the minimum and maximum distance. More... | |
| TEST_CASE ("HRectBoundDiameter", "[TreeTest]") | |
| Ensure that HRectBound::Diameter() works properly. | |
| TEST_CASE ("TreeCountMismatch", "[TreeTest]") | |
| It seems as though Bill has stumbled across a bug where BinarySpaceTree<>::count() returns something different than BinarySpaceTree<>::count_. More... | |
| TEST_CASE ("CheckParents", "[TreeTest]") | |
| TEST_CASE ("CheckDataset", "[TreeTest]") | |
| TEST_CASE ("FurthestDescendantDistanceTest", "[TreeTest]") | |
| TEST_CASE ("FurthestPointDistanceTest", "[TreeTest]") | |
| TEST_CASE ("ParentDistanceTest", "[TreeTest]") | |
| TEST_CASE ("ParentDistanceTestWithMapping", "[TreeTest]") | |
| template<typename TreeType > | |
| bool | CheckPointBounds (TreeType &node) |
| template<typename TreeType > | |
| void | GenerateVectorOfTree (TreeType *node, size_t depth, std::vector< TreeType *> &v) |
| TEST_CASE ("KdTreeTest", "[TreeTest]") | |
| Exhaustive kd-tree test based on #125. More... | |
| TEST_CASE ("MaxRPTreeTest", "[TreeTest]") | |
| template<typename TreeType > | |
| bool | CheckHyperplaneSplit (const TreeType &tree) |
| template<typename TreeType > | |
| void | CheckMaxRPTreeSplit (const TreeType &tree) |
| TEST_CASE ("MaxRPTreeSplitTest", "[TreeTest]") | |
| TEST_CASE ("RPTreeTest", "[TreeTest]") | |
| template<typename TreeType , typename MetricType > | |
| void | CheckRPTreeSplit (const TreeType &tree) |
| TEST_CASE ("RPTreeSplitTest", "[TreeTest]") | |
| TEST_CASE ("BallTreeTest", "[TreeTest]") | |
| Exhaustive ball tree test based on #125. More... | |
| TEST_CASE ("MahalanobisBallTreeTest", "[TreeTest]") | |
| Ensure that we can build a ball tree with a custom instantiated metric type. | |
| TEST_CASE ("ExhaustiveSparseKDTreeTest", "[TreeTest]") | |
| Exhaustive sparse kd-tree test based on #125. More... | |
| TEST_CASE ("BinarySpaceTreeMoveConstructorTest", "[TreeTest]") | |
| template<typename TreeType > | |
| void | RecurseTreeCountLeaves (const TreeType &node, arma::vec &counts) |
| template<typename TreeType > | |
| void | CheckSelfChild (const TreeType &node) |
| template<typename TreeType , typename MetricType > | |
| void | CheckCovering (const TreeType &node) |
| TEST_CASE ("SimpleCoverTreeConstructionTest", "[TreeTest]") | |
| Create a simple cover tree and then make sure it is valid. | |
| TEST_CASE ("CoverTreeConstructionTest", "[TreeTest]") | |
| Create a large cover tree and make sure it's accurate. | |
| TEST_CASE ("SparseCoverTreeConstructionTest", "[TreeTest]") | |
| Create a cover tree on sparse data and make sure it's accurate. | |
| TEST_CASE ("CoverTreeManualConstructorTest", "[TreeTest]") | |
| Test the manual constructor. | |
| TEST_CASE ("CoverTreeAlternateMetricTest", "[TreeTest]") | |
| Make sure cover trees work in different metric spaces. | |
| TEST_CASE ("CoverTreeCopyConstructor", "[TreeTest]") | |
| Make sure copy constructor works for the cover tree. | |
| TEST_CASE ("CoverTreeMoveDatasetTest", "[TreeTest]") | |
| TEST_CASE ("BinarySpaceTreeCopyConstructor", "[TreeTest]") | |
| Make sure copy constructor works right for the binary space tree. | |
| template<typename TreeType > | |
| size_t | NumLeaves (TreeType *node) |
| Count the number of leaves under this node. | |
| template<typename TreeType > | |
| bool | FindIndex (TreeType *node, const size_t index) |
| Returns true if the index is contained somewhere under this node. | |
| template<typename TreeType > | |
| bool | CheckAccessibility (TreeType *childNode, TreeType *rootNode) |
| Check that the points in the given node are accessible through the Descendant() function of the root node. More... | |
| template<typename TreeType > | |
| void | CheckDescendants (TreeType *node) |
| Check that Descendant() and NumDescendants() is right for this node. | |
| TEST_CASE ("CoverTreeDescendantTest", "[TreeTest]") | |
| Make sure Descendant() and NumDescendants() works properly for the cover tree. | |
Detailed Description
Tests for tree-building methods.
mlpack is free software; you may redistribute it and/or modify it under the terms of the 3-clause BSD license. You should have received a copy of the 3-clause BSD license along with mlpack. If not, see http://www.opensource.org/licenses/BSD-3-Clause for more information.
Function Documentation
◆ CheckAccessibility()
| bool CheckAccessibility | ( | TreeType * | childNode, |
| TreeType * | rootNode | ||
| ) |
Check that the points in the given node are accessible through the Descendant() function of the root node.
◆ TEST_CASE() [1/12]
| TEST_CASE | ( | "HRectBoundMaxDistancePoint" | , |
| "" | [TreeTest] | ||
| ) |
Ensure that we calculate the correct maximum distance between a bound and a point.
This uses the same test cases as the MinDistance test.
◆ TEST_CASE() [2/12]
| TEST_CASE | ( | "HRectBoundMaxDistanceBound" | , |
| "" | [TreeTest] | ||
| ) |
Ensure that we calculate the correct maximum distance between a bound and another bound.
This uses the same test cases as the MinDistance test.
◆ TEST_CASE() [3/12]
| TEST_CASE | ( | "HRectBoundRangeDistanceBound" | , |
| "" | [TreeTest] | ||
| ) |
Ensure that the ranges returned by RangeDistance() are equal to the minimum 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.
◆ TEST_CASE() [4/12]
| TEST_CASE | ( | "HRectBoundRangeDistancePoint" | , |
| "" | [TreeTest] | ||
| ) |
Ensure that the ranges returned by RangeDistance() are equal to the minimum and maximum distance.
We will perform this test by creating random bounds and comparing the bheavior to MinDistance() and MaxDistance() – so this test is assuming that those passed and operate correctly. This is for the bound-to-point case.
◆ TEST_CASE() [5/12]
| TEST_CASE | ( | "HRectBoundRootMaxDistancePoint" | , |
| "" | [TreeTest] | ||
| ) |
Ensure that we calculate the correct maximum distance between a bound and a point.
This uses the same test cases as the MinDistance test.
◆ TEST_CASE() [6/12]
| TEST_CASE | ( | "HRectBoundRootMaxDistanceBound" | , |
| "" | [TreeTest] | ||
| ) |
Ensure that we calculate the correct maximum distance between a bound and another bound.
This uses the same test cases as the MinDistance test.
◆ TEST_CASE() [7/12]
| TEST_CASE | ( | "HRectBoundRootRangeDistanceBound" | , |
| "" | [TreeTest] | ||
| ) |
Ensure that the ranges returned by RangeDistance() are equal to the minimum 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.
◆ TEST_CASE() [8/12]
| TEST_CASE | ( | "HRectBoundRootRangeDistancePoint" | , |
| "" | [TreeTest] | ||
| ) |
Ensure that the ranges returned by RangeDistance() are equal to the minimum and maximum distance.
We will perform this test by creating random bounds and comparing the bheavior to MinDistance() and MaxDistance() – so this test is assuming that those passed and operate correctly. This is for the bound-to-point case.
◆ TEST_CASE() [9/12]
| TEST_CASE | ( | "TreeCountMismatch" | , |
| "" | [TreeTest] | ||
| ) |
It seems as though Bill has stumbled across a bug where BinarySpaceTree<>::count() returns something different than BinarySpaceTree<>::count_.
So, let's build a simple tree and make sure they are the same.
◆ TEST_CASE() [10/12]
| TEST_CASE | ( | "KdTreeTest" | , |
| "" | [TreeTest] | ||
| ) |
Exhaustive kd-tree test based on #125.
- Generate a random dataset of a random size.
- Build a tree on that dataset.
- Ensure all the permutation indices map back to the correct points.
- Verify that each point is contained inside all of the bounds of its parent nodes.
- Verify that each bound at a particular level of the tree does not overlap with any other bounds at that level.
Then, we do that whole process a handful of times.
◆ TEST_CASE() [11/12]
| TEST_CASE | ( | "BallTreeTest" | , |
| "" | [TreeTest] | ||
| ) |
Exhaustive ball tree test based on #125.
- Generate a random dataset of a random size.
- Build a tree on that dataset.
- Ensure all the permutation indices map back to the correct points.
- Verify that each point is contained inside all of the bounds of its parent nodes.
Then, we do that whole process a handful of times.
◆ TEST_CASE() [12/12]
| TEST_CASE | ( | "ExhaustiveSparseKDTreeTest" | , |
| "" | [TreeTest] | ||
| ) |
Exhaustive sparse kd-tree test based on #125.
- Generate a random dataset of a random size.
- Build a tree on that dataset.
- Ensure all the permutation indices map back to the correct points.
- Verify that each point is contained inside all of the bounds of its parent nodes.
- Verify that each bound at a particular level of the tree does not overlap with any other bounds at that level.
Then, we do that whole process a handful of times.
