Merge branch 'master' into toplex_map

9 files changed, 179 insertions, 32 deletions

diff --git a/src/common/benchmark/CMakeLists.txt b/src/common/benchmark/CMakeLists.txt
new file mode 100644
index 00000000..a3787d6e
--- /dev/null
+++ b/src/common/benchmark/CMakeLists.txt
@@ -0,0 +1,3 @@
+project(common_benchmark)
+
+add_executable(Graph_simplicial_complex_benchmark Graph_simplicial_complex_benchmark.cpp)
diff --git a/src/common/benchmark/Graph_simplicial_complex_benchmark.cpp b/src/common/benchmark/Graph_simplicial_complex_benchmark.cpp
new file mode 100644
index 00000000..825d6cb5
--- /dev/null
+++ b/src/common/benchmark/Graph_simplicial_complex_benchmark.cpp
@@ -0,0 +1,150 @@
+/*    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) 2018 Inria
+ *
+ *    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/distance_functions.h>
+#include <gudhi/Simplex_tree.h>
+#include <gudhi/Clock.h>
+#include <gudhi/Points_off_io.h>
+
+#include <boost/graph/adjacency_list.hpp>
+
+#include <iostream>
+#include <string>
+#include <vector>
+#include <limits>  // for numeric limits
+#include <fstream>
+#include <cassert>
+
+
+std::ofstream results_csv("results.csv");
+
+template< typename Adjacency_list, typename ForwardPointRange, typename Distance >
+Adjacency_list proximity_graph_computation(const ForwardPointRange& points, double threshold, Distance distance) {
+  std::vector<std::pair< int, int >> edges;
+  std::vector< double > edges_fil;
+  std::map< int, double > vertices;
+
+  int idx_u, idx_v;
+  double fil;
+  idx_u = 0;
+  for (auto it_u = points.begin(); it_u != points.end(); ++it_u) {
+    idx_v = idx_u + 1;
+    for (auto it_v = it_u + 1; it_v != points.end(); ++it_v, ++idx_v) {
+      fil = distance(*it_u, *it_v);
+      if (fil <= threshold) {
+        edges.emplace_back(idx_u, idx_v);
+        edges_fil.push_back(fil);
+      }
+    }
+    ++idx_u;
+  }
+
+  // Points are labeled from 0 to idx_u-1
+  Adjacency_list skel_graph(edges.begin(), edges.end(), edges_fil.begin(), idx_u);
+
+  auto vertex_prop = boost::get(Gudhi::vertex_filtration_t(), skel_graph);
+
+  typename boost::graph_traits<Adjacency_list>::vertex_iterator vi, vi_end;
+  for (std::tie(vi, vi_end) = boost::vertices(skel_graph);
+       vi != vi_end; ++vi) {
+    boost::put(vertex_prop, *vi, 0.);
+  }
+
+  return skel_graph;
+}
+
+template <typename Adjacency_list>
+void benchmark_proximity_graph(const std::string& msg, const std::string& off_file_name) {
+  Gudhi::Points_off_reader<std::vector<double>> off_reader(off_file_name);
+  assert(off_reader.is_valid());
+
+  std::cout << "+ " << msg << std::endl;
+
+  results_csv << "\"nb_points\";"
+              << "\"nb_simplices\";"
+              << "\"compute proximity graph(sec.)\";"
+              << "\"complex_creation_time(sec.)\";"
+              << "\"" << msg << "\";" << std::endl;
+
+  Gudhi::Clock pg_compute_proximity_graph("    benchmark_proximity_graph - compute proximity graph");
+  pg_compute_proximity_graph.begin();
+  // benchmark begin
+  Adjacency_list proximity_graph = proximity_graph_computation<Adjacency_list>(off_reader.get_point_cloud(),
+                                                                               std::numeric_limits<double>::infinity(),
+                                                                               Gudhi::Euclidean_distance());
+  // benchmark end
+  pg_compute_proximity_graph.end();
+  std::cout << pg_compute_proximity_graph;
+
+  Gudhi::Simplex_tree<> complex;
+  Gudhi::Clock st_create_clock("    benchmark_proximity_graph - complex creation");
+  st_create_clock.begin();
+  // benchmark begin
+  complex.insert_graph(proximity_graph);
+  // benchmark end
+  st_create_clock.end();
+  std::cout << st_create_clock;
+
+  results_csv << off_reader.get_point_cloud().size() << ";" << complex.num_simplices() << ";"
+              << pg_compute_proximity_graph.num_seconds() << ";"
+              << st_create_clock.num_seconds() << ";" << std::endl;
+
+  std::cout << "    benchmark_proximity_graph - nb simplices = " << complex.num_simplices() << std::endl;
+}
+
+int main(int argc, char * const argv[]) {
+  std::string off_file_name(argv[1]);
+
+  // The fastest, the less memory used
+  using vecSdirectedS = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
+                                              boost::property<Gudhi::vertex_filtration_t, double>,
+                                              boost::property<Gudhi::edge_filtration_t, double>>;
+  benchmark_proximity_graph<vecSdirectedS>("vecSdirectedS", off_file_name);
+
+  using vecSundirectedS = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
+                                                boost::property<Gudhi::vertex_filtration_t, double>,
+                                                boost::property<Gudhi::edge_filtration_t, double>>;
+  benchmark_proximity_graph<vecSundirectedS>("vecSundirectedS", off_file_name);
+
+  using vecSbidirectionalS = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
+                                                   boost::property<Gudhi::vertex_filtration_t, double>,
+                                                   boost::property<Gudhi::edge_filtration_t, double>>;
+  benchmark_proximity_graph<vecSbidirectionalS>("vecSbidirectionalS", off_file_name);
+
+  using setSdirectedS = boost::adjacency_list<boost::setS, boost::vecS, boost::directedS,
+                                              boost::property<Gudhi::vertex_filtration_t, double>,
+                                              boost::property<Gudhi::edge_filtration_t, double>>;
+  benchmark_proximity_graph<setSdirectedS>("setSdirectedS", off_file_name);
+
+  using setSundirectedS = boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS,
+                                                boost::property<Gudhi::vertex_filtration_t, double>,
+                                                boost::property<Gudhi::edge_filtration_t, double>>;
+  benchmark_proximity_graph<setSundirectedS>("setSundirectedS", off_file_name);
+
+  using setSbidirectionalS = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
+                                                   boost::property<Gudhi::vertex_filtration_t, double>,
+                                                   boost::property<Gudhi::edge_filtration_t, double>>;
+  benchmark_proximity_graph<setSbidirectionalS>("setSbidirectionalS", off_file_name);
+
+  return 0;
+}
diff --git a/src/common/doc/examples.h b/src/common/doc/examples.h
index 40f202c7..c19b3444 100644
--- a/src/common/doc/examples.h
+++ b/src/common/doc/examples.h
@@ -53,10 +53,7 @@
  * @example Spatial_searching/example_spatial_searching.cpp
  * @example Alpha_complex/alpha_complex_3d_persistence.cpp
  * @example Alpha_complex/alpha_complex_persistence.cpp
- * @example Alpha_complex/weighted_periodic_alpha_complex_3d_persistence.cpp
- * @example Alpha_complex/weighted_alpha_complex_3d_persistence.cpp
- * @example Alpha_complex/periodic_alpha_complex_3d_persistence.cpp
- * @example Alpha_complex/exact_alpha_complex_3d_persistence.cpp
+ * @example Alpha_complex/Weighted_alpha_complex_3d_from_points.cpp
  * @example Bottleneck_distance/bottleneck_distance.cpp
  * @example Witness_complex/weak_witness_persistence.cpp
  * @example Witness_complex/strong_witness_persistence.cpp
diff --git a/src/common/doc/file_formats.h b/src/common/doc/file_formats.h
index 523153b8..23214e25 100644
--- a/src/common/doc/file_formats.h
+++ b/src/common/doc/file_formats.h
@@ -72,7 +72,7 @@ namespace Gudhi {
 
  \section FileFormatsPerseus Perseus
 
- This file format is the format used by the Perseus software
+ This file format is a format inspired from the Perseus software
  (http://www.sas.upenn.edu/~vnanda/perseus/) by Vidit Nanda.
  The first line contains a number d begin the dimension of the
  bitmap (2 in the example below). Next d lines are the numbers of top dimensional cubes in each dimensions (3 and 3
@@ -118,6 +118,10 @@ namespace Gudhi {
  Indicate that we have imposed periodic boundary conditions in the direction x, but not in the direction y.
 
  Other sample files can be found in the `data/bitmap` folder.
+ 
+ \note Unlike in Perseus format the filtration on the maximal cubes can be any double precision number.
+ Consequently one cannot mark the cubes that are not present with `-1`'s. To do that please set their filtration value
+ to \f$+\infty\f$ (aka. `inf` in the file).
 
 */
 }  // namespace Gudhi
