diff options
author | Gard Spreemann <gspreemann@gmail.com> | 2017-02-07 17:33:01 +0100 |
---|---|---|
committer | Gard Spreemann <gspreemann@gmail.com> | 2017-02-07 17:33:01 +0100 |
commit | 55c7181126aa7defce38c9b82872d14223d4c1dd (patch) | |
tree | 7c683f014709459f066fd87a21da7f74cfc31a53 /example |
Initial import of upstream's 1.3.1.upstream/1.3.1
Diffstat (limited to 'example')
45 files changed, 4683 insertions, 0 deletions
diff --git a/example/Alpha_complex/Alpha_complex_from_off.cpp b/example/Alpha_complex/Alpha_complex_from_off.cpp new file mode 100644 index 00000000..7836d59a --- /dev/null +++ b/example/Alpha_complex/Alpha_complex_from_off.cpp @@ -0,0 +1,56 @@ +#include <gudhi/Alpha_complex.h> +#include <CGAL/Epick_d.h> + +#include <iostream> +#include <string> + +void usage(int nbArgs, char * const progName) { + std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n"; + std::cerr << "Usage: " << progName << " filename.off alpha_square_max_value [ouput_file.txt]\n"; + std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.off 60.0\n"; + exit(-1); // ----- >> +} + +int main(int argc, char **argv) { + if ((argc != 3) && (argc != 4)) usage(argc, (argv[0] - 1)); + + std::string off_file_name(argv[1]); + double alpha_square_max_value = atof(argv[2]); + + // ---------------------------------------------------------------------------- + // Init of an alpha complex from an OFF file + // ---------------------------------------------------------------------------- + typedef CGAL::Epick_d< CGAL::Dynamic_dimension_tag > Kernel; + Gudhi::alpha_complex::Alpha_complex<Kernel> alpha_complex_from_file(off_file_name, alpha_square_max_value); + + std::streambuf* streambufffer; + std::ofstream ouput_file_stream; + + if (argc == 4) { + ouput_file_stream.open(std::string(argv[3])); + streambufffer = ouput_file_stream.rdbuf(); + } else { + streambufffer = std::cout.rdbuf(); + } + + std::ostream output_stream(streambufffer); + + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + output_stream << "Alpha complex is of dimension " << alpha_complex_from_file.dimension() << + " - " << alpha_complex_from_file.num_simplices() << " simplices - " << + alpha_complex_from_file.num_vertices() << " vertices." << std::endl; + + output_stream << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; + for (auto f_simplex : alpha_complex_from_file.filtration_simplex_range()) { + output_stream << " ( "; + for (auto vertex : alpha_complex_from_file.simplex_vertex_range(f_simplex)) { + output_stream << vertex << " "; + } + output_stream << ") -> " << "[" << alpha_complex_from_file.filtration(f_simplex) << "] "; + output_stream << std::endl; + } + ouput_file_stream.close(); + return 0; +} diff --git a/example/Alpha_complex/Alpha_complex_from_points.cpp b/example/Alpha_complex/Alpha_complex_from_points.cpp new file mode 100644 index 00000000..49f77276 --- /dev/null +++ b/example/Alpha_complex/Alpha_complex_from_points.cpp @@ -0,0 +1,62 @@ +#include <CGAL/Epick_d.h> +#include <gudhi/Alpha_complex.h> + +#include <iostream> +#include <string> +#include <vector> +#include <limits> // for numeric limits + +typedef CGAL::Epick_d< CGAL::Dimension_tag<2> > Kernel; +typedef Kernel::Point_d Point; +typedef std::vector<Point> Vector_of_points; + +void usage(int nbArgs, char * const progName) { + std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n"; + std::cerr << "Usage: " << progName << " [alpha_square_max_value]\n"; + std::cerr << " i.e.: " << progName << " 60.0\n"; + exit(-1); // ----- >> +} + +int main(int argc, char **argv) { + if ((argc != 1) && (argc != 2)) usage(argc, (argv[0] - 1)); + + // Delaunay complex if alpha_square_max_value is not given by the user. + double alpha_square_max_value = std::numeric_limits<double>::infinity(); + if (argc == 2) + alpha_square_max_value = atof(argv[1]); + + // ---------------------------------------------------------------------------- + // Init of a list of points + // ---------------------------------------------------------------------------- + Vector_of_points points; + points.push_back(Point(1.0, 1.0)); + points.push_back(Point(7.0, 0.0)); + points.push_back(Point(4.0, 6.0)); + points.push_back(Point(9.0, 6.0)); + points.push_back(Point(0.0, 14.0)); + points.push_back(Point(2.0, 19.0)); + points.push_back(Point(9.0, 17.0)); + + // ---------------------------------------------------------------------------- + // Init of an alpha complex from the list of points + // ---------------------------------------------------------------------------- + Gudhi::alpha_complex::Alpha_complex<Kernel> alpha_complex_from_points(points, alpha_square_max_value); + + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + std::cout << "Alpha complex is of dimension " << alpha_complex_from_points.dimension() << + " - " << alpha_complex_from_points.num_simplices() << " simplices - " << + alpha_complex_from_points.num_vertices() << " vertices." << std::endl; + + std::cout << "Iterator on alpha complex simplices in the filtration order, with [filtration value]:" << std::endl; + for (auto f_simplex : alpha_complex_from_points.filtration_simplex_range()) { + std::cout << " ( "; + for (auto vertex : alpha_complex_from_points.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << ") -> " << "[" << alpha_complex_from_points.filtration(f_simplex) << "] "; + std::cout << std::endl; + } + return 0; +} diff --git a/example/Alpha_complex/CMakeLists.txt b/example/Alpha_complex/CMakeLists.txt new file mode 100644 index 00000000..71a95d61 --- /dev/null +++ b/example/Alpha_complex/CMakeLists.txt @@ -0,0 +1,33 @@ +cmake_minimum_required(VERSION 2.6) +project(Alpha_complex_examples) + +# need CGAL 4.7 +# cmake -DCGAL_DIR=~/workspace/CGAL-4.7-Ic-41 ../../.. +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.7.0) + if (EIGEN3_FOUND) + add_executable ( alphapoints Alpha_complex_from_points.cpp ) + target_link_libraries(alphapoints ${Boost_SYSTEM_LIBRARY} ${Boost_THREAD_LIBRARY} ${CGAL_LIBRARY}) + add_executable ( alphaoffreader Alpha_complex_from_off.cpp ) + target_link_libraries(alphaoffreader ${Boost_SYSTEM_LIBRARY} ${Boost_THREAD_LIBRARY} ${CGAL_LIBRARY}) + if (TBB_FOUND) + target_link_libraries(alphapoints ${TBB_LIBRARIES}) + target_link_libraries(alphaoffreader ${TBB_LIBRARIES}) + endif() + + add_test(alphapoints ${CMAKE_CURRENT_BINARY_DIR}/alphapoints) + # Do not forget to copy test files in current binary dir + file(COPY "${CMAKE_SOURCE_DIR}/data/points/alphacomplexdoc.off" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) + add_test(alphaoffreader_doc_60 ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader alphacomplexdoc.off 60.0 ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_result_60.txt) + add_test(alphaoffreader_doc_32 ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader alphacomplexdoc.off 32.0 ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_result_32.txt) + if (DIFF_PATH) + # Do not forget to copy test results files in current binary dir + file(COPY "alphaoffreader_for_doc_32.txt" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) + file(COPY "alphaoffreader_for_doc_60.txt" DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/) + + add_test(alphaoffreader_doc_60_diff_files ${DIFF_PATH} ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_result_60.txt ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_for_doc_60.txt) + add_test(alphaoffreader_doc_32_diff_files ${DIFF_PATH} ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_result_32.txt ${CMAKE_CURRENT_BINARY_DIR}/alphaoffreader_for_doc_32.txt) + endif() + endif(EIGEN3_FOUND) + endif(NOT CGAL_VERSION VERSION_LESS 4.7.0) +endif(CGAL_FOUND) diff --git a/example/Alpha_complex/alphaoffreader_for_doc_32.txt b/example/Alpha_complex/alphaoffreader_for_doc_32.txt new file mode 100644 index 00000000..13183e86 --- /dev/null +++ b/example/Alpha_complex/alphaoffreader_for_doc_32.txt @@ -0,0 +1,22 @@ +Alpha complex is of dimension 2 - 20 simplices - 7 vertices. +Iterator on alpha complex simplices in the filtration order, with [filtration value]: + ( 0 ) -> [0] + ( 1 ) -> [0] + ( 2 ) -> [0] + ( 3 ) -> [0] + ( 4 ) -> [0] + ( 5 ) -> [0] + ( 6 ) -> [0] + ( 3 2 ) -> [6.25] + ( 5 4 ) -> [7.25] + ( 2 0 ) -> [8.5] + ( 1 0 ) -> [9.25] + ( 3 1 ) -> [10] + ( 2 1 ) -> [11.25] + ( 3 2 1 ) -> [12.5] + ( 2 1 0 ) -> [12.9959] + ( 6 5 ) -> [13.25] + ( 4 2 ) -> [20] + ( 6 4 ) -> [22.7367] + ( 6 5 4 ) -> [22.7367] + ( 6 3 ) -> [30.25] diff --git a/example/Alpha_complex/alphaoffreader_for_doc_60.txt b/example/Alpha_complex/alphaoffreader_for_doc_60.txt new file mode 100644 index 00000000..71f29a00 --- /dev/null +++ b/example/Alpha_complex/alphaoffreader_for_doc_60.txt @@ -0,0 +1,27 @@ +Alpha complex is of dimension 2 - 25 simplices - 7 vertices. +Iterator on alpha complex simplices in the filtration order, with [filtration value]: + ( 0 ) -> [0] + ( 1 ) -> [0] + ( 2 ) -> [0] + ( 3 ) -> [0] + ( 4 ) -> [0] + ( 5 ) -> [0] + ( 6 ) -> [0] + ( 3 2 ) -> [6.25] + ( 5 4 ) -> [7.25] + ( 2 0 ) -> [8.5] + ( 1 0 ) -> [9.25] + ( 3 1 ) -> [10] + ( 2 1 ) -> [11.25] + ( 3 2 1 ) -> [12.5] + ( 2 1 0 ) -> [12.9959] + ( 6 5 ) -> [13.25] + ( 4 2 ) -> [20] + ( 6 4 ) -> [22.7367] + ( 6 5 4 ) -> [22.7367] + ( 6 3 ) -> [30.25] + ( 6 2 ) -> [36.5] + ( 6 3 2 ) -> [36.5] + ( 6 4 2 ) -> [37.2449] + ( 4 0 ) -> [59.7107] + ( 4 2 0 ) -> [59.7107] diff --git a/example/Bitmap_cubical_complex/Bitmap_cubical_complex.cpp b/example/Bitmap_cubical_complex/Bitmap_cubical_complex.cpp new file mode 100644 index 00000000..e6bc6648 --- /dev/null +++ b/example/Bitmap_cubical_complex/Bitmap_cubical_complex.cpp @@ -0,0 +1,72 @@ +/* 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): Pawel Dlotko + * + * Copyright (C) 2015 INRIA Saclay (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 <gudhi/reader_utils.h> +#include <gudhi/Bitmap_cubical_complex.h> +#include <gudhi/Persistent_cohomology.h> + +// standard stuff +#include <iostream> +#include <sstream> +#include <vector> + +int main(int argc, char** argv) { + std::cout << "This program computes persistent homology, by using bitmap_cubical_complex class, of cubical " << + "complexes provided in text files in Perseus style (the only numbered in the first line is a dimension D of a" << + "bitmap. In the lines I between 2 and D+1 there are numbers of top dimensional cells in the direction I. Let " << + "N denote product of the numbers in the lines between 2 and D. In the lines D+2 to D+2+N there are " << + "filtrations of top dimensional cells. We assume that the cells are in the lexicographical order. See " << + "CubicalOneSphere.txt or CubicalTwoSphere.txt for example.\n" << std::endl; + + int p = 2; + double min_persistence = 0; + + if (argc != 2) { + std::cerr << "Wrong number of parameters. Please provide the name of a file with a Perseus style bitmap at " << + "the input. The program will now terminate.\n"; + return 1; + } + + typedef Gudhi::cubical_complex::Bitmap_cubical_complex_base<double> Bitmap_cubical_complex_base; + typedef Gudhi::cubical_complex::Bitmap_cubical_complex<Bitmap_cubical_complex_base> Bitmap_cubical_complex; + typedef Gudhi::persistent_cohomology::Field_Zp Field_Zp; + typedef Gudhi::persistent_cohomology::Persistent_cohomology<Bitmap_cubical_complex, Field_Zp> Persistent_cohomology; + + Bitmap_cubical_complex b(argv[1]); + + // Compute the persistence diagram of the complex + Persistent_cohomology pcoh(b); + pcoh.init_coefficients(p); // initializes the coefficient field for homology + pcoh.compute_persistent_cohomology(min_persistence); + + std::stringstream ss; + ss << argv[1] << "_persistence"; + std::ofstream out(ss.str().c_str()); + pcoh.output_diagram(out); + out.close(); + + std::cout << "Result in file: " << ss.str().c_str() << "\n"; + + return 0; +} + diff --git a/example/Bitmap_cubical_complex/Bitmap_cubical_complex_periodic_boundary_conditions.cpp b/example/Bitmap_cubical_complex/Bitmap_cubical_complex_periodic_boundary_conditions.cpp new file mode 100644 index 00000000..839a4c89 --- /dev/null +++ b/example/Bitmap_cubical_complex/Bitmap_cubical_complex_periodic_boundary_conditions.cpp @@ -0,0 +1,74 @@ +/* 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): Pawel Dlotko + * + * Copyright (C) 2015 INRIA Saclay (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 <gudhi/reader_utils.h> +#include <gudhi/Bitmap_cubical_complex.h> +#include <gudhi/Bitmap_cubical_complex_periodic_boundary_conditions_base.h> +#include <gudhi/Persistent_cohomology.h> + +// standard stuff +#include <iostream> +#include <sstream> +#include <vector> + +int main(int argc, char** argv) { + std::cout << "This program computes persistent homology, by using " << + "Bitmap_cubical_complex_periodic_boundary_conditions class, of cubical complexes provided in text files in " << + "Perseus style (the only numbered in the first line is a dimension D of a bitmap. In the lines I between 2 " << + "and D+1 there are numbers of top dimensional cells in the direction I. Let N denote product of the numbers " << + "in the lines between 2 and D. In the lines D+2 to D+2+N there are filtrations of top dimensional cells. We " << + "assume that the cells are in the lexicographical order. See CubicalOneSphere.txt or CubicalTwoSphere.txt for" << + " example.\n" << std::endl; + + int p = 2; + double min_persistence = 0; + + if (argc != 2) { + std::cerr << "Wrong number of parameters. Please provide the name of a file with a Perseus style bitmap at " << + "the input. The program will now terminate.\n"; + return 1; + } + + typedef Gudhi::cubical_complex::Bitmap_cubical_complex_periodic_boundary_conditions_base<double> Bitmap_base; + typedef Gudhi::cubical_complex::Bitmap_cubical_complex< Bitmap_base > Bitmap_cubical_complex; + + Bitmap_cubical_complex b(argv[1]); + + typedef Gudhi::persistent_cohomology::Field_Zp Field_Zp; + typedef Gudhi::persistent_cohomology::Persistent_cohomology<Bitmap_cubical_complex, Field_Zp> Persistent_cohomology; + // Compute the persistence diagram of the complex + Persistent_cohomology pcoh(b, true); + pcoh.init_coefficients(p); // initializes the coefficient field for homology + pcoh.compute_persistent_cohomology(min_persistence); + + std::stringstream ss; + ss << argv[1] << "_persistence"; + std::ofstream out(ss.str().c_str()); + pcoh.output_diagram(out); + out.close(); + + std::cout << "Result in file: " << ss.str().c_str() << "\n"; + + return 0; +} + diff --git a/example/Bitmap_cubical_complex/CMakeLists.txt b/example/Bitmap_cubical_complex/CMakeLists.txt new file mode 100644 index 00000000..2fddc514 --- /dev/null +++ b/example/Bitmap_cubical_complex/CMakeLists.txt @@ -0,0 +1,26 @@ +cmake_minimum_required(VERSION 2.6) +project(Bitmap_cubical_complex_examples) + +add_executable ( Bitmap_cubical_complex Bitmap_cubical_complex.cpp ) +target_link_libraries(Bitmap_cubical_complex ${Boost_SYSTEM_LIBRARY}) +if (TBB_FOUND) + target_link_libraries(Bitmap_cubical_complex ${TBB_LIBRARIES}) +endif() +add_test(Bitmap_cubical_complex_one_sphere ${CMAKE_CURRENT_BINARY_DIR}/Bitmap_cubical_complex ${CMAKE_SOURCE_DIR}/data/bitmap/CubicalOneSphere.txt) +add_test(Bitmap_cubical_complex_two_sphere ${CMAKE_CURRENT_BINARY_DIR}/Bitmap_cubical_complex ${CMAKE_SOURCE_DIR}/data/bitmap/CubicalTwoSphere.txt) + +add_executable ( Random_bitmap_cubical_complex Random_bitmap_cubical_complex.cpp ) +target_link_libraries(Random_bitmap_cubical_complex ${Boost_SYSTEM_LIBRARY}) +if (TBB_FOUND) + target_link_libraries(Random_bitmap_cubical_complex ${TBB_LIBRARIES}) +endif() +add_test(Random_bitmap_cubical_complex ${CMAKE_CURRENT_BINARY_DIR}/Random_bitmap_cubical_complex 2 100 100) + +add_executable ( Bitmap_cubical_complex_periodic_boundary_conditions Bitmap_cubical_complex_periodic_boundary_conditions.cpp ) +target_link_libraries(Bitmap_cubical_complex_periodic_boundary_conditions ${Boost_SYSTEM_LIBRARY}) +if (TBB_FOUND) + target_link_libraries(Bitmap_cubical_complex_periodic_boundary_conditions ${TBB_LIBRARIES}) +endif() +add_test(Bitmap_cubical_complex_periodic_2d_torus ${CMAKE_CURRENT_BINARY_DIR}/Bitmap_cubical_complex_periodic_boundary_conditions ${CMAKE_SOURCE_DIR}/data/bitmap/2d_torus.txt) +add_test(Bitmap_cubical_complex_periodic_3d_torus ${CMAKE_CURRENT_BINARY_DIR}/Bitmap_cubical_complex_periodic_boundary_conditions ${CMAKE_SOURCE_DIR}/data/bitmap/3d_torus.txt) + diff --git a/example/Bitmap_cubical_complex/Random_bitmap_cubical_complex.cpp b/example/Bitmap_cubical_complex/Random_bitmap_cubical_complex.cpp new file mode 100644 index 00000000..16ad65a0 --- /dev/null +++ b/example/Bitmap_cubical_complex/Random_bitmap_cubical_complex.cpp @@ -0,0 +1,83 @@ +/* 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): Pawel Dlotko + * + * Copyright (C) 2015 INRIA Saclay (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/>. + */ + + +// for persistence algorithm +#include <gudhi/reader_utils.h> +#include <gudhi/Bitmap_cubical_complex.h> +#include <gudhi/Persistent_cohomology.h> + +// standard stuff +#include <iostream> +#include <sstream> +#include <vector> + +int main(int argc, char** argv) { + srand(time(0)); + + std::cout << "This program computes persistent homology, by using bitmap_cubical_complex class, of cubical " << + "complexes. The first parameter of the program is the dimension D of the bitmap. The next D parameters are " << + "number of top dimensional cubes in each dimension of the bitmap. The program will create random cubical " << + "complex of that sizes and compute persistent homology of it." << std::endl; + + int p = 2; + double min_persistence = 0; + + if (argc < 3) { + std::cerr << "Wrong number of parameters, the program will now terminate\n"; + return 1; + } + + size_t dimensionOfBitmap = (size_t) atoi(argv[1]); + std::vector< unsigned > sizes; + size_t multipliers = 1; + for (size_t dim = 0; dim != dimensionOfBitmap; ++dim) { + unsigned sizeInThisDimension = (unsigned) atoi(argv[2 + dim]); + sizes.push_back(sizeInThisDimension); + multipliers *= sizeInThisDimension; + } + + std::vector< double > data; + for (size_t i = 0; i != multipliers; ++i) { + data.push_back(rand() / static_cast<double>(RAND_MAX)); + } + + typedef Gudhi::cubical_complex::Bitmap_cubical_complex_base<double> Bitmap_cubical_complex_base; + typedef Gudhi::cubical_complex::Bitmap_cubical_complex<Bitmap_cubical_complex_base> Bitmap_cubical_complex; + Bitmap_cubical_complex b(sizes, data); + + // Compute the persistence diagram of the complex + typedef Gudhi::persistent_cohomology::Field_Zp Field_Zp; + typedef Gudhi::persistent_cohomology::Persistent_cohomology<Bitmap_cubical_complex, Field_Zp> Persistent_cohomology; + Persistent_cohomology pcoh(b); + pcoh.init_coefficients(p); // initializes the coefficient field for homology + pcoh.compute_persistent_cohomology(min_persistence); + + std::stringstream ss; + ss << "randomComplex_persistence"; + std::ofstream out(ss.str().c_str()); + pcoh.output_diagram(out); + out.close(); + + return 0; +} + diff --git a/example/Contraction/CMakeLists.txt b/example/Contraction/CMakeLists.txt new file mode 100644 index 00000000..4c09a0a7 --- /dev/null +++ b/example/Contraction/CMakeLists.txt @@ -0,0 +1,15 @@ +cmake_minimum_required(VERSION 2.6) +project(Contraction_examples) + + +add_executable(RipsContraction Rips_contraction.cpp) +add_executable(GarlandHeckbert Garland_heckbert.cpp) + +target_link_libraries(RipsContraction ${Boost_TIMER_LIBRARY} ${Boost_SYSTEM_LIBRARY}) +target_link_libraries(GarlandHeckbert ${Boost_TIMER_LIBRARY} ${Boost_SYSTEM_LIBRARY}) + + +add_test(RipsContraction.tore3D.0.2 ${CMAKE_CURRENT_BINARY_DIR}/RipsContraction ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.off 0.2) +# TODO(DS) : These tests are too long under Windows +#add_test(RipsContraction.sphere.0.2 ${CMAKE_CURRENT_BINARY_DIR}/RipsContraction ${CMAKE_SOURCE_DIR}/data/points/sphere3D_2646.off 0.2) +#add_test(RipsContraction.S0310000 ${CMAKE_CURRENT_BINARY_DIR}/RipsContraction ${CMAKE_SOURCE_DIR}/data/points/SO3_10000.off 0.3) diff --git a/example/Contraction/Garland_heckbert.cpp b/example/Contraction/Garland_heckbert.cpp new file mode 100644 index 00000000..cbc46e91 --- /dev/null +++ b/example/Contraction/Garland_heckbert.cpp @@ -0,0 +1,199 @@ +/* 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): David Salinas + * + * 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 GARLAND_HECKBERT_H_ +#define GARLAND_HECKBERT_H_ + +#include <gudhi/Point.h> +#include <gudhi/Edge_contraction.h> +#include <gudhi/Skeleton_blocker.h> +#include <gudhi/Off_reader.h> + +#include <boost/timer/timer.hpp> +#include <iostream> + +#include "Garland_heckbert/Error_quadric.h" + +using namespace std; +using namespace Gudhi; +using namespace skeleton_blocker; +using namespace contraction; + +struct Geometry_trait { + typedef Point_d Point; +}; + +/** + * The vertex stored in the complex contains a quadric. + */ +struct Garland_heckbert_traits : public Skeleton_blocker_simple_geometric_traits<Geometry_trait> { + public: + struct Garland_heckbert_vertex : public Simple_geometric_vertex { + Error_quadric<Geometry_trait::Point> quadric; + }; + typedef Garland_heckbert_vertex Graph_vertex; +}; + +typedef Skeleton_blocker_geometric_complex< Garland_heckbert_traits > Complex; +typedef Edge_profile<Complex> EdgeProfile; +typedef Skeleton_blocker_contractor<Complex> Complex_contractor; + +/** + * How the new vertex is placed after an edge collapse : here it is placed at + * the point minimizing the cost of the quadric. + */ +class GH_placement : public Gudhi::contraction::Placement_policy<EdgeProfile> { + Complex& complex_; + + public: + typedef Gudhi::contraction::Placement_policy<EdgeProfile>::Placement_type Placement_type; + + GH_placement(Complex& complex) : complex_(complex) { } + + Placement_type operator()(const EdgeProfile& profile) const override { + auto sum_quad(profile.v0().quadric); + sum_quad += profile.v1().quadric; + + boost::optional<Point> min_quadric_pt(sum_quad.min_cost()); + if (min_quadric_pt) + return Placement_type(*min_quadric_pt); + else + return profile.p0(); + } +}; + +/** + * How much cost an edge collapse : here the costs is given by a quadric + * which expresses a squared distances with triangles planes. + */ +class GH_cost : public Gudhi::contraction::Cost_policy<EdgeProfile> { + Complex& complex_; + + public: + typedef Gudhi::contraction::Cost_policy<EdgeProfile>::Cost_type Cost_type; + + GH_cost(Complex& complex) : complex_(complex) { } + + Cost_type operator()(EdgeProfile const& profile, boost::optional<Point> const& new_point) const override { + Cost_type res; + if (new_point) { + auto sum_quad(profile.v0().quadric); + sum_quad += profile.v1().quadric; + res = sum_quad.cost(*new_point); + } + return res; + } +}; + +/** + * Visitor that is called at several moment. + * Here we initializes the quadrics of every vertex at the on_started call back + * and we update them when contracting an edge (the quadric become the sum of both quadrics). + */ +class GH_visitor : public Gudhi::contraction::Contraction_visitor<EdgeProfile> { + Complex& complex_; + + public: + GH_visitor(Complex& complex) : complex_(complex) { } + + // Compute quadrics for every vertex v + // The quadric of v consists in the sum of quadric + // of every triangles passing through v weighted by its area + + void on_started(Complex & complex) override { + for (auto v : complex.vertex_range()) { + auto & quadric_v(complex[v].quadric); + for (auto t : complex.triangle_range(v)) { + auto t_it = t.begin(); + const auto& p0(complex.point(*t_it++)); + const auto& p1(complex.point(*t_it++)); + const auto& p2(complex.point(*t_it++)); + quadric_v += Error_quadric<Point>(p0, p1, p2); + } + } + } + + /** + * @brief Called when an edge is about to be contracted and replaced by a vertex whose position is *placement. + */ + void on_contracting(EdgeProfile const &profile, boost::optional< Point > placement) + override { + profile.v0().quadric += profile.v1().quadric; + } +}; + +int main(int argc, char *argv[]) { + if (argc != 4) { + std::cerr << "Usage " << argv[0] << + " input.off output.off N to load the file input.off, contract N edges and save the result to output.off.\n"; + return EXIT_FAILURE; + } + + Complex complex; + typedef Complex::Vertex_handle Vertex_handle; + + // load the points + Skeleton_blocker_off_reader<Complex> off_reader(argv[1], complex); + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file:" << argv[1] << std::endl; + return EXIT_FAILURE; + } + + if (!complex.empty() && !(complex.point(Vertex_handle(0)).dimension() == 3)) { + std::cerr << "Only points of dimension 3 are supported." << std::endl; + return EXIT_FAILURE; + } + + std::cout << "Load complex with " << complex.num_vertices() << " vertices" << std::endl; + + int num_contractions = atoi(argv[3]); + + boost::timer::auto_cpu_timer t; + + // constructs the contractor object with Garland Heckbert policies. + Complex_contractor contractor(complex, + new GH_cost(complex), + new GH_placement(complex), + contraction::make_link_valid_contraction<EdgeProfile>(), + new GH_visitor(complex)); + + std::cout << "Contract " << num_contractions << " edges" << std::endl; + contractor.contract_edges(num_contractions); + + std::cout << "Final complex has " << + complex.num_vertices() << " vertices, " << + complex.num_edges() << " edges and " << + complex.num_triangles() << " triangles." << std::endl; + + // write simplified complex + Skeleton_blocker_off_writer<Complex> off_writer(argv[2], complex); + + return EXIT_SUCCESS; +} + +#endif // GARLAND_HECKBERT_H_ + + + + diff --git a/example/Contraction/Garland_heckbert/Error_quadric.h b/example/Contraction/Garland_heckbert/Error_quadric.h new file mode 100644 index 00000000..076f1be0 --- /dev/null +++ b/example/Contraction/Garland_heckbert/Error_quadric.h @@ -0,0 +1,182 @@ +/* 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): David Salinas + * + * 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 ERROR_QUADRIC_H_ +#define ERROR_QUADRIC_H_ + +#include <boost/optional/optional.hpp> + +#include <vector> +#include <utility> + +template <typename Point> class Error_quadric { + private: + double coeff[10]; + + public: + Error_quadric() { + clear(); + } + + /** + * Quadric corresponding to the L2 distance to the plane. + * + * According to the notation of Garland Heckbert, they + * denote a quadric symetric matrix as : + * Q = [ q11 q12 q13 q14] + * [ q12 q22 q23 q24] + * [ q13 q23 q33 q34] + * [ q14 q24 q34 q44] + * + * which is represented by a vector with 10 elts that + * are denoted ci for clarity with : + * Q = [ c0 c1 c2 c3 ] + * [ c1 c4 c5 c6 ] + * [ c2 c5 c7 c8 ] + * [ c3 c6 c8 c9 ] + * + * The constructor return the quadrics that represents + * the squared distance to the plane defined by triangle p0,p1,p2 + * times the area of triangle p0,p1,p2. + */ + Error_quadric(const Point & p0, const Point & p1, const Point & p2) { + Point normal(unit_normal(p0, p1, p2)); + double a = normal[0]; + double b = normal[1]; + double c = normal[2]; + double d = -a * p0[0] - b * p0[1] - c * p0[2]; + coeff[0] = a*a; + coeff[1] = a*b; + coeff[2] = a*c; + coeff[3] = a*d; + coeff[4] = b*b; + coeff[5] = b*c; + coeff[6] = b*d; + coeff[7] = c*c; + coeff[8] = c*d; + coeff[9] = d*d; + + double area_p0p1p2 = std::sqrt(squared_area(p0, p1, p2)); + for (auto& x : coeff) + x *= area_p0p1p2; + } + + inline double squared_area(const Point& p0, const Point& p1, const Point& p2) { + // if (x1,x2,x3) = p1-p0 and (y1,y2,y3) = p2-p0 + // then the squared area is = (u^2+v^2+w^2)/4 + // with: u = x2 * y3 - x3 * y2; + // v = x3 * y1 - x1 * y3; + // w = x1 * y2 - x2 * y1; + Point p0p1(p1 - p0); + Point p0p2(p2 - p0); + double A = p0p1[1] * p0p2[2] - p0p1[2] * p0p2[1]; + double B = p0p1[2] * p0p2[0] - p0p1[0] * p0p2[2]; + double C = p0p1[0] * p0p2[1] - p0p1[1] * p0p2[0]; + return 1. / 4. * (A * A + B * B + C * C); + } + + void clear() { + for (auto& x : coeff) + x = 0; + } + + Error_quadric& operator+=(const Error_quadric& other) { + if (this != &other) { + for (int i = 0; i < 10; ++i) + coeff[i] += other.coeff[i]; + } + return *this; + } + + /** + * @return The quadric quost defined by the scalar product v^T Q v where Q is the quadratic form of Garland/Heckbert + */ + inline double cost(const Point& point) const { + double cost = + coeff[0] * point.x() * point.x() + coeff[4] * point.y() * point.y() + coeff[7] * point.z() * point.z() + + 2 * (coeff[1] * point.x() * point.y() + coeff[5] * point.y() * point.z() + coeff[2] * point.z() * point.x()) + + 2 * (coeff[3] * point.x() + coeff[6] * point.y() + coeff[8] * point.z()) + + coeff[9]; + if (cost < 0) { + return 0; + } else { + return cost; + } + } + + inline double grad_determinant() const { + return + coeff[0] * coeff[4] * coeff[7] + - coeff[0] * coeff[5] * coeff[5] + - coeff[1] * coeff[1] * coeff[7] + + 2 * coeff[1] * coeff[5] * coeff[2] + - coeff[4] * coeff[2] * coeff[2]; + } + + /** + * Return the point such that it minimizes the gradient of the quadric. + * Det must be passed with the determinant value of the gradient (should be non zero). + */ + inline Point solve_linear_gradient(double det) const { + return Point({ + (-coeff[1] * coeff[5] * coeff[8] + coeff[1] * coeff[7] * coeff[6] + coeff[2] * coeff[8] * coeff[4] - + coeff[2] * coeff[5] * coeff[6] - coeff[3] * coeff[4] * coeff[7] + coeff[3] * coeff[5] * coeff[5]) + / det, + (coeff[0] * coeff[5] * coeff[8] - coeff[0] * coeff[7] * coeff[6] - coeff[5] * coeff[2] * coeff[3] - + coeff[1] * coeff[2] * coeff[8] + coeff[6] * coeff[2] * coeff[2] + coeff[1] * coeff[3] * coeff[7]) + / det, + (-coeff[8] * coeff[0] * coeff[4] + coeff[8] * coeff[1] * coeff[1] + coeff[2] * coeff[3] * coeff[4] + + coeff[5] * coeff[0] * coeff[6] - coeff[5] * coeff[1] * coeff[3] - coeff[1] * coeff[2] * coeff[6]) + / det + }); + } + + /** + * returns the point that minimizes the quadric. + * It inverses the quadric if its determinant is higher that a given threshold . + * If the determinant is lower than this value the returned value is uninitialized. + */ + boost::optional<Point> min_cost(double scale = 1) const { + // const double min_determinant = 1e-4 * scale*scale; + const double min_determinant = 1e-5; + boost::optional<Point> pt_res; + double det = grad_determinant(); + if (std::abs(det) > min_determinant) + pt_res = solve_linear_gradient(det); + return pt_res; + } + + friend std::ostream& operator<<(std::ostream& stream, const Error_quadric& quadric) { + stream << "\n[ " << quadric.coeff[0] << "," << quadric.coeff[1] << "," << quadric.coeff[2] << "," << + quadric.coeff[3] << ";\n"; + stream << " " << quadric.coeff[1] << "," << quadric.coeff[4] << "," << quadric.coeff[5] << "," << + quadric.coeff[6] << ";\n"; + stream << " " << quadric.coeff[2] << "," << quadric.coeff[5] << "," << quadric.coeff[7] << "," << + quadric.coeff[8] << ";\n"; + stream << " " << quadric.coeff[3] << "," << quadric.coeff[6] << "," << quadric.coeff[8] << "," << + quadric.coeff[9] << "]"; + return stream; + } +}; + +#endif // ERROR_QUADRIC_H_ diff --git a/example/Contraction/Rips_contraction.cpp b/example/Contraction/Rips_contraction.cpp new file mode 100644 index 00000000..978dd1cb --- /dev/null +++ b/example/Contraction/Rips_contraction.cpp @@ -0,0 +1,104 @@ +/* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 <gudhi/Edge_contraction.h> +#include <gudhi/Skeleton_blocker.h> +#include <gudhi/Off_reader.h> +#include <gudhi/Point.h> + +#include <boost/timer/timer.hpp> +#include <iostream> + +using namespace std; +using namespace Gudhi; +using namespace skeleton_blocker; +using namespace contraction; + +struct Geometry_trait { + typedef Point_d Point; +}; + +typedef Geometry_trait::Point Point; +typedef Skeleton_blocker_simple_geometric_traits<Geometry_trait> Complex_geometric_traits; +typedef Skeleton_blocker_geometric_complex< Complex_geometric_traits > Complex; +typedef Edge_profile<Complex> Profile; +typedef Skeleton_blocker_contractor<Complex> Complex_contractor; + +template<typename ComplexType> +void build_rips(ComplexType& complex, double offset) { + if (offset <= 0) return; + auto vertices = complex.vertex_range(); + for (auto p = vertices.begin(); p != vertices.end(); ++p) + for (auto q = p; ++q != vertices.end(); /**/) { + if (squared_dist(complex.point(*p), complex.point(*q)) < 4 * offset * offset) + complex.add_edge_without_blockers(*p, *q); + } +} + +int main(int argc, char *argv[]) { + if (argc != 3) { + std::cerr << "Usage " << argv[0] << " ../../../data/meshes/SO3_10000.off 0.3 to load the file " << + "../../data/SO3_10000.off and contract the Rips complex built with paremeter 0.3.\n"; + return -1; + } + + Complex complex; + + // load only the points + Skeleton_blocker_off_reader<Complex> off_reader(argv[1], complex, true); + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file:" << argv[1] << std::endl; + return EXIT_FAILURE; + } + + std::cout << "Build the Rips complex with " << complex.num_vertices() << " vertices" << std::endl; + + build_rips(complex, atof(argv[2])); + + boost::timer::auto_cpu_timer t; + + std::cout << "Initial complex has " << + complex.num_vertices() << " vertices and " << + complex.num_edges() << " edges" << std::endl; + + Complex_contractor contractor(complex, + new Edge_length_cost<Profile>, + contraction::make_first_vertex_placement<Profile>(), + contraction::make_link_valid_contraction<Profile>(), + contraction::make_remove_popable_blockers_visitor<Profile>()); + contractor.contract_edges(); + + std::cout << "Counting final number of simplices \n"; + unsigned num_simplices = std::distance(complex.complex_simplex_range().begin(), complex.complex_simplex_range().end()); + + std::cout << "Final complex has " << + complex.num_vertices() << " vertices, " << + complex.num_edges() << " edges, " << + complex.num_blockers() << " blockers and " << + num_simplices << " simplices" << std::endl; + + + std::cout << "Time to simplify and enumerate simplices:\n"; + + return EXIT_SUCCESS; +} + + diff --git a/example/Persistent_cohomology/CMakeLists.txt b/example/Persistent_cohomology/CMakeLists.txt new file mode 100644 index 00000000..d97d1b63 --- /dev/null +++ b/example/Persistent_cohomology/CMakeLists.txt @@ -0,0 +1,84 @@ +cmake_minimum_required(VERSION 2.6) +project(Persistent_cohomology_examples) + +# problem with Visual Studio link on Boost program_options +add_definitions( -DBOOST_ALL_NO_LIB ) +add_definitions( -DBOOST_ALL_DYN_LINK ) + +add_executable(plain_homology plain_homology.cpp) +target_link_libraries(plain_homology ${Boost_SYSTEM_LIBRARY}) + +add_executable(persistence_from_simple_simplex_tree persistence_from_simple_simplex_tree.cpp) +target_link_libraries(persistence_from_simple_simplex_tree ${Boost_SYSTEM_LIBRARY}) + +add_executable(rips_persistence rips_persistence.cpp) +target_link_libraries(rips_persistence ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) + +add_executable(rips_persistence_via_boundary_matrix rips_persistence_via_boundary_matrix.cpp) +target_link_libraries(rips_persistence_via_boundary_matrix ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) + +add_executable(persistence_from_file persistence_from_file.cpp) +target_link_libraries(persistence_from_file ${Boost_SYSTEM_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) + +if (TBB_FOUND) + target_link_libraries(plain_homology ${TBB_LIBRARIES}) + target_link_libraries(persistence_from_simple_simplex_tree ${TBB_LIBRARIES}) + target_link_libraries(rips_persistence ${TBB_LIBRARIES}) + target_link_libraries(rips_persistence_via_boundary_matrix ${TBB_LIBRARIES}) + target_link_libraries(persistence_from_file ${TBB_LIBRARIES}) +endif() + +add_test(plain_homology ${CMAKE_CURRENT_BINARY_DIR}/plain_homology) +add_test(persistence_from_simple_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_simple_simplex_tree 1 0) +add_test(rips_persistence_3 ${CMAKE_CURRENT_BINARY_DIR}/rips_persistence ${CMAKE_SOURCE_DIR}/data/points/Kl.txt -r 0.2 -d 3 -p 3 -m 100) +add_test(rips_persistence_via_boundary_matrix_3 ${CMAKE_CURRENT_BINARY_DIR}/rips_persistence_via_boundary_matrix ${CMAKE_SOURCE_DIR}/data/points/tore3D_1307.txt -r 0.3 -d 3 -p 3 -m 100) +add_test(persistence_from_file_3_2_0 ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.st -p 2 -m 0) +add_test(persistence_from_file_3_3_100 ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_file ${CMAKE_SOURCE_DIR}/data/points/bunny_5000.st -p 3 -m 100) + +if(GMP_FOUND) + if(GMPXX_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) + + add_test(rips_multifield_persistence_2_71 ${CMAKE_CURRENT_BINARY_DIR}/rips_multifield_persistence ${CMAKE_SOURCE_DIR}/data/points/Kl.txt -r 0.2 -d 3 -p 2 -q 71 -m 100) + endif(GMPXX_FOUND) +endif(GMP_FOUND) + +if(CGAL_FOUND) + add_executable(alpha_complex_3d_persistence alpha_complex_3d_persistence.cpp) + target_link_libraries(alpha_complex_3d_persistence ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + + if (TBB_FOUND) + target_link_libraries(alpha_complex_3d_persistence ${TBB_LIBRARIES}) + endif(TBB_FOUND) + add_test(alpha_complex_3d_persistence_2_0_5 ${CMAKE_CURRENT_BINARY_DIR}/alpha_complex_3d_persistence ${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off 2 0.45) + + + if (NOT CGAL_VERSION VERSION_LESS 4.7.0) + if (EIGEN3_FOUND) + add_executable (alpha_complex_persistence alpha_complex_persistence.cpp) + target_link_libraries(alpha_complex_persistence ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY} ${Boost_PROGRAM_OPTIONS_LIBRARY}) + + add_executable(periodic_alpha_complex_3d_persistence periodic_alpha_complex_3d_persistence.cpp) + target_link_libraries(periodic_alpha_complex_3d_persistence ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + + add_executable(custom_persistence_sort custom_persistence_sort.cpp) + target_link_libraries(custom_persistence_sort ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + + if (TBB_FOUND) + target_link_libraries(alpha_complex_persistence ${TBB_LIBRARIES}) + target_link_libraries(periodic_alpha_complex_3d_persistence ${TBB_LIBRARIES}) + target_link_libraries(custom_persistence_sort ${TBB_LIBRARIES}) + endif(TBB_FOUND) + add_test(alpha_complex_persistence_2_0_45 ${CMAKE_CURRENT_BINARY_DIR}/alpha_complex_persistence ${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off -m 0.45 -p 2) + add_test(periodic_alpha_complex_3d_persistence_2_0 ${CMAKE_CURRENT_BINARY_DIR}/periodic_alpha_complex_3d_persistence ${CMAKE_SOURCE_DIR}/data/points/grid_10_10_10_in_0_1.off ${CMAKE_SOURCE_DIR}/data/points/iso_cuboid_3_in_0_1.txt 2 0) + add_test(custom_persistence_sort ${CMAKE_CURRENT_BINARY_DIR}/custom_persistence_sort) + endif(EIGEN3_FOUND) + endif (NOT CGAL_VERSION VERSION_LESS 4.7.0) +endif(CGAL_FOUND) diff --git a/example/Persistent_cohomology/README b/example/Persistent_cohomology/README new file mode 100644 index 00000000..7803e5ab --- /dev/null +++ b/example/Persistent_cohomology/README @@ -0,0 +1,152 @@ +To build the example, run in a Terminal: + +cd /path-to-example/ +cmake . +make + +*********************************************************************************************************************** +Example of use of RIPS: + +Computation of the persistent homology with Z/2Z coefficients of the Rips complex on points +sampling a Klein bottle: + +./rips_persistence ../../data/points/Kl.txt -r 0.25 -d 3 -p 2 -m 100 + +output: +210 0 0 inf +210 1 0.0702103 inf +2 1 0.0702103 inf +2 2 0.159992 inf + + +Every line is of this format: p1*...*pr dim b d +where + p1*...*pr is the product of prime numbers pi such that the homology feature exists in homology with Z/piZ coefficients. + dim is the dimension of the homological feature, + b and d are respectively the birth and death of the feature and + + + +with Z/3Z coefficients: + +./rips_persistence ../../data/points/Kl.txt -r 0.25 -d 3 -p 3 -m 100 + +output: +3 0 0 inf +3 1 0.0702103 inf + +and the computation with Z/2Z and Z/3Z coefficients simultaneously: + +./rips_multifield_persistence ../../data/points/Kl.txt -r 0.25 -d 3 -p 2 -q 3 -m 100 + +output: +6 0 0 inf +6 1 0.0702103 inf +2 1 0.0702103 inf +2 2 0.159992 inf + +and finally the computation with all Z/pZ for 2 <= p <= 71 (20 first prime numbers): + + ./rips_multifield_persistence ../../data/points/Kl.txt -r 0.25 -d 3 -p 2 -q 71 -m 100 + +output: +557940830126698960967415390 0 0 inf +557940830126698960967415390 1 0.0702103 inf +2 1 0.0702103 inf +2 2 0.159992 inf + +*********************************************************************************************************************** +Example of use of ALPHA: + +For a more verbose mode, please run cmake with option "DEBUG_TRACES=TRUE" and recompile the programs. + +1) 3D special case +------------------ +Computation of the persistent homology with Z/2Z coefficients of the alpha complex on points +sampling a torus 3D: + +./alpha_complex_3d_persistence ../../data/points/tore3D_300.off 2 0.45 + +output: +Simplex_tree dim: 3 +2 0 0 inf +2 1 0.0682162 1.0001 +2 1 0.0934117 1.00003 +2 2 0.56444 1.03938 + +Here we retrieve expected Betti numbers on a tore 3D: +Betti numbers[0] = 1 +Betti numbers[1] = 2 +Betti numbers[2] = 1 + +N.B.: - alpha_complex_3d_persistence accepts only OFF files in 3D dimension. + - filtration values are alpha square values + +2) d-Dimension case +------------------- +Computation of the persistent homology with Z/2Z coefficients of the alpha complex on points +sampling a torus 3D: + +./alpha_complex_persistence -r 32 -p 2 -m 0.45 ../../data/points/tore3D_300.off + +output: +Alpha complex is of dimension 3 - 9273 simplices - 300 vertices. +Simplex_tree dim: 3 +2 0 0 inf +2 1 0.0682162 1.0001 +2 1 0.0934117 1.00003 +2 2 0.56444 1.03938 + +Here we retrieve expected Betti numbers on a tore 3D: +Betti numbers[0] = 1 +Betti numbers[1] = 2 +Betti numbers[2] = 1 + +N.B.: - alpha_complex_persistence accepts OFF files in d-Dimension. + - filtration values are alpha square values + +3) 3D periodic special case +--------------------------- +./periodic_alpha_complex_3d_persistence ../../data/points/grid_10_10_10_in_0_1.off 3 1.0 + +output: +Periodic Delaunay computed. +Simplex_tree dim: 3 +3 0 0 inf +3 1 0.0025 inf +3 1 0.0025 inf +3 1 0.0025 inf +3 2 0.005 inf +3 2 0.005 inf +3 2 0.005 inf +3 3 0.0075 inf + +Here we retrieve expected Betti numbers on a tore 3D: +Betti numbers[0] = 1 +Betti numbers[1] = 3 +Betti numbers[2] = 3 +Betti numbers[3] = 1 + +N.B.: - periodic_alpha_complex_3d_persistence accepts only OFF files in 3D dimension. In this example, the periodic cube +is hard coded to { x = [0,1]; y = [0,1]; z = [0,1] } + - filtration values are alpha square values + +*********************************************************************************************************************** +Example of use of PLAIN HOMOLOGY: + +This example computes the plain homology of the following simplicial complex without filtration values: + /* Complex to build. */ + /* 1 3 */ + /* o---o */ + /* /X\ / */ + /* o---o o */ + /* 2 0 4 */ + +./plain_homology + +output: +2 0 0 inf +2 0 0 inf +2 1 0 inf + +Here we retrieve the 2 entities {0,1,2,3} and {4} (Betti numbers[0] = 2) and the hole in {0,1,3} (Betti numbers[1] = 1) diff --git a/example/Persistent_cohomology/alpha_complex_3d_persistence.cpp b/example/Persistent_cohomology/alpha_complex_3d_persistence.cpp new file mode 100644 index 00000000..48fbb91a --- /dev/null +++ b/example/Persistent_cohomology/alpha_complex_3d_persistence.cpp @@ -0,0 +1,285 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2014 INRIA Saclay (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 <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> +#include <gudhi/Points_3D_off_io.h> +#include <boost/variant.hpp> + +#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> +#include <CGAL/Delaunay_triangulation_3.h> +#include <CGAL/Alpha_shape_3.h> +#include <CGAL/iterator.h> + +#include <fstream> +#include <cmath> +#include <string> +#include <tuple> +#include <map> +#include <utility> +#include <list> +#include <vector> + +// Alpha_shape_3 templates type definitions +typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel; +typedef CGAL::Alpha_shape_vertex_base_3<Kernel> Vb; +typedef CGAL::Alpha_shape_cell_base_3<Kernel> Fb; +typedef CGAL::Triangulation_data_structure_3<Vb, Fb> Tds; +typedef CGAL::Delaunay_triangulation_3<Kernel, Tds> Triangulation_3; +typedef CGAL::Alpha_shape_3<Triangulation_3> Alpha_shape_3; + +// From file type definition +typedef Kernel::Point_3 Point_3; + +// filtration with alpha values needed type definition +typedef Alpha_shape_3::FT Alpha_value_type; +typedef CGAL::Object Object; +typedef CGAL::Dispatch_output_iterator< +CGAL::cpp11::tuple<Object, Alpha_value_type>, +CGAL::cpp11::tuple<std::back_insert_iterator< std::vector<Object> >, + std::back_insert_iterator< std::vector<Alpha_value_type> > > > Dispatch; +typedef Alpha_shape_3::Cell_handle Cell_handle; +typedef Alpha_shape_3::Facet Facet; +typedef Alpha_shape_3::Edge Edge_3; +typedef std::list<Alpha_shape_3::Vertex_handle> Vertex_list; + +// gudhi type definition +typedef Gudhi::Simplex_tree<Gudhi::Simplex_tree_options_fast_persistence> ST; +typedef ST::Vertex_handle Simplex_tree_vertex; +typedef std::map<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex > Alpha_shape_simplex_tree_map; +typedef std::pair<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex> Alpha_shape_simplex_tree_pair; +typedef std::vector< Simplex_tree_vertex > Simplex_tree_vector_vertex; +typedef Gudhi::persistent_cohomology::Persistent_cohomology< ST, Gudhi::persistent_cohomology::Field_Zp > PCOH; + +Vertex_list from(const Cell_handle& ch) { + Vertex_list the_list; + for (auto i = 0; i < 4; i++) { +#ifdef DEBUG_TRACES + std::cout << "from cell[" << i << "]=" << ch->vertex(i)->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(ch->vertex(i)); + } + return the_list; +} + +Vertex_list from(const Facet& fct) { + Vertex_list the_list; + for (auto i = 0; i < 4; i++) { + if (fct.second != i) { +#ifdef DEBUG_TRACES + std::cout << "from facet=[" << i << "]" << fct.first->vertex(i)->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(fct.first->vertex(i)); + } + } + return the_list; +} + +Vertex_list from(const Edge_3& edg) { + Vertex_list the_list; + for (auto i = 0; i < 4; i++) { + if ((edg.second == i) || (edg.third == i)) { +#ifdef DEBUG_TRACES + std::cout << "from edge[" << i << "]=" << edg.first->vertex(i)->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(edg.first->vertex(i)); + } + } + return the_list; +} + +Vertex_list from(const Alpha_shape_3::Vertex_handle& vh) { + Vertex_list the_list; +#ifdef DEBUG_TRACES + std::cout << "from vertex=" << vh->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(vh); + return the_list; +} + +void usage(char * const progName) { + std::cerr << "Usage: " << progName << + " path_to_file_graph coeff_field_characteristic[integer > 0] min_persistence[float >= -1.0]\n"; + exit(-1); +} + +int main(int argc, char * const argv[]) { + // program args management + if (argc != 4) { + std::cerr << "Error: Number of arguments (" << argc << ") is not correct\n"; + usage(argv[0]); + } + + int coeff_field_characteristic = atoi(argv[2]); + + Filtration_value min_persistence = 0.0; + int returnedScanValue = sscanf(argv[3], "%lf", &min_persistence); + if ((returnedScanValue == EOF) || (min_persistence < -1.0)) { + std::cerr << "Error: " << argv[3] << " is not correct\n"; + usage(argv[0]); + } + + // Read points from file + std::string offInputFile(argv[1]); + // Read the OFF file (input file name given as parameter) and triangulate points + Gudhi::Points_3D_off_reader<Point_3> off_reader(offInputFile); + // Check the read operation was correct + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << offInputFile << std::endl; + usage(argv[0]); + } + + // Retrieve the triangulation + std::vector<Point_3> lp = off_reader.get_point_cloud(); + + // alpha shape construction from points. CGAL has a strange behavior in REGULARIZED mode. + Alpha_shape_3 as(lp.begin(), lp.end(), 0, Alpha_shape_3::GENERAL); +#ifdef DEBUG_TRACES + std::cout << "Alpha shape computed in GENERAL mode" << std::endl; +#endif // DEBUG_TRACES + + // filtration with alpha values from alpha shape + std::vector<Object> the_objects; + std::vector<Alpha_value_type> the_alpha_values; + + Dispatch disp = CGAL::dispatch_output<Object, Alpha_value_type>(std::back_inserter(the_objects), + std::back_inserter(the_alpha_values)); + + as.filtration_with_alpha_values(disp); +#ifdef DEBUG_TRACES + std::cout << "filtration_with_alpha_values returns : " << the_objects.size() << " objects" << std::endl; +#endif // DEBUG_TRACES + + Alpha_shape_3::size_type count_vertices = 0; + Alpha_shape_3::size_type count_edges = 0; + Alpha_shape_3::size_type count_facets = 0; + Alpha_shape_3::size_type count_cells = 0; + + // Loop on objects vector + Vertex_list vertex_list; + ST simplex_tree; + Alpha_shape_simplex_tree_map map_cgal_simplex_tree; + std::vector<Alpha_value_type>::iterator the_alpha_value_iterator = the_alpha_values.begin(); + int dim_max = 0; + Filtration_value filtration_max = 0.0; + for (auto object_iterator : the_objects) { + // Retrieve Alpha shape vertex list from object + if (const Cell_handle * cell = CGAL::object_cast<Cell_handle>(&object_iterator)) { + vertex_list = from(*cell); + count_cells++; + if (dim_max < 3) { + // Cell is of dim 3 + dim_max = 3; + } + } else if (const Facet * facet = CGAL::object_cast<Facet>(&object_iterator)) { + vertex_list = from(*facet); + count_facets++; + if (dim_max < 2) { + // Facet is of dim 2 + dim_max = 2; + } + } else if (const Edge_3 * edge = CGAL::object_cast<Edge_3>(&object_iterator)) { + vertex_list = from(*edge); + count_edges++; + if (dim_max < 1) { + // Edge_3 is of dim 1 + dim_max = 1; + } + } else if (const Alpha_shape_3::Vertex_handle * vertex = + CGAL::object_cast<Alpha_shape_3::Vertex_handle>(&object_iterator)) { + count_vertices++; + vertex_list = from(*vertex); + } + // Construction of the vector of simplex_tree vertex from list of alpha_shapes vertex + Simplex_tree_vector_vertex the_simplex_tree; + for (auto the_alpha_shape_vertex : vertex_list) { + Alpha_shape_simplex_tree_map::iterator the_map_iterator = map_cgal_simplex_tree.find(the_alpha_shape_vertex); + if (the_map_iterator == map_cgal_simplex_tree.end()) { + // alpha shape not found + Simplex_tree_vertex vertex = map_cgal_simplex_tree.size(); +#ifdef DEBUG_TRACES + std::cout << "vertex [" << the_alpha_shape_vertex->point() << "] not found - insert " << vertex << std::endl; +#endif // DEBUG_TRACES + the_simplex_tree.push_back(vertex); + map_cgal_simplex_tree.insert(Alpha_shape_simplex_tree_pair(the_alpha_shape_vertex, vertex)); + } else { + // alpha shape found + Simplex_tree_vertex vertex = the_map_iterator->second; +#ifdef DEBUG_TRACES + std::cout << "vertex [" << the_alpha_shape_vertex->point() << "] found in " << vertex << std::endl; +#endif // DEBUG_TRACES + the_simplex_tree.push_back(vertex); + } + } + // Construction of the simplex_tree + Filtration_value filtr = /*std::sqrt*/(*the_alpha_value_iterator); +#ifdef DEBUG_TRACES + std::cout << "filtration = " << filtr << std::endl; +#endif // DEBUG_TRACES + if (filtr > filtration_max) { + filtration_max = filtr; + } + simplex_tree.insert_simplex(the_simplex_tree, filtr); + if (the_alpha_value_iterator != the_alpha_values.end()) + ++the_alpha_value_iterator; + else + std::cout << "This shall not happen" << std::endl; + } + simplex_tree.set_filtration(filtration_max); + simplex_tree.set_dimension(dim_max); + +#ifdef DEBUG_TRACES + std::cout << "vertices \t\t" << count_vertices << std::endl; + std::cout << "edges \t\t" << count_edges << std::endl; + std::cout << "facets \t\t" << count_facets << std::endl; + std::cout << "cells \t\t" << count_cells << std::endl; + + + std::cout << "Information of the Simplex Tree: " << std::endl; + std::cout << " Number of vertices = " << simplex_tree.num_vertices() << " "; + std::cout << " Number of simplices = " << simplex_tree.num_simplices() << std::endl << std::endl; + std::cout << " Dimension = " << simplex_tree.dimension() << " "; + std::cout << " filtration = " << simplex_tree.filtration() << std::endl << std::endl; +#endif // DEBUG_TRACES + +#ifdef DEBUG_TRACES + std::cout << "Iterator on vertices: " << std::endl; + for (auto vertex : simplex_tree.complex_vertex_range()) { + std::cout << vertex << " "; + } +#endif // DEBUG_TRACES + + // Sort the simplices in the order of the filtration + simplex_tree.initialize_filtration(); + + std::cout << "Simplex_tree dim: " << simplex_tree.dimension() << std::endl; + // Compute the persistence diagram of the complex + PCOH pcoh(simplex_tree); + // initializes the coefficient field for homology + pcoh.init_coefficients(coeff_field_characteristic); + + pcoh.compute_persistent_cohomology(min_persistence); + + pcoh.output_diagram(); + + return 0; +} diff --git a/example/Persistent_cohomology/alpha_complex_persistence.cpp b/example/Persistent_cohomology/alpha_complex_persistence.cpp new file mode 100644 index 00000000..cb181936 --- /dev/null +++ b/example/Persistent_cohomology/alpha_complex_persistence.cpp @@ -0,0 +1,117 @@ +#include <boost/program_options.hpp> + +#include <CGAL/Epick_d.h> + +#include <gudhi/Alpha_complex.h> +#include <gudhi/Persistent_cohomology.h> + +#include <iostream> +#include <string> +#include <limits> // for numeric_limits + +void program_options(int argc, char * argv[] + , std::string & off_file_points + , std::string & output_file_diag + , Filtration_value & alpha_square_max_value + , int & coeff_field_characteristic + , Filtration_value & min_persistence); + +int main(int argc, char **argv) { + std::string off_file_points; + std::string output_file_diag; + Filtration_value alpha_square_max_value; + int coeff_field_characteristic; + Filtration_value min_persistence; + + program_options(argc, argv, off_file_points, output_file_diag, alpha_square_max_value, + coeff_field_characteristic, min_persistence); + + // ---------------------------------------------------------------------------- + // Init of an alpha complex from an OFF file + // ---------------------------------------------------------------------------- + using Kernel = CGAL::Epick_d< CGAL::Dynamic_dimension_tag >; + Gudhi::alpha_complex::Alpha_complex<Kernel> alpha_complex_from_file(off_file_points, alpha_square_max_value); + + // ---------------------------------------------------------------------------- + // Display information about the alpha complex + // ---------------------------------------------------------------------------- + std::cout << "Alpha complex is of dimension " << alpha_complex_from_file.dimension() << + " - " << alpha_complex_from_file.num_simplices() << " simplices - " << + alpha_complex_from_file.num_vertices() << " vertices." << std::endl; + + // Sort the simplices in the order of the filtration + alpha_complex_from_file.initialize_filtration(); + + std::cout << "Simplex_tree dim: " << alpha_complex_from_file.dimension() << std::endl; + // Compute the persistence diagram of the complex + Gudhi::persistent_cohomology::Persistent_cohomology< Gudhi::alpha_complex::Alpha_complex<Kernel>, + Gudhi::persistent_cohomology::Field_Zp > pcoh(alpha_complex_from_file); + // initializes the coefficient field for homology + pcoh.init_coefficients(coeff_field_characteristic); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + if (output_file_diag.empty()) { + pcoh.output_diagram(); + } else { + std::cout << "Result in file: " << output_file_diag << std::endl; + std::ofstream out(output_file_diag); + pcoh.output_diagram(out); + out.close(); + } + + return 0; +} + +void program_options(int argc, char * argv[] + , std::string & off_file_points + , std::string & output_file_diag + , Filtration_value & alpha_square_max_value + , int & coeff_field_characteristic + , Filtration_value & min_persistence) { + namespace po = boost::program_options; + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value<std::string>(&off_file_points), + "Name of file containing a point set. Format is one point per line: X1 ... Xd "); + + po::options_description visible("Allowed options", 100); + visible.add_options() + ("help,h", "produce help message") + ("output-file,o", po::value<std::string>(&output_file_diag)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("max-alpha-square-value,r", + po::value<Filtration_value>(&alpha_square_max_value)->default_value(std::numeric_limits<Filtration_value>::infinity()), + "Maximal alpha square value for the Alpha complex construction.") + ("field-charac,p", po::value<int>(&coeff_field_characteristic)->default_value(11), + "Characteristic p of the coefficient field Z/pZ for computing homology.") + ("min-persistence,m", po::value<Filtration_value>(&min_persistence), + "Minimal lifetime of homology feature to be recorded. Default is 0. Enter a negative value to see zero length intervals"); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + + po::variables_map vm; + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with coefficient field Z/pZ \n"; + std::cout << "of an Alpha complex defined on a set of input points.\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p is the characteristic of the field Z/pZ used for homology coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} diff --git a/example/Persistent_cohomology/custom_persistence_sort.cpp b/example/Persistent_cohomology/custom_persistence_sort.cpp new file mode 100644 index 00000000..9af38611 --- /dev/null +++ b/example/Persistent_cohomology/custom_persistence_sort.cpp @@ -0,0 +1,116 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2014 INRIA Saclay (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 <CGAL/Epick_d.h> +#include <CGAL/point_generators_d.h> +#include <CGAL/algorithm.h> +#include <CGAL/assertions.h> + +#include <gudhi/Alpha_complex.h> +#include <gudhi/Persistent_cohomology.h> + +#include <iostream> +#include <iterator> +#include <vector> +#include <fstream> // for std::ofstream +#include <algorithm> // for std::sort + + +using Kernel = CGAL::Epick_d< CGAL::Dimension_tag<3> >; +using Point = Kernel::Point_d; +using Alpha_complex = Gudhi::alpha_complex::Alpha_complex<Kernel>; + +std::vector<Point> random_points() { + // Instanciate a random point generator + CGAL::Random rng(0); + + // Generate "points_number" random points in a vector + std::vector<Point> points; + + // Generates 1000 random 3D points on a sphere of radius 4.0 + CGAL::Random_points_on_sphere_d<Point> rand_outside(3, 4.0, rng); + CGAL::cpp11::copy_n(rand_outside, 1000, std::back_inserter(points)); + // Generates 2000 random 3D points in a sphere of radius 3.0 + CGAL::Random_points_in_ball_d<Point> rand_inside(3, 3.0, rng); + CGAL::cpp11::copy_n(rand_inside, 2000, std::back_inserter(points)); + + return points; +} + +/* + * Compare two intervals by dimension, then by length. + */ +struct cmp_intervals_by_dim_then_length { + explicit cmp_intervals_by_dim_then_length(Alpha_complex * sc) + : sc_(sc) { } + + template<typename Persistent_interval> + bool operator()(const Persistent_interval & p1, const Persistent_interval & p2) { + if (sc_->dimension(get < 0 > (p1)) == sc_->dimension(get < 0 > (p2))) + return (sc_->filtration(get < 1 > (p1)) - sc_->filtration(get < 0 > (p1)) + > sc_->filtration(get < 1 > (p2)) - sc_->filtration(get < 0 > (p2))); + else + return (sc_->dimension(get < 0 > (p1)) > sc_->dimension(get < 0 > (p2))); + } + Alpha_complex* sc_; +}; + +int main(int argc, char **argv) { + std::vector<Point> points = random_points(); + + // Alpha complex persistence computation from generated points + Alpha_complex alpha_complex_from_points(points, 0.6); + + using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology< Alpha_complex, + Gudhi::persistent_cohomology::Field_Zp >; + Persistent_cohomology pcoh(alpha_complex_from_points); + + // initializes the coefficient field for homology - Z/3Z + pcoh.init_coefficients(3); + pcoh.compute_persistent_cohomology(0.2); + + // Custom sort and output persistence + cmp_intervals_by_dim_then_length cmp(&alpha_complex_from_points); + auto persistent_pairs = pcoh.get_persistent_pairs(); + std::sort(std::begin(persistent_pairs), std::end(persistent_pairs), cmp); + for (auto pair : persistent_pairs) { + std::cout << alpha_complex_from_points.dimension(get<0>(pair)) << " " + << alpha_complex_from_points.filtration(get<0>(pair)) << " " + << alpha_complex_from_points.filtration(get<1>(pair)) << std::endl; + } + + // Persistent Betti numbers + std::cout << "The persistent Betti numbers in interval [0.40, 0.41] are : "; + for (int dim = 0; dim < alpha_complex_from_points.dimension(); dim++) + std::cout << "b" << dim << " = " << pcoh.persistent_betti_number(dim, 0.40, 0.41) << " ; "; + std::cout << std::endl; + + // Betti numbers + std::vector<int> betti_numbers = pcoh.betti_numbers(); + std::cout << "The Betti numbers are : "; + for (std::size_t i = 0; i < betti_numbers.size(); i++) + std::cout << "b" << i << " = " << betti_numbers[i] << " ; "; + std::cout << std::endl; + + return 0; +} + diff --git a/example/Persistent_cohomology/performance_rips_persistence.cpp b/example/Persistent_cohomology/performance_rips_persistence.cpp new file mode 100644 index 00000000..b4d282ac --- /dev/null +++ b/example/Persistent_cohomology/performance_rips_persistence.cpp @@ -0,0 +1,214 @@ +/* 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): Clément Maria + * + * 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/>. + */ + +#include <gudhi/reader_utils.h> +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/distance_functions.h> +#include <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> +#include <gudhi/Persistent_cohomology/Multi_field.h> +#include <gudhi/Hasse_complex.h> + +#include <chrono> +#include <string> +#include <vector> + +using namespace Gudhi; +using namespace Gudhi::persistent_cohomology; + +/* Compute the persistent homology of the complex cpx with coefficients in Z/pZ. */ +template< typename FilteredComplex> +void timing_persistence(FilteredComplex & cpx + , int p); + +/* Compute multi-field persistent homology of the complex cpx with coefficients in + * Z/rZ for all prime number r in [p;q].*/ +template< typename FilteredComplex> +void timing_persistence(FilteredComplex & cpx + , int p + , int q); + +/* Timings for the computation of persistent homology with different + * representations of a Rips complex and different coefficient fields. The + * Rips complex is built on a set of 10000 points sampling a Klein bottle embedded + * in dimension 5. + * We represent complexes with a simplex tree and + * with a Hasse diagram. The Hasse diagram represents explicitly all + * codimension 1 incidence relations in the complex, and hence leads to + * a faster computation of persistence because boundaries are precomputed. + * Hovewer, the simplex tree may be constructed directly from a point cloud and + * is more compact. + * We compute persistent homology with coefficient fields Z/2Z and Z/1223Z. + * We present also timings for the computation of multi-field persistent + * homology in all fields Z/rZ for r prime between 2 and 1223. + */ +int main(int argc, char * argv[]) { + std::chrono::time_point<std::chrono::system_clock> start, end; + int elapsed_sec; + { + + std::string filepoints = "../../../data/points/Kl.txt"; + Filtration_value threshold = 0.27; + int dim_max = 3; + int p = 2; + int q = 1223; + + // Extract the points from the file filepoints + typedef std::vector<double> Point_t; + std::vector< Point_t > points; + read_points(filepoints, points); + + // Compute the proximity graph of the points + start = std::chrono::system_clock::now(); + Graph_t prox_graph = compute_proximity_graph(points, threshold + , euclidean_distance<Point_t>); + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << "Compute Rips graph in " << elapsed_sec << " ms.\n"; + + // Construct the Rips complex in a Simplex Tree + Simplex_tree<Simplex_tree_options_fast_persistence> st; + start = std::chrono::system_clock::now(); + + // insert the proximity graph in the simplex tree + st.insert_graph(prox_graph); + // expand the graph until dimension dim_max + st.expansion(dim_max); + + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << "Compute Rips complex in " << elapsed_sec << " ms.\n"; + std::cout << " - dimension = " << st.dimension() << std::endl; + std::cout << " - number of simplices = " << st.num_simplices() << std::endl; + + // Sort the simplices in the order of the filtration + start = std::chrono::system_clock::now(); + st.initialize_filtration(); + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << "Order the simplices of the filtration in " << elapsed_sec << " ms.\n"; + + // Copy the keys inside the simplices + start = std::chrono::system_clock::now(); + { + int count = 0; + for (auto sh : st.filtration_simplex_range()) + st.assign_key(sh, count++); + } + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << "Copied the keys inside the simplices in " << elapsed_sec << " ms.\n"; + + // Convert the simplex tree into a hasse diagram + start = std::chrono::system_clock::now(); + Hasse_complex<> hcpx(st); + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << "Convert the simplex tree into a Hasse diagram in " << elapsed_sec << " ms.\n"; + + + std::cout << "Timings when using a simplex tree: \n"; + timing_persistence(st, p); + timing_persistence(st, q); + timing_persistence(st, p, q); + + std::cout << "Timings when using a Hasse complex: \n"; + timing_persistence(hcpx, p); + timing_persistence(hcpx, q); + timing_persistence(hcpx, p, q); + + start = std::chrono::system_clock::now(); + } + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << "Running the complex destructors in " << elapsed_sec << " ms.\n"; + return 0; +} + +template< typename FilteredComplex> +void +timing_persistence(FilteredComplex & cpx + , int p) { + std::chrono::time_point<std::chrono::system_clock> start, end; + int elapsed_sec; + { + start = std::chrono::system_clock::now(); + Persistent_cohomology< FilteredComplex, Field_Zp > pcoh(cpx); + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << " Initialize pcoh in " << elapsed_sec << " ms.\n"; + // initializes the coefficient field for homology + start = std::chrono::system_clock::now(); + pcoh.init_coefficients(p); + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << " Initialize the coefficient field in " << elapsed_sec << " ms.\n"; + + start = std::chrono::system_clock::now(); + + pcoh.compute_persistent_cohomology(INFINITY); + + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << " Compute persistent homology in Z/" << p << "Z in " << elapsed_sec << " ms.\n"; + start = std::chrono::system_clock::now(); + } + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << " Run the persistence destructors in " << elapsed_sec << " ms.\n"; +} + +template< typename FilteredComplex> +void +timing_persistence(FilteredComplex & cpx + , int p + , int q) { + std::chrono::time_point<std::chrono::system_clock> start, end; + int elapsed_sec; + { + start = std::chrono::system_clock::now(); + Persistent_cohomology< FilteredComplex, Multi_field > pcoh(cpx); + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << " Initialize pcoh in " << elapsed_sec << " ms.\n"; + // initializes the coefficient field for homology + start = std::chrono::system_clock::now(); + pcoh.init_coefficients(p, q); + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << " Initialize the coefficient field in " << elapsed_sec << " ms.\n"; + // compute persistent homology, disgarding persistent features of life shorter than min_persistence + + start = std::chrono::system_clock::now(); + + pcoh.compute_persistent_cohomology(INFINITY); + + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << " Compute multi-field persistent homology in all coefficient fields Z/pZ " + << "with p in [" << p << ";" << q << "] in " << elapsed_sec << " ms.\n"; + start = std::chrono::system_clock::now(); + } + end = std::chrono::system_clock::now(); + elapsed_sec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count(); + std::cout << " Run the persistence destructors in " << elapsed_sec << " ms.\n"; +} diff --git a/example/Persistent_cohomology/periodic_alpha_complex_3d_persistence.cpp b/example/Persistent_cohomology/periodic_alpha_complex_3d_persistence.cpp new file mode 100644 index 00000000..a199fea1 --- /dev/null +++ b/example/Persistent_cohomology/periodic_alpha_complex_3d_persistence.cpp @@ -0,0 +1,313 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2014 INRIA Saclay (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 <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> +#include <gudhi/Points_3D_off_io.h> +#include <boost/variant.hpp> + +#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> +#include <CGAL/Periodic_3_Delaunay_triangulation_traits_3.h> +#include <CGAL/Periodic_3_Delaunay_triangulation_3.h> +#include <CGAL/Alpha_shape_3.h> +#include <CGAL/iterator.h> + +#include <fstream> +#include <cmath> +#include <string> +#include <tuple> +#include <map> +#include <utility> +#include <list> +#include <vector> + +// Traits +using K = CGAL::Exact_predicates_inexact_constructions_kernel; +using PK = CGAL::Periodic_3_Delaunay_triangulation_traits_3<K>; +// Vertex type +using DsVb = CGAL::Periodic_3_triangulation_ds_vertex_base_3<>; +using Vb = CGAL::Triangulation_vertex_base_3<PK, DsVb>; +using AsVb = CGAL::Alpha_shape_vertex_base_3<PK, Vb>; +// Cell type +using DsCb = CGAL::Periodic_3_triangulation_ds_cell_base_3<>; +using Cb = CGAL::Triangulation_cell_base_3<PK, DsCb>; +using AsCb = CGAL::Alpha_shape_cell_base_3<PK, Cb>; +using Tds = CGAL::Triangulation_data_structure_3<AsVb, AsCb>; +using P3DT3 = CGAL::Periodic_3_Delaunay_triangulation_3<PK, Tds>; +using Alpha_shape_3 = CGAL::Alpha_shape_3<P3DT3>; +using Point_3 = PK::Point_3; + +// filtration with alpha values needed type definition +using Alpha_value_type = Alpha_shape_3::FT; +using Object = CGAL::Object; +using Dispatch = CGAL::Dispatch_output_iterator< + CGAL::cpp11::tuple<Object, Alpha_value_type>, + CGAL::cpp11::tuple<std::back_insert_iterator< std::vector<Object> >, + std::back_insert_iterator< std::vector<Alpha_value_type> > > >; +using Cell_handle = Alpha_shape_3::Cell_handle; +using Facet = Alpha_shape_3::Facet; +using Edge_3 = Alpha_shape_3::Edge; +using Vertex_list = std::list<Alpha_shape_3::Vertex_handle>; + +// gudhi type definition +using ST = Gudhi::Simplex_tree<Gudhi::Simplex_tree_options_fast_persistence>; +using Simplex_tree_vertex = ST::Vertex_handle; +using Alpha_shape_simplex_tree_map = std::map<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex >; +using Alpha_shape_simplex_tree_pair = std::pair<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex>; +using Simplex_tree_vector_vertex = std::vector< Simplex_tree_vertex >; +using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology< + ST, Gudhi::persistent_cohomology::Field_Zp >; + +Vertex_list from(const Cell_handle& ch) { + Vertex_list the_list; + for (auto i = 0; i < 4; i++) { +#ifdef DEBUG_TRACES + std::cout << "from cell[" << i << "]=" << ch->vertex(i)->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(ch->vertex(i)); + } + return the_list; +} + +Vertex_list from(const Facet& fct) { + Vertex_list the_list; + for (auto i = 0; i < 4; i++) { + if (fct.second != i) { +#ifdef DEBUG_TRACES + std::cout << "from facet=[" << i << "]" << fct.first->vertex(i)->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(fct.first->vertex(i)); + } + } + return the_list; +} + +Vertex_list from(const Edge_3& edg) { + Vertex_list the_list; + for (auto i = 0; i < 4; i++) { + if ((edg.second == i) || (edg.third == i)) { +#ifdef DEBUG_TRACES + std::cout << "from edge[" << i << "]=" << edg.first->vertex(i)->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(edg.first->vertex(i)); + } + } + return the_list; +} + +Vertex_list from(const Alpha_shape_3::Vertex_handle& vh) { + Vertex_list the_list; +#ifdef DEBUG_TRACES + std::cout << "from vertex=" << vh->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(vh); + return the_list; +} + +void usage(char * const progName) { + std::cerr << "Usage: " << progName << + " path_to_file_graph path_to_iso_cuboid_3_file coeff_field_characteristic[integer > 0] min_persistence[float >= -1.0]\n"; + exit(-1); +} + +int main(int argc, char * const argv[]) { + // program args management + if (argc != 5) { + std::cerr << "Error: Number of arguments (" << argc << ") is not correct\n"; + usage(argv[0]); + } + + int coeff_field_characteristic = 0; + int returnedScanValue = sscanf(argv[3], "%d", &coeff_field_characteristic); + if ((returnedScanValue == EOF) || (coeff_field_characteristic <= 0)) { + std::cerr << "Error: " << argv[3] << " is not correct\n"; + usage(argv[0]); + } + + Filtration_value min_persistence = 0.0; + returnedScanValue = sscanf(argv[4], "%lf", &min_persistence); + if ((returnedScanValue == EOF) || (min_persistence < -1.0)) { + std::cerr << "Error: " << argv[4] << " is not correct\n"; + usage(argv[0]); + } + + // Read points from file + std::string offInputFile(argv[1]); + // Read the OFF file (input file name given as parameter) and triangulate points + Gudhi::Points_3D_off_reader<Point_3> off_reader(offInputFile); + // Check the read operation was correct + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << offInputFile << std::endl; + usage(argv[0]); + } + + // Read iso_cuboid_3 information from file + std::ifstream iso_cuboid_str(argv[2]); + double x_min, y_min, z_min, x_max, y_max, z_max; + if (iso_cuboid_str.good()) { + iso_cuboid_str >> x_min >> y_min >> z_min >> x_max >> y_max >> z_max; + } else { + std::cerr << "Unable to read file " << argv[2] << std::endl; + usage(argv[0]); + } + + // Retrieve the triangulation + std::vector<Point_3> lp = off_reader.get_point_cloud(); + + // Define the periodic cube + P3DT3 pdt(PK::Iso_cuboid_3(x_min, y_min, z_min, x_max, y_max, z_max)); + // Heuristic for inserting large point sets (if pts is reasonably large) + pdt.insert(lp.begin(), lp.end(), true); + // As pdt won't be modified anymore switch to 1-sheeted cover if possible + if (pdt.is_triangulation_in_1_sheet()) pdt.convert_to_1_sheeted_covering(); + std::cout << "Periodic Delaunay computed." << std::endl; + + // alpha shape construction from points. CGAL has a strange behavior in REGULARIZED mode. This is the default mode + // Maybe need to set it to GENERAL mode + Alpha_shape_3 as(pdt, 0, Alpha_shape_3::GENERAL); + + // filtration with alpha values from alpha shape + std::vector<Object> the_objects; + std::vector<Alpha_value_type> the_alpha_values; + + Dispatch disp = CGAL::dispatch_output<Object, Alpha_value_type>(std::back_inserter(the_objects), + std::back_inserter(the_alpha_values)); + + as.filtration_with_alpha_values(disp); +#ifdef DEBUG_TRACES + std::cout << "filtration_with_alpha_values returns : " << the_objects.size() << " objects" << std::endl; +#endif // DEBUG_TRACES + + Alpha_shape_3::size_type count_vertices = 0; + Alpha_shape_3::size_type count_edges = 0; + Alpha_shape_3::size_type count_facets = 0; + Alpha_shape_3::size_type count_cells = 0; + + // Loop on objects vector + Vertex_list vertex_list; + ST simplex_tree; + Alpha_shape_simplex_tree_map map_cgal_simplex_tree; + std::vector<Alpha_value_type>::iterator the_alpha_value_iterator = the_alpha_values.begin(); + int dim_max = 0; + Filtration_value filtration_max = 0.0; + for (auto object_iterator : the_objects) { + // Retrieve Alpha shape vertex list from object + if (const Cell_handle * cell = CGAL::object_cast<Cell_handle>(&object_iterator)) { + vertex_list = from(*cell); + count_cells++; + if (dim_max < 3) { + // Cell is of dim 3 + dim_max = 3; + } + } else if (const Facet * facet = CGAL::object_cast<Facet>(&object_iterator)) { + vertex_list = from(*facet); + count_facets++; + if (dim_max < 2) { + // Facet is of dim 2 + dim_max = 2; + } + } else if (const Edge_3 * edge = CGAL::object_cast<Edge_3>(&object_iterator)) { + vertex_list = from(*edge); + count_edges++; + if (dim_max < 1) { + // Edge_3 is of dim 1 + dim_max = 1; + } + } else if (const Alpha_shape_3::Vertex_handle * vertex = + CGAL::object_cast<Alpha_shape_3::Vertex_handle>(&object_iterator)) { + count_vertices++; + vertex_list = from(*vertex); + } + // Construction of the vector of simplex_tree vertex from list of alpha_shapes vertex + Simplex_tree_vector_vertex the_simplex_tree; + for (auto the_alpha_shape_vertex : vertex_list) { + Alpha_shape_simplex_tree_map::iterator the_map_iterator = map_cgal_simplex_tree.find(the_alpha_shape_vertex); + if (the_map_iterator == map_cgal_simplex_tree.end()) { + // alpha shape not found + Simplex_tree_vertex vertex = map_cgal_simplex_tree.size(); +#ifdef DEBUG_TRACES + std::cout << "vertex [" << the_alpha_shape_vertex->point() << "] not found - insert " << vertex << std::endl; +#endif // DEBUG_TRACES + the_simplex_tree.push_back(vertex); + map_cgal_simplex_tree.insert(Alpha_shape_simplex_tree_pair(the_alpha_shape_vertex, vertex)); + } else { + // alpha shape found + Simplex_tree_vertex vertex = the_map_iterator->second; +#ifdef DEBUG_TRACES + std::cout << "vertex [" << the_alpha_shape_vertex->point() << "] found in " << vertex << std::endl; +#endif // DEBUG_TRACES + the_simplex_tree.push_back(vertex); + } + } + // Construction of the simplex_tree + Filtration_value filtr = /*std::sqrt*/(*the_alpha_value_iterator); +#ifdef DEBUG_TRACES + std::cout << "filtration = " << filtr << std::endl; +#endif // DEBUG_TRACES + if (filtr > filtration_max) { + filtration_max = filtr; + } + simplex_tree.insert_simplex(the_simplex_tree, filtr); + if (the_alpha_value_iterator != the_alpha_values.end()) + ++the_alpha_value_iterator; + else + std::cout << "This shall not happen" << std::endl; + } + simplex_tree.set_filtration(filtration_max); + simplex_tree.set_dimension(dim_max); + +#ifdef DEBUG_TRACES + std::cout << "vertices \t\t" << count_vertices << std::endl; + std::cout << "edges \t\t" << count_edges << std::endl; + std::cout << "facets \t\t" << count_facets << std::endl; + std::cout << "cells \t\t" << count_cells << std::endl; + + + std::cout << "Information of the Simplex Tree: " << std::endl; + std::cout << " Number of vertices = " << simplex_tree.num_vertices() << " "; + std::cout << " Number of simplices = " << simplex_tree.num_simplices() << std::endl << std::endl; + std::cout << " Dimension = " << simplex_tree.dimension() << " "; + std::cout << " filtration = " << simplex_tree.filtration() << std::endl << std::endl; +#endif // DEBUG_TRACES + +#ifdef DEBUG_TRACES + std::cout << "Iterator on vertices: " << std::endl; + for (auto vertex : simplex_tree.complex_vertex_range()) { + std::cout << vertex << " "; + } +#endif // DEBUG_TRACES + + // Sort the simplices in the order of the filtration + simplex_tree.initialize_filtration(); + + std::cout << "Simplex_tree dim: " << simplex_tree.dimension() << std::endl; + // Compute the persistence diagram of the complex + Persistent_cohomology pcoh(simplex_tree, true); + // initializes the coefficient field for homology + pcoh.init_coefficients(coeff_field_characteristic); + + pcoh.compute_persistent_cohomology(min_persistence); + + pcoh.output_diagram(); + + return 0; +} diff --git a/example/Persistent_cohomology/persistence_from_file.cpp b/example/Persistent_cohomology/persistence_from_file.cpp new file mode 100644 index 00000000..67235467 --- /dev/null +++ b/example/Persistent_cohomology/persistence_from_file.cpp @@ -0,0 +1,144 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2014 INRIA Saclay (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 <gudhi/reader_utils.h> +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/distance_functions.h> +#include <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> + +#include <boost/program_options.hpp> + +#include <string> + +using namespace Gudhi; +using namespace Gudhi::persistent_cohomology; + +typedef int Vertex_handle; +typedef double Filtration_value; + +void program_options(int argc, char * argv[] + , std::string & simplex_tree_file + , std::string & output_file + , int & p + , Filtration_value & min_persistence); + +int main(int argc, char * argv[]) { + std::string simplex_tree_file; + std::string output_file; + int p; + Filtration_value min_persistence; + + program_options(argc, argv, simplex_tree_file, output_file, p, min_persistence); + + std::cout << "Simplex_tree from file=" << simplex_tree_file.c_str() << " - output_file=" << output_file.c_str() + << std::endl; + std::cout << " - p=" << p << " - min_persistence=" << min_persistence << std::endl; + + // Read the list of simplices from a file. + Simplex_tree<> simplex_tree; + + std::ifstream simplex_tree_stream(simplex_tree_file); + simplex_tree_stream >> simplex_tree; + + std::cout << "The complex contains " << simplex_tree.num_simplices() << " simplices" << std::endl; + std::cout << " - dimension " << simplex_tree.dimension() << " - filtration " << simplex_tree.filtration() + << std::endl; + + /* + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for( auto f_simplex : simplex_tree.filtration_simplex_range() ) + { std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + for( auto vertex : simplex_tree.simplex_vertex_range(f_simplex) ) + { std::cout << vertex << " "; } + std::cout << std::endl; + }*/ + + // Sort the simplices in the order of the filtration + simplex_tree.initialize_filtration(); + + // Compute the persistence diagram of the complex + Persistent_cohomology< Simplex_tree<>, Field_Zp > pcoh(simplex_tree); + // initializes the coefficient field for homology + pcoh.init_coefficients(p); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in output_file + if (output_file.empty()) { + pcoh.output_diagram(); + } else { + std::ofstream out(output_file); + pcoh.output_diagram(out); + out.close(); + } + + return 0; +} + +void program_options(int argc, char * argv[] + , std::string & simplex_tree_file + , std::string & output_file + , int & p + , Filtration_value & min_persistence) { + namespace po = boost::program_options; + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value<std::string>(&simplex_tree_file), + "Name of file containing a simplex set. Format is one simplex per line (cf. reader_utils.h - read_simplex): Dim1 X11 X12 ... X1d Fil1 "); + + po::options_description visible("Allowed options", 100); + visible.add_options() + ("help,h", "produce help message") + ("output-file,o", po::value<std::string>(&output_file)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("field-charac,p", po::value<int>(&p)->default_value(11), + "Characteristic p of the coefficient field Z/pZ for computing homology.") + ("min-persistence,m", po::value<Filtration_value>(&min_persistence), + "Minimal lifetime of homology feature to be recorded. Default is 0"); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + + po::variables_map vm; + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with coefficient field Z/pZ \n"; + std::cout << "of a Rips complex defined on a set of input points.\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p is the characteristic of the field Z/pZ used for homology coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} diff --git a/example/Persistent_cohomology/persistence_from_simple_simplex_tree.cpp b/example/Persistent_cohomology/persistence_from_simple_simplex_tree.cpp new file mode 100644 index 00000000..ba772f04 --- /dev/null +++ b/example/Persistent_cohomology/persistence_from_simple_simplex_tree.cpp @@ -0,0 +1,178 @@ +/* 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): Vincent Rouvreau + * + * 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/>. + */ + +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> + +#include <iostream> +#include <ctime> +#include <utility> +#include <vector> + +using namespace Gudhi; +using namespace Gudhi::persistent_cohomology; + +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex; +typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool; +typedef Simplex_tree<> typeST; + +void usage(char * const progName) { + std::cerr << "Usage: " << progName << " coeff_field_characteristic[integer > 0] min_persistence[float >= -1.0]\n"; + exit(-1); +} + +int main(int argc, char * const argv[]) { + // program args management + if (argc != 3) { + std::cerr << "Error: Number of arguments (" << argc << ") is not correct\n"; + usage(argv[0]); + } + + int coeff_field_characteristic = 0; + int returnedScanValue = sscanf(argv[1], "%d", &coeff_field_characteristic); + if ((returnedScanValue == EOF) || (coeff_field_characteristic <= 0)) { + std::cerr << "Error: " << argv[1] << " is not correct\n"; + usage(argv[0]); + } + + Filtration_value min_persistence = 0.0; + returnedScanValue = sscanf(argv[2], "%lf", &min_persistence); + if ((returnedScanValue == EOF) || (min_persistence < -1.0)) { + std::cerr << "Error: " << argv[2] << " is not correct\n"; + usage(argv[0]); + } + + // TEST OF INSERTION + std::cout << "********************************************************************" << std::endl; + std::cout << "TEST OF INSERTION" << std::endl; + typeST st; + + // ++ FIRST + std::cout << " - INSERT (0,1,2)" << std::endl; + typeVectorVertex SimplexVector = {0, 1, 2}; + st.insert_simplex_and_subfaces(SimplexVector, 0.3); + + // ++ SECOND + std::cout << " - INSERT 3" << std::endl; + SimplexVector = {3}; + st.insert_simplex_and_subfaces(SimplexVector, 0.1); + + // ++ THIRD + std::cout << " - INSERT (0,3)" << std::endl; + SimplexVector = {0, 3}; + st.insert_simplex_and_subfaces(SimplexVector, 0.2); + + // ++ FOURTH + std::cout << " - INSERT (0,1) (already inserted)" << std::endl; + SimplexVector = {0, 1}; + st.insert_simplex_and_subfaces(SimplexVector, 0.2); + + // ++ FIFTH + std::cout << " - INSERT (3,4,5)" << std::endl; + SimplexVector = {3, 4, 5}; + st.insert_simplex_and_subfaces(SimplexVector, 0.3); + + // ++ SIXTH + std::cout << " - INSERT (0,1,6,7)" << std::endl; + SimplexVector = {0, 1, 6, 7}; + st.insert_simplex_and_subfaces(SimplexVector, 0.4); + + // ++ SEVENTH + std::cout << " - INSERT (4,5,8,9)" << std::endl; + SimplexVector = {4, 5, 8, 9}; + st.insert_simplex_and_subfaces(SimplexVector, 0.4); + + // ++ EIGHTH + std::cout << " - INSERT (9,10,11)" << std::endl; + SimplexVector = {9, 10, 11}; + st.insert_simplex_and_subfaces(SimplexVector, 0.3); + + // ++ NINETH + std::cout << " - INSERT (2,10,12)" << std::endl; + SimplexVector = {2, 10, 12}; + st.insert_simplex_and_subfaces(SimplexVector, 0.3); + + // ++ TENTH + std::cout << " - INSERT (11,6)" << std::endl; + SimplexVector = {6, 11}; + st.insert_simplex_and_subfaces(SimplexVector, 0.2); + + // ++ ELEVENTH + std::cout << " - INSERT (13,14,15)" << std::endl; + SimplexVector = {13, 14, 15}; + st.insert_simplex_and_subfaces(SimplexVector, 0.25); + + /* Inserted simplex: */ + /* 1 6 */ + /* o---o */ + /* /X\7/ 4 2 */ + /* o---o---o---o o */ + /* 2 0 3\X/8\ 10 /X\ */ + /* o---o---o---o */ + /* 5 9\X/ 12 */ + /* o---o */ + /* 11 6 */ + /* In other words: */ + /* A facet [2,1,0] */ + /* An edge [0,3] */ + /* A facet [3,4,5] */ + /* A cell [0,1,6,7] */ + /* A cell [4,5,8,9] */ + /* A facet [9,10,11] */ + /* An edge [11,6] */ + /* An edge [10,12,2] */ + + st.set_dimension(2); + st.set_filtration(0.4); + + std::cout << "The complex contains " << st.num_simplices() << " simplices - " << st.num_vertices() << " vertices " + << std::endl; + std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" + << std::endl; + std::cout << "**************************************************************" << std::endl; + std::cout << "strict graph G { " << std::endl; + + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << static_cast<int>(vertex) << " -- "; + } + std::cout << ";" << std::endl; + } + + std::cout << "}" << std::endl; + std::cout << "**************************************************************" << std::endl; + + // Compute the persistence diagram of the complex + persistent_cohomology::Persistent_cohomology< Simplex_tree<>, Field_Zp > pcoh(st); + // initializes the coefficient field for homology + pcoh.init_coefficients(coeff_field_characteristic); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + pcoh.output_diagram(); + return 0; +} diff --git a/example/Persistent_cohomology/plain_homology.cpp b/example/Persistent_cohomology/plain_homology.cpp new file mode 100644 index 00000000..ae82c817 --- /dev/null +++ b/example/Persistent_cohomology/plain_homology.cpp @@ -0,0 +1,95 @@ +/* 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): Marc Glisse + * + * Copyright (C) 2015 INRIA Saclay - Ile-de-France (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 <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> + +#include <iostream> +#include <vector> +#include <cstdint> // for std::uint8_t + +using namespace Gudhi; + +/* We could perfectly well use the default Simplex_tree<> (which uses + * Simplex_tree_options_full_featured), the following simply demonstrates + * how to save on storage by not storing a filtration value. */ + +struct MyOptions : Simplex_tree_options_full_featured { + // Implicitly use 0 as filtration value for all simplices + static const bool store_filtration = false; + // The persistence algorithm needs this + static const bool store_key = true; + // I have few vertices + typedef short Vertex_handle; + // Maximum number of simplices to compute persistence is 2^8 - 1 = 255. One is reserved for null_key + typedef std::uint8_t Simplex_key; +}; +typedef Simplex_tree<MyOptions> ST; + +int main() { + ST st; + + /* Complex to build. */ + /* 1 3 */ + /* o---o */ + /* /X\ / */ + /* o---o o */ + /* 2 0 4 */ + + const short triangle012[] = {0, 1, 2}; + const short edge03[] = {0, 3}; + const short edge13[] = {1, 3}; + const short vertex4[] = {4}; + st.insert_simplex_and_subfaces(triangle012); + st.insert_simplex_and_subfaces(edge03); + st.insert_simplex(edge13); + st.insert_simplex(vertex4); + // FIXME: Remove this line + st.set_dimension(2); + + // Sort the simplices in the order of the filtration + st.initialize_filtration(); + + // Class for homology computation + persistent_cohomology::Persistent_cohomology<ST, persistent_cohomology::Field_Zp> pcoh(st); + + // Initialize the coefficient field Z/2Z for homology + pcoh.init_coefficients(2); + + // Compute the persistence diagram of the complex + pcoh.compute_persistent_cohomology(); + + // Print the result. The format is, on each line: 2 dim 0 inf + // where 2 represents the field, dim the dimension of the feature. + // 2 0 0 inf + // 2 0 0 inf + // 2 1 0 inf + // means that in Z/2Z-homology, the Betti numbers are b0=2 and b1=1. + pcoh.output_diagram(); + + // Print the Betti numbers are b0=2 and b1=1. + std::cout << std::endl; + std::cout << "The Betti numbers are : "; + for (int i = 0; i < st.dimension(); i++) + std::cout << "b" << i << " = " << pcoh.betti_number(i) << " ; "; + std::cout << std::endl; +} diff --git a/example/Persistent_cohomology/rips_multifield_persistence.cpp b/example/Persistent_cohomology/rips_multifield_persistence.cpp new file mode 100644 index 00000000..c5cd775d --- /dev/null +++ b/example/Persistent_cohomology/rips_multifield_persistence.cpp @@ -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): Clément Maria + * + * 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/>. + */ + +#include <gudhi/reader_utils.h> +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/distance_functions.h> +#include <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> +#include <gudhi/Persistent_cohomology/Multi_field.h> + +#include <boost/program_options.hpp> + +#include <string> +#include <vector> + +using namespace Gudhi; +using namespace Gudhi::persistent_cohomology; + +typedef int Vertex_handle; +typedef double Filtration_value; + +void program_options(int argc, char * argv[] + , std::string & filepoints + , std::string & filediag + , Filtration_value & threshold + , int & dim_max + , int & min_p + , int & max_p + , Filtration_value & min_persistence); + +int main(int argc, char * argv[]) { + std::string filepoints; + std::string filediag; + Filtration_value threshold; + int dim_max; + int min_p; + int max_p; + Filtration_value min_persistence; + + program_options(argc, argv, filepoints, filediag, threshold, dim_max, min_p, max_p, min_persistence); + + // Extract the points from the file filepoints + typedef std::vector<double> Point_t; + std::vector< Point_t > points; + read_points(filepoints, points); + + // Compute the proximity graph of the points + Graph_t prox_graph = compute_proximity_graph(points, threshold + , euclidean_distance<Point_t>); + + // Construct the Rips complex in a Simplex Tree + typedef Simplex_tree<Simplex_tree_options_fast_persistence> ST; + ST st; + // insert the proximity graph in the simplex tree + st.insert_graph(prox_graph); + // expand the graph until dimension dim_max + st.expansion(dim_max); + + // Sort the simplices in the order of the filtration + st.initialize_filtration(); + + // Compute the persistence diagram of the complex + Persistent_cohomology<ST, Multi_field > pcoh(st); + // initializes the coefficient field for homology + pcoh.init_coefficients(min_p, max_p); + // compute persistent homology, disgarding persistent features of life shorter than min_persistence + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + if (filediag.empty()) { + pcoh.output_diagram(); + } else { + std::ofstream out(filediag); + pcoh.output_diagram(out); + out.close(); + } + + return 0; +} + +void program_options(int argc, char * argv[] + , std::string & filepoints + , std::string & filediag + , Filtration_value & threshold + , int & dim_max + , int & min_p + , int & max_p + , Filtration_value & min_persistence) { + namespace po = boost::program_options; + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value<std::string>(&filepoints), + "Name of file containing a point set. Format is one point per line: X1 ... Xd \n"); + + po::options_description visible("Allowed options"); + visible.add_options() + ("help,h", "produce help message") + ("output-file,o", po::value<std::string>(&filediag)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("max-edge-length,r", po::value<Filtration_value>(&threshold)->default_value(0), + "Maximal length of an edge for the Rips complex construction.") + ("cpx-dimension,d", po::value<int>(&dim_max)->default_value(1), + "Maximal dimension of the Rips complex we want to compute.") + ("min-field-charac,p", po::value<int>(&min_p)->default_value(2), + "Minimal characteristic p of the coefficient field Z/pZ.") + ("max-field-charac,q", po::value<int>(&max_p)->default_value(1223), + "Minimial characteristic q of the coefficient field Z/pZ.") + ("min-persistence,m", po::value<Filtration_value>(&min_persistence), + "Minimal lifetime of homology feature to be recorded. Default is 0"); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + + po::variables_map vm; + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with various coefficient fields \n"; + std::cout << "of a Rips complex defined on a set of input points. The coefficient \n"; + std::cout << "fields are all the Z/rZ for a prime number r contained in the \n"; + std::cout << "specified range [p,q]\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p1*...*pr dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p1*...*pr is the product of prime numbers pi such that the homology \n"; + std::cout << "feature exists in homology with Z/piZ coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} diff --git a/example/Persistent_cohomology/rips_persistence.cpp b/example/Persistent_cohomology/rips_persistence.cpp new file mode 100644 index 00000000..cab49395 --- /dev/null +++ b/example/Persistent_cohomology/rips_persistence.cpp @@ -0,0 +1,153 @@ +/* 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): Clément Maria + * + * 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/>. + */ + +#include <gudhi/reader_utils.h> +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/distance_functions.h> +#include <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> + +#include <boost/program_options.hpp> + +#include <string> +#include <vector> +#include <limits> // infinity + +using namespace Gudhi; +using namespace Gudhi::persistent_cohomology; + +typedef int Vertex_handle; +typedef double Filtration_value; + +void program_options(int argc, char * argv[] + , std::string & filepoints + , std::string & filediag + , Filtration_value & threshold + , int & dim_max + , int & p + , Filtration_value & min_persistence); + +int main(int argc, char * argv[]) { + std::string filepoints; + std::string filediag; + Filtration_value threshold; + int dim_max; + int p; + Filtration_value min_persistence; + + program_options(argc, argv, filepoints, filediag, threshold, dim_max, p, min_persistence); + + // Extract the points from the file filepoints + typedef std::vector<double> Point_t; + std::vector< Point_t > points; + read_points(filepoints, points); + + // Compute the proximity graph of the points + Graph_t prox_graph = compute_proximity_graph(points, threshold + , euclidean_distance<Point_t>); + + // Construct the Rips complex in a Simplex Tree + typedef Simplex_tree<Simplex_tree_options_fast_persistence> ST; + ST st; + // insert the proximity graph in the simplex tree + st.insert_graph(prox_graph); + // expand the graph until dimension dim_max + st.expansion(dim_max); + + std::cout << "The complex contains " << st.num_simplices() << " simplices \n"; + std::cout << " and has dimension " << st.dimension() << " \n"; + + // Sort the simplices in the order of the filtration + st.initialize_filtration(); + + // Compute the persistence diagram of the complex + persistent_cohomology::Persistent_cohomology<ST, Field_Zp > pcoh(st); + // initializes the coefficient field for homology + pcoh.init_coefficients(p); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + if (filediag.empty()) { + pcoh.output_diagram(); + } else { + std::ofstream out(filediag); + pcoh.output_diagram(out); + out.close(); + } + + return 0; +} + +void program_options(int argc, char * argv[] + , std::string & filepoints + , std::string & filediag + , Filtration_value & threshold + , int & dim_max + , int & p + , Filtration_value & min_persistence) { + namespace po = boost::program_options; + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value<std::string>(&filepoints), + "Name of file containing a point set. Format is one point per line: X1 ... Xd "); + + po::options_description visible("Allowed options", 100); + visible.add_options() + ("help,h", "produce help message") + ("output-file,o", po::value<std::string>(&filediag)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("max-edge-length,r", po::value<Filtration_value>(&threshold)->default_value(std::numeric_limits<Filtration_value>::infinity()), + "Maximal length of an edge for the Rips complex construction.") + ("cpx-dimension,d", po::value<int>(&dim_max)->default_value(1), + "Maximal dimension of the Rips complex we want to compute.") + ("field-charac,p", po::value<int>(&p)->default_value(11), + "Characteristic p of the coefficient field Z/pZ for computing homology.") + ("min-persistence,m", po::value<Filtration_value>(&min_persistence), + "Minimal lifetime of homology feature to be recorded. Default is 0. Enter a negative value to see zero length intervals"); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + + po::variables_map vm; + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with coefficient field Z/pZ \n"; + std::cout << "of a Rips complex defined on a set of input points.\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p is the characteristic of the field Z/pZ used for homology coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} diff --git a/example/Persistent_cohomology/rips_persistence_via_boundary_matrix.cpp b/example/Persistent_cohomology/rips_persistence_via_boundary_matrix.cpp new file mode 100644 index 00000000..4c6656f5 --- /dev/null +++ b/example/Persistent_cohomology/rips_persistence_via_boundary_matrix.cpp @@ -0,0 +1,180 @@ +/* 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): Clément Maria, Marc Glisse + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France), + * 2015 INRIA Saclay Île de 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 <gudhi/reader_utils.h> +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/distance_functions.h> +#include <gudhi/Simplex_tree.h> +#include <gudhi/Persistent_cohomology.h> +#include <gudhi/Hasse_complex.h> + +#include <boost/program_options.hpp> + +#ifdef GUDHI_USE_TBB +#include <tbb/task_scheduler_init.h> +#endif + +#include <string> +#include <vector> + +//////////////////////////////////////////////////////////////// +// // +// WARNING: persistence computation itself is not parallel, // +// and this uses more memory than rips_persistence. // +// // +//////////////////////////////////////////////////////////////// + +using namespace Gudhi; +using namespace Gudhi::persistent_cohomology; + +typedef int Vertex_handle; +typedef double Filtration_value; + +void program_options(int argc, char * argv[] + , std::string & filepoints + , std::string & filediag + , Filtration_value & threshold + , int & dim_max + , int & p + , Filtration_value & min_persistence); + +int main(int argc, char * argv[]) { + std::string filepoints; + std::string filediag; + Filtration_value threshold; + int dim_max; + int p; + Filtration_value min_persistence; + + program_options(argc, argv, filepoints, filediag, threshold, dim_max, p, min_persistence); + + // Extract the points from the file filepoints + typedef std::vector<double> Point_t; + std::vector< Point_t > points; + read_points(filepoints, points); + + // Compute the proximity graph of the points + Graph_t prox_graph = compute_proximity_graph(points, threshold + , euclidean_distance<Point_t>); + + // Construct the Rips complex in a Simplex Tree + Simplex_tree<>& st = *new Simplex_tree<>; + // insert the proximity graph in the simplex tree + st.insert_graph(prox_graph); + // expand the graph until dimension dim_max + st.expansion(dim_max); + + std::cout << "The complex contains " << st.num_simplices() << " simplices \n"; + std::cout << " and has dimension " << st.dimension() << " \n"; + +#ifdef GUDHI_USE_TBB + // Unnecessary, but clarifies which operations are parallel. + tbb::task_scheduler_init ts; +#endif + + // Sort the simplices in the order of the filtration + st.initialize_filtration(); + int count = 0; + for (auto sh : st.filtration_simplex_range()) + st.assign_key(sh, count++); + + // Convert to a more convenient representation. + Hasse_complex<> hcpx(st); + +#ifdef GUDHI_USE_TBB + ts.terminate(); +#endif + + // Free some space. + delete &st; + + // Compute the persistence diagram of the complex + persistent_cohomology::Persistent_cohomology< Hasse_complex<>, Field_Zp > pcoh(hcpx); + // initializes the coefficient field for homology + pcoh.init_coefficients(p); + + pcoh.compute_persistent_cohomology(min_persistence); + + // Output the diagram in filediag + if (filediag.empty()) { + pcoh.output_diagram(); + } else { + std::ofstream out(filediag); + pcoh.output_diagram(out); + out.close(); + } +} + +void program_options(int argc, char * argv[] + , std::string & filepoints + , std::string & filediag + , Filtration_value & threshold + , int & dim_max + , int & p + , Filtration_value & min_persistence) { + namespace po = boost::program_options; + po::options_description hidden("Hidden options"); + hidden.add_options() + ("input-file", po::value<std::string>(&filepoints), + "Name of file containing a point set. Format is one point per line: X1 ... Xd "); + + po::options_description visible("Allowed options", 100); + visible.add_options() + ("help,h", "produce help message") + ("output-file,o", po::value<std::string>(&filediag)->default_value(std::string()), + "Name of file in which the persistence diagram is written. Default print in std::cout") + ("max-edge-length,r", po::value<Filtration_value>(&threshold)->default_value(0), + "Maximal length of an edge for the Rips complex construction.") + ("cpx-dimension,d", po::value<int>(&dim_max)->default_value(1), + "Maximal dimension of the Rips complex we want to compute.") + ("field-charac,p", po::value<int>(&p)->default_value(11), + "Characteristic p of the coefficient field Z/pZ for computing homology.") + ("min-persistence,m", po::value<Filtration_value>(&min_persistence), + "Minimal lifetime of homology feature to be recorded. Default is 0. Enter a negative value to see zero length intervals"); + + po::positional_options_description pos; + pos.add("input-file", 1); + + po::options_description all; + all.add(visible).add(hidden); + + po::variables_map vm; + po::store(po::command_line_parser(argc, argv). + options(all).positional(pos).run(), vm); + po::notify(vm); + + if (vm.count("help") || !vm.count("input-file")) { + std::cout << std::endl; + std::cout << "Compute the persistent homology with coefficient field Z/pZ \n"; + std::cout << "of a Rips complex defined on a set of input points.\n \n"; + std::cout << "The output diagram contains one bar per line, written with the convention: \n"; + std::cout << " p dim b d \n"; + std::cout << "where dim is the dimension of the homological feature,\n"; + std::cout << "b and d are respectively the birth and death of the feature and \n"; + std::cout << "p is the characteristic of the field Z/pZ used for homology coefficients." << std::endl << std::endl; + + std::cout << "Usage: " << argv[0] << " [options] input-file" << std::endl << std::endl; + std::cout << visible << std::endl; + std::abort(); + } +} diff --git a/example/Simplex_tree/CMakeLists.txt b/example/Simplex_tree/CMakeLists.txt new file mode 100644 index 00000000..9314a805 --- /dev/null +++ b/example/Simplex_tree/CMakeLists.txt @@ -0,0 +1,29 @@ +cmake_minimum_required(VERSION 2.6) +project(Simplex_tree_examples) + +add_executable ( simplex_tree_from_cliques_of_graph simplex_tree_from_cliques_of_graph.cpp ) +if (TBB_FOUND) + target_link_libraries(simplex_tree_from_cliques_of_graph ${TBB_LIBRARIES}) +endif() +add_test(simplex_tree_from_cliques_of_graph_2 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph ${CMAKE_SOURCE_DIR}/data/points/Klein_bottle_complex.txt 2) +add_test(simplex_tree_from_cliques_of_graph_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_cliques_of_graph ${CMAKE_SOURCE_DIR}/data/points/Klein_bottle_complex.txt 3) + +add_executable ( simple_simplex_tree simple_simplex_tree.cpp ) +if (TBB_FOUND) + target_link_libraries(simple_simplex_tree ${TBB_LIBRARIES}) +endif() +add_test(simple_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/simple_simplex_tree) + +add_executable ( mini_simplex_tree mini_simplex_tree.cpp ) +add_test(mini_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/mini_simplex_tree) + + +# An example with Simplex-tree using CGAL alpha_shapes_3 +if(GMP_FOUND AND CGAL_FOUND) + add_executable ( simplex_tree_from_alpha_shapes_3 simplex_tree_from_alpha_shapes_3.cpp ) + target_link_libraries(simplex_tree_from_alpha_shapes_3 ${GMP_LIBRARIES} ${CGAL_LIBRARY} ${Boost_SYSTEM_LIBRARY}) + if (TBB_FOUND) + target_link_libraries(simplex_tree_from_alpha_shapes_3 ${TBB_LIBRARIES}) + endif() + add_test(simplex_tree_from_alpha_shapes_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_alpha_shapes_3 ${CMAKE_SOURCE_DIR}/data/points/bunny_5000) +endif() diff --git a/example/Simplex_tree/README b/example/Simplex_tree/README new file mode 100644 index 00000000..e37af790 --- /dev/null +++ b/example/Simplex_tree/README @@ -0,0 +1,73 @@ +To build the example, run in a Terminal: + +cd /path-to-gudhi/ +cmake . +cd /path-to-example/ +make + + +Example of use : + +*** Simple simplex tree construction + +./simple_simplex_tree + +******************************************************************** +EXAMPLE OF SIMPLE INSERTION + * INSERT 0 + + 0 INSERTED + * INSERT 1 + + 1 INSERTED + * INSERT (0,1) + + (0,1) INSERTED + * INSERT 2 + + 2 INSERTED + * INSERT (2,0) + + (2,0) INSERTED + * INSERT (2,1) + + (2,1) INSERTED + * INSERT (2,1,0) + + (2,1,0) INSERTED + * INSERT 3 + + 3 INSERTED + * INSERT (3,0) + + (3,0) INSERTED + * INSERT 0 (already inserted) + - 0 NOT INSERTED + * INSERT (2,1,0) (already inserted) + - (2,1,0) NOT INSERTED +******************************************************************** +* The complex contains 9 simplices + - dimension 2 - filtration 0.4 +* Iterator on Simplices in the filtration, with [filtration value]: + [0.1] 0 + [0.1] 1 + [0.1] 2 + [0.1] 3 + [0.2] 1 0 + [0.2] 2 0 + [0.2] 2 1 + [0.2] 3 0 + [0.3] 2 1 0 + +*** Simplex tree construction with Z/2Z coefficients on weighted graph Klein bottle file: + +./simplex_tree_from_cliques_of_graph ../../../data/points/Klein_bottle_complex.txt 2 +Insert the 1-skeleton in the simplex tree in 0 s. +Expand the simplex tree in 0 s. +Information of the Simplex Tree: + Number of vertices = 10 Number of simplices = 82 + +with Z/3Z coefficients: + +./simplex_tree_from_cliques_of_graph ../../../data/points/Klein_bottle_complex.txt 3 + +Insert the 1-skeleton in the simplex tree in 0 s. +Expand the simplex tree in 0 s. +Information of the Simplex Tree: + Number of vertices = 10 Number of simplices = 106 + +*** Simplex_tree computed and displayed from a 3D alpha complex: + [ Requires CGAL, GMP and GMPXX to be installed] + +./simplex_tree_from_alpha_shapes_3 ../../../data/points/bunny_5000 diff --git a/example/Simplex_tree/mini_simplex_tree.cpp b/example/Simplex_tree/mini_simplex_tree.cpp new file mode 100644 index 00000000..7e48aaaf --- /dev/null +++ b/example/Simplex_tree/mini_simplex_tree.cpp @@ -0,0 +1,69 @@ +/* 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): Marc Glisse + * + * Copyright (C) 2015 INRIA Saclay - Ile-de-France (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 <gudhi/Simplex_tree.h> +#include <iostream> +#include <initializer_list> + +using namespace Gudhi; + +struct MyOptions : Simplex_tree_options_full_featured { + // Not doing persistence, so we don't need those + static const bool store_key = false; + static const bool store_filtration = false; + // I have few vertices + typedef short Vertex_handle; +}; +typedef Simplex_tree<MyOptions> ST; + +// Dictionary should be private, but for now this is the easiest way. +static_assert(sizeof(ST::Dictionary::value_type) < sizeof(Simplex_tree<>::Dictionary::value_type), + "Not storing the filtration and key should save some space"); + +int main() { + ST st; + + /* Complex to build. */ + /* 1 */ + /* o */ + /* /X\ */ + /* o---o---o */ + /* 2 0 3 */ + + auto triangle012 = {0, 1, 2}; + auto edge03 = {0, 3}; + st.insert_simplex_and_subfaces(triangle012); + st.insert_simplex_and_subfaces(edge03); + // FIXME: Remove this line + st.set_dimension(2); + + auto edge02 = {0, 2}; + ST::Simplex_handle e = st.find(edge02); + // We are not using filtrations so everything has value 0 + assert(st.filtration(e) == 0); + for (ST::Simplex_handle t : st.cofaces_simplex_range(e, 1)) { + // Only coface is 012 + for (ST::Vertex_handle v : st.simplex_vertex_range(t)) // v in { 0, 1, 2 } + std::cout << v; + std::cout << '\n'; + } +} diff --git a/example/Simplex_tree/simple_simplex_tree.cpp b/example/Simplex_tree/simple_simplex_tree.cpp new file mode 100644 index 00000000..5146b906 --- /dev/null +++ b/example/Simplex_tree/simple_simplex_tree.cpp @@ -0,0 +1,253 @@ +/* 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): Vincent Rouvreau + * + * 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/>. + */ + +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/Simplex_tree.h> + +#include <iostream> +#include <utility> // for pair +#include <vector> + +using namespace Gudhi; + +typedef std::vector< Vertex_handle > typeVectorVertex; +typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool; + +int main(int argc, char * const argv[]) { + const Filtration_value FIRST_FILTRATION_VALUE = 0.1; + const Filtration_value SECOND_FILTRATION_VALUE = 0.2; + const Filtration_value THIRD_FILTRATION_VALUE = 0.3; + const Filtration_value FOURTH_FILTRATION_VALUE = 0.4; + + // TEST OF INSERTION + std::cout << "********************************************************************" << std::endl; + std::cout << "EXAMPLE OF SIMPLE INSERTION" << std::endl; + // Construct the Simplex Tree + Simplex_tree<> simplexTree; + + /* Simplex to be inserted: */ + /* 1 */ + /* o */ + /* /X\ */ + /* o---o---o */ + /* 2 0 3 */ + + // ++ FIRST + std::cout << " * INSERT 0" << std::endl; + typeVectorVertex firstSimplexVector = { 0 }; + typePairSimplexBool returnValue = + simplexTree.insert_simplex(firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + 0 INSERTED" << std::endl; + } else { + std::cout << " - 0 NOT INSERTED" << std::endl; + } + + // ++ SECOND + std::cout << " * INSERT 1" << std::endl; + typeVectorVertex secondSimplexVector = { 1 }; + returnValue = + simplexTree.insert_simplex(secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + 1 INSERTED" << std::endl; + } else { + std::cout << " - 1 NOT INSERTED" << std::endl; + } + + // ++ THIRD + std::cout << " * INSERT (0,1)" << std::endl; + typeVectorVertex thirdSimplexVector = { 0, 1 }; + returnValue = + simplexTree.insert_simplex(thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + (0,1) INSERTED" << std::endl; + } else { + std::cout << " - (0,1) NOT INSERTED" << std::endl; + } + + // ++ FOURTH + std::cout << " * INSERT 2" << std::endl; + typeVectorVertex fourthSimplexVector = { 2 }; + returnValue = + simplexTree.insert_simplex(fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + 2 INSERTED" << std::endl; + } else { + std::cout << " - 2 NOT INSERTED" << std::endl; + } + + // ++ FIFTH + std::cout << " * INSERT (2,0)" << std::endl; + typeVectorVertex fifthSimplexVector = { 2, 0 }; + returnValue = + simplexTree.insert_simplex(fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + (2,0) INSERTED" << std::endl; + } else { + std::cout << " - (2,0) NOT INSERTED" << std::endl; + } + + // ++ SIXTH + std::cout << " * INSERT (2,1)" << std::endl; + typeVectorVertex sixthSimplexVector = { 2, 1 }; + returnValue = + simplexTree.insert_simplex(sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + (2,1) INSERTED" << std::endl; + } else { + std::cout << " - (2,1) NOT INSERTED" << std::endl; + } + + // ++ SEVENTH + std::cout << " * INSERT (2,1,0)" << std::endl; + typeVectorVertex seventhSimplexVector = { 2, 1, 0 }; + returnValue = + simplexTree.insert_simplex(seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + (2,1,0) INSERTED" << std::endl; + } else { + std::cout << " - (2,1,0) NOT INSERTED" << std::endl; + } + + // ++ EIGHTH + std::cout << " * INSERT 3" << std::endl; + typeVectorVertex eighthSimplexVector = { 3 }; + returnValue = + simplexTree.insert_simplex(eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + 3 INSERTED" << std::endl; + } else { + std::cout << " - 3 NOT INSERTED" << std::endl; + } + + // ++ NINETH + std::cout << " * INSERT (3,0)" << std::endl; + typeVectorVertex ninethSimplexVector = { 3, 0 }; + returnValue = + simplexTree.insert_simplex(ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + (3,0) INSERTED" << std::endl; + } else { + std::cout << " - (3,0) NOT INSERTED" << std::endl; + } + + // ++ TENTH + std::cout << " * INSERT 0 (already inserted)" << std::endl; + typeVectorVertex tenthSimplexVector = { 0 }; + // With a different filtration value + returnValue = simplexTree.insert_simplex(tenthSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + 0 INSERTED" << std::endl; + } else { + std::cout << " - 0 NOT INSERTED" << std::endl; + } + + // ++ ELEVENTH + std::cout << " * INSERT (2,1,0) (already inserted)" << std::endl; + typeVectorVertex eleventhSimplexVector = { 2, 1, 0 }; + returnValue = + simplexTree.insert_simplex(eleventhSimplexVector, Filtration_value(FOURTH_FILTRATION_VALUE)); + + if (returnValue.second == true) { + std::cout << " + (2,1,0) INSERTED" << std::endl; + } else { + std::cout << " - (2,1,0) NOT INSERTED" << std::endl; + } + + // ++ GENERAL VARIABLE SET + simplexTree.set_filtration(FOURTH_FILTRATION_VALUE); // Max filtration value + simplexTree.set_dimension(2); // Max dimension = 2 -> (2,1,0) + + std::cout << "********************************************************************\n"; + // Display the Simplex_tree - Can not be done in the middle of 2 inserts + std::cout << "* The complex contains " << simplexTree.num_simplices() << " simplices\n"; + std::cout << " - dimension " << simplexTree.dimension() << " - filtration " << simplexTree.filtration() << "\n"; + std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + for (auto f_simplex : simplexTree.filtration_simplex_range()) { + std::cout << " " << "[" << simplexTree.filtration(f_simplex) << "] "; + for (auto vertex : simplexTree.simplex_vertex_range(f_simplex)) { + std::cout << static_cast<int>(vertex) << " "; + } + std::cout << std::endl; + } + // [0.1] 0 + // [0.1] 1 + // [0.1] 2 + // [0.1] 3 + // [0.2] 1 0 + // [0.2] 2 0 + // [0.2] 2 1 + // [0.2] 3 0 + // [0.3] 2 1 0 + + // ------------------------------------------------------------------------------------------------------------------ + // Find in the simplex_tree + // ------------------------------------------------------------------------------------------------------------------ + Simplex_tree<>::Simplex_handle simplexFound = simplexTree.find(secondSimplexVector); + std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != simplexTree.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + + typeVectorVertex unknownSimplexVector = { 15 }; + simplexFound = simplexTree.find(unknownSimplexVector); + std::cout << "**************IS THE SIMPLEX {15} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != simplexTree.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + + simplexFound = simplexTree.find(fifthSimplexVector); + std::cout << "**************IS THE SIMPLEX {2,0} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != simplexTree.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + + typeVectorVertex otherSimplexVector = { 1, 15 }; + simplexFound = simplexTree.find(otherSimplexVector); + std::cout << "**************IS THE SIMPLEX {15,1} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != simplexTree.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + + typeVectorVertex invSimplexVector = { 1, 2, 0 }; + simplexFound = simplexTree.find(invSimplexVector); + std::cout << "**************IS THE SIMPLEX {1,2,0} IN THE SIMPLEX TREE ?\n"; + if (simplexFound != simplexTree.null_simplex()) + std::cout << "***+ YES IT IS!\n"; + else + std::cout << "***- NO IT ISN'T\n"; + return 0; +} diff --git a/example/Simplex_tree/simplex_tree_from_alpha_shapes_3.cpp b/example/Simplex_tree/simplex_tree_from_alpha_shapes_3.cpp new file mode 100644 index 00000000..49d358ab --- /dev/null +++ b/example/Simplex_tree/simplex_tree_from_alpha_shapes_3.cpp @@ -0,0 +1,276 @@ +/* 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): Vincent Rouvreau + * + * Copyright (C) 2014 INRIA Saclay (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 <gudhi/graph_simplicial_complex.h> +#include <gudhi/Simplex_tree.h> +#include <boost/variant.hpp> + +#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> +#include <CGAL/Delaunay_triangulation_3.h> +#include <CGAL/Alpha_shape_3.h> +#include <CGAL/iterator.h> + +#include <fstream> +#include <cmath> +#include <string> +#include <tuple> // for tuple<> +#include <map> +#include <utility> // for pair<> +#include <list> +#include <vector> + +// Alpha_shape_3 templates type definitions +typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel; +typedef CGAL::Alpha_shape_vertex_base_3<Kernel> Vb; +typedef CGAL::Alpha_shape_cell_base_3<Kernel> Fb; +typedef CGAL::Triangulation_data_structure_3<Vb, Fb> Tds; +typedef CGAL::Delaunay_triangulation_3<Kernel, Tds> Triangulation_3; +typedef CGAL::Alpha_shape_3<Triangulation_3> Alpha_shape_3; + +// From file type definition +typedef Kernel::Point_3 Point; + +// filtration with alpha values needed type definition +typedef Alpha_shape_3::FT Alpha_value_type; +typedef CGAL::Object Object; +typedef CGAL::Dispatch_output_iterator< +CGAL::cpp11::tuple<Object, Alpha_value_type>, +CGAL::cpp11::tuple<std::back_insert_iterator< std::vector<Object> >, + std::back_insert_iterator< std::vector<Alpha_value_type> > > > Dispatch; +typedef Alpha_shape_3::Cell_handle Cell_handle; +typedef Alpha_shape_3::Facet Facet; +typedef Alpha_shape_3::Edge Edge; +typedef std::list<Alpha_shape_3::Vertex_handle> Vertex_list; + +// gudhi type definition +typedef Gudhi::Simplex_tree<> Simplex_tree; +typedef Simplex_tree::Vertex_handle Simplex_tree_vertex; +typedef std::map<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex > Alpha_shape_simplex_tree_map; +typedef std::pair<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex> Alpha_shape_simplex_tree_pair; +typedef std::vector< Simplex_tree_vertex > Simplex_tree_vector_vertex; + +Vertex_list from(const Cell_handle& ch) { + Vertex_list the_list; + for (auto i = 0; i < 4; i++) { +#ifdef DEBUG_TRACES + std::cout << "from cell[" << i << "]=" << ch->vertex(i)->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(ch->vertex(i)); + } + return the_list; +} + +Vertex_list from(const Facet& fct) { + Vertex_list the_list; + for (auto i = 0; i < 4; i++) { + if (fct.second != i) { +#ifdef DEBUG_TRACES + std::cout << "from facet=[" << i << "]" << fct.first->vertex(i)->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(fct.first->vertex(i)); + } + } + return the_list; +} + +Vertex_list from(const Edge& edg) { + Vertex_list the_list; + for (auto i = 0; i < 4; i++) { + if ((edg.second == i) || (edg.third == i)) { +#ifdef DEBUG_TRACES + std::cout << "from edge[" << i << "]=" << edg.first->vertex(i)->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(edg.first->vertex(i)); + } + } + return the_list; +} + +Vertex_list from(const Alpha_shape_3::Vertex_handle& vh) { + Vertex_list the_list; +#ifdef DEBUG_TRACES + std::cout << "from vertex=" << vh->point() << std::endl; +#endif // DEBUG_TRACES + the_list.push_back(vh); + return the_list; +} + +int main(int argc, char * const argv[]) { + // program args management + if (argc != 2) { + std::cerr << "Usage: " << argv[0] + << " path_to_file_graph \n"; + return 0; + } + + // Read points from file + std::string filegraph = argv[1]; + std::list<Point> lp; + std::ifstream is(filegraph.c_str()); + int n; + is >> n; +#ifdef DEBUG_TRACES + std::cout << "Reading " << n << " points " << std::endl; +#endif // DEBUG_TRACES + Point p; + for (; n > 0; n--) { + is >> p; + lp.push_back(p); + } + + // alpha shape construction from points. CGAL has a strange behavior in REGULARIZED mode. + Alpha_shape_3 as(lp.begin(), lp.end(), 0, Alpha_shape_3::GENERAL); +#ifdef DEBUG_TRACES + std::cout << "Alpha shape computed in GENERAL mode" << std::endl; +#endif // DEBUG_TRACES + + // filtration with alpha values from alpha shape + std::vector<Object> the_objects; + std::vector<Alpha_value_type> the_alpha_values; + + Dispatch disp = CGAL::dispatch_output<Object, Alpha_value_type>(std::back_inserter(the_objects), + std::back_inserter(the_alpha_values)); + + as.filtration_with_alpha_values(disp); +#ifdef DEBUG_TRACES + std::cout << "filtration_with_alpha_values returns : " << the_objects.size() << " objects" << std::endl; +#endif // DEBUG_TRACES + + Alpha_shape_3::size_type count_vertices = 0; + Alpha_shape_3::size_type count_edges = 0; + Alpha_shape_3::size_type count_facets = 0; + Alpha_shape_3::size_type count_cells = 0; + + // Loop on objects vector + Vertex_list vertex_list; + Simplex_tree simplex_tree; + Alpha_shape_simplex_tree_map map_cgal_simplex_tree; + std::vector<Alpha_value_type>::iterator the_alpha_value_iterator = the_alpha_values.begin(); + for (auto object_iterator : the_objects) { + // Retrieve Alpha shape vertex list from object + if (const Cell_handle * cell = CGAL::object_cast<Cell_handle>(&object_iterator)) { + vertex_list = from(*cell); + count_cells++; + } else if (const Facet * facet = CGAL::object_cast<Facet>(&object_iterator)) { + vertex_list = from(*facet); + count_facets++; + } else if (const Edge * edge = CGAL::object_cast<Edge>(&object_iterator)) { + vertex_list = from(*edge); + count_edges++; + } else if (const Alpha_shape_3::Vertex_handle * vertex = + CGAL::object_cast<Alpha_shape_3::Vertex_handle>(&object_iterator)) { + count_vertices++; + vertex_list = from(*vertex); + } + // Construction of the vector of simplex_tree vertex from list of alpha_shapes vertex + Simplex_tree_vector_vertex the_simplex_tree; + for (auto the_alpha_shape_vertex : vertex_list) { + Alpha_shape_simplex_tree_map::iterator the_map_iterator = map_cgal_simplex_tree.find(the_alpha_shape_vertex); + if (the_map_iterator == map_cgal_simplex_tree.end()) { + // alpha shape not found + Simplex_tree_vertex vertex = map_cgal_simplex_tree.size(); +#ifdef DEBUG_TRACES + std::cout << "vertex [" << the_alpha_shape_vertex->point() << "] not found - insert_simplex " << vertex << "\n"; +#endif // DEBUG_TRACES + the_simplex_tree.push_back(vertex); + map_cgal_simplex_tree.insert(Alpha_shape_simplex_tree_pair(the_alpha_shape_vertex, vertex)); + } else { + // alpha shape found + Simplex_tree_vertex vertex = the_map_iterator->second; +#ifdef DEBUG_TRACES + std::cout << "vertex [" << the_alpha_shape_vertex->point() << "] found in " << vertex << std::endl; +#endif // DEBUG_TRACES + the_simplex_tree.push_back(vertex); + } + } + // Construction of the simplex_tree +#ifdef DEBUG_TRACES + std::cout << "filtration = " << *the_alpha_value_iterator << std::endl; +#endif // DEBUG_TRACES + simplex_tree.insert_simplex(the_simplex_tree, std::sqrt(*the_alpha_value_iterator)); + if (the_alpha_value_iterator != the_alpha_values.end()) + ++the_alpha_value_iterator; + else + std::cerr << "This shall not happen" << std::endl; + } +#ifdef DEBUG_TRACES + std::cout << "vertices \t\t" << count_vertices << std::endl; + std::cout << "edges \t\t" << count_edges << std::endl; + std::cout << "facets \t\t" << count_facets << std::endl; + std::cout << "cells \t\t" << count_cells << std::endl; + + + std::cout << "Information of the Simplex Tree:\n"; + std::cout << " Number of vertices = " << simplex_tree.num_vertices() << " "; + std::cout << " Number of simplices = " << simplex_tree.num_simplices() << std::endl << std::endl; +#endif // DEBUG_TRACES + +#ifdef DEBUG_TRACES + std::cout << "Iterator on vertices: \n"; + for (auto vertex : simplex_tree.complex_vertex_range()) { + std::cout << vertex << " "; + } +#endif // DEBUG_TRACES + + std::cout << simplex_tree << std::endl; + +#ifdef DEBUG_TRACES + std::cout << std::endl << std::endl << "Iterator on simplices:\n"; + for (auto simplex : simplex_tree.complex_simplex_range()) { + std::cout << " "; + for (auto vertex : simplex_tree.simplex_vertex_range(simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } +#endif // DEBUG_TRACES +#ifdef DEBUG_TRACES + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:\n"; + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { + std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } +#endif // DEBUG_TRACES +#ifdef DEBUG_TRACES + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, and their boundary simplices:\n"; + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { + std::cout << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + + for (auto b_simplex : simplex_tree.boundary_simplex_range(f_simplex)) { + std::cout << " " << "[" << simplex_tree.filtration(b_simplex) << "] "; + for (auto vertex : simplex_tree.simplex_vertex_range(b_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } + } +#endif // DEBUG_TRACES + + return 0; +} diff --git a/example/Simplex_tree/simplex_tree_from_cliques_of_graph.cpp b/example/Simplex_tree/simplex_tree_from_cliques_of_graph.cpp new file mode 100644 index 00000000..58085014 --- /dev/null +++ b/example/Simplex_tree/simplex_tree_from_cliques_of_graph.cpp @@ -0,0 +1,114 @@ +/* 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): Clément Maria + * + * 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/>. + */ + +#include <gudhi/reader_utils.h> +#include <gudhi/Simplex_tree.h> + +#include <iostream> +#include <ctime> +#include <string> + +using namespace Gudhi; + +int main(int argc, char * const argv[]) { + if (argc != 3) { + std::cerr << "Usage: " << argv[0] + << " path_to_file_graph max_dim \n"; + return 0; + } + std::string filegraph = argv[1]; + int max_dim = atoi(argv[2]); + + clock_t start, end; + // Construct the Simplex Tree + Simplex_tree<> st; + + start = clock(); + auto g = read_graph(filegraph); + // insert the graph in the simplex tree as 1-skeleton + st.insert_graph(g); + end = clock(); + std::cout << "Insert the 1-skeleton in the simplex tree in " + << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + + start = clock(); + // expand the 1-skeleton until dimension max_dim + st.expansion(max_dim); + end = clock(); + std::cout << "max_dim = " << max_dim << "\n"; + std::cout << "Expand the simplex tree in " + << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + + std::cout << "Information of the Simplex Tree: " << std::endl; + std::cout << " Number of vertices = " << st.num_vertices() << " "; + std::cout << " Number of simplices = " << st.num_simplices() << std::endl; + std::cout << std::endl << std::endl; + + std::cout << "Iterator on vertices: "; + for (auto vertex : st.complex_vertex_range()) { + std::cout << vertex << " "; + } + + std::cout << std::endl; + + std::cout << std::endl << std::endl; + + std::cout << "Iterator on simplices: " << std::endl; + for (auto simplex : st.complex_simplex_range()) { + std::cout << " "; + for (auto vertex : st.simplex_vertex_range(simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } + + std::cout << std::endl << std::endl; + + std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } + + std::cout << std::endl << std::endl; + + std::cout << "Iterator on Simplices in the filtration, and their boundary simplices:" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + std::cout << " " << "[" << st.filtration(f_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + + for (auto b_simplex : st.boundary_simplex_range(f_simplex)) { + std::cout << " " << "[" << st.filtration(b_simplex) << "] "; + for (auto vertex : st.simplex_vertex_range(b_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } + } + return 0; +} diff --git a/example/Skeleton_blocker/CMakeLists.txt b/example/Skeleton_blocker/CMakeLists.txt new file mode 100644 index 00000000..cc7f37f3 --- /dev/null +++ b/example/Skeleton_blocker/CMakeLists.txt @@ -0,0 +1,12 @@ +cmake_minimum_required(VERSION 2.6) +project(Skeleton_blocker_examples) + +add_executable(SkeletonBlockerFromSimplices Skeleton_blocker_from_simplices.cpp) +add_executable(SkeletonBlockerIteration Skeleton_blocker_iteration.cpp) +add_executable(SkeletonBlockerLink Skeleton_blocker_link.cpp) + +target_link_libraries(SkeletonBlockerIteration ${Boost_TIMER_LIBRARY} ${Boost_SYSTEM_LIBRARY}) + +add_test(SkeletonBlockerFromSimplices ${CMAKE_CURRENT_BINARY_DIR}/SkeletonBlockerFromSimplices) +add_test(SkeletonBlockerIteration ${CMAKE_CURRENT_BINARY_DIR}/SkeletonBlockerIteration) +add_test(SkeletonBlockerLink ${CMAKE_CURRENT_BINARY_DIR}/SkeletonBlockerLink) diff --git a/example/Skeleton_blocker/Skeleton_blocker_from_simplices.cpp b/example/Skeleton_blocker/Skeleton_blocker_from_simplices.cpp new file mode 100644 index 00000000..171f35f2 --- /dev/null +++ b/example/Skeleton_blocker/Skeleton_blocker_from_simplices.cpp @@ -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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 <gudhi/Skeleton_blocker.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string> +#include <fstream> +#include <sstream> +#include <vector> + +using namespace std; +using namespace Gudhi; +using namespace skeleton_blocker; + +typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; +typedef Complex::Vertex_handle Vertex_handle; +typedef Complex::Simplex Simplex; + +int main(int argc, char *argv[]) { + std::vector<Simplex> simplices; + + // add 4 triangles of a tetrahedron 0123 + simplices.push_back(Simplex(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(1), Vertex_handle(2), Vertex_handle(3))); + simplices.push_back(Simplex(Vertex_handle(3), Vertex_handle(0), Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(3), Vertex_handle(0), Vertex_handle(1))); + + // get complex from top faces + Complex complex(make_complex_from_top_faces<Complex>(simplices.begin(), simplices.end())); + + + std::cout << "Simplices:" << std::endl; + for (const Simplex & s : complex.complex_simplex_range()) + std::cout << s << " "; + std::cout << std::endl; + + // One blocker as simplex 0123 is not in the complex but all its proper faces are. + std::cout << "Blockers: " << complex.blockers_to_string() << std::endl; + + // now build a complex from its full list of simplices + simplices.clear(); + simplices.push_back(Simplex(Vertex_handle(0))); + simplices.push_back(Simplex(Vertex_handle(1))); + simplices.push_back(Simplex(Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(0), Vertex_handle(1))); + simplices.push_back(Simplex(Vertex_handle(1), Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(2), Vertex_handle(0))); + complex = Complex(simplices.begin(), simplices.end()); + + std::cout << "Simplices:" << std::endl; + for (const Simplex & s : complex.complex_simplex_range()) + std::cout << s << " "; + std::cout << std::endl; + + // One blocker as simplex 012 is not in the complex but all its proper faces are. + std::cout << "Blockers: " << complex.blockers_to_string() << std::endl; + + return EXIT_SUCCESS; +} diff --git a/example/Skeleton_blocker/Skeleton_blocker_iteration.cpp b/example/Skeleton_blocker/Skeleton_blocker_iteration.cpp new file mode 100644 index 00000000..8d9d1a67 --- /dev/null +++ b/example/Skeleton_blocker/Skeleton_blocker_iteration.cpp @@ -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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 <gudhi/Skeleton_blocker.h> + +#include <boost/timer/timer.hpp> + +#include <stdio.h> +#include <stdlib.h> +#include <string> +#include <fstream> +#include <sstream> + + +using namespace std; +using namespace Gudhi; +using namespace skeleton_blocker; + +typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; +typedef Complex::Vertex_handle Vertex_handle; +typedef Complex::Simplex Simplex; + +Complex build_complete_complex(int n) { + // build a full complex with n vertices and 2^n-1 simplices + Complex complex; + for (int i = 0; i < n; i++) + complex.add_vertex(); + for (int i = 0; i < n; i++) + for (int j = 0; j < i; j++) + complex.add_edge_without_blockers(Vertex_handle(i), Vertex_handle(j)); + return complex; +} + +int main(int argc, char *argv[]) { + boost::timer::auto_cpu_timer t; + + const int n = 15; + + // build a full complex with n vertices and 2^n-1 simplices + Complex complex(build_complete_complex(n)); + + // this is just to illustrate iterators, to count number of vertices + // or edges, complex.num_vertices() and complex.num_edges() are + // more appropriated! + unsigned num_vertices = 0; + for (auto v : complex.vertex_range()) { + std::cout << "Vertex " << v << std::endl; + ++num_vertices; + } + + // such loop can also be done directly with distance as iterators are STL compliant + auto edges = complex.edge_range(); + unsigned num_edges = std::distance(edges.begin(), edges.end()); + + unsigned euler = 0; + unsigned num_simplices = 0; + // we use a reference to a simplex instead of a copy + // value here because a simplex is a set of integers + // and copying it cost time + for (const Simplex & s : complex.complex_simplex_range()) { + ++num_simplices; + if (s.dimension() % 2 == 0) + euler += 1; + else + euler -= 1; + } + std::cout << "Saw " << num_vertices << " vertices, " << num_edges << " edges and " << num_simplices << " simplices" + << std::endl; + std::cout << "The Euler Characteristic is " << euler << std::endl; + return EXIT_SUCCESS; +} diff --git a/example/Skeleton_blocker/Skeleton_blocker_link.cpp b/example/Skeleton_blocker/Skeleton_blocker_link.cpp new file mode 100644 index 00000000..1f937170 --- /dev/null +++ b/example/Skeleton_blocker/Skeleton_blocker_link.cpp @@ -0,0 +1,71 @@ +/* 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): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (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 <gudhi/Skeleton_blocker.h> + +#include <stdio.h> +#include <stdlib.h> +#include <string> +#include <fstream> +#include <sstream> + +using namespace std; +using namespace Gudhi; +using namespace skeleton_blocker; + +typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; +typedef Complex::Vertex_handle Vertex_handle; +typedef Complex::Root_vertex_handle Root_vertex_handle; +typedef Complex::Simplex Simplex; + +int main(int argc, char *argv[]) { + // build a full complex with 4 vertices and 2^4-1 simplices + + // Create a complex with four vertices (0,1,2,3) + Complex complex; + + // Add a tetrahedron to this complex + Simplex tetrahedron(Vertex_handle(0), Vertex_handle(1), Vertex_handle(2), Vertex_handle(3)); + complex.add_simplex(tetrahedron); + + cout << "complex:" << complex.to_string() << endl; + + // build the link of vertex 1, eg a triangle {0,2,3} + auto link = complex.link(Vertex_handle(1)); + cout << "link:" << link.to_string() << endl; + + // Internally link is a subcomplex of 'complex' and its vertices are stored in a vector. + // They can be accessed via Vertex_handle(x) where x is an index of the vector. + // In that example, link has three vertices and thus it contains only + // Vertex_handle(0),Vertex_handle(1) and Vertex_handle(2) are). + for (int i = 0; i < 5; ++i) + cout << "link.contains_vertex(Vertex_handle(" << i << ")):" << link.contains_vertex(Vertex_handle(i)) << endl; + cout << endl; + + // To access to the initial vertices eg (0,1,2,3,4), Root_vertex_handle must be used. + // For instance, to test if the link contains the vertex that was labeled i: + for (int i = 0; i < 5; ++i) + cout << "link.contains_vertex(Root_vertex_handle(" << i << ")):" << + link.contains_vertex(Root_vertex_handle(i)) << endl; + + return EXIT_SUCCESS; +} diff --git a/example/Witness_complex/CMakeLists.txt b/example/Witness_complex/CMakeLists.txt new file mode 100644 index 00000000..4d67e0d0 --- /dev/null +++ b/example/Witness_complex/CMakeLists.txt @@ -0,0 +1,16 @@ +cmake_minimum_required(VERSION 2.6) +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) + +if(CGAL_FOUND) + if (NOT CGAL_VERSION VERSION_LESS 4.6.0) + if (EIGEN3_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) + endif(EIGEN3_FOUND) + endif (NOT CGAL_VERSION VERSION_LESS 4.6.0) +endif() diff --git a/example/Witness_complex/generators.h b/example/Witness_complex/generators.h new file mode 100644 index 00000000..ac445261 --- /dev/null +++ b/example/Witness_complex/generators.h @@ -0,0 +1,147 @@ +/* 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 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; +typedef std::vector<Point_d> Point_Vector; +typedef CGAL::Random_points_in_cube_d<Point_d> Random_cube_iterator; +typedef CGAL::Random_points_in_ball_d<Point_d> Random_point_iterator; + +/** + * \brief Rock age method of reading off file + * + */ +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; + } + std::string line; + double x; + // Line OFF. No need in it + 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; + } + // 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)); + } + in_file.close(); +} + +/** + * \brief Customized version of read_points + * which takes into account a possible nbP first line + * + */ +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; + } + 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); + } + in_file.close(); +} + +/** \brief Generate points on a grid in a cube of side 2 + * having {+-1}^D as vertices and insert them in W. + * The grid has "width" points on each side. + * If torus is true then it is supposed that the cube represents + * 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) { + 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); + } +} + +/** \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) { + Random_cube_iterator rp(dim, 1.0); + 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); + for (int i = 0; i < nbP; i++) + W.push_back(*rp++); +} + +#endif // EXAMPLE_WITNESS_COMPLEX_GENERATORS_H_ diff --git a/example/Witness_complex/witness_complex_from_file.cpp b/example/Witness_complex/witness_complex_from_file.cpp new file mode 100644 index 00000000..53207ad2 --- /dev/null +++ b/example/Witness_complex/witness_complex_from_file.cpp @@ -0,0 +1,100 @@ +/* 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 <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 <iostream> +#include <fstream> +#include <ctime> +#include <string> +#include <vector> + +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"; + return 0; + } + + std::string file_name = argv[1]; + int nbL = atoi(argv[2]); + clock_t start, end; + + // Construct the Simplex Tree + Gudhi::Simplex_tree<> simplex_tree; + + // Read the point file + Point_Vector point_vector; + 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"; + + // Choose landmarks + start = clock(); + std::vector<std::vector< int > > knn; + Gudhi::witness_complex::landmark_choice_by_random_point(point_vector, nbL, knn); + end = clock(); + std::cout << "Landmark choice for " << nbL << " landmarks took " + << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + + // Compute witness complex + start = clock(); + Gudhi::witness_complex::witness_complex(knn, nbL, point_vector[0].size(), simplex_tree); + end = clock(); + std::cout << "Witness complex took " + << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; +} diff --git a/example/Witness_complex/witness_complex_sphere.cpp b/example/Witness_complex/witness_complex_sphere.cpp new file mode 100644 index 00000000..b26c9f36 --- /dev/null +++ b/example/Witness_complex/witness_complex_sphere.cpp @@ -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/>. + */ +#define BOOST_PARAMETER_MAX_ARITY 12 + + +#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 <iostream> +#include <fstream> +#include <ctime> +#include <utility> +#include <string> +#include <vector> + +#include "generators.h" + +/** 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) { + std::ofstream ofs(filename, std::ofstream::out); + 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] + << " number_of_landmarks \n"; + return 0; + } + + int number_of_landmarks = atoi(argv[1]); + clock_t start, end; + + // Construct the Simplex Tree + Gudhi::Simplex_tree<> simplex_tree; + + std::vector< std::pair<int, double> > l_time; + + // Read the point file + for (int nbP = 500; nbP < 10000; nbP += 500) { + Point_Vector point_vector; + 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; + Gudhi::witness_complex::landmark_choice_by_random_point(point_vector, number_of_landmarks, knn); + + // Compute witness complex + Gudhi::witness_complex::witness_complex(knn, number_of_landmarks, point_vector[0].size(), simplex_tree); + end = clock(); + double time = static_cast<double>(end - start) / CLOCKS_PER_SEC; + std::cout << "Witness complex for " << number_of_landmarks << " landmarks took " + << time << " s. \n"; + std::cout << "Number of simplices is: " << simplex_tree.num_simplices() << "\n"; + l_time.push_back(std::make_pair(nbP, time)); + } + write_data(l_time, "w_time.dat"); +} diff --git a/example/common/CGAL_3D_points_off_reader.cpp b/example/common/CGAL_3D_points_off_reader.cpp new file mode 100644 index 00000000..d48bb17d --- /dev/null +++ b/example/common/CGAL_3D_points_off_reader.cpp @@ -0,0 +1,41 @@ +#include <gudhi/Points_3D_off_io.h> + +#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> + +#include <iostream> +#include <string> +#include <vector> + +using Kernel = CGAL::Exact_predicates_inexact_constructions_kernel; +using Point_3 = Kernel::Point_3; + +void usage(char * const progName) { + std::cerr << "Usage: " << progName << " inputFile.off" << std::endl; + exit(-1); +} + +int main(int argc, char **argv) { + if (argc != 2) { + std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; + usage(argv[0]); + } + + std::string offInputFile(argv[1]); + // Read the OFF file (input file name given as parameter) and triangulate points + Gudhi::Points_3D_off_reader<Point_3> off_reader(offInputFile); + // Check the read operation was correct + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << offInputFile << std::endl; + usage(argv[0]); + } + + // Retrieve the triangulation + std::vector<Point_3> point_cloud = off_reader.get_point_cloud(); + + int n {0}; + for (auto point : point_cloud) { + ++n; + std::cout << "Point[" << n << "] = (" << point[0] << ", " << point[1] << ", " << point[2] << ")\n"; + } + return 0; +} diff --git a/example/common/CGAL_points_off_reader.cpp b/example/common/CGAL_points_off_reader.cpp new file mode 100644 index 00000000..d1ca166d --- /dev/null +++ b/example/common/CGAL_points_off_reader.cpp @@ -0,0 +1,46 @@ +#include <gudhi/Points_off_io.h> + +// For CGAL points type in dimension d +// cf. http://doc.cgal.org/latest/Kernel_d/classCGAL_1_1Point__d.html +#include <CGAL/Epick_d.h> + +#include <iostream> +#include <string> +#include <vector> + +using Kernel = CGAL::Epick_d< CGAL::Dynamic_dimension_tag >; +using Point_d = Kernel::Point_d; + +void usage(char * const progName) { + std::cerr << "Usage: " << progName << " inputFile.off" << std::endl; + exit(-1); +} + +int main(int argc, char **argv) { + if (argc != 2) { + std::cerr << "Error: Number of arguments (" << argc << ") is not correct" << std::endl; + usage(argv[0]); + } + + std::string offInputFile(argv[1]); + // Read the OFF file (input file name given as parameter) and triangulate points + Gudhi::Points_off_reader<Point_d> off_reader(offInputFile); + // Check the read operation was correct + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << offInputFile << std::endl; + usage(argv[0]); + } + + // Retrieve the triangulation + std::vector<Point_d> point_cloud = off_reader.get_point_cloud(); + + int n {0}; + for (auto point : point_cloud) { + std::cout << "Point[" << n << "] = "; + for (int i {0}; i < point.dimension(); i++) + std::cout << point[i] << " "; + std::cout << "\n"; + ++n; + } + return 0; +} diff --git a/example/common/CMakeLists.txt b/example/common/CMakeLists.txt new file mode 100644 index 00000000..0da3dcc0 --- /dev/null +++ b/example/common/CMakeLists.txt @@ -0,0 +1,17 @@ +cmake_minimum_required(VERSION 2.6) +project(Common_examples) + +# need CGAL 4.7 +if(CGAL_FOUND) + add_executable ( cgal3Doffreader CGAL_3D_points_off_reader.cpp ) + target_link_libraries(cgal3Doffreader ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + add_test(cgal3Doffreader ${CMAKE_CURRENT_BINARY_DIR}/cgal3Doffreader ${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off) + + if (NOT CGAL_VERSION VERSION_LESS 4.7.0) + if (EIGEN3_FOUND) + add_executable ( cgaloffreader CGAL_points_off_reader.cpp ) + target_link_libraries(cgaloffreader ${Boost_SYSTEM_LIBRARY} ${CGAL_LIBRARY}) + add_test(cgaloffreader ${CMAKE_CURRENT_BINARY_DIR}/cgaloffreader ${CMAKE_SOURCE_DIR}/data/points/alphacomplexdoc.off) + endif(EIGEN3_FOUND) + endif (NOT CGAL_VERSION VERSION_LESS 4.7.0) +endif() diff --git a/example/common/cgal3Doffreader_result.txt b/example/common/cgal3Doffreader_result.txt new file mode 100644 index 00000000..f992c8e3 --- /dev/null +++ b/example/common/cgal3Doffreader_result.txt @@ -0,0 +1,8 @@ +Point[1] = (0.959535, -0.418347, 0.302237) +Point[2] = (2.16795, 1.85348, -0.52312) +Point[3] = (-2.38753, -1.50911, -0.565889) +Point[4] = (-2.70428, -1.25688, 0.188394) +Point[5] = (-1.22932, -1.64337, -0.998632) +... +Point[300] = (-0.56244, 2.6018, -0.749591) + diff --git a/example/common/cgaloffreader_result.txt b/example/common/cgaloffreader_result.txt new file mode 100644 index 00000000..1deb8dbd --- /dev/null +++ b/example/common/cgaloffreader_result.txt @@ -0,0 +1,7 @@ +Point[0] = 1 1 +Point[1] = 7 0 +Point[2] = 4 6 +Point[3] = 9 6 +Point[4] = 0 14 +Point[5] = 2 19 +Point[6] = 9 17 |