diff options
author | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-11-16 11:49:41 +0000 |
---|---|---|
committer | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-11-16 11:49:41 +0000 |
commit | 668e76bbe8f350ab0fdf6f6105e8c7818a5ad38f (patch) | |
tree | 069ec9b257efeb05f775bf8f267b26adc720cb68 /src/Witness_complex | |
parent | def467c2cb019b7a5cc758b6778957be11465a6e (diff) | |
parent | 1839d09009b10ce3c62770e082a4d7816d991e14 (diff) |
Merged last trunk modifications
Make Witness compile and test
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/rips_complex_module@1755 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: e6eec55ac0a4cc66da3bb081a222cae5b998c1cf
Diffstat (limited to 'src/Witness_complex')
4 files changed, 113 insertions, 18 deletions
diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp index 6a203383..59dd28e0 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> @@ -36,6 +38,7 @@ typedef std::vector< int > typeVectorVertex; typedef std::vector< std::vector <double> > Point_Vector; +typedef Gudhi::Simplex_tree<> Simplex_tree; int main(int argc, char * const argv[]) { if (argc != 3) { @@ -49,7 +52,7 @@ int main(int argc, char * const argv[]) { clock_t start, end; // Construct the Simplex Tree - Gudhi::Simplex_tree<> simplex_tree; + Simplex_tree simplex_tree; // Read the OFF file (input file name given as parameter) and triangulate points Gudhi::Points_off_reader<std::vector <double>> off_reader(off_file_name); @@ -65,7 +68,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<Simplex_tree::Filtration_value>(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..7ab86cc0 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> @@ -39,6 +40,8 @@ #include "generators.h" +typedef Gudhi::Simplex_tree<> Simplex_tree; + /** Write a gnuplot readable file. * Data range is a random access range of pairs (arg, value) */ @@ -61,13 +64,13 @@ int main(int argc, char * const argv[]) { clock_t start, end; // Construct the Simplex Tree - Gudhi::Simplex_tree<> simplex_tree; + Simplex_tree simplex_tree; std::vector< std::pair<int, double> > l_time; // 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 +78,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<Simplex_tree::Filtration_value>(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/Construct_closest_landmark_table.h b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h new file mode 100644 index 00000000..ec93ae71 --- /dev/null +++ b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h @@ -0,0 +1,92 @@ +/* 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 CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ +#define CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ + +#include <boost/range/size.hpp> + +#include <queue> // for priority_queue<> +#include <utility> // for pair<> +#include <iterator> +#include <vector> +#include <set> + +namespace Gudhi { + +namespace witness_complex { + + /** + * \ingroup witness_complex + * \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 + * Vertex_handle is the label type of a vertex in a simplicial complex. + * Closest_landmark_range needs to have push_back operation. + */ + + template <typename FiltrationValue, + 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 >= boost::size(landmarks)); + + int dim = boost::size(*std::begin(points)); + typedef std::pair<double, int> dist_i; + typedef bool (*comp)(dist_i, dist_i); + knn = KNearestNeighbours(nbP); + for (int points_i = 0; points_i < nbP; points_i++) { + std::priority_queue<dist_i, std::vector<dist_i>, comp> l_heap([](dist_i j1, dist_i j2) { + return j1.first > j2.first; + }); + 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<FiltrationValue>(points[points_i], *landmarks_it), + landmarks_i); + l_heap.push(dist); + } + for (int i = 0; i < dim + 1; i++) { + dist_i dist = l_heap.top(); + knn[points_i].push_back(dist.second); + l_heap.pop(); + } + } + } + +} // namespace witness_complex + +} // namespace Gudhi + +#endif // CONSTRUCT_CLOSEST_LANDMARK_TABLE_H_ diff --git a/src/Witness_complex/test/witness_complex_points.cpp b/src/Witness_complex/test/witness_complex_points.cpp index 03c9adc0..b7067f87 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<Simplex_tree::Filtration_value>(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)); } |