Merge last trunk modifications

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

Former-commit-id: b246c9007b06ed57d59dc1d18b02262d9c765fb9

8 files changed, 89 insertions, 40 deletions

diff --git a/src/cython/doc/examples.rst b/src/cython/doc/examples.rst
index 1f02f8a2..edbc2f72 100644
--- a/src/cython/doc/examples.rst
+++ b/src/cython/doc/examples.rst
@@ -22,6 +22,7 @@ Examples
     * :download:`rips_complex_diagram_persistence_from_off_file_example.py <../example/rips_complex_diagram_persistence_from_off_file_example.py>`
     * :download:`rips_complex_diagram_persistence_from_distance_matrix_file_example.py <../example/rips_complex_diagram_persistence_from_distance_matrix_file_example.py>`
     * :download:`rips_persistence_diagram.py <../example/rips_persistence_diagram.py>`
+    * :download:`sparse_rips_persistence_diagram.py <../example/sparse_rips_persistence_diagram.py>`
     * :download:`random_cubical_complex_persistence_example.py <../example/random_cubical_complex_persistence_example.py>`
     * :download:`coordinate_graph_induced_complex.py <../example/coordinate_graph_induced_complex.py>`
     * :download:`functional_graph_induced_complex.py <../example/functional_graph_induced_complex.py>`
diff --git a/src/cython/doc/installation.rst b/src/cython/doc/installation.rst
index 43576ec9..040f6b4a 100644
--- a/src/cython/doc/installation.rst
+++ b/src/cython/doc/installation.rst
@@ -7,7 +7,7 @@ Installation
 
 Compiling
 *********
-The library uses c++11 and requires `Boost <https://www.boost.org/>`_ ≥ 1.48.0
+The library uses c++11 and requires `Boost <https://www.boost.org/>`_ ≥ 1.56.0
 and `CMake <https://www.cmake.org/>`_   ≥ 3.1.
 It is a multi-platform library and compiles on Linux, Mac OSX and Visual
 Studio 2015.
@@ -195,7 +195,7 @@ The following examples require the `Matplotlib <http://matplotlib.org>`_:
     * :download:`euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py>`
     * :download:`euclidean_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_witness_complex_diagram_persistence_from_off_file_example.py>`
 
-Numpy
+NumPy
 =====
 
 The :doc:`persistence graphical tools </persistence_graphical_tools_user>`
@@ -216,6 +216,13 @@ The following examples require the `NumPy <http://numpy.org>`_:
     * :download:`euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py>`
     * :download:`euclidean_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_witness_complex_diagram_persistence_from_off_file_example.py>`
 
+SciPy
+=====
+
+The :doc:`persistence graphical tools </persistence_graphical_tools_user>`
+module requires `SciPy <http://scipy.org>`_, a Python-based ecosystem of
+open-source software for mathematics, science, and engineering.
+
 Threading Building Blocks
 =========================
 
diff --git a/src/cython/doc/nerve_gic_complex_sum.rst b/src/cython/doc/nerve_gic_complex_sum.rst
index 72782c7a..523c119f 100644
--- a/src/cython/doc/nerve_gic_complex_sum.rst
+++ b/src/cython/doc/nerve_gic_complex_sum.rst
@@ -1,5 +1,5 @@
 =================================================================  ===================================  ===================================
-:Author: Mathieu Carrière                                          :Introduced in: GUDHI 2.1.0          :Copyright: GPL v3
+:Author: Mathieu Carrière                                          :Introduced in: GUDHI 2.3.0          :Copyright: GPL v3
 :Requires: CGAL :math:`\geq` 4.8.1
 =================================================================  ===================================  ===================================
 
diff --git a/src/cython/doc/persistence_graphical_tools_ref.rst b/src/cython/doc/persistence_graphical_tools_ref.rst
index a2c6bcef..54aff4bc 100644
--- a/src/cython/doc/persistence_graphical_tools_ref.rst
+++ b/src/cython/doc/persistence_graphical_tools_ref.rst
@@ -9,3 +9,4 @@ Persistence graphical tools reference manual
 .. autofunction:: gudhi.__min_birth_max_death
 .. autofunction:: gudhi.plot_persistence_barcode
 .. autofunction:: gudhi.plot_persistence_diagram