diff --git a/src/common/doc/installation.h b/src/common/doc/installation.h
index df7eed37..8fb8b330 100644
--- a/src/common/doc/installation.h
+++ b/src/common/doc/installation.h
@@ -5,7 +5,7 @@
  * Examples of GUDHI headers inclusion can be found in \ref utilities.
  * 
  * \section compiling Compiling
- * The library uses c++11 and requires <a target="_blank" href="http://www.boost.org/">Boost</a>  &ge; 1.48.0
+ * The library uses c++11 and requires <a target="_blank" href="http://www.boost.org/">Boost</a>  &ge; 1.56.0
  * and <a target="_blank" href="https://www.cmake.org/">CMake</a> &ge; 3.1.
  * It is a multi-platform library and compiles on Linux, Mac OSX and Visual Studio 2015.
  * 
@@ -72,12 +72,6 @@ make doxygen
  * 
  * The following examples/utilities require the <a target="_blank" href="http://www.cgal.org/">Computational Geometry Algorithms
  * Library</a> (CGAL \cite cgal:eb-15b) and will not be built if CGAL is not installed:
- * \li <a href="_alpha_complex_2alpha_complex_3d_persistence_8cpp-example.html">
- * Alpha_complex/alpha_complex_3d_persistence.cpp</a>
- * \li <a href="_alpha_complex_2exact_alpha_complex_3d_persistence_8cpp-example.html">
- * Alpha_complex/exact_alpha_complex_3d_persistence.cpp</a>
- * \li <a href="_alpha_complex_2weighted_alpha_complex_3d_persistence_8cpp-example.html">
- * Alpha_complex/weighted_alpha_complex_3d_persistence.cpp</a>
  * \li <a href="_simplex_tree_2example_alpha_shapes_3_simplex_tree_from_off_file_8cpp-example.html">
  * Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp</a>
  * 
