diff options
author | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-10-20 10:04:05 +0000 |
---|---|---|
committer | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2016-10-20 10:04:05 +0000 |
commit | 8d656e33138ef8b3a7d86a7375c92646efc29511 (patch) | |
tree | 3711227c4c1b2a6e9f25dda1db8dafb8365063a0 /src/Witness_complex | |
parent | 355dc2a0ae73f243fc0aa8d7c797509d8ba5e6b4 (diff) | |
parent | 30e538a98919004e36b3b382017884486919cb6e (diff) |
Merge last trunk modification
Fix doc issue
Still doc issue
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/ST_cythonize@1739 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: 0a99345f06e93a3525691699a6fe1505979e8e8e
Diffstat (limited to 'src/Witness_complex')
-rw-r--r-- | src/Witness_complex/example/CMakeLists.txt | 35 | ||||
-rw-r--r-- | src/Witness_complex/example/witness_complex_from_file.cpp | 47 | ||||
-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 |
6 files changed, 47 insertions, 206 deletions
diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt index e6a916cd..857ec819 100644 --- a/src/Witness_complex/example/CMakeLists.txt +++ b/src/Witness_complex/example/CMakeLists.txt @@ -3,42 +3,15 @@ project(Witness_complex_examples) # A simple example add_executable( witness_complex_from_file witness_complex_from_file.cpp ) - add_test( witness_complex_from_bunny ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000 100) + add_test( witness_complex_from_bunny ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_from_file + ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.off 100) if(CGAL_FOUND) if (NOT CGAL_VERSION VERSION_LESS 4.6.0) - message(STATUS "CGAL version: ${CGAL_VERSION}.") - - include( ${CGAL_USE_FILE} ) - # In CMakeLists.txt, when include(${CGAL_USE_FILE}), CXX_FLAGS are overwritten. - # cf. http://doc.cgal.org/latest/Manual/installation.html#title40 - # A workaround is to add "-std=c++11" again. - # A fix would be to use https://cmake.org/cmake/help/v3.1/prop_gbl/CMAKE_CXX_KNOWN_FEATURES.html - # or even better https://cmake.org/cmake/help/v3.1/variable/CMAKE_CXX_STANDARD.html - # but it implies to use cmake version 3.1 at least. - if(NOT MSVC) - include(CheckCXXCompilerFlag) - CHECK_CXX_COMPILER_FLAG(-std=c++11 COMPILER_SUPPORTS_CXX11) - if(COMPILER_SUPPORTS_CXX11) - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11") - endif() - endif() - # - End of workaround - - find_package(Eigen3 3.1.0) if (EIGEN3_FOUND) - message(STATUS "Eigen3 version: ${EIGEN3_VERSION}.") - include( ${EIGEN3_USE_FILE} ) - message(STATUS "Eigen3 use file: ${EIGEN3_USE_FILE}.") - include_directories (BEFORE "../../include") - add_executable ( witness_complex_sphere witness_complex_sphere.cpp ) target_link_libraries(witness_complex_sphere ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) add_test( witness_complex_sphere_10 ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_sphere 10) - else() - message(WARNING "Eigen3 not found. Version 3.1.0 is required for witness_complex_sphere example.") - endif() - else() - message(WARNING "CGAL version: ${CGAL_VERSION} is too old to compile witness_complex_sphere example. Version 4.6.0 is required.") - endif () + endif(EIGEN3_FOUND) + endif (NOT CGAL_VERSION VERSION_LESS 4.6.0) endif() diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp index 53207ad2..bb641b3c 100644 --- a/src/Witness_complex/example/witness_complex_from_file.cpp +++ b/src/Witness_complex/example/witness_complex_from_file.cpp @@ -23,9 +23,11 @@ #include <sys/types.h> #include <sys/stat.h> +#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> @@ -37,56 +39,37 @@ typedef std::vector< Vertex_handle > typeVectorVertex; typedef std::vector< std::vector <double> > Point_Vector; -/** - * \brief Customized version of read_points - * which takes into account a possible nbP first line - * - */ -inline void -read_points_cust(std::string file_name, std::vector< std::vector< double > > & points) { - std::ifstream in_file(file_name.c_str(), std::ios::in); - if (!in_file.is_open()) { - std::cerr << "Unable to open file " << file_name << std::endl; - return; - } - std::string line; - double x; - while (getline(in_file, line)) { - std::vector< double > point; - std::istringstream iss(line); - while (iss >> x) { - point.push_back(x); - } - if (point.size() != 1) - points.push_back(point); - } - in_file.close(); -} - int main(int argc, char * const argv[]) { if (argc != 3) { std::cerr << "Usage: " << argv[0] - << " path_to_point_file nbL \n"; + << " path_to_point_file.off nbL \n"; return 0; } - std::string file_name = argv[1]; + std::string off_file_name = argv[1]; int nbL = atoi(argv[2]); clock_t start, end; // Construct the Simplex Tree Gudhi::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); + // Check the read operation was correct + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << off_file_name << std::endl; + } // Read the point file - Point_Vector point_vector; - read_points_cust(file_name, point_vector); + Point_Vector point_vector = off_reader.get_point_cloud(); std::cout << "Successfully read " << point_vector.size() << " points.\n"; std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n"; // 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)); } |