+.. autofunction:: gudhi.plot_persistence_density
diff --git a/src/cython/doc/persistence_graphical_tools_sum.inc b/src/cython/doc/persistence_graphical_tools_sum.inc
index d602daa7..5577cf99 100644
--- a/src/cython/doc/persistence_graphical_tools_sum.inc
+++ b/src/cython/doc/persistence_graphical_tools_sum.inc
@@ -1,11 +1,11 @@
 =================================================================  ===================================  ===================================
 :Author: Vincent Rouvreau                                          :Introduced in: GUDHI 2.0.0          :Copyright: GPL v3
-:Requires: Matplotlib                                              Numpy
+:Requires: matplotlib                                              numpy                                scipy
 =================================================================  ===================================  ===================================
 
 +-----------------------------------------------------------------+-----------------------------------------------------------------------+
 | .. figure::                                                     | These graphical tools comes on top of persistence results and allows  |
-|      img/graphical_tools_representation.png                     | the user to build easily barcode and persistence diagram.             |
+|      img/graphical_tools_representation.png                     | the user to build easily persistence barcode, diagram or density.     |
 |                                                                 |                                                                       |
 +-----------------------------------------------------------------+-----------------------------------------------------------------------+
 |  :doc:`persistence_graphical_tools_user`                        | :doc:`persistence_graphical_tools_ref`                                |
diff --git a/src/cython/doc/persistence_graphical_tools_user.rst b/src/cython/doc/persistence_graphical_tools_user.rst
index 292915eb..b2124fdd 100644
--- a/src/cython/doc/persistence_graphical_tools_user.rst
+++ b/src/cython/doc/persistence_graphical_tools_user.rst
@@ -12,6 +12,9 @@ Definition
 Show persistence as a barcode
 -----------------------------
 
+.. note::
+    this function requires matplotlib and numpy to be available
+
 This function can display the persistence result as a barcode:
 
 .. plot::
@@ -19,16 +22,22 @@ This function can display the persistence result as a barcode:
 
     import gudhi
 
-    perseus_file = gudhi.__root_source_dir__ + '/data/bitmap/3d_torus.txt'
-    periodic_cc = gudhi.PeriodicCubicalComplex(perseus_file=perseus_file)
-    diag = periodic_cc.persistence()
-    print("diag = ", diag)
-    plt = gudhi.plot_persistence_barcode(diag)
-    plt.show()
+    off_file = gudhi.__root_source_dir__ + '/data/points/tore3D_300.off'
+    point_cloud = gudhi.read_off(off_file=off_file)
+
+    rips_complex = gudhi.RipsComplex(points=point_cloud, max_edge_length=0.7)
+    simplex_tree = rips_complex.create_simplex_tree(max_dimension=3)
+    diag = simplex_tree.persistence(min_persistence=0.4)
+
+    plot = gudhi.plot_persistence_barcode(diag)
+    plot.show()
 
 Show persistence as a diagram
 -----------------------------
 
+.. note::
+    this function requires matplotlib and numpy to be available
+
 This function can display the persistence result as a diagram:
 
 .. plot::
@@ -43,6 +52,12 @@ This function can display the persistence result as a diagram:
         legend=True)
     plt.show()
 
+Persistence density
+-------------------
+
+.. note::
+    this function requires matplotlib, numpy and scipy to be available
+
 If you want more information on a specific dimension, for instance:
 
 .. plot::
@@ -50,13 +65,9 @@ If you want more information on a specific dimension, for instance:
 
     import gudhi
 
+    # rips_on_tore3D_1307.pers obtained from write_persistence_diagram method
     persistence_file=gudhi.__root_source_dir__ + \
         '/data/persistence_diagram/rips_on_tore3D_1307.pers'
-    diag = \
-        gudhi.read_persistence_intervals_grouped_by_dimension(persistence_file=\
-            persistence_file)
-    dim = 1
-    # Display all points with some transparency
-    plt = gudhi.plot_persistence_diagram([(dim,interval) for interval in diag[dim]],
-        max_plots=0, alpha=0.1)
+    plt = gudhi.plot_persistence_density(persistence_file=persistence_file,
+        max_intervals=0, dimension=1, legend=True)
     plt.show()
