Add bottleneck distance

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

Former-commit-id: 1320379f3d41ef4d11326c1aad1dd20469d3f4e0

8 files changed, 257 insertions, 0 deletions

diff --git a/src/cython/cython/bottleneck_distance.pyx b/src/cython/cython/bottleneck_distance.pyx
new file mode 100644
index 00000000..ee3e6ef9
--- /dev/null
+++ b/src/cython/cython/bottleneck_distance.pyx
@@ -0,0 +1,59 @@
+from cython cimport numeric
+from libcpp.vector cimport vector
+from libcpp.utility cimport pair
+import os
+
+"""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) 2016 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/>.
+"""
+
+__author__ = "Vincent Rouvreau"
+__copyright__ = "Copyright (C) 2016 INRIA"
+__license__ = "GPL v3"
+
+cdef extern from "Bottleneck_distance_interface.h" namespace "Gudhi::persistence_diagram":
+    double bottleneck(vector[pair[double, double]], vector[pair[double, double]], double)
+    double bottleneck(vector[pair[double, double]], vector[pair[double, double]])
+
+def bottleneck_distance(diagram_1, diagram_2, e=0.0):
+    """This function returns the point corresponding to a given vertex.
+
+    :param diagram_1: The first diagram.
+    :type diagram_1: vector[pair[double, double]]
+    :param diagram_2: The second diagram.
+    :type diagram_2: vector[pair[double, double]]
+    :param e: If `e` is 0, this uses an expensive algorithm to compute the
+        exact distance.
+        If `e` is not 0, it asks for an additive `e`-approximation, and
+        currently also allows a small multiplicative error (the last 2 or 3
+        bits of the mantissa may be wrong). This version of the algorithm takes
+        advantage of the limited precision of `double` and is usually a lot
+        faster to compute, whatever the value of `e`.
+
+        Thus, by default, `e` is the smallest positive double.
+    :type e: float
+    :rtype: float
+    :returns: the bottleneck distance.
+    """
+    if e is 0.0:
+        return bottleneck(diagram_1, diagram_2)
+    else:
+        return bottleneck(diagram_1, diagram_2, e)
diff --git a/src/cython/doc/bottleneck_distance_ref.rst b/src/cython/doc/bottleneck_distance_ref.rst
new file mode 100644
index 00000000..7f816cd6
--- /dev/null
+++ b/src/cython/doc/bottleneck_distance_ref.rst
@@ -0,0 +1,5 @@
+===========================
+Bottleneck reference manual
+===========================
+
+.. automethod:: gudhi.bottleneck_distance
diff --git a/src/cython/doc/bottleneck_distance_sum.rst b/src/cython/doc/bottleneck_distance_sum.rst
new file mode 100644
index 00000000..6cffa122
--- /dev/null
+++ b/src/cython/doc/bottleneck_distance_sum.rst
@@ -0,0 +1,15 @@
+=====================================  =====================================  =====================================
+:Author: Francois Godi                 :Introduced in: GUDHI 1.4.0            :Copyright: GPL v3
+=====================================  =====================================  =====================================
+:Requires: CGAL &ge; 4.8.0
+=====================================  =====================================  =====================================
+
++-------------------------------------------+----------------------------------------------------------------------+
+| .. image::                                | Bottleneck distance measures the similarity between two persistence  |
+|      img/perturb_pd.png                   | diagrams. It's the shortest distance b for which there exists a      |
+|                                           | perfect matching between the points of the two diagrams (+ all the   |
+|                                           | diagonal points) such that any couple of matched points are at       |
+|                                           | distance at most b.                                                  |
++-------------------------------------------+----------------------------------------------------------------------+
+| :doc:`bottleneck_distance_user`           | :doc:`bottleneck_distance_ref`                                       |
++-------------------------------------------+----------------------------------------------------------------------+
diff --git a/src/cython/doc/bottleneck_distance_user.rst b/src/cython/doc/bottleneck_distance_user.rst
new file mode 100644
index 00000000..08c6e451
--- /dev/null
+++ b/src/cython/doc/bottleneck_distance_user.rst
@@ -0,0 +1,37 @@
+===============================
+Bottleneck distance user manual
+===============================
+Definition
+----------
+
+.. include:: bottleneck_distance_sum.rst
+
+Function
+--------
+.. automethod:: gudhi.bottleneck_distance
+
+
+Basic example
+-------------
+
+This example computes the bottleneck distance from 2 persistence diagrams:
+
+.. testcode::
+
+    import gudhi
+
+    diag1 = [[2.7, 3.7],[9.6, 14.],[34.2, 34.974], [3.,float('Inf')]]
+    diag2 = [[2.8, 4.45],[9.5, 14.1],[3.2,float('Inf')]]
+
+    message = "Bottleneck distance approximation=" + repr(gudhi.bottleneck_distance(diag1, diag2, 0.1))
+    print(message)
+
+    message = "Bottleneck distance exact value=" + repr(gudhi.bottleneck_distance(diag1, diag2))
+    print(message)
+
+The output is:
+
+.. testoutput::
+
+    Bottleneck distance approximation=0.8081763781405569
+    Bottleneck distance exact value=0.75
diff --git a/src/cython/doc/index.rst b/src/cython/doc/index.rst
index 91e31ff6..de90cf7c 100644
--- a/src/cython/doc/index.rst
+++ b/src/cython/doc/index.rst
@@ -62,6 +62,11 @@ Witness complex
 Toolbox
 *******
 
