From 2bbba93e7f0837b42def9bed13a6fa790c0eabda Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sat, 31 Oct 2020 23:39:01 +0100 Subject: s/kernel/distance/ for choose_n_farthest_points argument --- src/Subsampling/example/CMakeLists.txt | 4 +- .../example/example_choose_n_farthest_points.cpp | 2 +- .../example/example_custom_distance.cpp | 44 +++++++++++++++ src/Subsampling/example/example_custom_kernel.cpp | 63 ---------------------- .../include/gudhi/choose_n_farthest_points.h | 26 +++++---- .../test/test_choose_n_farthest_points.cpp | 20 +++---- 6 files changed, 70 insertions(+), 89 deletions(-) create mode 100644 src/Subsampling/example/example_custom_distance.cpp delete mode 100644 src/Subsampling/example/example_custom_kernel.cpp (limited to 'src/Subsampling') diff --git a/src/Subsampling/example/CMakeLists.txt b/src/Subsampling/example/CMakeLists.txt index 28aab103..fb6875e1 100644 --- a/src/Subsampling/example/CMakeLists.txt +++ b/src/Subsampling/example/CMakeLists.txt @@ -3,7 +3,7 @@ project(Subsampling_examples) if(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0) add_executable(Subsampling_example_pick_n_random_points example_pick_n_random_points.cpp) add_executable(Subsampling_example_choose_n_farthest_points example_choose_n_farthest_points.cpp) - add_executable(Subsampling_example_custom_kernel example_custom_kernel.cpp) + add_executable(Subsampling_example_custom_distance example_custom_distance.cpp) add_executable(Subsampling_example_sparsify_point_set example_sparsify_point_set.cpp) target_link_libraries(Subsampling_example_sparsify_point_set ${CGAL_LIBRARY}) @@ -16,7 +16,7 @@ if(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0) install(TARGETS Subsampling_example_pick_n_random_points DESTINATION bin) install(TARGETS Subsampling_example_choose_n_farthest_points DESTINATION bin) - install(TARGETS Subsampling_example_custom_kernel DESTINATION bin) + install(TARGETS Subsampling_example_custom_distance DESTINATION bin) install(TARGETS Subsampling_example_sparsify_point_set DESTINATION bin) endif(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0) diff --git a/src/Subsampling/example/example_choose_n_farthest_points.cpp b/src/Subsampling/example/example_choose_n_farthest_points.cpp index 27cf5d4e..e8b3ce2d 100644 --- a/src/Subsampling/example/example_choose_n_farthest_points.cpp +++ b/src/Subsampling/example/example_choose_n_farthest_points.cpp @@ -20,7 +20,7 @@ int main(void) { K k; std::vector results; - Gudhi::subsampling::choose_n_farthest_points(k, points, 100, + Gudhi::subsampling::choose_n_farthest_points(k.squared_distance_d_object(), points, 100, Gudhi::subsampling::random_starting_point, std::back_inserter(results)); std::clog << "Before sparsification: " << points.size() << " points.\n"; diff --git a/src/Subsampling/example/example_custom_distance.cpp b/src/Subsampling/example/example_custom_distance.cpp new file mode 100644 index 00000000..3325b12d --- /dev/null +++ b/src/Subsampling/example/example_custom_distance.cpp @@ -0,0 +1,44 @@ +#include + +#include +#include +#include + + +typedef unsigned Point; + +/* The class Distance contains a distance function defined on the set of points {0, 1, 2, 3} + * and computes a distance according to the matrix: + * 0 1 2 4 + * 1 0 4 2 + * 2 4 0 1 + * 4 2 1 0 + */ +class Distance { + private: + std::vector> matrix_; + + public: + Distance() { + matrix_.push_back({0, 1, 2, 4}); + matrix_.push_back({1, 0, 4, 2}); + matrix_.push_back({2, 4, 0, 1}); + matrix_.push_back({4, 2, 1, 0}); + } + + double operator()(Point p1, Point p2) const { + return matrix_[p1][p2]; + } +}; + +int main(void) { + std::vector points = {0, 1, 2, 3}; + std::vector results; + + Gudhi::subsampling::choose_n_farthest_points(Distance(), points, 2, + Gudhi::subsampling::random_starting_point, + std::back_inserter(results)); + std::clog << "Before sparsification: " << points.size() << " points.\n"; + std::clog << "After sparsification: " << results.size() << " points.\n"; + std::clog << "Result table: {" << results[0] << "," << results[1] << "}\n"; +} diff --git a/src/Subsampling/example/example_custom_kernel.cpp b/src/Subsampling/example/example_custom_kernel.cpp deleted file mode 100644 index 535bf42a..00000000 --- a/src/Subsampling/example/example_custom_kernel.cpp +++ /dev/null @@ -1,63 +0,0 @@ -#include - -#include -#include -#include - - -/* The class Kernel contains a distance function defined on the set of points {0, 1, 2, 3} - * and computes a distance according to the matrix: - * 0 1 2 4 - * 1 0 4 2 - * 2 4 0 1 - * 4 2 1 0 - */ -class Kernel { - public: - typedef double FT; - typedef unsigned Point_d; - - // Class Squared_distance_d - class Squared_distance_d { - private: - std::vector> matrix_; - - public: - Squared_distance_d() { - matrix_.push_back(std::vector({0, 1, 2, 4})); - matrix_.push_back(std::vector({1, 0, 4, 2})); - matrix_.push_back(std::vector({2, 4, 0, 1})); - matrix_.push_back(std::vector({4, 2, 1, 0})); - } - - FT operator()(Point_d p1, Point_d p2) { - return matrix_[p1][p2]; - } - }; - - // Constructor - Kernel() {} - - // Object of type Squared_distance_d - Squared_distance_d squared_distance_d_object() const { - return Squared_distance_d(); - } -}; - -int main(void) { - typedef Kernel K; - typedef typename K::Point_d Point_d; - - K k; - std::vector points = {0, 1, 2, 3}; - std::vector results; - - Gudhi::subsampling::choose_n_farthest_points(k, points, 2, - Gudhi::subsampling::random_starting_point, - std::back_inserter(results)); - std::clog << "Before sparsification: " << points.size() << " points.\n"; - std::clog << "After sparsification: " << results.size() << " points.\n"; - std::clog << "Result table: {" << results[0] << "," << results[1] << "}\n"; - - return 0; -} diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h index b70af8a0..561dcf3e 100644 --- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -38,33 +38,33 @@ enum : std::size_t { * \ingroup subsampling * \brief Subsample by a greedy strategy of iteratively adding the farthest point from the * current chosen point set to the subsampling. - * The iteration starts with the landmark `starting point` or, if `starting point==random_starting_point`, with a random landmark. - * \tparam Kernel must provide a type Kernel::Squared_distance_d which is a model of the - * concept Kernel_d::Squared_distance_d (despite the name, taken from CGAL, this can be any kind of metric or proximity measure). - * It must also contain a public member `squared_distance_d_object()` that returns an object of this type. - * \tparam Point_range Range whose value type is Kernel::Point_d. It must provide random-access - * via `operator[]` and the points should be stored contiguously in memory. - * \tparam PointOutputIterator Output iterator whose value type is Kernel::Point_d. + * The iteration starts with the landmark `starting point` or, if `starting point==random_starting_point`, + * with a random landmark. + * \tparam Distance must provide an operator() that takes 2 points (value type of the range) + * and returns their distance (or some more general proximity measure). + * \tparam Point_range Random access range of points. + * \tparam PointOutputIterator Output iterator whose value type is the point type. * \tparam DistanceOutputIterator Output iterator for distances. * \details It chooses `final_size` points from a random access range * `input_pts` (or the number of distinct points if `final_size` is larger) * and outputs them in the output iterator `output_it`. It also * outputs the distance from each of those points to the set of previous * points in `dist_it`. - * @param[in] k A kernel object. + * @param[in] dist A distance function. * @param[in] input_pts Const reference to the input points. * @param[in] final_size The size of the subsample to compute. * @param[in] starting_point The seed in the farthest point algorithm. * @param[out] output_it The output iterator for points. * @param[out] dist_it The optional output iterator for distances. + * + * \warning Older versions of this function took a CGAL kernel as argument. Users need to replace `k` with `k.squared_distance_d_object()` in the first argument of every call to `choose_n_farthest_points`. * */ -template < typename Kernel, +template < typename Distance, typename Point_range, typename PointOutputIterator, typename DistanceOutputIterator = Null_output_iterator> -void choose_n_farthest_points(Kernel const &k, +void choose_n_farthest_points(Distance dist, Point_range const &input_pts, std::size_t final_size, std::size_t starting_point, @@ -86,8 +86,6 @@ void choose_n_farthest_points(Kernel const &k, starting_point = dis(gen); } - typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); - std::size_t current_number_of_landmarks = 0; // counter for landmarks const double infty = std::numeric_limits::infinity(); // infinity (see next entry) std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from input_pts @@ -100,7 +98,7 @@ void choose_n_farthest_points(Kernel const &k, *dist_it++ = dist_to_L[curr_max_w]; std::size_t i = 0; for (auto&& p : input_pts) { - double curr_dist = sqdist(p, input_pts[curr_max_w]); + double curr_dist = dist(p, input_pts[curr_max_w]); if (curr_dist < dist_to_L[i]) dist_to_L[i] = curr_dist; ++i; diff --git a/src/Subsampling/test/test_choose_n_farthest_points.cpp b/src/Subsampling/test/test_choose_n_farthest_points.cpp index b318d58e..94793295 100644 --- a/src/Subsampling/test/test_choose_n_farthest_points.cpp +++ b/src/Subsampling/test/test_choose_n_farthest_points.cpp @@ -44,7 +44,8 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(test_choose_farthest_point, Kernel, list_of_tested landmarks.clear(); Kernel k; - Gudhi::subsampling::choose_n_farthest_points(k, points, 100, Gudhi::subsampling::random_starting_point, std::back_inserter(landmarks)); + auto d = k.squared_distance_d_object(); + Gudhi::subsampling::choose_n_farthest_points(d, points, 100, Gudhi::subsampling::random_starting_point, std::back_inserter(landmarks)); BOOST_CHECK(landmarks.size() == 100); for (auto landmark : landmarks) @@ -61,32 +62,33 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(test_choose_farthest_point_limits, Kernel, list_of std::vector< FT > distances; landmarks.clear(); Kernel k; + auto d = k.squared_distance_d_object(); // Choose -1 farthest points in an empty point cloud - Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); + Gudhi::subsampling::choose_n_farthest_points(d, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); BOOST_CHECK(landmarks.size() == 0); landmarks.clear(); distances.clear(); // Choose 0 farthest points in an empty point cloud - Gudhi::subsampling::choose_n_farthest_points(k, points, 0, -1, std::back_inserter(landmarks), std::back_inserter(distances)); + Gudhi::subsampling::choose_n_farthest_points(d, points, 0, -1, std::back_inserter(landmarks), std::back_inserter(distances)); BOOST_CHECK(landmarks.size() == 0); landmarks.clear(); distances.clear(); // Choose 1 farthest points in an empty point cloud - Gudhi::subsampling::choose_n_farthest_points(k, points, 1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); + Gudhi::subsampling::choose_n_farthest_points(d, points, 1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); BOOST_CHECK(landmarks.size() == 0); landmarks.clear(); distances.clear(); std::vector point({0.0, 0.0, 0.0, 0.0}); points.emplace_back(point.begin(), point.end()); // Choose -1 farthest points in a one point cloud - Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); + Gudhi::subsampling::choose_n_farthest_points(d, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); BOOST_CHECK(landmarks.size() == 1 && distances.size() == 1); BOOST_CHECK(distances[0] == std::numeric_limits::infinity()); landmarks.clear(); distances.clear(); // Choose 0 farthest points in a one point cloud - Gudhi::subsampling::choose_n_farthest_points(k, points, 0, -1, std::back_inserter(landmarks), std::back_inserter(distances)); + Gudhi::subsampling::choose_n_farthest_points(d, points, 0, -1, std::back_inserter(landmarks), std::back_inserter(distances)); BOOST_CHECK(landmarks.size() == 0 && distances.size() == 0); landmarks.clear(); distances.clear(); // Choose 1 farthest points in a one point cloud - Gudhi::subsampling::choose_n_farthest_points(k, points, 1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); + Gudhi::subsampling::choose_n_farthest_points(d, points, 1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); BOOST_CHECK(landmarks.size() == 1 && distances.size() == 1); BOOST_CHECK(distances[0] == std::numeric_limits::infinity()); landmarks.clear(); distances.clear(); @@ -94,7 +96,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(test_choose_farthest_point_limits, Kernel, list_of std::vector point2({1.0, 0.0, 0.0, 0.0}); points.emplace_back(point2.begin(), point2.end()); // Choose all farthest points among 2 points - Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); + Gudhi::subsampling::choose_n_farthest_points(d, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); BOOST_CHECK(landmarks.size() == 2 && distances.size() == 2); BOOST_CHECK(distances[0] == std::numeric_limits::infinity()); BOOST_CHECK(distances[1] == 1); @@ -102,7 +104,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(test_choose_farthest_point_limits, Kernel, list_of // Ignore duplicated points points.emplace_back(point.begin(), point.end()); - Gudhi::subsampling::choose_n_farthest_points(k, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); + Gudhi::subsampling::choose_n_farthest_points(d, points, -1, -1, std::back_inserter(landmarks), std::back_inserter(distances)); BOOST_CHECK(landmarks.size() == 2 && distances.size() == 2); BOOST_CHECK(distances[0] == std::numeric_limits::infinity()); BOOST_CHECK(distances[1] == 1); -- cgit v1.2.3 From e3492366b040a0cac046498cdb8c2ecddfd818a9 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sat, 31 Oct 2020 23:55:57 +0100 Subject: long line --- src/Subsampling/include/gudhi/choose_n_farthest_points.h | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/Subsampling') diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h index 561dcf3e..f22cb2d7 100644 --- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -57,7 +57,8 @@ enum : std::size_t { * @param[out] output_it The output iterator for points. * @param[out] dist_it The optional output iterator for distances. * - * \warning Older versions of this function took a CGAL kernel as argument. Users need to replace `k` with `k.squared_distance_d_object()` in the first argument of every call to `choose_n_farthest_points`. + * \warning Older versions of this function took a CGAL kernel as argument. Users need to replace `k` with + * `k.squared_distance_d_object()` in the first argument of every call to `choose_n_farthest_points`. * */ template < typename Distance, -- cgit v1.2.3 From c54a40fc6293fd746e1842f6811efae96df36bed Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sun, 1 Nov 2020 20:42:43 +0100 Subject: Document that only double is supported. --- src/Subsampling/include/gudhi/choose_n_farthest_points.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'src/Subsampling') diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h index f22cb2d7..bdd2993a 100644 --- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -41,7 +41,7 @@ enum : std::size_t { * The iteration starts with the landmark `starting point` or, if `starting point==random_starting_point`, * with a random landmark. * \tparam Distance must provide an operator() that takes 2 points (value type of the range) - * and returns their distance (or some more general proximity measure). + * and returns their distance (or some more general proximity measure) as a `double`. * \tparam Point_range Random access range of points. * \tparam PointOutputIterator Output iterator whose value type is the point type. * \tparam DistanceOutputIterator Output iterator for distances. @@ -88,6 +88,8 @@ void choose_n_farthest_points(Distance dist, } std::size_t current_number_of_landmarks = 0; // counter for landmarks + static_assert(std::numeric_limits::has_infinity); + // FIXME: don't hard-code the type as double. For Epeck_d, we also want to handle types that do not have an infinity. const double infty = std::numeric_limits::infinity(); // infinity (see next entry) std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from input_pts -- cgit v1.2.3 From 7d8e6d025436f269bc2e09292f118c4d8a035660 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sun, 1 Nov 2020 20:50:40 +0100 Subject: Doc tweaks. --- src/Subsampling/include/gudhi/choose_n_farthest_points.h | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) (limited to 'src/Subsampling') diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h index bdd2993a..3c337025 100644 --- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -38,20 +38,21 @@ enum : std::size_t { * \ingroup subsampling * \brief Subsample by a greedy strategy of iteratively adding the farthest point from the * current chosen point set to the subsampling. + * \details * The iteration starts with the landmark `starting point` or, if `starting point==random_starting_point`, * with a random landmark. + * It chooses `final_size` points from a random access range + * `input_pts` (or the number of distinct points if `final_size` is larger) + * and outputs them in the output iterator `output_it`. It also + * outputs the distance from each of those points to the set of previous + * points in `dist_it`. * \tparam Distance must provide an operator() that takes 2 points (value type of the range) * and returns their distance (or some more general proximity measure) as a `double`. * \tparam Point_range Random access range of points. * \tparam PointOutputIterator Output iterator whose value type is the point type. * \tparam DistanceOutputIterator Output iterator for distances. - * \details It chooses `final_size` points from a random access range - * `input_pts` (or the number of distinct points if `final_size` is larger) - * and outputs them in the output iterator `output_it`. It also - * outputs the distance from each of those points to the set of previous - * points in `dist_it`. * @param[in] dist A distance function. - * @param[in] input_pts Const reference to the input points. + * @param[in] input_pts The input points. * @param[in] final_size The size of the subsample to compute. * @param[in] starting_point The seed in the farthest point algorithm. * @param[out] output_it The output iterator for points. -- cgit v1.2.3 From 20c50414163aabe6216c638b25c9568cfd1db458 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sun, 1 Nov 2020 21:04:21 +0100 Subject: The example does not need CGAL/eigen anymore. I had done a search and replace without checking. I don't understand why there are "install" directives for examples... --- src/Subsampling/example/CMakeLists.txt | 5 +++-- src/common/doc/installation.h | 4 ---- 2 files changed, 3 insertions(+), 6 deletions(-) (limited to 'src/Subsampling') diff --git a/src/Subsampling/example/CMakeLists.txt b/src/Subsampling/example/CMakeLists.txt index fb6875e1..bb02b37d 100644 --- a/src/Subsampling/example/CMakeLists.txt +++ b/src/Subsampling/example/CMakeLists.txt @@ -3,7 +3,6 @@ project(Subsampling_examples) if(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0) add_executable(Subsampling_example_pick_n_random_points example_pick_n_random_points.cpp) add_executable(Subsampling_example_choose_n_farthest_points example_choose_n_farthest_points.cpp) - add_executable(Subsampling_example_custom_distance example_custom_distance.cpp) add_executable(Subsampling_example_sparsify_point_set example_sparsify_point_set.cpp) target_link_libraries(Subsampling_example_sparsify_point_set ${CGAL_LIBRARY}) @@ -16,7 +15,9 @@ if(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0) install(TARGETS Subsampling_example_pick_n_random_points DESTINATION bin) install(TARGETS Subsampling_example_choose_n_farthest_points DESTINATION bin) - install(TARGETS Subsampling_example_custom_distance DESTINATION bin) install(TARGETS Subsampling_example_sparsify_point_set DESTINATION bin) endif(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0) + +add_executable(Subsampling_example_custom_distance example_custom_distance.cpp) +install(TARGETS Subsampling_example_custom_distance DESTINATION bin) diff --git a/src/common/doc/installation.h b/src/common/doc/installation.h index a6b9292b..c2e63a24 100644 --- a/src/common/doc/installation.h +++ b/src/common/doc/installation.h @@ -113,8 +113,6 @@ make doxygen * Spatial_searching/example_spatial_searching.cpp * \li * Subsampling/example_choose_n_farthest_points.cpp - * \li - * Subsampling/example_custom_distance.cpp * \li * Subsampling/example_pick_n_random_points.cpp * \li @@ -153,8 +151,6 @@ make doxygen * Spatial_searching/example_spatial_searching.cpp * \li * Subsampling/example_choose_n_farthest_points.cpp - * \li - * Subsampling/example_custom_distance.cpp * \li * Subsampling/example_pick_n_random_points.cpp * \li -- cgit v1.2.3 From 78100c3f35e6d05da3313fc8b28e24e550c8240a Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Mon, 9 Nov 2020 18:21:36 +0100 Subject: static_assert message --- src/Subsampling/include/gudhi/choose_n_farthest_points.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Subsampling') diff --git a/src/Subsampling/include/gudhi/choose_n_farthest_points.h b/src/Subsampling/include/gudhi/choose_n_farthest_points.h index 3c337025..e6347d96 100644 --- a/src/Subsampling/include/gudhi/choose_n_farthest_points.h +++ b/src/Subsampling/include/gudhi/choose_n_farthest_points.h @@ -89,7 +89,7 @@ void choose_n_farthest_points(Distance dist, } std::size_t current_number_of_landmarks = 0; // counter for landmarks - static_assert(std::numeric_limits::has_infinity); + static_assert(std::numeric_limits::has_infinity, "the number type needs to support infinity()"); // FIXME: don't hard-code the type as double. For Epeck_d, we also want to handle types that do not have an infinity. const double infty = std::numeric_limits::infinity(); // infinity (see next entry) std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from input_pts -- cgit v1.2.3