From fee58180eb9e2617f92e2f92bb6d1120348f310f Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 27 Jan 2017 17:10:54 +0000 Subject: 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 --- src/cython/cython/bottleneck_distance.pyx | 59 ++++++++++++++++++++++ src/cython/doc/bottleneck_distance_ref.rst | 5 ++ src/cython/doc/bottleneck_distance_sum.rst | 15 ++++++ src/cython/doc/bottleneck_distance_user.rst | 37 ++++++++++++++ src/cython/doc/index.rst | 5 ++ src/cython/example/bottleneck_basic_example.py | 48 ++++++++++++++++++ src/cython/include/Bottleneck_distance_interface.h | 53 +++++++++++++++++++ src/cython/test/test_bottleneck_distance.py | 35 +++++++++++++ 8 files changed, 257 insertions(+) create mode 100644 src/cython/cython/bottleneck_distance.pyx create mode 100644 src/cython/doc/bottleneck_distance_ref.rst create mode 100644 src/cython/doc/bottleneck_distance_sum.rst create mode 100644 src/cython/doc/bottleneck_distance_user.rst create mode 100755 src/cython/example/bottleneck_basic_example.py create mode 100644 src/cython/include/Bottleneck_distance_interface.h create mode 100755 src/cython/test/test_bottleneck_distance.py (limited to 'src/cython') 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 . +""" + +__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 ≥ 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 . +""" + +__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 . + */ + +#ifndef BOTTLENECK_DISTANCE_INTERFACE_H +#define BOTTLENECK_DISTANCE_INTERFACE_H + +#include + +#include +#include +#include // 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> &diag1, + const std::vector> &diag2, + double e) { + return bottleneck_distance(diag1, diag2, e); + } + + double bottleneck(const std::vector> &diag1, + const std::vector> &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 . +""" + +__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) -- cgit v1.2.3