From 83dd60a38920cdf85e4c1108404cfa7c294f98e2 Mon Sep 17 00:00:00 2001 From: skachano Date: Wed, 22 Jun 2016 09:42:57 +0000 Subject: Took into account Clément's remarks MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/subsampling_and_spatialsearching@1328 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 6f1db13d0e8cec8e64c5bb30da53b72b00446de3 --- src/Subsampling/include/gudhi/Pick_random_points.h | 78 -------------------- .../include/gudhi/choose_by_farthest_point.h | 31 ++++---- src/Subsampling/include/gudhi/pick_random_points.h | 82 ++++++++++++++++++++++ .../test/test_choose_farthest_point.cpp | 8 +-- src/Subsampling/test/test_pick_random_points.cpp | 10 +-- 5 files changed, 106 insertions(+), 103 deletions(-) delete mode 100644 src/Subsampling/include/gudhi/Pick_random_points.h create mode 100644 src/Subsampling/include/gudhi/pick_random_points.h (limited to 'src/Subsampling') diff --git a/src/Subsampling/include/gudhi/Pick_random_points.h b/src/Subsampling/include/gudhi/Pick_random_points.h deleted file mode 100644 index 98902264..00000000 --- a/src/Subsampling/include/gudhi/Pick_random_points.h +++ /dev/null @@ -1,78 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): Siargey Kachanovich - * - * Copyright (C) 2016 INRIA - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ - -#ifndef PICK_RANDOM_POINTS_H_ -#define PICK_RANDOM_POINTS_H_ - -#include - -#include // random_device, mt19937 -#include // shuffle -#include // iota -#include -#include - - -namespace Gudhi { - - /** - * \ingroup witness_complex - * \brief Landmark choice strategy by taking random vertices for landmarks. - * - * \details It chooses nbL distinct landmarks from a random access range `points` - * and outputs them to an output iterator. - * Point_container::iterator should be ValueSwappable and RandomAccessIterator. - */ - - template - void pick_random_points(Point_container const &points, - unsigned nbL, - OutputIterator output_it) { -#ifdef GUDHI_LM_PROFILING - Gudhi::Clock t; -#endif - - unsigned nbP = boost::size(points); - assert(nbP >= nbL); - std::vector landmarks(nbP); - std::iota(landmarks.begin(), landmarks.end(), 0); - - std::random_device rd; - std::mt19937 g(rd()); - - std::shuffle(landmarks.begin(), landmarks.end(), g); - landmarks.resize(nbL); - - for (int l: landmarks) - *output_it++ = points[l]; - -#ifdef GUDHI_LM_PROFILING - t.end(); - std::cerr << "Random landmark choice took " << t.num_seconds() - << " seconds." << std::endl; -#endif - } - -} // namespace Gudhi - -#endif // PICK_RANDOM_POINTS_H_ diff --git a/src/Subsampling/include/gudhi/choose_by_farthest_point.h b/src/Subsampling/include/gudhi/choose_by_farthest_point.h index 2918983f..52647c16 100644 --- a/src/Subsampling/include/gudhi/choose_by_farthest_point.h +++ b/src/Subsampling/include/gudhi/choose_by_farthest_point.h @@ -31,32 +31,29 @@ #include namespace Gudhi { - + +namespace subsampling { /** - * \ingroup witness_complex - * \brief Landmark choice strategy by iteratively adding the farthest witness from the - * current landmark set as the new landmark. - * \details It chooses nbL landmarks from a random access range `points` and - * writes {witness}*{closest landmarks} matrix in `knn`. - * - * The type KNearestNeighbors can be seen as - * Witness_range>, where - * Witness_range and Closest_landmark_range are random access ranges + * \ingroup subsampling + * \brief Subsample by a greedy strategy of iteratively adding the farthest point from the + * current chosen point set to the subsampling. + * \details It chooses `final_size` points from a random access range `points` and + * outputs it in the output iterator `output_it`. * */ template < typename Kernel, typename Point_container, typename OutputIterator> - void choose_by_farthest_point(Kernel& k, - Point_container const &points, - int nbL, - OutputIterator output_it) + void choose_by_farthest_point( Kernel& k, + Point_container const &points, + int final_size, + OutputIterator output_it) { typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); int nb_points = boost::size(points); - assert(nb_points >= nbL); + assert(nb_points >= final_size); int current_number_of_landmarks = 0; // counter for landmarks double curr_max_dist = 0; // used for defining the furhest point from L @@ -69,7 +66,7 @@ namespace Gudhi { std::uniform_int_distribution<> dis(1, 6); int curr_max_w = dis(gen); - for (current_number_of_landmarks = 0; current_number_of_landmarks != nbL; current_number_of_landmarks++) { + for (current_number_of_landmarks = 0; current_number_of_landmarks != final_size; current_number_of_landmarks++) { // curr_max_w at this point is the next landmark *output_it++ = points[curr_max_w]; // std::cout << curr_max_w << "\n"; @@ -89,6 +86,8 @@ namespace Gudhi { } } } + +} // namespace subsampling } // namespace Gudhi diff --git a/src/Subsampling/include/gudhi/pick_random_points.h b/src/Subsampling/include/gudhi/pick_random_points.h new file mode 100644 index 00000000..732ae3f7 --- /dev/null +++ b/src/Subsampling/include/gudhi/pick_random_points.h @@ -0,0 +1,82 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): Siargey Kachanovich + * + * Copyright (C) 2016 INRIA + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program 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 General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef PICK_RANDOM_POINTS_H_ +#define PICK_RANDOM_POINTS_H_ + +#include + +#include // random_device, mt19937 +#include // shuffle +#include // iota +#include +#include + + +namespace Gudhi { + +namespace subsampling { + + /** + * \ingroup subsampling + * \brief Subsample a point set by picking random vertices. + * + * \details It chooses `final_size` distinct points from a random access range `points` + * and outputs them to the output iterator `output_it`. + * Point_container::iterator should be ValueSwappable and RandomAccessIterator. + */ + + template + void pick_random_points(Point_container const &points, + unsigned final_size, + OutputIterator output_it) { +#ifdef GUDHI_SUBS_PROFILING + Gudhi::Clock t; +#endif + + unsigned nbP = boost::size(points); + assert(nbP >= final_size); + std::vector landmarks(nbP); + std::iota(landmarks.begin(), landmarks.end(), 0); + + std::random_device rd; + std::mt19937 g(rd()); + + std::shuffle(landmarks.begin(), landmarks.end(), g); + landmarks.resize(final_size); + + for (int l: landmarks) + *output_it++ = points[l]; + +#ifdef GUDHI_SUBS_PROFILING + t.end(); + std::cerr << "Random landmark choice took " << t.num_seconds() + << " seconds." << std::endl; +#endif + } + +} // namesapce subsampling + +} // namespace Gudhi + +#endif // PICK_RANDOM_POINTS_H_ diff --git a/src/Subsampling/test/test_choose_farthest_point.cpp b/src/Subsampling/test/test_choose_farthest_point.cpp index 991fcbfe..87c2c38d 100644 --- a/src/Subsampling/test/test_choose_farthest_point.cpp +++ b/src/Subsampling/test/test_choose_farthest_point.cpp @@ -41,7 +41,7 @@ typedef typename K::Point_d Point_d; BOOST_AUTO_TEST_CASE(test_choose_farthest_point) { - std::vector< Point_d > points, landmarks; + std::vector< Point_d > points, results; // Add grid points (625 points) for (FT i = 0; i < 5; i += 1.0) for (FT j = 0; j < 5; j += 1.0) @@ -49,9 +49,9 @@ BOOST_AUTO_TEST_CASE(test_choose_farthest_point) { for (FT l = 0; l < 5; l += 1.0) points.push_back(Point_d(std::vector({i, j, k, l}))); - landmarks.clear(); + results.clear(); K k; - Gudhi::choose_by_farthest_point(k, points, 100, std::back_inserter(landmarks)); + Gudhi::subsampling::choose_by_farthest_point(k, points, 100, std::back_inserter(results)); - assert(landmarks.size() == 100); + assert(results.size() == 100); } diff --git a/src/Subsampling/test/test_pick_random_points.cpp b/src/Subsampling/test/test_pick_random_points.cpp index 81c7ffdb..8156160e 100644 --- a/src/Subsampling/test/test_pick_random_points.cpp +++ b/src/Subsampling/test/test_pick_random_points.cpp @@ -24,7 +24,7 @@ // # define TBB_USE_THREADING_TOOL // #endif -#include +#include #include #include @@ -55,11 +55,11 @@ int main() { vect.push_back(Point_d(std::vector({1,1,1,1}))); - std::vector landmarks; - Gudhi::pick_random_points(vect, 5, std::back_inserter(landmarks)); + std::vector results; + Gudhi::subsampling::pick_random_points(vect, 5, std::back_inserter(results)); std::cout << "landmark vector contains: "; - for (auto l: landmarks) + for (auto l: results) std::cout << l << "\n"; - assert(landmarks_size() == 5); + assert(results.size() == 5); } -- cgit v1.2.3