+Bottleneck distance
+===================
+
+.. include:: bottleneck_distance_sum.rst
+
 Persistence cohomology
 ======================
 
diff --git a/src/cython/example/bottleneck_basic_example.py b/src/cython/example/bottleneck_basic_example.py
new file mode 100755
index 00000000..31cecb29
--- /dev/null
+++ b/src/cython/example/bottleneck_basic_example.py
@@ -0,0 +1,48 @@
+#!/usr/bin/env python
+
+import gudhi
+
+"""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):       Francois Godi, Vincent Rouvreau
+
+   Copyright (C) 2016 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/>.
+"""
+
+__author__ = "Francois Godi, Vincent Rouvreau"
+__copyright__ = "Copyright (C) 2016 INRIA"
+__license__ = "GPL v3"
+
+import gudhi
+
+diag1 = [[2.7, 3.7],[9.6, 14.],[34.2, 34.974], [3.,float('Inf')]]
+
+diag2 = [[2.8, 4.45],[9.5, 14.1],[3.2,float('Inf')]]
+
+message = "diag1=" + repr(diag1)
+print(message)
+
+message = "diag2=" + repr(diag2)
+print(message)
+
+message = "Bottleneck distance approximation=" + repr(gudhi.bottleneck_distance(diag1, diag2, 0.1))
+print(message)
+
+message = "Bottleneck distance exact value=" + repr(gudhi.bottleneck_distance(diag1, diag2))
+print(message)
+
diff --git a/src/cython/include/Bottleneck_distance_interface.h b/src/cython/include/Bottleneck_distance_interface.h
new file mode 100644
index 00000000..b814661e
--- /dev/null
+++ b/src/cython/include/Bottleneck_distance_interface.h
@@ -0,0 +1,53 @@
+/*    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) 2016 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/>.
+ */
+
+#ifndef BOTTLENECK_DISTANCE_INTERFACE_H
+#define	BOTTLENECK_DISTANCE_INTERFACE_H
+
+#include <gudhi/Bottleneck.h>
+
+#include <iostream>
+#include <vector>
+#include <utility>  // for std::pair
+
+namespace Gudhi {
+
+namespace persistence_diagram {
+
+  // bottleneck_distance function renamed for the python function can be called bottleneck_dstance
+  double bottleneck(const std::vector<std::pair<double, double>> &diag1,
+                    const std::vector<std::pair<double, double>> &diag2,
+                    double e) {
+    return bottleneck_distance(diag1, diag2, e);
+  }
+
+  double bottleneck(const std::vector<std::pair<double, double>> &diag1,
+                    const std::vector<std::pair<double, double>> &diag2) {
+    return bottleneck_distance(diag1, diag2);
+  }
+
+}  // namespace alpha_complex
+
+}  // namespace Gudhi
+
+
+#endif  // BOTTLENECK_DISTANCE_INTERFACE_H
diff --git a/src/cython/test/test_bottleneck_distance.py b/src/cython/test/test_bottleneck_distance.py
new file mode 100755
index 00000000..3d982d34
--- /dev/null
+++ b/src/cython/test/test_bottleneck_distance.py
@@ -0,0 +1,35 @@
+import gudhi
+
+"""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) 2016 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/>.
+"""
+
+__author__ = "Vincent Rouvreau"
+__copyright__ = "Copyright (C) 2016 INRIA"
+__license__ = "GPL v3"
+
+
+def test_basic_bottleneck():
+    diag1 = [[2.7, 3.7],[9.6, 14.],[34.2, 34.974], [3.,float('Inf')]]
+    diag2 = [[2.8, 4.45],[9.5, 14.1],[3.2,float('Inf')]]
+
+    assert(gudhi.bottleneck_distance(diag1, diag2, 0.1) == 0.8081763781405569)
+    assert(gudhi.bottleneck_distance(diag1, diag2) == 0.75)