Backmerge from trunk

git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/tbb@953 636b058d-ea47-450e-bf9e-a15bfbe3eedb

Former-commit-id: 06624ae4ed4031c7bae56e0b8fa305a318b934bc

11 files changed, 126 insertions, 28 deletions

diff --git a/src/Persistent_cohomology/concept/FilteredComplex.h b/src/Persistent_cohomology/concept/FilteredComplex.h
index 1834903b..e124d524 100644
--- a/src/Persistent_cohomology/concept/FilteredComplex.h
+++ b/src/Persistent_cohomology/concept/FilteredComplex.h
@@ -65,9 +65,9 @@ struct FilteredComplex
   Simplex_key              key      ( Simplex_handle sh );
 /** \brief Returns the simplex associated to a key.
   *
-  * If key is different from null_key(), there must be a unique 
-  * simplex having this key. */  
-  Simplex_handle           simplex  ( Simplex_key key );
+  * If key is different from null_key(), returns the simplex that
+  * has index idx in the filtration. */
+  Simplex_handle           simplex  ( Simplex_key idx );
 /** \brief Assign a key to a simplex. */
   void                     assign_key(Simplex_handle sh, Simplex_key key);
  
diff --git a/src/Persistent_cohomology/example/CMakeLists.txt b/src/Persistent_cohomology/example/CMakeLists.txt
index ea69352e..50d10025 100644
--- a/src/Persistent_cohomology/example/CMakeLists.txt
+++ b/src/Persistent_cohomology/example/CMakeLists.txt
@@ -5,6 +5,10 @@ project(GUDHIExPersCohom)
 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_test(plain_homology ${CMAKE_CURRENT_BINARY_DIR}/plain_homology)
+
 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_test(persistence_from_simple_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/persistence_from_simple_simplex_tree 1 0)
diff --git a/src/Persistent_cohomology/example/alpha_shapes_persistence.cpp b/src/Persistent_cohomology/example/alpha_shapes_persistence.cpp
index 6d5eebcf..92c0b065 100644
--- a/src/Persistent_cohomology/example/alpha_shapes_persistence.cpp
+++ b/src/Persistent_cohomology/example/alpha_shapes_persistence.cpp
@@ -66,7 +66,8 @@ typedef Alpha_shape_3::Edge Edge_3;
 typedef std::list<Alpha_shape_3::Vertex_handle> Vertex_list;
 
 // gudhi type definition