diff --git a/src/cython/doc/rips_complex_sum.inc b/src/cython/doc/rips_complex_sum.inc
index 5616bfa9..ea26769a 100644
--- a/src/cython/doc/rips_complex_sum.inc
+++ b/src/cython/doc/rips_complex_sum.inc
@@ -1,6 +1,6 @@
-=================================================================  ===================================  ===================================
-:Author: Clément Maria, Pawel Dlotko, Vincent Rouvreau             :Introduced in: GUDHI 2.0.0          :Copyright: GPL v3
-=================================================================  ===================================  ===================================
+=====================================================================  ===========================  ===================================
+:Author: Clément Maria, Pawel Dlotko, Vincent Rouvreau, Marc Glisse    :Introduced in: GUDHI 2.0.0          :Copyright: GPL v3
+=====================================================================  ===========================  ===================================
 
 +----------------------------------------------------------------+------------------------------------------------------------------------+
 | .. figure::                                                    | Rips complex is a simplicial complex constructed from a one skeleton   |
diff --git a/src/cython/doc/rips_complex_user.rst b/src/cython/doc/rips_complex_user.rst
index a8c06cf9..e814b4c3 100644
--- a/src/cython/doc/rips_complex_user.rst
+++ b/src/cython/doc/rips_complex_user.rst
@@ -7,27 +7,27 @@ Rips complex user manual
 Definition
 ----------
 
-=======================================================  =====================================  =====================================
-:Authors: Clément Maria, Pawel Dlotko, Vincent Rouvreau  :Introduced in: GUDHI 2.0.0            :Copyright: GPL v3
-=======================================================  =====================================  =====================================
+====================================================================  ================================  ======================
+:Authors: Clément Maria, Pawel Dlotko, Vincent Rouvreau, Marc Glisse  :Introduced in: GUDHI 2.0.0       :Copyright: GPL v3
+====================================================================  ================================  ======================
 
 +-------------------------------------------+----------------------------------------------------------------------+
 | :doc:`rips_complex_user`                  | :doc:`rips_complex_ref`                                              |
 +-------------------------------------------+----------------------------------------------------------------------+
 
-`Rips complex <https://en.wikipedia.org/wiki/Vietoris%E2%80%93Rips_complex>`_ is a one skeleton graph that allows to
-construct a simplicial complex from it. The input can be a point cloud with a given distance function, or a distance
-matrix.
+The `Rips complex <https://en.wikipedia.org/wiki/Vietoris%E2%80%93Rips_complex>`_ is a simplicial complex that
+generalizes proximity (:math:`\varepsilon`-ball) graphs to higher dimensions. The vertices correspond to the input
+points, and a simplex is present if and only if its diameter is smaller than some parameter α.  Considering all
+parameters α defines a filtered simplicial complex, where the filtration value of a simplex is its diameter.
+The filtration can be restricted to values α smaller than some threshold, to reduce its size.
 
-The filtration value of each edge is computed from a user-given distance function, or directly from the distance
-matrix.
+The input discrete metric space can be provided as a point cloud plus a distance function, or as a distance matrix.
 
-All edges that have a filtration value strictly greater than a given threshold value are not inserted into the complex.
+When creating a simplicial complex from the graph, :doc:`RipsComplex <rips_complex_ref>` first builds the graph and
+inserts it into the data structure. It then expands the simplicial complex (adds the simplices corresponding to cliques)
+when required. The expansion can be stopped at dimension `max_dimension`, by default 1.
 
-When creating a simplicial complex from this one skeleton graph, Rips inserts the one skeleton graph into the data
-structure, and then expands the simplicial complex when required.
-
-Vertex name correspond to the index of the point in the given range (aka. the point cloud).
+A vertex name corresponds to the index of the point in the given range (aka. the point cloud).
 
 .. figure::
     ../../doc/Rips_complex/rips_complex_representation.png
