diff options
-rw-r--r-- | CMakeLists.txt | 43 | ||||
-rw-r--r-- | src/CMakeLists.txt | 3 | ||||
-rw-r--r-- | src/Witness_complex/concept/Simplicial_complex.h | 155 | ||||
-rw-r--r-- | src/Witness_complex/example/CMakeLists.txt | 1 | ||||
-rw-r--r-- | src/Witness_complex/example/generators.h | 153 | ||||
-rw-r--r-- | src/Witness_complex/example/witness_complex_from_file.cpp | 77 | ||||
-rw-r--r-- | src/Witness_complex/example/witness_complex_sphere.cpp | 77 | ||||
-rw-r--r-- | src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h | 123 | ||||
-rw-r--r-- | src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h | 103 | ||||
-rw-r--r-- | src/Witness_complex/include/gudhi/Witness_complex.h | 414 | ||||
-rw-r--r-- | src/Witness_complex/include/gudhi/Witness_complex_doc.h | 2 | ||||
-rw-r--r-- | src/Witness_complex/test/CMakeLists.txt | 40 | ||||
-rw-r--r-- | src/Witness_complex/test/simple_witness_complex.cpp | 50 | ||||
-rw-r--r-- | src/Witness_complex/test/witness_complex_points.cpp | 34 |
14 files changed, 634 insertions, 641 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 29ab2a55..6a49185f 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -18,7 +18,7 @@ if(MSVC) # Turn off some VC++ warnings SET (CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4267 /wd4668 /wd4311 /wd4800 /wd4820 /wd4503 /wd4244 /wd4345 /wd4996 /wd4396 /wd4018") else() - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2 -std=c++11 -Wall -Wsign-compare") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2 -std=c++11 -Wall -Wpedantic -Wsign-compare") set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb -O0") set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE}") endif() @@ -27,10 +27,10 @@ set(Boost_USE_STATIC_LIBS ON) set(Boost_USE_MULTITHREADED ON) set(Boost_USE_STATIC_RUNTIME OFF) -#find_package(GMP) -#if(GMP_FOUND) - #find_package(GMPXX) -#endif() +find_package(GMP) +if(GMP_FOUND) + find_package(GMPXX) +endif() find_package(CGAL) @@ -39,28 +39,16 @@ set(TBB_FIND_QUIETLY ON) find_package(TBB) # Required programs for unitary tests purpose -FIND_PROGRAM( LCOV_PATH lcov ) -if (LCOV_PATH) - message("lcov found in ${LCOV_PATH}") +FIND_PROGRAM( GCOVR_PATH gcovr ) +if (GCOVR_PATH) + message("gcovr found in ${GCOVR_PATH}") endif() - -FIND_PROGRAM( PYTHON_PATH python ) -if (PYTHON_PATH) - message("python found in ${PYTHON_PATH}") +# Required programs for unitary tests purpose +FIND_PROGRAM( GPROF_PATH gprof ) +if (GPROF_PATH) + message("gprof found in ${GPROF_PATH}") endif() -# Function to add_test cpplint on each header file of the Gudhi module -function(cpplint_add_tests the_directory) - if (PYTHON_PATH) - # Cpplint tests on coding style - file(GLOB files "${the_directory}/*.h" "${the_directory}/*/*.h") - foreach(filename ${files}) - message(${filename}) - add_test("${filename}.cpplint" ${CMAKE_SOURCE_DIR}/scripts/check_google_style.sh ${filename} ${CMAKE_SOURCE_DIR}/scripts/cpplint.py) - endforeach() - endif() -endfunction(cpplint_add_tests) - if(NOT Boost_FOUND) message(FATAL_ERROR "NOTICE: This demo requires Boost and will not be compiled.") @@ -92,13 +80,8 @@ else() add_subdirectory(src/Skeleton_blocker/test) add_subdirectory(src/Skeleton_blocker/example) add_subdirectory(src/Contraction/example) - # add_subdirectory(src/Hasse_complex/example) add_subdirectory(src/Witness_complex/test) add_subdirectory(src/Witness_complex/example) - # add_subdirectory(src/Alpha_shapes/example) - # add_subdirectory(src/Alpha_shapes/test) - add_subdirectory(src/Bottleneck/example) - add_subdirectory(src/Bottleneck/test) # data points generator add_subdirectory(data/points/generator) @@ -108,5 +91,3 @@ else() add_subdirectory(src/GudhUI) endif() - - diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 4598bc19..81e6f864 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -52,10 +52,7 @@ else() add_subdirectory(example/Persistent_cohomology) add_subdirectory(example/Skeleton_blocker) add_subdirectory(example/Contraction) - # add_subdirectory(example/Hasse_complex) add_subdirectory(example/Witness_complex) - # add_subdirectory(example/Alpha_shapes) - # add_subdirectory(example/Bottleneck) # data points generator add_subdirectory(data/points/generator) diff --git a/src/Witness_complex/concept/Simplicial_complex.h b/src/Witness_complex/concept/Simplicial_complex.h index 6b0df212..d7f3496d 100644 --- a/src/Witness_complex/concept/Simplicial_complex.h +++ b/src/Witness_complex/concept/Simplicial_complex.h @@ -1,83 +1,94 @@ - /* 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) 2014 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/>. - */ +/* 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) 2014 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 CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_H_ +#define CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_H_ + +namespace Gudhi { + +namespace witness_complex { /** \brief The concept Simplicial_Complex describes the requirements - * for a type to implement a simplicial complex, - * used for example to build a 'Witness_complex'. - */ -struct Simplicial_complex -{ -/** Handle to specify a simplex. */ - typedef unspecified Simplex_handle; -/** Handle to specify a vertex. Must be a non-negative integer. */ - typedef unspecified Vertex_handle; - -/** Returns a Simplex_hanlde that is different from all simplex handles - * of the simplices. */ - Simplex_handle null_simplex(); -/** \brief Returns the number of simplices in the complex. - * - * Does not count the empty simplex. */ - size_t num_simplices(); - -/** \brief Iterator over the simplices of the complex, - * in an arbitrary order. - * - * 'value_type' must be 'Simplex_handle'.*/ -typedef unspecified Complex_simplex_iterator; -typedef unspecified Complex_simplex_range; - -/** -* \brief Returns a range over all the simplices of a -* complex. -*/ -Complex_simplex_range complex_simplex_range(); - -/** \brief Iterator over vertices of a simplex. - * - * 'value type' must be 'Vertex_handle'.*/ + * for a type to implement a simplicial complex, + * used for example to build a 'Witness_complex'. + */ +struct Simplicial_complex { + /** Handle to specify a simplex. */ + typedef unspecified Simplex_handle; + /** Handle to specify a vertex. Must be a non-negative integer. */ + typedef unspecified Vertex_handle; + + /** Returns a Simplex_hanlde that is different from all simplex handles + * of the simplices. */ + Simplex_handle null_simplex(); + /** \brief Returns the number of simplices in the complex. + * + * Does not count the empty simplex. */ + size_t num_simplices(); + + /** \brief Iterator over the simplices of the complex, + * in an arbitrary order. + * + * 'value_type' must be 'Simplex_handle'.*/ + typedef unspecified Complex_simplex_iterator; + typedef unspecified Complex_simplex_range; + + /** + * \brief Returns a range over all the simplices of a + * complex. + */ + Complex_simplex_range complex_simplex_range(); + + /** \brief Iterator over vertices of a simplex. + * + * 'value type' must be 'Vertex_handle'.*/ typedef unspecified Simplex_vertex_range; -/** \brief Returns a range over vertices of a given - * simplex. */ + /** \brief Returns a range over vertices of a given + * simplex. */ Simplex_vertex_range simplex_vertex_range(Simplex_handle const & simplex); - -/** \brief Return type of an insertion of a simplex - */ + + /** \brief Return type of an insertion of a simplex + */ typedef unspecified Insertion_result_type; -/** \brief Input range of vertices. - * 'value_type' must be 'Vertex_handle'. */ + /** \brief Input range of vertices. + * 'value_type' must be 'Vertex_handle'. */ typedef unspecified Input_vertex_range; - -/** \brief Inserts a simplex with vertices from a given range - * 'vertex_range' in the simplicial complex. - * */ - Insertion_result_type insert_simplex(Input_vertex_range const & vertex_range); -/** \brief Finds a simplex with vertices given by a range - * - * If a simplex exists, its Simplex_handle is returned. - * Otherwise null_simplex() is returned. */ - Simplex_handle find(Input_vertex_range const & vertex_range); + /** \brief Inserts a simplex with vertices from a given range + * 'vertex_range' in the simplicial complex. + * */ + Insertion_result_type insert_simplex(Input_vertex_range const & vertex_range); + /** \brief Finds a simplex with vertices given by a range + * + * If a simplex exists, its Simplex_handle is returned. + * Otherwise null_simplex() is returned. */ + Simplex_handle find(Input_vertex_range const & vertex_range); }; + +} // namespace witness_complex + +} // namespace Gudhi + +#endif // CONCEPT_WITNESS_COMPLEX_SIMPLICIAL_COMPLEX_H_ diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt index fa6dd062..b304479e 100644 --- a/src/Witness_complex/example/CMakeLists.txt +++ b/src/Witness_complex/example/CMakeLists.txt @@ -34,6 +34,7 @@ if(CGAL_FOUND) 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() diff --git a/src/Witness_complex/example/generators.h b/src/Witness_complex/example/generators.h index 0d42cda2..ac445261 100644 --- a/src/Witness_complex/example/generators.h +++ b/src/Witness_complex/example/generators.h @@ -1,11 +1,35 @@ -#ifndef GENERATORS_H -#define GENERATORS_H +/* 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/>. + */ -#include <fstream> +#ifndef EXAMPLE_WITNESS_COMPLEX_GENERATORS_H_ +#define EXAMPLE_WITNESS_COMPLEX_GENERATORS_H_ #include <CGAL/Epick_d.h> #include <CGAL/point_generators_d.h> +#include <fstream> +#include <string> +#include <vector> + typedef CGAL::Epick_d<CGAL::Dynamic_dimension_tag> K; typedef K::FT FT; typedef K::Point_d Point_d; @@ -18,36 +42,33 @@ typedef CGAL::Random_points_in_ball_d<Point_d> Random_point_iterator; * */ inline void -off_reader_cust ( std::string file_name , std::vector<Point_d> & 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; - } +off_reader_cust(std::string file_name, std::vector<Point_d> & 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; // Line OFF. No need in it - if (!getline(in_file, line)) - { - std::cerr << "No line OFF\n"; - return; - } + if (!getline(in_file, line)) { + std::cerr << "No line OFF\n"; + return; + } // Line with 3 numbers. No need - if (!getline(in_file, line)) - { - std::cerr << "No line with 3 numbers\n"; - return; - } + if (!getline(in_file, line)) { + std::cerr << "No line with 3 numbers\n"; + return; + } // Reading points - while( getline ( in_file , line ) ) - { - std::vector< double > point; - std::istringstream iss( line ); - while(iss >> x) { point.push_back(x); } - points.push_back(Point_d(point)); + while (getline(in_file, line)) { + std::vector< double > point; + std::istringstream iss(line); + while (iss >> x) { + point.push_back(x); } + points.push_back(Point_d(point)); + } in_file.close(); } @@ -57,25 +78,24 @@ off_reader_cust ( std::string file_name , std::vector<Point_d> & points) * */ inline void -read_points_cust ( std::string file_name , Point_Vector & 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; - } +read_points_cust(std::string file_name, Point_Vector & 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); } - Point_d p(point.begin(), point.end()); - if (point.size() != 1) - points.push_back(p); + while (getline(in_file, line)) { + std::vector< double > point; + std::istringstream iss(line); + while (iss >> x) { + point.push_back(x); } + Point_d p(point.begin(), point.end()); + if (point.size() != 1) + points.push_back(p); + } in_file.close(); } @@ -86,49 +106,42 @@ read_points_cust ( std::string file_name , Point_Vector & points) * a flat torus, hence the opposite borders are associated. * The points on border in this case are not placed twice. */ -void generate_points_grid(Point_Vector& W, int width, int D, bool torus) -{ +void generate_points_grid(Point_Vector& W, int width, int D, bool torus) { int nb_points = 1; for (int i = 0; i < D; ++i) nb_points *= width; - for (int i = 0; i < nb_points; ++i) - { - std::vector<double> point; - int cell_i = i; - for (int l = 0; l < D; ++l) - { - if (torus) - point.push_back(-1+(2.0/(width-1))*(cell_i%width)); - else - point.push_back(-1+(2.0/width)*(cell_i%width)); - //attention: the bottom and the right are covered too! - cell_i /= width; - } - W.push_back(point); + for (int i = 0; i < nb_points; ++i) { + std::vector<double> point; + int cell_i = i; + for (int l = 0; l < D; ++l) { + if (torus) + point.push_back(-1 + (2.0 / (width - 1))*(cell_i % width)); + else + point.push_back(-1 + (2.0 / width)*(cell_i % width)); + // attention: the bottom and the right are covered too! + cell_i /= width; } + W.push_back(point); + } } /** \brief Generate nbP points uniformly in a cube of side 2 * having {+-1}^dim as its vertices and insert them in W. */ -void generate_points_random_box(Point_Vector& W, int nbP, int dim) -{ +void generate_points_random_box(Point_Vector& W, int nbP, int dim) { Random_cube_iterator rp(dim, 1.0); - for (int i = 0; i < nbP; i++) - { - W.push_back(*rp++); - } + for (int i = 0; i < nbP; i++) { + W.push_back(*rp++); + } } /** \brief Generate nbP points uniformly on a (dim-1)-sphere * and insert them in W. */ -void generate_points_sphere(Point_Vector& W, int nbP, int dim) -{ - CGAL::Random_points_on_sphere_d<Point_d> rp(dim,1); +void generate_points_sphere(Point_Vector& W, int nbP, int dim) { + CGAL::Random_points_on_sphere_d<Point_d> rp(dim, 1); for (int i = 0; i < nbP; i++) W.push_back(*rp++); } - -#endif +#endif // EXAMPLE_WITNESS_COMPLEX_GENERATORS_H_ diff --git a/src/Witness_complex/example/witness_complex_from_file.cpp b/src/Witness_complex/example/witness_complex_from_file.cpp index 72caf30b..d94502b1 100644 --- a/src/Witness_complex/example/witness_complex_from_file.cpp +++ b/src/Witness_complex/example/witness_complex_from_file.cpp @@ -20,17 +20,19 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#include <iostream> -#include <fstream> -#include <ctime> - #include <sys/types.h> #include <sys/stat.h> -#include "gudhi/Simplex_tree.h" -#include "gudhi/Witness_complex.h" -#include "gudhi/Landmark_choice_by_random_point.h" -#include "gudhi/reader_utils.h" +#include <gudhi/Simplex_tree.h> +#include <gudhi/Witness_complex.h> +#include <gudhi/Landmark_choice_by_random_point.h> +#include <gudhi/reader_utils.h> + +#include <iostream> +#include <fstream> +#include <ctime> +#include <string> +#include <vector> using namespace Gudhi; using namespace Gudhi::witness_complex; @@ -46,24 +48,23 @@ typedef Witness_complex< Simplex_tree<> > WitnessComplex; * */ 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; - } +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); + 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(); } @@ -71,25 +72,22 @@ read_points_cust ( std::string file_name , std::vector< std::vector< double > > * Data range is a random access range of pairs (arg, value) */ template < typename Data_range > -void write_data( Data_range & data, std::string filename ) -{ +void write_data(Data_range & data, std::string filename) { std::ofstream ofs(filename, std::ofstream::out); - for (auto entry: data) + for (auto entry : data) ofs << entry.first << ", " << entry.second << "\n"; ofs.close(); } -int main (int argc, char * const argv[]) -{ - if (argc != 3) - { - std::cerr << "Usage: " << argv[0] - << " path_to_point_file nbL \n"; - return 0; - } +int main(int argc, char * const argv[]) { + if (argc != 3) { + std::cerr << "Usage: " << argv[0] + << " path_to_point_file nbL \n"; + return 0; + } - std::string file_name = argv[1]; - int nbL = atoi(argv[2]); + std::string file_name = argv[1]; + int nbL = atoi(argv[2]); clock_t start, end; // Construct the Simplex Tree @@ -107,13 +105,12 @@ int main (int argc, char * const argv[]) Landmark_choice_by_random_point(point_vector, nbL, knn); end = clock(); std::cout << "Landmark choice for " << nbL << " landmarks took " - << (double)(end-start)/CLOCKS_PER_SEC << " s. \n"; - + << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + // Compute witness complex start = clock(); WitnessComplex(knn, simplex_tree, nbL, point_vector[0].size()); end = clock(); std::cout << "Witness complex took " - << (double)(end-start)/CLOCKS_PER_SEC << " s. \n"; - + << 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 9dc458d4..36f63437 100644 --- a/src/Witness_complex/example/witness_complex_sphere.cpp +++ b/src/Witness_complex/example/witness_complex_sphere.cpp @@ -22,11 +22,6 @@ #define BOOST_PARAMETER_MAX_ARITY 12 -#include <iostream> -#include <fstream> -#include <ctime> -#include <utility> - #include <sys/types.h> #include <sys/stat.h> @@ -35,6 +30,13 @@ #include <gudhi/Landmark_choice_by_random_point.h> #include <gudhi/reader_utils.h> +#include <iostream> +#include <fstream> +#include <ctime> +#include <utility> +#include <string> +#include <vector> + #include "generators.h" using namespace Gudhi; @@ -44,56 +46,51 @@ typedef std::vector< Vertex_handle > typeVectorVertex; typedef Witness_complex< Simplex_tree<> > WitnessComplex; - /** Write a gnuplot readable file. * Data range is a random access range of pairs (arg, value) */ template < typename Data_range > -void write_data( Data_range & data, std::string filename ) -{ +void write_data(Data_range & data, std::string filename) { std::ofstream ofs(filename, std::ofstream::out); - for (auto entry: data) + for (auto entry : data) ofs << entry.first << ", " << entry.second << "\n"; ofs.close(); } -int main (int argc, char * const argv[]) -{ - if (argc != 2) - { - std::cerr << "Usage: " << argv[0] - << " nbL \n"; - return 0; - } +int main(int argc, char * const argv[]) { + if (argc != 2) { + std::cerr << "Usage: " << argv[0] + << " nbL \n"; + return 0; + } - int nbL = atoi(argv[1]); + int nbL = atoi(argv[1]); clock_t start, end; // Construct the Simplex Tree Simplex_tree<> simplex_tree; - std::vector< std::pair<int, double> > l_time; - + std::vector< std::pair<int, double> > l_time; + // Read the point file - for (int nbP = 500; nbP < 10000; nbP += 500) - { - Point_Vector point_vector; - 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"; - - // Choose landmarks - start = clock(); - std::vector<std::vector< int > > knn; - Landmark_choice_by_random_point(point_vector, nbL, knn); - - // Compute witness complex - WitnessComplex(knn, simplex_tree, nbL, point_vector[0].size()); - end = clock(); - double time = (double)(end-start)/CLOCKS_PER_SEC; - std::cout << "Witness complex for " << nbL << " landmarks took " - << time << " s. \n"; - l_time.push_back(std::make_pair(nbP,time)); - } + for (int nbP = 500; nbP < 10000; nbP += 500) { + Point_Vector point_vector; + 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"; + + // Choose landmarks + start = clock(); + std::vector<std::vector< int > > knn; + Landmark_choice_by_random_point(point_vector, nbL, knn); + + // Compute witness complex + WitnessComplex(knn, simplex_tree, nbL, point_vector[0].size()); + end = clock(); + double time = static_cast<double>(end - start) / CLOCKS_PER_SEC; + std::cout << "Witness complex for " << nbL << " landmarks took " + << time << " s. \n"; + l_time.push_back(std::make_pair(nbP, time)); + } write_data(l_time, "w_time.dat"); } 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 index 8dfec99c..bb7e87f5 100644 --- a/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h +++ b/src/Witness_complex/include/gudhi/Landmark_choice_by_furthest_point.h @@ -23,6 +23,10 @@ #ifndef LANDMARK_CHOICE_BY_FURTHEST_POINT_H_ #define LANDMARK_CHOICE_BY_FURTHEST_POINT_H_ +#include <limits> // for numeric_limits<> +#include <algorithm> // for sort +#include <vector> + namespace Gudhi { namespace witness_complex { @@ -36,73 +40,68 @@ namespace witness_complex { */ class Landmark_choice_by_furthest_point { - -private: + private: typedef std::vector<int> typeVectorVertex; - -public: - -/** - * \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`. - */ - template <typename KNearestNeighbours, - typename Point_random_access_range> - Landmark_choice_by_furthest_point(Point_random_access_range const &points, - int nbL, - KNearestNeighbours &knn) - { - int nb_points = points.end() - points.begin(); - assert(nb_points >= nbL); - std::vector<std::vector<double>> wit_land_dist(nb_points, std::vector<double>()); // distance matrix witness x landmarks - typeVectorVertex chosen_landmarks; // landmark list - - 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 - //int dim = points.begin()->size(); - - 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, *(points.begin() + 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; - } + public: + /** + * \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`. + */ + + template <typename KNearestNeighbours, + typename Point_random_access_range> + Landmark_choice_by_furthest_point(Point_random_access_range const &points, + int nbL, + KNearestNeighbours &knn) { + int nb_points = points.end() - points.begin(); + 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 + 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, *(points.begin() + 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 (unsigned i = 0; i < points.size(); ++i) - std::sort(knn[i].begin(), - knn[i].end(), - [&wit_land_dist, i](int a, int b) - { return wit_land_dist[i][a] < wit_land_dist[i][b]; }); } - + for (unsigned i = 0; i < points.size(); ++i) + std::sort(knn[i].begin(), + knn[i].end(), + [&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 +#endif // LANDMARK_CHOICE_BY_FURTHEST_POINT_H_ diff --git a/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h b/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h index 3f8a8d32..4747dd73 100644 --- a/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h +++ b/src/Witness_complex/include/gudhi/Landmark_choice_by_random_point.h @@ -23,6 +23,11 @@ #ifndef LANDMARK_CHOICE_BY_RANDOM_POINT_H_ #define LANDMARK_CHOICE_BY_RANDOM_POINT_H_ +#include <queue> // for priority_queue<> +#include <utility> // for pair<> +#include <vector> +#include <set> + namespace Gudhi { namespace witness_complex { @@ -36,60 +41,56 @@ namespace witness_complex { */ class Landmark_choice_by_random_point { + public: + /** \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. + */ -public: - - /** \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. - */ - - template <typename KNearestNeighbours, - typename Point_random_access_range> - Landmark_choice_by_random_point(Point_random_access_range const &points, - int nbL, - KNearestNeighbours &knn) - { - int nbP = points.end() - points.begin(); - assert(nbP >= nbL); - std::set<int> landmarks; - int current_number_of_landmarks=0; // counter for landmarks - - 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); - } + template <typename KNearestNeighbours, + typename Point_random_access_range> + Landmark_choice_by_random_point(Point_random_access_range const &points, + int nbL, + KNearestNeighbours &knn) { + int nbP = points.end() - points.begin(); + assert(nbP >= nbL); + std::set<int> landmarks; + int current_number_of_landmarks = 0; // counter for landmarks - int dim = points.begin()->size(); - 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;}); - std::set<int>::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); - 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(); - } - } + // 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); } + int dim = points.begin()->size(); + 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; + }); + std::set<int>::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); + 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(); + } + } + } }; -} - -} - -#endif +} // namespace witness_complex + +} // namespace Gudhi + +#endif // LANDMARK_CHOICE_BY_RANDOM_POINT_H_ diff --git a/src/Witness_complex/include/gudhi/Witness_complex.h b/src/Witness_complex/include/gudhi/Witness_complex.h index 819a0583..34cbc882 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex.h +++ b/src/Witness_complex/include/gudhi/Witness_complex.h @@ -23,257 +23,227 @@ #ifndef WITNESS_COMPLEX_H_ #define WITNESS_COMPLEX_H_ +// Needed for the adjacency graph in bad link search +#include <boost/graph/graph_traits.hpp> +#include <boost/graph/adjacency_list.hpp> +#include <boost/graph/connected_components.hpp> + #include <boost/container/flat_map.hpp> #include <boost/iterator/transform_iterator.hpp> + +#include <gudhi/distance_functions.h> + #include <algorithm> #include <utility> -#include <gudhi/distance_functions.h> #include <vector> #include <list> #include <set> #include <queue> #include <limits> -#include <math.h> #include <ctime> #include <iostream> -// Needed for the adjacency graph in bad link search -#include <boost/graph/graph_traits.hpp> -#include <boost/graph/adjacency_list.hpp> -#include <boost/graph/connected_components.hpp> - namespace Gudhi { - namespace witness_complex { - - /** - \class Witness_complex - \brief Constructs the witness complex for the given set of witnesses and landmarks. - \ingroup witness_complex - */ - template< class Simplicial_complex> - class Witness_complex { - - private: - - struct Active_witness { - int witness_id; - int landmark_id; - - Active_witness(int witness_id_, int landmark_id_) +namespace witness_complex { + +/** + \class Witness_complex + \brief Constructs the witness complex for the given set of witnesses and landmarks. + \ingroup witness_complex + */ +template< class Simplicial_complex> +class Witness_complex { + private: + struct Active_witness { + int witness_id; + int landmark_id; + + Active_witness(int witness_id_, int landmark_id_) : witness_id(witness_id_), - landmark_id(landmark_id_) - {} - }; + landmark_id(landmark_id_) { } + }; + private: + typedef typename Simplicial_complex::Simplex_handle Simplex_handle; + typedef typename Simplicial_complex::Vertex_handle Vertex_handle; - private: - - typedef typename Simplicial_complex::Simplex_handle Simplex_handle; - typedef typename Simplicial_complex::Vertex_handle Vertex_handle; - - typedef std::vector< double > Point_t; - typedef std::vector< Point_t > Point_Vector; + typedef std::vector< double > Point_t; + typedef std::vector< Point_t > Point_Vector; - //typedef typename Simplicial_complex::Filtration_value Filtration_value; - typedef std::vector< Vertex_handle > typeVectorVertex; - typedef std::pair< typeVectorVertex, Filtration_value> typeSimplex; - typedef std::pair< Simplex_handle, bool > typePairSimplexBool; - - typedef int Witness_id; - typedef int Landmark_id; - typedef std::list< Vertex_handle > ActiveWitnessList; - - private: - int nbL; // Number of landmarks - double density; // Desired density - Simplicial_complex& sc; // Simplicial complex - - public: + // typedef typename Simplicial_complex::Filtration_value Filtration_value; + typedef std::vector< Vertex_handle > typeVectorVertex; + typedef std::pair< typeVectorVertex, Filtration_value> typeSimplex; + typedef std::pair< Simplex_handle, bool > typePairSimplexBool; - ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - /** @name Constructor - */ + typedef int Witness_id; + typedef int Landmark_id; + typedef std::list< Vertex_handle > ActiveWitnessList; - //@{ + private: + int nbL; // Number of landmarks + Simplicial_complex& sc; // Simplicial complex - // Witness_range<Closest_landmark_range<Vertex_handle>> - - /** - * \brief Iterative construction of the witness complex. - * \details The witness complex is written in sc_ basing on a matrix knn of - * nearest neighbours of the form {witnesses}x{landmarks}. - * - * 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. - * - * Constructor takes into account at most (dim+1) - * first landmarks from each landmark range to construct simplices. - * - * Landmarks are supposed to be in [0,nbL_-1] - */ - template< typename KNearestNeighbors > - Witness_complex(KNearestNeighbors const & knn, - Simplicial_complex & sc_, - int nbL_, - int dim ): nbL(nbL_), sc(sc_) - { - //Construction of the active witness list - int nbW = knn.size(); - typeVectorVertex vv; - typeSimplex simplex; - typePairSimplexBool returnValue; - int counter = 0; - /* The list of still useful witnesses - * it will diminuish in the course of iterations - */ - ActiveWitnessList active_w;// = new ActiveWitnessList(); - for (int i=0; i != nbL; ++i) { - // initial fill of 0-dimensional simplices - // by doing it we don't assume that landmarks are necessarily witnesses themselves anymore - counter++; - vv = {i}; - returnValue = sc.insert_simplex(vv); - /* TODO Error if not inserted : normally no need here though*/ - } - int k=1; /* current dimension in iterative construction */ - for (int i=0; i != nbW; ++i) - active_w.push_back(i); - //std::cout << "Successfully added edges" << std::endl; - while (!active_w.empty() && k < dim ) - { - //std::cout << "Started the step k=" << k << std::endl; - typename ActiveWitnessList::iterator it = active_w.begin(); - while (it != active_w.end()) - { - typeVectorVertex simplex_vector; - /* THE INSERTION: Checking if all the subfaces are in the simplex tree*/ - bool ok = all_faces_in(knn, *it, k); - if (ok) - { - for (int i = 0; i != k+1; ++i) - simplex_vector.push_back(knn[*it][i]); - returnValue = sc.insert_simplex(simplex_vector,0.0); - it++; - } - else - active_w.erase(it++); //First increase the iterator and then erase the previous element - } - k++; - } - } + public: + ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + /** @name Constructor + */ - //@} - - private: - - /** \brief Check if the facets of the k-dimensional simplex witnessed - * by witness witness_id are already in the complex. - * inserted_vertex is the handle of the (k+1)-th vertex witnessed by witness_id + //@{ + + // Witness_range<Closest_landmark_range<Vertex_handle>> + + /** + * \brief Iterative construction of the witness complex. + * \details The witness complex is written in sc_ basing on a matrix knn of + * nearest neighbours of the form {witnesses}x{landmarks}. + * + * 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. + * + * Constructor takes into account at most (dim+1) + * first landmarks from each landmark range to construct simplices. + * + * Landmarks are supposed to be in [0,nbL_-1] + */ + template< typename KNearestNeighbors > + Witness_complex(KNearestNeighbors const & knn, + Simplicial_complex & sc_, + int nbL_, + int dim) : nbL(nbL_), sc(sc_) { + // Construction of the active witness list + int nbW = knn.size(); + typeVectorVertex vv; + int counter = 0; + /* The list of still useful witnesses + * it will diminuish in the course of iterations */ - template <typename KNearestNeighbors> - bool all_faces_in(KNearestNeighbors const &knn, int witness_id, int k) - { - //std::cout << "All face in with the landmark " << inserted_vertex << std::endl; - std::vector< Vertex_handle > facet; - //Vertex_handle curr_vh = curr_sh->first; - // CHECK ALL THE FACETS - for (int i = 0; i != k+1; ++i) - { - facet = {}; - for (int j = 0; j != k+1; ++j) - { - if (j != i) - { - facet.push_back(knn[witness_id][j]); - } - }//endfor - if (sc.find(facet) == sc.null_simplex()) - return false; - //std::cout << "++++ finished loop safely\n"; - } //endfor - return true; + ActiveWitnessList active_w; // = new ActiveWitnessList(); + for (int i = 0; i != nbL; ++i) { + // initial fill of 0-dimensional simplices + // by doing it we don't assume that landmarks are necessarily witnesses themselves anymore + counter++; + vv = {i}; + sc.insert_simplex(vv); + // TODO(SK) Error if not inserted : normally no need here though + } + int k = 1; /* current dimension in iterative construction */ + for (int i = 0; i != nbW; ++i) + active_w.push_back(i); + // std::cout << "Successfully added edges" << std::endl; + while (!active_w.empty() && k < dim) { + // std::cout << "Started the step k=" << k << std::endl; + typename ActiveWitnessList::iterator it = active_w.begin(); + while (it != active_w.end()) { + typeVectorVertex simplex_vector; + /* THE INSERTION: Checking if all the subfaces are in the simplex tree*/ + bool ok = all_faces_in(knn, *it, k); + if (ok) { + for (int i = 0; i != k + 1; ++i) + simplex_vector.push_back(knn[*it][i]); + sc.insert_simplex(simplex_vector, 0.0); + // TODO(SK) Error if not inserted : normally no need here though + it++; + } else { + active_w.erase(it++); // First increase the iterator and then erase the previous element + } + } + k++; } + } - template <typename T> - void print_vector(const std::vector<T> v) - { - std::cout << "["; - if (!v.empty()) - { - std::cout << *(v.begin()); - for (auto it = v.begin()+1; it != v.end(); ++it) - { - std::cout << ","; - std::cout << *it; - } + //@} + + private: + /** \brief Check if the facets of the k-dimensional simplex witnessed + * by witness witness_id are already in the complex. + * inserted_vertex is the handle of the (k+1)-th vertex witnessed by witness_id + */ + template <typename KNearestNeighbors> + bool all_faces_in(KNearestNeighbors const &knn, int witness_id, int k) { + // std::cout << "All face in with the landmark " << inserted_vertex << std::endl; + std::vector< Vertex_handle > facet; + // Vertex_handle curr_vh = curr_sh->first; + // CHECK ALL THE FACETS + for (int i = 0; i != k + 1; ++i) { + facet = {}; + for (int j = 0; j != k + 1; ++j) { + if (j != i) { + facet.push_back(knn[witness_id][j]); + } + } // endfor + if (sc.find(facet) == sc.null_simplex()) + return false; + // std::cout << "++++ finished loop safely\n"; + } // endfor + return true; + } + + template <typename T> + static void print_vector(const std::vector<T>& v) { + std::cout << "["; + if (!v.empty()) { + std::cout << *(v.begin()); + for (auto it = v.begin() + 1; it != v.end(); ++it) { + std::cout << ","; + std::cout << *it; } - std::cout << "]"; } - - public: - - /** - * \brief Verification if every simplex in the complex is witnessed by witnesses in knn. - * \param print_output =true will print the witnesses for each simplex - * \remark Added for debugging purposes. - */ - template< class KNearestNeighbors > - bool is_witness_complex(KNearestNeighbors const & knn, bool print_output) - { - //bool final_result = true; - for (Simplex_handle sh: sc.complex_simplex_range()) - { - bool is_witnessed = false; - typeVectorVertex simplex; - int nbV = 0; //number of verticed in the simplex - for (int v: sc.simplex_vertex_range(sh)) - simplex.push_back(v); - nbV = simplex.size(); - for (typeVectorVertex w: knn) - { - bool has_vertices = true; - for (int v: simplex) - if (std::find(w.begin(), w.begin()+nbV, v) == w.begin()+nbV) - { - has_vertices = false; - //break; - } - if (has_vertices) - { - is_witnessed = true; - if (print_output) - { - std::cout << "The simplex "; - print_vector(simplex); - std::cout << " is witnessed by the witness "; - print_vector(w); - std::cout << std::endl; - } - break; - } - } - if (!is_witnessed) - { - if (print_output) - { - std::cout << "The following simplex is not witnessed "; - print_vector(simplex); - std::cout << std::endl; - } - assert(is_witnessed); - return false; - } + std::cout << "]"; + } + + public: + /** + * \brief Verification if every simplex in the complex is witnessed by witnesses in knn. + * \param print_output =true will print the witnesses for each simplex + * \remark Added for debugging purposes. + */ + template< class KNearestNeighbors > + bool is_witness_complex(KNearestNeighbors const & knn, bool print_output) { + // bool final_result = true; + for (Simplex_handle sh : sc.complex_simplex_range()) { + bool is_witnessed = false; + typeVectorVertex simplex; + int nbV = 0; // number of verticed in the simplex + for (int v : sc.simplex_vertex_range(sh)) + simplex.push_back(v); + nbV = simplex.size(); + for (typeVectorVertex w : knn) { + bool has_vertices = true; + for (int v : simplex) + if (std::find(w.begin(), w.begin() + nbV, v) == w.begin() + nbV) { + has_vertices = false; + // break; + } + if (has_vertices) { + is_witnessed = true; + if (print_output) { + std::cout << "The simplex "; + print_vector(simplex); + std::cout << " is witnessed by the witness "; + print_vector(w); + std::cout << std::endl; + } + break; + } + } + if (!is_witnessed) { + if (print_output) { + std::cout << "The following simplex is not witnessed "; + print_vector(simplex); + std::cout << std::endl; } - return true; + assert(is_witnessed); + return false; + } } + return true; + } +}; - - }; //class Witness_complex +} // namespace witness_complex - } //namespace witness_complex - -} // namespace Guhdi +} // namespace Gudhi -#endif +#endif // WITNESS_COMPLEX_H_ diff --git a/src/Witness_complex/include/gudhi/Witness_complex_doc.h b/src/Witness_complex/include/gudhi/Witness_complex_doc.h index dbe9e7ce..e9f78170 100644 --- a/src/Witness_complex/include/gudhi/Witness_complex_doc.h +++ b/src/Witness_complex/include/gudhi/Witness_complex_doc.h @@ -35,4 +35,4 @@ */ -#endif +#endif // WITNESS_COMPLEX_DOC_H_ diff --git a/src/Witness_complex/test/CMakeLists.txt b/src/Witness_complex/test/CMakeLists.txt index a13fd94a..9422c152 100644 --- a/src/Witness_complex/test/CMakeLists.txt +++ b/src/Witness_complex/test/CMakeLists.txt @@ -1,16 +1,34 @@ cmake_minimum_required(VERSION 2.6) -project(GUDHITestWitnessComplex) +project(GUDHIWitnessComplexUT) -#if(NOT MSVC) -# set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} --coverage") -# set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} --coverage") -# set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} --coverage") -#endif() +if (GCOVR_PATH) + # for gcovr to make coverage reports - Corbera Jenkins plugin + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -fprofile-arcs -ftest-coverage") + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -fprofile-arcs -ftest-coverage") + set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -fprofile-arcs -ftest-coverage") +endif() +if (GPROF_PATH) + # for gprof to make coverage reports - Jenkins + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -pg") + set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -pg") + set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -pg") +endif() -add_executable ( simple_witness_complex simple_witness_complex.cpp ) -add_test(test ${CMAKE_CURRENT_BINARY_DIR}/simple_witness_complex) +add_executable ( simple_witness_complexUT simple_witness_complex.cpp ) +target_link_libraries(simple_witness_complexUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) -add_executable ( witness_complex_points witness_complex_points.cpp ) -add_test(test ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_points) +# Unitary tests definition and xml result file generation +add_test(NAME simple_witness_complexUT + COMMAND ${CMAKE_CURRENT_BINARY_DIR}/simple_witness_complexUT + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/simple_witness_complexUT.xml --log_level=test_suite --report_level=no) + +add_executable ( witness_complex_pointsUT witness_complex_points.cpp ) +target_link_libraries(witness_complex_pointsUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + +# Unitary tests definition and xml result file generation +add_test(NAME witness_complex_pointsUT + COMMAND ${CMAKE_CURRENT_BINARY_DIR}/witness_complex_pointsUT + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/witness_complex_pointsUT.xml --log_level=test_suite --report_level=no) -#cpplint_add_tests("${CMAKE_SOURCE_DIR}/src/Simplex_tree/include/gudhi") diff --git a/src/Witness_complex/test/simple_witness_complex.cpp b/src/Witness_complex/test/simple_witness_complex.cpp index 7735ca6f..7d44b90c 100644 --- a/src/Witness_complex/test/simple_witness_complex.cpp +++ b/src/Witness_complex/test/simple_witness_complex.cpp @@ -20,34 +20,40 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#include <iostream> -#include <ctime> +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "simple_witness_complex" +#include <boost/test/unit_test.hpp> +#include <boost/mpl/list.hpp> + #include <gudhi/Simplex_tree.h> #include <gudhi/Witness_complex.h> -using namespace Gudhi; -using namespace Gudhi::witness_complex; +#include <iostream> +#include <ctime> +#include <vector> +typedef Gudhi::Simplex_tree<> Simplex_tree; typedef std::vector< Vertex_handle > typeVectorVertex; -typedef Witness_complex<Simplex_tree<>> WitnessComplex; +typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex; -int main (int argc, char * const argv[]) -{ - Simplex_tree<> complex; +BOOST_AUTO_TEST_CASE(simple_witness_complex) { + Simplex_tree complex; std::vector< typeVectorVertex > knn; - typeVectorVertex witness0 = {1,0,5,2,6,3,4}; knn.push_back(witness0 ); - typeVectorVertex witness1 = {2,6,4,5,0,1,3}; knn.push_back(witness1 ); - typeVectorVertex witness2 = {3,4,2,1,5,6,0}; knn.push_back(witness2 ); - typeVectorVertex witness3 = {4,2,1,3,5,6,0}; knn.push_back(witness3 ); - typeVectorVertex witness4 = {5,1,6,0,2,3,4}; knn.push_back(witness4 ); - typeVectorVertex witness5 = {6,0,5,2,1,3,4}; knn.push_back(witness5 ); - typeVectorVertex witness6 = {0,5,6,1,2,3,4}; knn.push_back(witness6 ); - typeVectorVertex witness7 = {2,6,4,5,3,1,0}; knn.push_back(witness7 ); - typeVectorVertex witness8 = {1,2,5,4,3,6,0}; knn.push_back(witness8 ); - typeVectorVertex witness9 = {3,4,0,6,5,1,2}; knn.push_back(witness9 ); - typeVectorVertex witness10 = {5,0,1,3,6,2,4}; knn.push_back(witness10); - typeVectorVertex witness11 = {5,6,1,0,2,3,4}; knn.push_back(witness11); - typeVectorVertex witness12 = {1,6,0,5,2,3,4}; knn.push_back(witness12); + + knn.push_back({1, 0, 5, 2, 6, 3, 4}); + knn.push_back({2, 6, 4, 5, 0, 1, 3}); + knn.push_back({3, 4, 2, 1, 5, 6, 0}); + knn.push_back({4, 2, 1, 3, 5, 6, 0}); + knn.push_back({5, 1, 6, 0, 2, 3, 4}); + knn.push_back({6, 0, 5, 2, 1, 3, 4}); + knn.push_back({0, 5, 6, 1, 2, 3, 4}); + knn.push_back({2, 6, 4, 5, 3, 1, 0}); + knn.push_back({1, 2, 5, 4, 3, 6, 0}); + knn.push_back({3, 4, 0, 6, 5, 1, 2}); + knn.push_back({5, 0, 1, 3, 6, 2, 4}); + knn.push_back({5, 6, 1, 0, 2, 3, 4}); + knn.push_back({1, 6, 0, 5, 2, 3, 4}); WitnessComplex witnessComplex(knn, complex, 7, 7); - assert(witnessComplex.is_witness_complex(knn, false)); + + BOOST_CHECK(witnessComplex.is_witness_complex(knn, false)); } diff --git a/src/Witness_complex/test/witness_complex_points.cpp b/src/Witness_complex/test/witness_complex_points.cpp index 3850bd82..300b2ac5 100644 --- a/src/Witness_complex/test/witness_complex_points.cpp +++ b/src/Witness_complex/test/witness_complex_points.cpp @@ -20,45 +20,47 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#include <iostream> -#include <ctime> +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "witness_complex_points" +#include <boost/test/unit_test.hpp> +#include <boost/mpl/list.hpp> + #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 <iostream> +#include <vector> -using namespace Gudhi; -using namespace Gudhi::witness_complex; - -typedef std::vector< Vertex_handle > typeVectorVertex; -typedef Witness_complex<Simplex_tree<>> WitnessComplex; typedef std::vector<double> Point; -//typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex; -//typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool; +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef Gudhi::Simplex_tree<> Simplex_tree; +typedef Gudhi::witness_complex::Witness_complex<Simplex_tree> WitnessComplex; +typedef Gudhi::witness_complex::Landmark_choice_by_random_point Landmark_choice_by_random_point; +typedef Gudhi::witness_complex::Landmark_choice_by_furthest_point Landmark_choice_by_furthest_point; -int main (int argc, char * const argv[]) -{ +BOOST_AUTO_TEST_CASE(witness_complex_points) { std::vector< typeVectorVertex > knn; std::vector< Point > points; // Add grid points as witnesses for (double i = 0; i < 10; i += 1.0) for (double j = 0; j < 10; j += 1.0) for (double k = 0; k < 10; k += 1.0) - points.push_back(Point({i,j,k})); + points.push_back(Point({i, j, k})); bool b_print_output = false; // First test: random choice - Simplex_tree<> complex1; + Simplex_tree complex1; Landmark_choice_by_random_point lcrp(points, 100, knn); assert(!knn.empty()); WitnessComplex witnessComplex1(knn, complex1, 100, 3); - assert(witnessComplex1.is_witness_complex(knn, b_print_output)); + BOOST_CHECK(witnessComplex1.is_witness_complex(knn, b_print_output)); // Second test: furthest choice knn.clear(); - Simplex_tree<> complex2; + Simplex_tree complex2; Landmark_choice_by_furthest_point lcfp(points, 100, knn); WitnessComplex witnessComplex2(knn, complex2, 100, 3); - assert(witnessComplex2.is_witness_complex(knn, b_print_output)); + BOOST_CHECK(witnessComplex2.is_witness_complex(knn, b_print_output)); } |