diff options
Diffstat (limited to 'src/Witness_complex')
| -rw-r--r-- | src/Witness_complex/example/witness_complex_from_file.cpp | 8 | ||||
| -rw-r--r-- | src/Witness_complex/example/witness_complex_sphere.cpp | 8 | ||||
| -rw-r--r-- | src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h (renamed from src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h) | 42 | ||||
| -rw-r--r-- | src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h | 105 | ||||
| -rw-r--r-- | src/Witness_complex/test/witness_complex_points.cpp | 16 |
5 files changed, 34 insertions, 145 deletions
diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp index 915af1ab..bb641b3c 100644 --- a/src/Witness_complex/example/witness_complex_from_file.cpp +++ b/src/Witness_complex/example/witness_complex_from_file.cpp @@ -26,7 +26,9 @@ #include <gudhi/Points_off_io.h> #include <gudhi/Simplex_tree.h> #include <gudhi/Witness_complex.h> -#include <gudhi/Landmark_choice_by_random_point.h> +#include <gudhi/Construct_closest_landmark_table.h> +#include <gudhi/pick_n_random_points.h> +#include <gudhi/reader_utils.h> #include <iostream> #include <fstream> @@ -65,7 +67,9 @@ int main(int argc, char * const argv[]) { // Choose landmarks start = clock(); std::vector<std::vector< int > > knn; - Gudhi::witness_complex::landmark_choice_by_random_point(point_vector, nbL, knn); + Point_Vector landmarks; + Gudhi::subsampling::pick_n_random_points(point_vector, 100, std::back_inserter(landmarks)); + Gudhi::witness_complex::construct_closest_landmark_table(point_vector, landmarks, knn); end = clock(); std::cout << "Landmark choice for " << nbL << " landmarks took " << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; diff --git a/src/Witness_complex/example/witness_complex_sphere.cpp b/src/Witness_complex/example/witness_complex_sphere.cpp index b26c9f36..e6f88274 100644 --- a/src/Witness_complex/example/witness_complex_sphere.cpp +++ b/src/Witness_complex/example/witness_complex_sphere.cpp @@ -27,7 +27,8 @@ #include <gudhi/Simplex_tree.h> #include <gudhi/Witness_complex.h> -#include <gudhi/Landmark_choice_by_random_point.h> +#include <gudhi/Construct_closest_landmark_table.h> +#include <gudhi/pick_n_random_points.h> #include <gudhi/reader_utils.h> #include <iostream> @@ -67,7 +68,7 @@ int main(int argc, char * const argv[]) { // Read the point file for (int nbP = 500; nbP < 10000; nbP += 500) { - Point_Vector point_vector; + Point_Vector point_vector, landmarks; generate_points_sphere(point_vector, nbP, 4); std::cout << "Successfully generated " << point_vector.size() << " points.\n"; std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n"; @@ -75,7 +76,8 @@ int main(int argc, char * const argv[]) { // Choose landmarks start = clock(); std::vector<std::vector< int > > knn; - Gudhi::witness_complex::landmark_choice_by_random_point(point_vector, number_of_landmarks, knn); + Gudhi::subsampling::pick_n_random_points(point_vector, 100, std::back_inserter(landmarks)); + Gudhi::witness_complex::construct_closest_landmark_table(point_vector, landmarks, knn); // Compute witness complex Gudhi::witness_complex::witness_complex(knn, number_of_landmarks, point_vector[0].size(), simplex_tree); diff --git a/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h index ebf6aad1..ef711c34 100644 --- a/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h +++ b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h @@ -20,8 +20,8 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef LANDMARK_CHOICE_BY_RANDOM_POINT_H_ -#define LANDMARK_CHOICE_BY_RANDOM_POINT_H_ +#ifndef CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ +#define CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ #include <boost/range/size.hpp> @@ -37,10 +37,13 @@ namespace witness_complex { /** * \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 a matrix {witness}*{closest landmarks} in knn. + * \brief Construct the closest landmark tables for all witnesses. + * \details Output a table 'knn', each line of which represents a witness and + * consists of landmarks sorted by + * euclidean distance from the corresponding witness. * + * The type WitnessContainer is a random access range and + * the type LandmarkContainer is a range. * The type KNearestNeighbors can be seen as * Witness_range<Closest_landmark_range<Vertex_handle>>, where * Witness_range and Closest_landmark_range are random access ranges and @@ -48,23 +51,14 @@ namespace witness_complex { * Closest_landmark_range needs to have push_back operation. */ - template <typename KNearestNeighbours, - typename Point_random_access_range> - void landmark_choice_by_random_point(Point_random_access_range const &points, - int nbL, - KNearestNeighbours &knn) { + template <typename WitnessContainer, + typename LandmarkContainer, + typename KNearestNeighbours> + void construct_closest_landmark_table(WitnessContainer const &points, + LandmarkContainer const &landmarks, + KNearestNeighbours &knn) { int nbP = boost::size(points); - assert(nbP >= nbL); - std::set<int> landmarks; - int current_number_of_landmarks = 0; // counter for landmarks - - // TODO(SK) Consider using rand_r(...) instead of rand(...) for improved thread safety - int chosen_landmark = rand() % nbP; - for (current_number_of_landmarks = 0; current_number_of_landmarks != nbL; current_number_of_landmarks++) { - while (landmarks.find(chosen_landmark) != landmarks.end()) - chosen_landmark = rand() % nbP; - landmarks.insert(chosen_landmark); - } + assert(nbP >= boost::size(landmarks)); int dim = boost::size(*std::begin(points)); typedef std::pair<double, int> dist_i; @@ -74,11 +68,11 @@ namespace witness_complex { std::priority_queue<dist_i, std::vector<dist_i>, comp> l_heap([](dist_i j1, dist_i j2) { return j1.first > j2.first; }); - std::set<int>::iterator landmarks_it; + typename LandmarkContainer::const_iterator landmarks_it; int landmarks_i = 0; for (landmarks_it = landmarks.begin(), landmarks_i = 0; landmarks_it != landmarks.end(); ++landmarks_it, landmarks_i++) { - dist_i dist = std::make_pair(euclidean_distance(points[points_i], points[*landmarks_it]), landmarks_i); + dist_i dist = std::make_pair(euclidean_distance(points[points_i], *landmarks_it), landmarks_i); l_heap.push(dist); } for (int i = 0; i < dim + 1; i++) { @@ -93,4 +87,4 @@ namespace witness_complex { } // namespace Gudhi -#endif // LANDMARK_CHOICE_BY_RANDOM_POINT_H_ +#endif // CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ diff --git a/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h b/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h deleted file mode 100644 index df93155b..00000000 --- a/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h +++ /dev/null @@ -1,105 +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) 2015 INRIA Sophia Antipolis-Méditerranée (France) - * - * 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 <http://www.gnu.org/licenses/>. - */ - -#ifndef LANDMARK_CHOICE_BY_FURTHEST_POINT_H_ -#define LANDMARK_CHOICE_BY_FURTHEST_POINT_H_ - -#include <boost/range/size.hpp> - -#include <limits> // for numeric_limits<> -#include <iterator> -#include <algorithm> // for sort -#include <vector> - -namespace Gudhi { - -namespace witness_complex { - - typedef std::vector<int> typeVectorVertex; - - /** - * \ingroup witness_complex - * \brief Landmark choice strategy by iteratively adding the furthest 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<Closest_landmark_range<Vertex_handle>>, where - * Witness_range and Closest_landmark_range are random access ranges - * - */ - - template <typename KNearestNeighbours, - typename Point_random_access_range> - void landmark_choice_by_furthest_point(Point_random_access_range const &points, - int nbL, - KNearestNeighbours &knn) { - int nb_points = boost::size(points); - assert(nb_points >= nbL); - // distance matrix witness x landmarks - std::vector<std::vector<double>> wit_land_dist(nb_points, std::vector<double>()); - // landmark list - typeVectorVertex chosen_landmarks; - - knn = KNearestNeighbours(nb_points, std::vector<int>()); - int current_number_of_landmarks = 0; // counter for landmarks - double curr_max_dist = 0; // used for defining the furhest point from L - const double infty = std::numeric_limits<double>::infinity(); // infinity (see next entry) - std::vector< double > dist_to_L(nb_points, infty); // vector of current distances to L from points - - // TODO(SK) Consider using rand_r(...) instead of rand(...) for improved thread safety - // or better yet std::uniform_int_distribution - int rand_int = rand() % nb_points; - int curr_max_w = rand_int; // For testing purposes a pseudo-random number is used here - - for (current_number_of_landmarks = 0; current_number_of_landmarks != nbL; current_number_of_landmarks++) { - // curr_max_w at this point is the next landmark - chosen_landmarks.push_back(curr_max_w); - unsigned i = 0; - for (auto& p : points) { - double curr_dist = euclidean_distance(p, *(std::begin(points) + chosen_landmarks[current_number_of_landmarks])); - wit_land_dist[i].push_back(curr_dist); - knn[i].push_back(current_number_of_landmarks); - if (curr_dist < dist_to_L[i]) - dist_to_L[i] = curr_dist; - ++i; - } - curr_max_dist = 0; - for (i = 0; i < dist_to_L.size(); i++) - if (dist_to_L[i] > curr_max_dist) { - curr_max_dist = dist_to_L[i]; - curr_max_w = i; - } - } - for (int i = 0; i < nb_points; ++i) - std::sort(std::begin(knn[i]), - std::end(knn[i]), - [&wit_land_dist, i](int a, int b) { - return wit_land_dist[i][a] < wit_land_dist[i][b]; }); - } - -} // namespace witness_complex - -} // namespace Gudhi - -#endif // LANDMARK_CHOICE_BY_FURTHEST_POINT_H_ diff --git a/src/Witness_complex/test/witness_complex_points.cpp b/src/Witness_complex/test/witness_complex_points.cpp index bd3df604..d40bbf14 100644 --- a/src/Witness_complex/test/witness_complex_points.cpp +++ b/src/Witness_complex/test/witness_complex_points.cpp @@ -27,8 +27,8 @@ #include <gudhi/Simplex_tree.h> #include <gudhi/Witness_complex.h> -#include <gudhi/Landmark_choice_by_random_point.h> -#include <gudhi/Landmark_choice_by_furthest_point.h> +#include <gudhi/Construct_closest_landmark_table.h> +#include <gudhi/pick_n_random_points.h> #include <iostream> #include <vector> @@ -40,7 +40,7 @@ typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex; BOOST_AUTO_TEST_CASE(witness_complex_points) { std::vector< typeVectorVertex > knn; - std::vector< Point > points; + std::vector< Point > points, landmarks; // Add grid points as witnesses for (double i = 0; i < 10; i += 1.0) for (double j = 0; j < 10; j += 1.0) @@ -50,15 +50,9 @@ BOOST_AUTO_TEST_CASE(witness_complex_points) { bool b_print_output = false; // First test: random choice Simplex_tree complex1; - Gudhi::witness_complex::landmark_choice_by_random_point(points, 100, knn); + Gudhi::subsampling::pick_n_random_points(points, 100, std::back_inserter(landmarks)); + Gudhi::witness_complex::construct_closest_landmark_table(points, landmarks, knn); assert(!knn.empty()); WitnessComplex witnessComplex1(knn, 100, 3, complex1); BOOST_CHECK(witnessComplex1.is_witness_complex(knn, b_print_output)); - - // Second test: furthest choice - knn.clear(); - Simplex_tree complex2; - Gudhi::witness_complex::landmark_choice_by_furthest_point(points, 100, knn); - WitnessComplex witnessComplex2(knn, 100, 3, complex2); - BOOST_CHECK(witnessComplex2.is_witness_complex(knn, b_print_output)); } |