-typedef Simplex_tree<>::Vertex_handle Simplex_tree_vertex;
+typedef Simplex_tree<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;
@@ -184,7 +185,7 @@ int main(int argc, char * const argv[]) {
 
   // Loop on objects vector
   Vertex_list vertex_list;
-  Simplex_tree<> simplex_tree;
+  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;
@@ -281,7 +282,7 @@ int main(int argc, char * const argv[]) {
 
   std::cout << "Simplex_tree dim: " << simplex_tree.dimension() << std::endl;
   // Compute the persistence diagram of the complex
-  Persistent_cohomology< Simplex_tree<>, Field_Zp > pcoh(simplex_tree);
+  Persistent_cohomology< ST, Field_Zp > pcoh(simplex_tree);
   // initializes the coefficient field for homology
   pcoh.init_coefficients(coeff_field_characteristic);
 
diff --git a/src/Persistent_cohomology/example/performance_rips_persistence.cpp b/src/Persistent_cohomology/example/performance_rips_persistence.cpp
index fc48d6b1..b4d282ac 100644
--- a/src/Persistent_cohomology/example/performance_rips_persistence.cpp
+++ b/src/Persistent_cohomology/example/performance_rips_persistence.cpp
@@ -86,7 +86,7 @@ int main(int argc, char * argv[]) {
   std::cout << "Compute Rips graph in " << elapsed_sec << " ms.\n";
 
   // Construct the Rips complex in a Simplex Tree
-  Simplex_tree<> st;
+  Simplex_tree<Simplex_tree_options_fast_persistence> st;
   start = std::chrono::system_clock::now();
 
   // insert the proximity graph in the simplex tree
diff --git a/src/Persistent_cohomology/example/persistence_from_file.cpp b/src/Persistent_cohomology/example/persistence_from_file.cpp
index 8eb8d0f3..67235467 100644
--- a/src/Persistent_cohomology/example/persistence_from_file.cpp
+++ b/src/Persistent_cohomology/example/persistence_from_file.cpp
@@ -54,7 +54,7 @@ int main(int argc, char * argv[]) {
       << std::endl;
   std::cout << "     - p=" << p << " - min_persistence=" << min_persistence << std::endl;
 
-  // Construct the Rips complex in a Simplex Tree
+  // Read the list of simplices from a file.
   Simplex_tree<> simplex_tree;
 
   std::ifstream simplex_tree_stream(simplex_tree_file);
diff --git a/src/Persistent_cohomology/example/plain_homology.cpp b/src/Persistent_cohomology/example/plain_homology.cpp
new file mode 100644
index 00000000..0a692717
--- /dev/null
+++ b/src/Persistent_cohomology/example/plain_homology.cpp
@@ -0,0 +1,84 @@
+/*    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>
+
+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;
+};
+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();
+}
diff --git a/src/Persistent_cohomology/example/rips_multifield_persistence.cpp b/src/Persistent_cohomology/example/rips_multifield_persistence.cpp
index 5277bf7a..c5cd775d 100644
--- a/src/Persistent_cohomology/example/rips_multifield_persistence.cpp
+++ b/src/Persistent_cohomology/example/rips_multifield_persistence.cpp
@@ -68,7 +68,8 @@ int main(int argc, char * argv[]) {
                                                , euclidean_distance<Point_t>);
 
   // Construct the Rips complex in a Simplex Tree
-  Simplex_tree<> st;
+  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
@@ -78,7 +79,7 @@ int main(int argc, char * argv[]) {
   st.initialize_filtration();
 
   // Compute the persistence diagram of the complex
-  Persistent_cohomology< Simplex_tree<>, Multi_field > pcoh(st);
+  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
diff --git a/src/Persistent_cohomology/example/rips_persistence.cpp b/src/Persistent_cohomology/example/rips_persistence.cpp
index 9b1ef42f..2d926a0d 100644
--- a/src/Persistent_cohomology/example/rips_persistence.cpp
+++ b/src/Persistent_cohomology/example/rips_persistence.cpp
@@ -65,7 +65,8 @@ int main(int argc, char * argv[]) {
                                                , euclidean_distance<Point_t>);
 
   // Construct the Rips complex in a Simplex Tree
-  Simplex_tree<> st;
+  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
@@ -78,7 +79,7 @@ int main(int argc, char * argv[]) {
   st.initialize_filtration();
 
   // Compute the persistence diagram of the complex
-  persistent_cohomology::Persistent_cohomology< Simplex_tree<>, Field_Zp > pcoh(st);
+  persistent_cohomology::Persistent_cohomology<ST, Field_Zp > pcoh(st);
   // initializes the coefficient field for homology
   pcoh.init_coefficients(p);
 
diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h
index d096792f..643b810c 100644
--- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h
+++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h
@@ -27,7 +27,6 @@
 #include <gudhi/Persistent_cohomology/Field_Zp.h>
 #include <gudhi/Simple_object_pool.h>
 
-#include <boost/tuple/tuple.hpp>
 #include <boost/intrusive/set.hpp>
 #include <boost/pending/disjoint_sets.hpp>
 #include <boost/intrusive/list.hpp>
@@ -223,7 +222,7 @@ class Persistent_cohomology {
 // Sparse column type for the annotation of the boundary of an element.
   typedef std::vector<std::pair<Simplex_key, Arith_element> > A_ds_type;
 // Persistent interval type. The Arith_element field is used for the multi-field framework.
-  typedef boost::tuple<Simplex_handle, Simplex_handle, Arith_element> Persistent_interval;
+  typedef std::tuple<Simplex_handle, Simplex_handle, Arith_element> Persistent_interval;
 
   /** \brief Initializes the Persistent_cohomology class.
    *
@@ -431,9 +430,12 @@ class Persistent_cohomology {
       std::map<Simplex_key, Arith_element> & map_a_ds, Simplex_handle sigma,
       int dim_sigma) {
     // traverses the boundary of sigma, keeps track of the annotation vectors,
-    // with multiplicity, in a map.
-    std::map<Column *, int> annotations_in_boundary;
-    std::pair<typename std::map<Column *, int>::iterator, bool> result_insert_bound;
+    // with multiplicity. We used to sum the coefficients directly in
+    // annotations_in_boundary by using a map, we now do it later.
+    typedef std::pair<Column *, int> annotation_t;
+    // Danger: not thread-safe!
+    static std::vector<annotation_t> annotations_in_boundary;
+    annotations_in_boundary.clear();
     int sign = 1 - 2 * (dim_sigma % 2);  // \in {-1,1} provides the sign in the
                                          // alternate sum in the boundary.
     Simplex_key key;
@@ -445,22 +447,29 @@ class Persistent_cohomology {
         // Find its annotation vector
         curr_col = ds_repr_[dsets_.find_set(key)];
         if (curr_col != NULL) {  // and insert it in annotations_in_boundary with multyiplicative factor "sign".
-          result_insert_bound = annotations_in_boundary.insert(std::pair<Column *, int>(curr_col, sign));
-          if (!(result_insert_bound.second)) {
-            result_insert_bound.first->second += sign;
-          }
+	  annotations_in_boundary.emplace_back(curr_col, sign);
         }
       }
       sign = -sign;
     }
+    // Place identical annotations consecutively so we can easily sum their multiplicities.
+    std::sort(annotations_in_boundary.begin(), annotations_in_boundary.end(),
+	[](annotation_t const& a, annotation_t const& b) { return a.first < b.first; });
+
     // Sum the annotations with multiplicity, using a map<key,coeff>
     // to represent a sparse vector.
     std::pair<typename std::map<Simplex_key, Arith_element>::iterator, bool> result_insert_a_ds;
 
-    for (auto ann_ref : annotations_in_boundary) {
-      if (ann_ref.second != coeff_field_.additive_identity()) {  // For all columns in the boundary,
-        for (auto cell_ref : ann_ref.first->col_) {  // insert every cell in map_a_ds with multiplicity
-          Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, ann_ref.second);  // coefficient * multiplicity
+    for (auto ann_it = annotations_in_boundary.begin(); ann_it != annotations_in_boundary.end(); /**/) {
+      Column* col = ann_it->first;
+      int mult = ann_it->second;
+      while (++ann_it != annotations_in_boundary.end() && ann_it->first == col) {
+	mult += ann_it->second;
+      }
+      // The following test is just a heuristic, it is not required, and it is fine that is misses p == 0.
+      if (mult != coeff_field_.additive_identity()) {  // For all columns in the boundary,
+        for (auto cell_ref : col->col_) {  // insert every cell in map_a_ds with multiplicity
+          Arith_element w_y = coeff_field_.times(cell_ref.coefficient_, mult);  // coefficient * multiplicity
 
           if (w_y != coeff_field_.additive_identity()) {  // if != 0
             result_insert_a_ds = map_a_ds.insert(std::pair<Simplex_key, Arith_element>(cell_ref.key_, w_y));
diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h
index 0591fc95..38bc08d1 100644
--- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h
+++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h
@@ -81,8 +81,7 @@ class Multi_field {
     // set m to primorial(bound_prime)
     prod_characteristics_ = 1;
     for (auto p : primes_) {
-      mpz_mul_ui(prod_characteristics_.get_mpz_t(),
-                 prod_characteristics_.get_mpz_t(), p);
+      prod_characteristics_ *= p;
     }
 
     // Uvect_
diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Persistent_cohomology_column.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Persistent_cohomology_column.h
index 612658e6..5deb2d88 100644
--- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Persistent_cohomology_column.h
+++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Persistent_cohomology_column.h
@@ -23,7 +23,6 @@
 #ifndef PERSISTENT_COHOMOLOGY_PERSISTENT_COHOMOLOGY_COLUMN_H_
 #define PERSISTENT_COHOMOLOGY_PERSISTENT_COHOMOLOGY_COLUMN_H_
 
-#include <boost/tuple/tuple.hpp>
 #include <boost/intrusive/set.hpp>
 #include <boost/intrusive/list.hpp>