From 9b4c31ef855bf5c98718675a9caab52e8d8514e7 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 5 Aug 2016 09:58:11 +0000 Subject: Fix the 3 billions of simplices limit Add some comment and documentation about the new limit (4 billions) Rephrase third party library installation documentation git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/3billions_simplices_fix@1420 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 95b20677e455b61578da74aabbd3764b4a27816d --- .../include/gudhi/Persistent_cohomology.h | 5 +++ .../test/betti_numbers_unit_test.cpp | 4 +-- .../test/persistent_cohomology_unit_test.cpp | 42 ++++++++++++++++++++++ src/Simplex_tree/include/gudhi/Simplex_tree.h | 19 ++++++---- src/common/doc/main_page.h | 32 +++++++++-------- 5 files changed, 80 insertions(+), 22 deletions(-) (limited to 'src') diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index a7d1e463..d3da812e 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -41,6 +41,7 @@ #include #include #include +#include // for std::out_of_range namespace Gudhi { @@ -89,6 +90,7 @@ class Persistent_cohomology { * * @param[in] cpx Complex for which the persistent homology is computed. * cpx is a model of FilteredComplex + * @exception std::out_of_range In case the number of simplices is more than Simplex_key type numeric limit. */ explicit Persistent_cohomology(Complex_ds& cpx) : cpx_(&cpx), @@ -106,6 +108,9 @@ class Persistent_cohomology { interval_length_policy(&cpx, 0), column_pool_(), // memory pools for the CAM cell_pool_() { + if (cpx_->num_simplices() > std::numeric_limits::max()) { + throw std::out_of_range ("The number of simplices is more than Simplex_key type numeric limit."); + } Simplex_key idx_fil = 0; for (auto sh : cpx_->filtration_simplex_range()) { cpx_->assign_key(sh, idx_fil); diff --git a/src/Persistent_cohomology/test/betti_numbers_unit_test.cpp b/src/Persistent_cohomology/test/betti_numbers_unit_test.cpp index a4e00b45..40221005 100644 --- a/src/Persistent_cohomology/test/betti_numbers_unit_test.cpp +++ b/src/Persistent_cohomology/test/betti_numbers_unit_test.cpp @@ -12,7 +12,7 @@ #include "gudhi/Simplex_tree.h" #include "gudhi/Persistent_cohomology.h" -struct MyOptions : Gudhi::Simplex_tree_options_full_featured { +struct MiniSTOptions : Gudhi::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 @@ -21,7 +21,7 @@ struct MyOptions : Gudhi::Simplex_tree_options_full_featured { typedef short Vertex_handle; }; -using Mini_simplex_tree = Gudhi::Simplex_tree; +using Mini_simplex_tree = Gudhi::Simplex_tree; using Mini_st_persistence = Gudhi::persistent_cohomology::Persistent_cohomology; diff --git a/src/Persistent_cohomology/test/persistent_cohomology_unit_test.cpp b/src/Persistent_cohomology/test/persistent_cohomology_unit_test.cpp index 5c54ed5f..530e7092 100644 --- a/src/Persistent_cohomology/test/persistent_cohomology_unit_test.cpp +++ b/src/Persistent_cohomology/test/persistent_cohomology_unit_test.cpp @@ -4,6 +4,7 @@ #include // std::pair, std::make_pair #include // float comparison #include +#include // for std::uint8_t #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MODULE "persistent_cohomology" @@ -172,3 +173,44 @@ BOOST_AUTO_TEST_CASE( rips_persistent_cohomology_single_field_dim_5 ) // std::string str_rips_persistence = test_rips_persistence(6, 0); // TODO(VR): division by zero // std::string str_rips_persistence = test_rips_persistence(0, 0); + +/** SimplexTree minimal options to test the limits. + * + * Maximum number of simplices to compute persistence is std::numeric_limits::max()<\CODE> = 256.*/ +struct MiniSTOptions { + typedef linear_indexing_tag Indexing_tag; + typedef short Vertex_handle; + typedef double Filtration_value; + typedef std::uint8_t Simplex_key; + static const bool store_key = true; + static const bool store_filtration = false; + static const bool contiguous_vertices = false; +}; + +using Mini_simplex_tree = Gudhi::Simplex_tree; +using Mini_st_persistence = + Gudhi::persistent_cohomology::Persistent_cohomology; + +BOOST_AUTO_TEST_CASE( persistence_constructor_exception ) +{ + Mini_simplex_tree st; + + // To make number of simplices = 255 + const short simplex_0[] = {0, 1, 2, 3, 4, 5, 6, 7}; + st.insert_simplex_and_subfaces(simplex_0); + // FIXME: Remove this line + st.set_dimension(8); + + // Sort the simplices in the order of the filtration + st.initialize_filtration(); + + BOOST_CHECK(st.num_simplices() <= std::numeric_limits::max()); + // Class for homology computation + BOOST_CHECK_NO_THROW(Mini_st_persistence pcoh(st)); + + st.insert_simplex({8}); + BOOST_CHECK(st.num_simplices() > std::numeric_limits::max()); + // Class for homology computation + BOOST_CHECK_THROW(Mini_st_persistence pcoh2(st), std::out_of_range); + +} diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 65ead001..91b27f28 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -48,6 +48,7 @@ #include // Inf #include #include // for std::max +#include // for std::uint32_t namespace Gudhi { /** \defgroup simplex_tree Filtered Complexes @@ -1297,25 +1298,31 @@ std::istream& operator>>(std::istream & is, Simplex_tree & st) { return is; } -/// Model of SimplexTreeOptions. +/** Model of SimplexTreeOptions. + * + * Maximum number of simplices to compute persistence is std::numeric_limits::max()<\CODE> + * (about 4 billions of simplices). */ struct Simplex_tree_options_full_featured { typedef linear_indexing_tag Indexing_tag; typedef int Vertex_handle; typedef double Filtration_value; - typedef int Simplex_key; + typedef std::uint32_t Simplex_key; static const bool store_key = true; static const bool store_filtration = true; static const bool contiguous_vertices = false; }; -/** Model of SimplexTreeOptions, faster than - `Simplex_tree_options_full_featured` but note the unsafe - `contiguous_vertices` option. */ +/** Model of SimplexTreeOptions, faster than `Simplex_tree_options_full_featured` but note the unsafe + * `contiguous_vertices` option. + * + * Maximum number of simplices to compute persistence is std::numeric_limits::max()<\CODE> + * (about 4 billions of simplices). */ + struct Simplex_tree_options_fast_persistence { typedef linear_indexing_tag Indexing_tag; typedef int Vertex_handle; typedef float Filtration_value; - typedef int Simplex_key; + typedef std::uint32_t Simplex_key; static const bool store_key = true; static const bool store_filtration = true; static const bool contiguous_vertices = true; diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index 2391e147..9146bed1 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -154,6 +154,7 @@ */ /*! \page installation Gudhi installation + * \tableofcontents * As Gudhi is a header only library, there is no need to install the library. * * Examples of Gudhi headers inclusion can be found in \ref demos. @@ -162,6 +163,20 @@ * The library uses c++11 and requires Boost with version 1.48.0 or * more recent. It is a multi-platform library and compiles on Linux, Mac OSX and Visual Studio 2015. * + * \subsection demos Demos and examples + * To build the demos and examples, run the following commands in a terminal: +\verbatim cd /path-to-gudhi/ +mkdir build +cd build/ +cmake .. +make \endverbatim + * A list of examples is available here. + * + * \subsection testsuites Test suites + * To test your build, run the following command in a terminal: + * \verbatim make test \endverbatim + * + * \section optionallibrary Optional third-party library * \subsection gmp GMP: * The multi-field persistent homology algorithm requires GMP which is a free library for arbitrary-precision * arithmetic, operating on signed integers, rational numbers, and floating point numbers. @@ -176,7 +191,8 @@ * Having GMP version 4.2 or higher installed is recommended. * * \subsection cgal CGAL: - * CGAL is a C++ library which provides easy access to efficient and reliable geometric algorithms. + * The \ref alpha_complex data structure and few examples requires CGAL, which is a C++ library which provides easy + * access to efficient and reliable geometric algorithms. * * Having CGAL version 4.4 or higher installed is recommended. The procedure to install this library according to * your operating system is detailed here http://doc.cgal.org/latest/Manual/installation.html @@ -205,6 +221,7 @@ * Persistent_cohomology/custom_persistence_sort.cpp * * \subsection eigen3 Eigen3: + * The \ref alpha_complex data structure and few examples requires * Eigen3 is a C++ template library for linear algebra: * matrices, vectors, numerical solvers, and related algorithms. * @@ -270,19 +287,6 @@ * \li * Persistent_cohomology/custom_persistence_sort.cpp * - * \subsection demos Demos and examples - * To build the demos and examples, run the following commands in a terminal: -\verbatim cd /path-to-gudhi/ -mkdir build -cd build/ -cmake .. -make \endverbatim - * A list of examples is available here. - * - * \subsection testsuites Test suites - * To test your build, run the following command in a terminal: - * \verbatim make test \endverbatim - * * \section Contributions Bug reports and contributions * Please help us improving the quality of the GUDHI library. You may report bugs or suggestions to: * \verbatim Contact: gudhi-users@lists.gforge.inria.fr \endverbatim -- cgit v1.2.3