@@ -100,8 +94,6 @@ make doxygen
  * Alpha_complex/Alpha_complex_from_points.cpp</a>
  * \li <a href="_alpha_complex_2alpha_complex_persistence_8cpp-example.html">
  * Alpha_complex/alpha_complex_persistence.cpp</a>
- * \li <a href="_alpha_complex_2periodic_alpha_complex_3d_persistence_8cpp-example.html">
- * Alpha_complex/periodic_alpha_complex_3d_persistence.cpp</a>
  * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html">
  * Persistent_cohomology/custom_persistence_sort.cpp</a>
  * 
@@ -135,6 +127,12 @@ make doxygen
  * \li <a href="_tangential_complex_2example_with_perturb_8cpp-example.html">
  * Tangential_complex/example_with_perturb.cpp</a>
  *
+ * The following example requires CGAL version &ge; 4.11.0:
+ * \li <a href="_alpha_complex_2_weighted_alpha_complex_3d_from_points_8cpp-example.html">
+ * Alpha_complex/Weighted_alpha_complex_3d_from_points.cpp</a>
+ * \li <a href="_alpha_complex_2alpha_complex_3d_persistence_8cpp-example.html">
+ * Alpha_complex/alpha_complex_3d_persistence.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:
@@ -148,8 +146,10 @@ make doxygen
  * Alpha_complex/Alpha_complex_from_points.cpp</a>
  * \li <a href="_alpha_complex_2alpha_complex_persistence_8cpp-example.html">
  * Alpha_complex/alpha_complex_persistence.cpp</a>
