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

5 files changed, 80 insertions, 22 deletions

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 <tuple>
 #include <algorithm>
 #include <string>
+#include <stdexcept>  // 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<Simplex_key>::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<MyOptions>;
+using Mini_simplex_tree = Gudhi::Simplex_tree<MiniSTOptions>;
 using Mini_st_persistence =
     Gudhi::persistent_cohomology::Persistent_cohomology<Mini_simplex_tree, Gudhi::persistent_cohomology::Field_Zp>;
 
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 <utility> // std::pair, std::make_pair
 #include <cmath> // float comparison
 #include <limits>
+#include <cstdint>  // 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 <CODE>std::numeric_limits<std::uint8_t>::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<MiniSTOptions>;
+using Mini_st_persistence =
+    Gudhi::persistent_cohomology::Persistent_cohomology<Mini_simplex_tree, Gudhi::persistent_cohomology::Field_Zp>;
+
+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<MiniSTOptions::Simplex_key>::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<MiniSTOptions::Simplex_key>::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 <limits>  // Inf
 #include <initializer_list>
 #include <algorithm>  // for std::max
+#include <cstdint>  // for std::uint32_t
 
 namespace Gudhi {
 /** \defgroup simplex_tree Filtered Complexes
@@ -1297,25 +1298,31 @@ std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) {
   return is;
 }
 
-/// Model of SimplexTreeOptions.
+/** Model of SimplexTreeOptions.
+ * 
+ * Maximum number of simplices to compute persistence is <CODE>std::numeric_limits<std::uint32_t>::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 <CODE>std::numeric_limits<std::uint32_t>::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 <a target="_blank" href="http://www.boost.org/">Boost</a> 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 <a href="examples.html">here</a>.
+ * 
+ * \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</a>
  * 
  * \subsection eigen3 Eigen3:
+ * The \ref alpha_complex data structure and few examples requires
  * <a target="_blank" href="http://eigen.tuxfamily.org/">Eigen3</a> is a C++ template library for linear algebra:
  * matrices, vectors, numerical solvers, and related algorithms.
  * 
@@ -270,19 +287,6 @@
  * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html">
  * Persistent_cohomology/custom_persistence_sort.cpp</a>
  * 
- * \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 <a href="examples.html">here</a>.
- * 
- * \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