diff options
Diffstat (limited to 'src')
13 files changed, 687 insertions, 22 deletions
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index e55e4395..f4d15b64 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -92,6 +92,8 @@ else() add_subdirectory(example/Bitmap_cubical_complex) add_subdirectory(example/Witness_complex) add_subdirectory(example/Alpha_complex) + add_subdirectory(example/Spatial_searching) + add_subdirectory(example/Subsampling) # data points generator add_subdirectory(data/points/generator) diff --git a/src/Persistent_cohomology/example/CMakeLists.txt b/src/Persistent_cohomology/example/CMakeLists.txt index b823d658..c37b4229 100644 --- a/src/Persistent_cohomology/example/CMakeLists.txt +++ b/src/Persistent_cohomology/example/CMakeLists.txt @@ -41,11 +41,11 @@ if(GMP_FOUND) if(GMPXX_FOUND) message("GMPXX_LIBRARIES = ${GMPXX_LIBRARIES}") - add_executable(rips_multifield_persistence rips_multifield_persistence.cpp ) - target_link_libraries(rips_multifield_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES}) - add_executable ( performance_rips_persistence performance_rips_persistence.cpp ) - target_link_libraries(performance_rips_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES}) - if (TBB_FOUND) + add_executable(rips_multifield_persistence rips_multifield_persistence.cpp ) + target_link_libraries(rips_multifield_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES}) + add_executable ( performance_rips_persistence performance_rips_persistence.cpp ) + target_link_libraries(performance_rips_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY} ${GMPXX_LIBRARIES} ${GMP_LIBRARIES}) + if (TBB_FOUND) target_link_libraries(rips_multifield_persistence ${TBB_LIBRARIES}) target_link_libraries(performance_rips_persistence ${TBB_LIBRARIES}) endif(TBB_FOUND) diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index a7d1e463..b6cef611 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -308,14 +308,14 @@ class Persistent_cohomology { // Find its annotation vector curr_col = ds_repr_[dsets_.find_set(key)]; if (curr_col != NULL) { // and insert it in annotations_in_boundary with multyiplicative factor "sign". - annotations_in_boundary.emplace_back(curr_col, sign); + annotations_in_boundary.emplace_back(curr_col, sign); } } sign = -sign; } // Place identical annotations consecutively so we can easily sum their multiplicities. std::sort(annotations_in_boundary.begin(), annotations_in_boundary.end(), - [](annotation_t const& a, annotation_t const& b) { return a.first < b.first; }); + [](annotation_t const& a, annotation_t const& b) { return a.first < b.first; }); // Sum the annotations with multiplicity, using a map<key,coeff> // to represent a sparse vector. @@ -325,7 +325,7 @@ class Persistent_cohomology { Column* col = ann_it->first; int mult = ann_it->second; while (++ann_it != annotations_in_boundary.end() && ann_it->first == col) { - mult += ann_it->second; + mult += ann_it->second; } // The following test is just a heuristic, it is not required, and it is fine that is misses p == 0. if (mult != coeff_field_.additive_identity()) { // For all columns in the boundary, diff --git a/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h b/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h new file mode 100644 index 00000000..b4dbbba1 --- /dev/null +++ b/src/Spatial_searching/include/gudhi/Spatial_tree_data_structure.h @@ -0,0 +1,169 @@ +/* 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): Clement Jamin + * + * Copyright (C) 2016 INRIA Sophia-Antipolis (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 GUDHI_POINT_CLOUD_H +#define GUDHI_POINT_CLOUD_H + +#include <CGAL/Orthogonal_k_neighbor_search.h> +#include <CGAL/Orthogonal_incremental_neighbor_search.h> +#include <CGAL/Search_traits.h> +#include <CGAL/Search_traits_adapter.h> + +#include <boost/iterator/counting_iterator.hpp> + +#include <cstddef> +#include <vector> + +namespace Gudhi { + +template <typename K, typename Point_container_> +class Spatial_tree_data_structure +{ +public: + typedef typename Point_container_::value_type Point; + typedef K Kernel; + typedef typename Kernel::FT FT; + + typedef CGAL::Search_traits< + FT, Point, + typename Kernel::Cartesian_const_iterator_d, + typename Kernel::Construct_cartesian_const_iterator_d> Traits_base; + // using a pointer as a special property map type + typedef CGAL::Search_traits_adapter< + std::ptrdiff_t, Point*, Traits_base> STraits; + + typedef CGAL::Orthogonal_k_neighbor_search<STraits> K_neighbor_search; + typedef typename K_neighbor_search::Tree Tree; + typedef typename K_neighbor_search::Distance Distance; + typedef typename K_neighbor_search::iterator KNS_iterator; + typedef K_neighbor_search KNS_range; + + typedef CGAL::Orthogonal_incremental_neighbor_search< + STraits, Distance, CGAL::Sliding_midpoint<STraits>, Tree> + Incremental_neighbor_search; + typedef typename Incremental_neighbor_search::iterator INS_iterator; + typedef Incremental_neighbor_search INS_range; + + /// Constructor + Spatial_tree_data_structure(Point_container_ const& points) + : m_points(points), + m_tree(boost::counting_iterator<std::ptrdiff_t>(0), + boost::counting_iterator<std::ptrdiff_t>(points.size()), + typename Tree::Splitter(), + STraits((Point*)&(points[0])) ) + { + // Build the tree now (we don't want to wait for the first query) + m_tree.build(); + } + + /// Constructor + template <typename Point_indices_range> + Spatial_tree_data_structure( + Point_container_ const& points, + Point_indices_range const& only_these_points) + : m_points(points), + m_tree( + only_these_points.begin(), only_these_points.end(), + typename Tree::Splitter(), + STraits((Point*)&(points[0]))) + { + // Build the tree now (we don't want to wait for the first query) + m_tree.build(); + } + + /// Constructor + Spatial_tree_data_structure( + Point_container_ const& points, + std::size_t begin_idx, std::size_t past_the_end_idx) + : m_points(points), + m_tree( + boost::counting_iterator<std::ptrdiff_t>(begin_idx), + boost::counting_iterator<std::ptrdiff_t>(past_the_end_idx), + typename Tree::Splitter(), + STraits((Point*)&(points[0])) ) + { + // Build the tree now (we don't want to wait for the first query) + m_tree.build(); + } + + /*Point_container_ &points() + { + return m_points; + } + + const Point_container_ &points() const + { + return m_points; + }*/ + + // Be careful, this function invalidates the tree, + // which will be recomputed at the next query + void insert(std::ptrdiff_t point_idx) + { + m_tree.insert(point_idx); + } + + KNS_range query_ANN(const + Point &sp, + unsigned int k, + bool sorted = true) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + K_neighbor_search search( + m_tree, + sp, + k, + FT(0), + true, + CGAL::Distance_adapter<std::ptrdiff_t,Point*,CGAL::Euclidean_distance<Traits_base> >( + (Point*)&(m_points[0])), + sorted); + + return search; + } + + INS_range query_incremental_ANN(const Point &sp) const + { + // Initialize the search structure, and search all N points + // Note that we need to pass the Distance explicitly since it needs to + // know the property map + Incremental_neighbor_search search( + m_tree, + sp, + FT(0), + true, + CGAL::Distance_adapter<std::ptrdiff_t, Point*, CGAL::Euclidean_distance<Traits_base> >( + (Point*)&(m_points[0])) ); + + return search; + } + +protected: + Point_container_ const& m_points; + Tree m_tree; +}; + +} //namespace Gudhi + +#endif // GUDHI_POINT_CLOUD_H diff --git a/src/Subsampling/include/gudhi/Landmark_choice_by_farthest_point.h b/src/Subsampling/include/gudhi/Landmark_choice_by_farthest_point.h new file mode 100644 index 00000000..198c9f9f --- /dev/null +++ b/src/Subsampling/include/gudhi/Landmark_choice_by_farthest_point.h @@ -0,0 +1,158 @@ +/* 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_FARTHEST_POINT_H_ +#define LANDMARK_CHOICE_BY_FARTHEST_POINT_H_ + +#include <gudhi/Spatial_tree_data_structure.h> + +#include <iterator> +#include <algorithm> // for sort +#include <vector> +#include <random> +#include <boost/heap/fibonacci_heap.hpp> + +namespace Gudhi { + + + template < typename Point_d, + typename Heap, + typename Tree, + typename Presence_table > + void update_heap( Point_d &l, + unsigned nbL, + Heap &heap, + Tree &tree, + Presence_table &table) + { + auto search = tree.query_incremental_ANN(l); + for (auto w: search) { + if (table[w.first].first) + if (w.second < table[w.first].second->second) { + heap.update(table[w.first].second, w); + } + } + } + + /** + * \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<Closest_landmark_range<Vertex_handle>>, where + * Witness_range and Closest_landmark_range are random access ranges + * + */ + + template < typename Kernel, + typename Point_container, + typename OutputIterator> + void landmark_choice_by_farthest_point( Kernel& k, + Point_container const &points, + int nbL, + OutputIterator output_it) + { + + // typedef typename Kernel::FT FT; + // typedef std::pair<unsigned, FT> Heap_node; + + // struct R_max_compare + // { + // bool operator()(const Heap_node &rmh1, const Heap_node &rmh2) const + // { + // return rmh1.second < rmh2.second; + // } + // }; + + // typedef boost::heap::fibonacci_heap<Heap_node, boost::heap::compare<R_max_compare>> Heap; + // typedef Spatial_tree_data_structure<Kernel, Point_container> Tree; + // typedef std::vector< std::pair<bool, Heap_node*> > Presence_table; + + typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); + + // Tree tree(points); + // Heap heap; + // Presence_table table(points.size()); + // for (auto p: table) + // std::cout << p.first << "\n"; + // int number_landmarks = 0; // number of treated 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(points.size(), infty); // vector of current distances to L from points + + // // Choose randomly the first landmark + // std::random_device rd; + // std::mt19937 gen(rd()); + // std::uniform_int_distribution<> dis(1, 6); + // int curr_landmark = dis(gen); + + // do { + // *output_landmarks++ = points[curr_landmark]; + // std::cout << curr_landmark << "\n"; + // number_landmarks++; + // } + // while (number_landmarks < nbL); + // } + + int nb_points = boost::size(points); + assert(nb_points >= nbL); + + 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 + + // Choose randomly the first landmark + std::random_device rd; + std::mt19937 gen(rd()); + 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++) { + // curr_max_w at this point is the next landmark + *output_it++ = points[curr_max_w]; + std::cout << curr_max_w << "\n"; + unsigned i = 0; + for (auto& p : points) { + double curr_dist = sqdist(p, *(std::begin(points) + curr_max_w)); + if (curr_dist < dist_to_L[i]) + dist_to_L[i] = curr_dist; + ++i; + } + // choose the next curr_max_w + 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; + } + } + } + +} // namespace Gudhi + +#endif // LANDMARK_CHOICE_BY_FARTHEST_POINT_H_ diff --git a/src/Subsampling/include/gudhi/Landmark_choice_by_random_point.h b/src/Subsampling/include/gudhi/Landmark_choice_by_random_point.h new file mode 100644 index 00000000..daa05d1a --- /dev/null +++ b/src/Subsampling/include/gudhi/Landmark_choice_by_random_point.h @@ -0,0 +1,80 @@ +/* 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 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_RANDOM_POINT_H_ +#define LANDMARK_CHOICE_BY_RANDOM_POINT_H_ + +#include <boost/range/size.hpp> + +#include <random> // random_device, mt19937 +#include <algorithm> // shuffle +#include <numeric> // iota +#include <iterator> +#include <gudhi/Clock.h> + + +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 <typename Point_container, + typename OutputIterator> + void landmark_choice_by_random_point(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<int> 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 // LANDMARK_CHOICE_BY_RANDOM_POINT_H_ diff --git a/src/Subsampling/include/gudhi/sparsify_point_set.h b/src/Subsampling/include/gudhi/sparsify_point_set.h new file mode 100644 index 00000000..3784e583 --- /dev/null +++ b/src/Subsampling/include/gudhi/sparsify_point_set.h @@ -0,0 +1,98 @@ +/* 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): Clement Jamin +* +* Copyright (C) 2016 INRIA Sophia-Antipolis (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 GUDHI_SPARSIFY_POINT_SET_H +#define GUDHI_SPARSIFY_POINT_SET_H + +#include <gudhi/Spatial_tree_data_structure.h> +#ifdef GUDHI_TC_PROFILING +#include <gudhi/Clock.h> +#endif + +#include <cstddef> +#include <vector> + +namespace Gudhi { +namespace subsampling { + +template <typename Kernel, typename Point_container, typename OutputIterator> +bool +sparsify_point_set( + const Kernel &k, Point_container const& input_pts, + typename Kernel::FT min_squared_dist, + OutputIterator output_it) +{ + typedef typename Gudhi::Spatial_tree_data_structure< + Kernel, Point_container> Points_ds; + + typename Kernel::Squared_distance_d sqdist = k.squared_distance_d_object(); + +#ifdef GUDHI_TC_PROFILING + Gudhi::Clock t; +#endif + + Points_ds points_ds(input_pts); + + std::vector<bool> dropped_points(input_pts.size(), false); + + // Parse the input points, and add them if they are not too close to + // the other points + std::size_t pt_idx = 0; + for (typename Point_container::const_iterator it_pt = input_pts.begin() ; + it_pt != input_pts.end(); + ++it_pt, ++pt_idx) + { + if (dropped_points[pt_idx]) + continue; + + *output_it++ = *it_pt; + + auto ins_range = points_ds.query_incremental_ANN(*it_pt); + + // If another point Q is closer that min_squared_dist, mark Q to be dropped + for (auto const& neighbor : ins_range) + { + std::size_t neighbor_point_idx = neighbor.first; + // If the neighbor is too close, we drop the neighbor + if (neighbor.second < min_squared_dist) + { + // N.B.: If neighbor_point_idx < pt_idx, + // dropped_points[neighbor_point_idx] is already true but adding a + // test doesn't make things faster, so why bother? + dropped_points[neighbor_point_idx] = true; + } + else + break; + } + } + +#ifdef GUDHI_TC_PROFILING + t.end(); + std::cerr << "Point set sparsified in " << t.num_seconds() + << " seconds." << std::endl; +#endif +} + +} // namespace subsampling +} // namespace Gudhi + +#endif // GUDHI_POINT_CLOUD_H diff --git a/src/Subsampling/test/CMakeLists.txt b/src/Subsampling/test/CMakeLists.txt new file mode 100644 index 00000000..3a45c685 --- /dev/null +++ b/src/Subsampling/test/CMakeLists.txt @@ -0,0 +1,22 @@ +cmake_minimum_required(VERSION 2.6) +project(GUDHILandmarkingTest) + +# Landmarking test +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.8.0) + message(STATUS "CGAL version: ${CGAL_VERSION}.") + + find_package(Eigen3 3.1.0) + if (EIGEN3_FOUND) + message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") + include( ${EIGEN3_USE_FILE} ) + include_directories (BEFORE "../../include") + + add_executable( landmarking_UT landmarking.cpp ) + else() + message(WARNING "Eigen3 not found. Version 3.1.0 is required for Landmarking feature.") + endif() + else() + message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile Landmarking feature. Version 4.8.0 is required.") + endif () +endif() diff --git a/src/Subsampling/test/landmarking.cpp b/src/Subsampling/test/landmarking.cpp new file mode 100644 index 00000000..3131c798 --- /dev/null +++ b/src/Subsampling/test/landmarking.cpp @@ -0,0 +1,47 @@ +// #ifdef _DEBUG +// # define TBB_USE_THREADING_TOOL +// #endif + +#include <gudhi/Landmark_choice_by_random_point.h> +#include <gudhi/Landmark_choice_by_farthest_point.h> +#include <vector> +#include <iterator> + +#include <CGAL/Epick_d.h> + + +int main() { + typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K; + typedef typename K::FT FT; + typedef typename K::Point_d Point_d; + + std::vector<Point_d> vect; + vect.push_back(Point_d(std::vector<FT>({0,0,0,0}))); + vect.push_back(Point_d(std::vector<FT>({0,0,0,1}))); + vect.push_back(Point_d(std::vector<FT>({0,0,1,0}))); + vect.push_back(Point_d(std::vector<FT>({0,0,1,1}))); + vect.push_back(Point_d(std::vector<FT>({0,1,0,0}))); + vect.push_back(Point_d(std::vector<FT>({0,1,0,1}))); + vect.push_back(Point_d(std::vector<FT>({0,1,1,0}))); + vect.push_back(Point_d(std::vector<FT>({0,1,1,1}))); + vect.push_back(Point_d(std::vector<FT>({1,0,0,0}))); + vect.push_back(Point_d(std::vector<FT>({1,0,0,1}))); + vect.push_back(Point_d(std::vector<FT>({1,0,1,0}))); + vect.push_back(Point_d(std::vector<FT>({1,0,1,1}))); + vect.push_back(Point_d(std::vector<FT>({1,1,0,0}))); + vect.push_back(Point_d(std::vector<FT>({1,1,0,1}))); + vect.push_back(Point_d(std::vector<FT>({1,1,1,0}))); + vect.push_back(Point_d(std::vector<FT>({1,1,1,1}))); + + + std::vector<Point_d> landmarks; + Gudhi::landmark_choice_by_random_point(vect, 5, std::back_inserter(landmarks)); + std::cout << "landmark vector contains: "; + for (auto l: landmarks) + std::cout << l << "\n"; + + landmarks.clear(); + K k; + Gudhi::landmark_choice_by_farthest_point(k, vect, 16, std::back_inserter(landmarks)); + +} diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp index 53207ad2..fbc3cf1d 100644 --- a/src/Witness_complex/example/witness_complex_from_file.cpp +++ b/src/Witness_complex/example/witness_complex_from_file.cpp @@ -25,6 +25,7 @@ #include <gudhi/Simplex_tree.h> #include <gudhi/Witness_complex.h> +#include <gudhi/Construct_closest_landmark_table.h> #include <gudhi/Landmark_choice_by_random_point.h> #include <gudhi/reader_utils.h> @@ -78,7 +79,7 @@ int main(int argc, char * const argv[]) { Gudhi::Simplex_tree<> simplex_tree; // Read the point file - Point_Vector point_vector; + Point_Vector point_vector, landmarks; read_points_cust(file_name, point_vector); std::cout << "Successfully read " << point_vector.size() << " points.\n"; std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n"; @@ -86,7 +87,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, nbL, knn); + Gudhi::landmark_choice_by_random_point(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..9cf2f119 100644 --- a/src/Witness_complex/example/witness_complex_sphere.cpp +++ b/src/Witness_complex/example/witness_complex_sphere.cpp @@ -27,6 +27,7 @@ #include <gudhi/Simplex_tree.h> #include <gudhi/Witness_complex.h> +#include <gudhi/Construct_closest_landmark_table.h> #include <gudhi/Landmark_choice_by_random_point.h> #include <gudhi/reader_utils.h> @@ -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::landmark_choice_by_random_point(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/Construct_closest_landmark_table.h b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h new file mode 100644 index 00000000..ef711c34 --- /dev/null +++ b/src/Witness_complex/include/gudhi/Construct_closest_landmark_table.h @@ -0,0 +1,90 @@ +/* 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 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(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 bd3df604..c0006142 100644 --- a/src/Witness_complex/test/witness_complex_points.cpp +++ b/src/Witness_complex/test/witness_complex_points.cpp @@ -27,8 +27,9 @@ #include <gudhi/Simplex_tree.h> #include <gudhi/Witness_complex.h> +#include <gudhi/Construct_closest_landmark_table.h> #include <gudhi/Landmark_choice_by_random_point.h> -#include <gudhi/Landmark_choice_by_furthest_point.h> +#include <gudhi/Landmark_choice_by_farthest_point.h> #include <iostream> #include <vector> @@ -40,7 +41,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 +51,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::landmark_choice_by_random_point(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)); } |