- * \li <a href="_alpha_complex_2periodic_alpha_complex_3d_persistence_8cpp-example.html">
- * Alpha_complex/periodic_alpha_complex_3d_persistence.cpp</a>
+ * \li <a href="_alpha_complex_2alpha_complex_3d_persistence_8cpp-example.html">
+ * Alpha_complex/alpha_complex_3d_persistence.cpp</a>
+ * \li <a href="_alpha_complex_2_weighted_alpha_complex_3d_from_points_8cpp-example.html">
+ * Alpha_complex/Weighted_alpha_complex_3d_from_points.cpp</a>
  * \li <a href="_bottleneck_distance_2alpha_rips_persistence_bottleneck_distance_8cpp-example.html">
  * Bottleneck_distance/alpha_rips_persistence_bottleneck_distance.cpp.cpp</a>
  * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html">
@@ -195,12 +195,6 @@ make doxygen
  * Alpha_complex/alpha_complex_3d_persistence.cpp</a>
  * \li <a href="_alpha_complex_2alpha_complex_persistence_8cpp-example.html">
  * Alpha_complex/alpha_complex_persistence.cpp</a>
- * \li <a href="_alpha_complex_2exact_alpha_complex_3d_persistence_8cpp-example.html">
- * Alpha_complex/exact_alpha_complex_3d_persistence.cpp</a>
- * \li <a href="_alpha_complex_2periodic_alpha_complex_3d_persistence_8cpp-example.html">
- * Alpha_complex/periodic_alpha_complex_3d_persistence.cpp</a>
- * \li <a href="_alpha_complex_2weighted_alpha_complex_3d_persistence_8cpp-example.html">
- * Alpha_complex/weighted_alpha_complex_3d_persistence.cpp</a>
  * \li <a href="_bitmap_cubical_complex_2_bitmap_cubical_complex_8cpp-example.html">
  * Bitmap_cubical_complex/cubical_complex_persistence.cpp</a>
  * \li <a href="_bitmap_cubical_complex_2_bitmap_cubical_complex_periodic_boundary_conditions_8cpp-example.html">
@@ -239,10 +233,6 @@ make doxygen
  * Persistent_cohomology/rips_multifield_persistence.cpp</a>
  * \li <a href="_persistent_cohomology_2rips_persistence_step_by_step_8cpp-example.html">
  * Persistent_cohomology/rips_persistence_step_by_step.cpp</a>
- * \li <a href="_persistent_cohomology_2exact_alpha_complex_3d_persistence_8cpp-example.html">
- * Persistent_cohomology/exact_alpha_complex_3d_persistence.cpp</a>
- * \li <a href="_persistent_cohomology_2weighted_alpha_complex_3d_persistence_8cpp-example.html">
- * Persistent_cohomology/weighted_alpha_complex_3d_persistence.cpp</a>
  * \li <a href="_persistent_cohomology_2custom_persistence_sort_8cpp-example.html">
  * Persistent_cohomology/custom_persistence_sort.cpp</a>
  * \li <a href="_rips_complex_2example_one_skeleton_rips_from_points_8cpp-example.html">
diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h
index 5ccb648f..afe9b68c 100644
--- a/src/common/doc/main_page.h
+++ b/src/common/doc/main_page.h
@@ -29,7 +29,9 @@
       <b>Author:</b> Vincent Rouvreau<br>
       <b>Introduced in:</b> GUDHI 1.3.0<br>
       <b>Copyright:</b> GPL v3<br>
-      <b>Requires:</b> \ref cgal &ge; 4.7.0 and \ref eigen3
+      <b>Requires:</b> \ref eigen3 and<br>
+      \ref cgal &ge; 4.7.0 for Alpha_complex<br>
+      \ref cgal &ge; 4.11.0 for Alpha_complex_3d
     </td>
     <td width="75%">
     Alpha_complex is a simplicial complex constructed from the finite cells of a Delaunay Triangulation.<br>
@@ -38,7 +40,8 @@
     values of the codimension 1 cofaces that make it not Gabriel otherwise.
     All simplices that have a filtration value strictly greater than a given alpha squared value are not inserted into
     the complex.<br>
-    <b>User manual:</b> \ref alpha_complex - <b>Reference manual:</b> Gudhi::alpha_complex::Alpha_complex
+    <b>User manual:</b> \ref alpha_complex - <b>Reference manual:</b> Gudhi::alpha_complex::Alpha_complex and
+    Gudhi::alpha_complex::Alpha_complex_3d
     </td>
  </tr>
 </table>
diff --git a/src/common/include/gudhi/Unitary_tests_utils.h b/src/common/include/gudhi/Unitary_tests_utils.h
index e07c8d42..22f00212 100644
--- a/src/common/include/gudhi/Unitary_tests_utils.h
+++ b/src/common/include/gudhi/Unitary_tests_utils.h
@@ -34,7 +34,7 @@ void GUDHI_TEST_FLOAT_EQUALITY_CHECK(FloatingType a, FloatingType b,
   std::cout << "GUDHI_TEST_FLOAT_EQUALITY_CHECK - " << a << " versus " << b
             << " | diff = " << std::fabs(a - b) << " - epsilon = " << epsilon << std::endl;
 #endif
-  BOOST_CHECK(std::fabs(a - b) < epsilon);
+  BOOST_CHECK(std::fabs(a - b) <= epsilon);
 }
 
 #endif  // UNITARY_TESTS_UTILS_H_
diff --git a/src/common/include/gudhi/graph_simplicial_complex.h b/src/common/include/gudhi/graph_simplicial_complex.h
index 49fe56cc..0d81ca71 100644
--- a/src/common/include/gudhi/graph_simplicial_complex.h
+++ b/src/common/include/gudhi/graph_simplicial_complex.h
@@ -49,7 +49,7 @@ struct vertex_filtration_t {
  *
  */
 template <typename SimplicialComplexForProximityGraph>
-using Proximity_graph = typename boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS
+using Proximity_graph = typename boost::adjacency_list < boost::vecS, boost::vecS, boost::directedS
 , boost::property < vertex_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value >
 , boost::property < edge_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value >>;
 
diff --git a/src/common/include/gudhi/reader_utils.h b/src/common/include/gudhi/reader_utils.h
index 26eeb76d..0ee7649d 100644
--- a/src/common/include/gudhi/reader_utils.h
+++ b/src/common/include/gudhi/reader_utils.h
@@ -172,10 +172,10 @@ bool read_simplex(std::istream& in_, std::vector<Vertex_handle>& simplex, Filtra
   if (!(in_ >> dim)) return false;
   Vertex_handle v;
   for (int i = 0; i < dim + 1; ++i) {
-    in_ >> v;
+    if (!(in_ >> v)) return false;
     simplex.push_back(v);
   }
-  in_ >> fil;
+  if (!(in_ >> fil)) return false;
   in_.ignore((std::numeric_limits<std::streamsize>::max)(), '\n');  // ignore until the carriage return
   return true;
 }