@@ -38,8 +38,27 @@ Vertex name correspond to the index of the point in the given range (aka. the po
 On this example, as edges (4,5), (4,6) and (5,6) are in the complex, simplex (4,5,6) is added with the filtration value
 set with :math:`max(filtration(4,5), filtration(4,6), filtration(5,6))`. And so on for simplex (0,1,2,3).
 
-If the Rips_complex interfaces are not detailed enough for your need, please refer to rips_persistence_step_by_step.cpp
-example, where the graph construction over the Simplex_tree is more detailed.
+If the `RipsComplex` interfaces are not detailed enough for your need, please refer to rips_persistence_step_by_step.cpp
+C++ example, where the graph construction over the Simplex_tree is more detailed.
+
+A Rips complex can easily become huge, even if we limit the length of the edges
+and the dimension of the simplices. One easy trick, before building a Rips
+complex on a point cloud, is to call `sparsify_point_set` which removes points
+that are too close to each other. This does not change its persistence diagram
+by more than the length used to define "too close".
+
+A more general technique is to use a sparse approximation of the Rips
+introduced by Don Sheehy :cite:`sheehy13linear`. We are using the version
+described in :cite:`buchet16efficient` (except that we multiply all filtration
+values by 2, to match the usual Rips complex), which proves a
+:math:`\frac{1+\varepsilon}{1-\varepsilon}`-interleaving, although in practice the
+error is usually smaller.  A more intuitive presentation of the idea is
+available in :cite:`cavanna15geometric`, and in a video
+:cite:`cavanna15visualizing`. Passing an extra argument `sparse=0.3` at the
+construction of a `RipsComplex` object asks it to build a sparse Rips with
+parameter :math:`\varepsilon=0.3`, while the default `sparse=None` builds the
+regular Rips complex.
+
 
 Point cloud
 -----------
@@ -47,7 +66,7 @@ Point cloud
 Example from a point cloud
 ^^^^^^^^^^^^^^^^^^^^^^^^^^
 
-This example builds the one skeleton graph from the given points, and max_edge_length value.
+This example builds the neighborhood graph from the given points, up to max_edge_length.
 Then it creates a :doc:`Simplex_tree <simplex_tree_ref>` with it.
 
 Finally, it is asked to display information about the simplicial complex.
@@ -56,7 +75,7 @@ Finally, it is asked to display information about the simplicial complex.
 
     import gudhi
     rips_complex = gudhi.RipsComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]],
-        max_edge_length=12.0)
+                                     max_edge_length=12.0)
 
     simplex_tree = rips_complex.create_simplex_tree(max_dimension=1)
     result_str = 'Rips complex is of dimension ' + repr(simplex_tree.dimension()) + ' - ' + \
@@ -92,10 +111,20 @@ until dimension 1 - one skeleton graph in other words), the output is:
     [4, 6] -> 9.49
     [3, 6] -> 11.00
 
+Notice that if we use
+
+.. code-block:: python
+
+    rips_complex = gudhi.RipsComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]],
+                                     max_edge_length=12.0, sparse=2)
+
+asking for a very sparse version (theory only gives some guarantee on the meaning of the output if `sparse<1`),
+2 to 5 edges disappear, depending on the random vertex used to start the sparsification.
+
 Example from OFF file
 ^^^^^^^^^^^^^^^^^^^^^
 
-This example builds the :doc:`Rips_complex <rips_complex_ref>` from the given
+This example builds the :doc:`RipsComplex <rips_complex_ref>` from the given
 points in an OFF file, and max_edge_length value.
 Then it creates a :doc:`Simplex_tree <simplex_tree_ref>` with it.
 
@@ -200,7 +229,7 @@ until dimension 1 - one skeleton graph in other words), the output is:
 Example from csv file
 ^^^^^^^^^^^^^^^^^^^^^
 
-This example builds the :doc:`Rips_complex <rips_complex_ref>` from the given
+This example builds the :doc:`RipsComplex <rips_complex_ref>` from the given
 distance matrix in a csv file, and max_edge_length value.
 Then it creates a :doc:`Simplex_tree <simplex_tree_ref>` with it.