From 30fac00a3aee2f26aa44e62eb923af733c4f3bc7 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 6 Jun 2019 11:56:54 +0200 Subject: Add an example to explain how the distance is computed --- .../doc/bottleneck_distance_example.ipe | 287 +++++++++++++++++++++ .../doc/bottleneck_distance_example.png | Bin 0 -> 29619 bytes 2 files changed, 287 insertions(+) create mode 100644 src/Bottleneck_distance/doc/bottleneck_distance_example.ipe create mode 100644 src/Bottleneck_distance/doc/bottleneck_distance_example.png (limited to 'src') diff --git a/src/Bottleneck_distance/doc/bottleneck_distance_example.ipe b/src/Bottleneck_distance/doc/bottleneck_distance_example.ipe new file mode 100644 index 00000000..9dc5420e --- /dev/null +++ b/src/Bottleneck_distance/doc/bottleneck_distance_example.ipe @@ -0,0 +1,287 @@ + + + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + +0.6 0 0 0.6 0 0 e + + + + + +0.5 0 0 0.5 0 0 e + + +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e + + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h + + + + + +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h + + +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +-0.4 -0.4 m +0.4 -0.4 l +0.4 0.4 l +-0.4 0.4 l +h + + + + + + +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h + + +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h + + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h + + + + +-1 0.333 m +0 0 l +-1 -0.333 l + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +160 256 m +288 256 l + + +160 256 m +160 384 l + + +160 256 m +264 360 l +264 360 l + + + + +200 296 m +224 320 l + +(0, 0) +(13, 0) +(6.5, 6.5) + +160.433 359.995 m +213.999 309.986 l + + +Bottleneck +distance is 6.5 + + diff --git a/src/Bottleneck_distance/doc/bottleneck_distance_example.png b/src/Bottleneck_distance/doc/bottleneck_distance_example.png new file mode 100644 index 00000000..fb6847c8 Binary files /dev/null and b/src/Bottleneck_distance/doc/bottleneck_distance_example.png differ -- cgit v1.2.3 From 90198a22800834acd333f9b8360221035f6862cf Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 6 Jun 2019 14:36:36 +0200 Subject: Fix #11 - Distance computation shall be better documented. --- .../doc/Intro_bottleneck_distance.h | 40 +++++++++++++++++++++ .../doc/bottleneck_distance_example.png | Bin 29619 -> 21465 bytes .../example/bottleneck_basic_example.cpp | 22 ------------ src/Bottleneck_distance/include/gudhi/Bottleneck.h | 7 ++++ src/cython/doc/bottleneck_distance_user.rst | 33 ++++++++++++++--- 5 files changed, 75 insertions(+), 27 deletions(-) (limited to 'src') diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index 6fd058a8..49137ee1 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -6,6 +6,9 @@ * * Copyright (C) 2015 Inria * + * Modifications: + * - 2019/06 Vincent Rouvreau : Fix #11 - Distance computation shall be better documented. + * * 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 @@ -44,6 +47,43 @@ namespace persistence_diagram { * This implementation is based on ideas from "Geometry Helps in Bottleneck Matching and Related Problems" * \cite DBLP:journals/algorithmica/EfratIK01. Another relevant publication, although it was not used is * "Geometry Helps to Compare Persistence Diagrams" \cite Kerber:2017:GHC:3047249.3064175. + * + * \section bottleneckdistanceprecision Distance computation + * + * Bottleneck distance does not use Euclidean distance, like explained in the following example: + * + * \code{.cpp} +#include + +#include +#include +#include // for pair + +int main() { + std::vector< std::pair > diag1, diag2; + diag1.emplace_back(0., 0.); + diag2.emplace_back(0., 13.); + + double b = Gudhi::persistence_diagram::bottleneck_distance(diag1, diag2); + std::cout << "Bottleneck distance = " << b << std::endl; +} + * \endcode + * + * \code Bottleneck distance = 6.5 + * \endcode + * + * \image html bottleneck_distance_example.png The point (0, 13) is at 6.5 distance from the diagonal and more specifically from the point (6.5, 6.5) + * + * \section bottleneckbasicexample Basic example + * + * This another example computes the bottleneck distance from 2 persistence diagrams: + * \include Bottleneck_distance/bottleneck_basic_example.cpp + * + * \code + Bottleneck distance = 0.75 + Approx bottleneck distance = 0.808176 + * \endcode + */ /** @} */ // end defgroup bottleneck_distance diff --git a/src/Bottleneck_distance/doc/bottleneck_distance_example.png b/src/Bottleneck_distance/doc/bottleneck_distance_example.png index fb6847c8..b56ee791 100644 Binary files a/src/Bottleneck_distance/doc/bottleneck_distance_example.png and b/src/Bottleneck_distance/doc/bottleneck_distance_example.png differ diff --git a/src/Bottleneck_distance/example/bottleneck_basic_example.cpp b/src/Bottleneck_distance/example/bottleneck_basic_example.cpp index 3df7d12d..61778a55 100644 --- a/src/Bottleneck_distance/example/bottleneck_basic_example.cpp +++ b/src/Bottleneck_distance/example/bottleneck_basic_example.cpp @@ -1,25 +1,3 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Authors: Francois Godi, small modifications by Pawel Dlotko - * - * Copyright (C) 2015 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 . - */ - #include #include diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index 7a553006..4ce6cacc 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -6,6 +6,9 @@ * * Copyright (C) 2015 Inria * + * Modifications: + * - 2019/06 Vincent Rouvreau : Fix doxygen warning. + * * 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 @@ -92,6 +95,10 @@ inline double bottleneck_distance_exact(Persistence_graph& g) { * * \tparam Persistence_diagram1,Persistence_diagram2 * models of the concept `PersistenceDiagram`. + * + * \param[in] diag1 The first persistence diagram. + * \param[in] diag2 The second persistence diagram. + * * \param[in] e * \parblock * If `e` is 0, this uses an expensive algorithm to compute the exact distance. diff --git a/src/cython/doc/bottleneck_distance_user.rst b/src/cython/doc/bottleneck_distance_user.rst index 605db022..96e881c8 100644 --- a/src/cython/doc/bottleneck_distance_user.rst +++ b/src/cython/doc/bottleneck_distance_user.rst @@ -13,11 +13,34 @@ Function -------- .. autofunction:: gudhi.bottleneck_distance +Distance computation +-------------------- + +Bottleneck distance does not use Euclidean distance, like explained in the following example: + +.. testcode:: + + import gudhi + + message = "Bottleneck distance = " + '%.2f' % gudhi.bottleneck_distance([0., 0.], [0., 13.]) + print(message) + +.. testoutput:: + + Bottleneck distance = 6.5 + +.. figure:: + ../../doc/Bottleneck_distance/bottleneck_distance_example.png + :figclass: align-center + + The point (0, 13) is at 6.5 distance from the diagonal and more + specifically from the point (6.5, 6.5) + Basic example ------------- -This example computes the bottleneck distance from 2 persistence diagrams: +This another example computes the bottleneck distance from 2 persistence diagrams: .. testcode:: @@ -26,15 +49,15 @@ This example computes the bottleneck distance from 2 persistence diagrams: 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=" + '%.2f' % gudhi.bottleneck_distance(diag1, diag2, 0.1) + message = "Bottleneck distance approximation = " + '%.2f' % gudhi.bottleneck_distance(diag1, diag2, 0.1) print(message) - message = "Bottleneck distance value=" + '%.2f' % gudhi.bottleneck_distance(diag1, diag2) + message = "Bottleneck distance value = " + '%.2f' % gudhi.bottleneck_distance(diag1, diag2) print(message) The output is: .. testoutput:: - Bottleneck distance approximation=0.81 - Bottleneck distance value=0.75 + Bottleneck distance approximation = 0.81 + Bottleneck distance value = 0.75 -- cgit v1.2.3 From 03b8ed6090acbebca633440896958626e4eb4080 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 6 Jun 2019 15:05:05 +0200 Subject: Fix sphinx test --- src/cython/doc/bottleneck_distance_user.rst | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src') diff --git a/src/cython/doc/bottleneck_distance_user.rst b/src/cython/doc/bottleneck_distance_user.rst index 96e881c8..a6a4426f 100644 --- a/src/cython/doc/bottleneck_distance_user.rst +++ b/src/cython/doc/bottleneck_distance_user.rst @@ -22,7 +22,7 @@ Bottleneck distance does not use Euclidean distance, like explained in the follo import gudhi - message = "Bottleneck distance = " + '%.2f' % gudhi.bottleneck_distance([0., 0.], [0., 13.]) + message = "Bottleneck distance = " + '%.1f' % gudhi.bottleneck_distance([[0., 0.]], [[0., 13.]]) print(message) .. testoutput:: -- cgit v1.2.3 From af3b12d763fdd113a1c4de6b58cc4a096bc646e9 Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau Date: Fri, 7 Jun 2019 15:59:51 +0200 Subject: Update src/Bottleneck_distance/doc/Intro_bottleneck_distance.h Co-Authored-By: Marc Glisse --- src/Bottleneck_distance/doc/Intro_bottleneck_distance.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src') diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index 49137ee1..d204b610 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -76,7 +76,7 @@ int main() { * * \section bottleneckbasicexample Basic example * - * This another example computes the bottleneck distance from 2 persistence diagrams: + * This other example computes the bottleneck distance from 2 persistence diagrams: * \include Bottleneck_distance/bottleneck_basic_example.cpp * * \code -- cgit v1.2.3 From cb890f276bc5327ebad1e1fcd1cc05a0d300de83 Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau Date: Fri, 7 Jun 2019 16:00:12 +0200 Subject: Update src/Bottleneck_distance/doc/Intro_bottleneck_distance.h Co-Authored-By: Marc Glisse --- src/Bottleneck_distance/doc/Intro_bottleneck_distance.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src') diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index d204b610..520aab4f 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -72,7 +72,7 @@ int main() { * \code Bottleneck distance = 6.5 * \endcode * - * \image html bottleneck_distance_example.png The point (0, 13) is at 6.5 distance from the diagonal and more specifically from the point (6.5, 6.5) + * \image html bottleneck_distance_example.png The point (0, 13) is at distance 6.5 from the diagonal and more specifically from the point (6.5, 6.5) * * \section bottleneckbasicexample Basic example * -- cgit v1.2.3 From 4b401e9a51cbcbb44d47f4819b57ec7787088df4 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 7 Jun 2019 17:27:29 +0200 Subject: Fix doc review. Add citations for python doc version. Replace (13,0) with (0,13) in figure --- .../doc/Intro_bottleneck_distance.h | 5 +++-- .../doc/bottleneck_distance_example.ipe | 8 ++++---- .../doc/bottleneck_distance_example.png | Bin 21465 -> 19485 bytes src/common/doc/main_page.md | 4 +++- src/cython/doc/bottleneck_distance_sum.inc | 4 ++-- src/cython/doc/bottleneck_distance_user.rst | 10 +++++++--- 6 files changed, 19 insertions(+), 12 deletions(-) (limited to 'src') diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index 520aab4f..7cb0752e 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -40,7 +40,8 @@ namespace persistence_diagram { * * The bottleneck distance measures the similarity between two persistence diagrams. It is the shortest distance b for * which there exists a perfect matching between the points of the two diagrams (completed with all the points on the - * diagonal in order to ignore cardinality mismatchs) such that any couple of matched points are at distance at most b. + * diagonal in order to ignore cardinality mismatchs) such that any couple of matched points are at distance at most b, + * where the distance between points is the sup norm in \f$\mathbb{R}^2\f$ (not the Euclidean distance). * * \image html perturb_pd.png On this picture, the red edges represent the matching. The bottleneck distance is the length of the longest edge. * @@ -50,7 +51,7 @@ namespace persistence_diagram { * * \section bottleneckdistanceprecision Distance computation * - * Bottleneck distance does not use Euclidean distance, like explained in the following example: + * The following example explains how the distance is computed: * * \code{.cpp} #include diff --git a/src/Bottleneck_distance/doc/bottleneck_distance_example.ipe b/src/Bottleneck_distance/doc/bottleneck_distance_example.ipe index 9dc5420e..2033ea56 100644 --- a/src/Bottleneck_distance/doc/bottleneck_distance_example.ipe +++ b/src/Bottleneck_distance/doc/bottleneck_distance_example.ipe @@ -1,7 +1,7 @@ - + @@ -220,13 +220,13 @@ h + + - - @@ -274,7 +274,7 @@ h 224 320 l (0, 0) -(13, 0) +(0, 13) (6.5, 6.5) 160.433 359.995 m diff --git a/src/Bottleneck_distance/doc/bottleneck_distance_example.png b/src/Bottleneck_distance/doc/bottleneck_distance_example.png index b56ee791..1d3b91aa 100644 Binary files a/src/Bottleneck_distance/doc/bottleneck_distance_example.png and b/src/Bottleneck_distance/doc/bottleneck_distance_example.png differ diff --git a/src/common/doc/main_page.md b/src/common/doc/main_page.md index e61eee81..a0a3496d 100644 --- a/src/common/doc/main_page.md +++ b/src/common/doc/main_page.md @@ -349,7 +349,9 @@ Bottleneck distance measures the similarity between two persistence 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. + any couple of matched points are at distance at most b, + where the distance between points is the sup norm in \f$\mathbb{R}^2\f$ + (not the Euclidean distance). Author: François Godi
diff --git a/src/cython/doc/bottleneck_distance_sum.inc b/src/cython/doc/bottleneck_distance_sum.inc index 41b9c5a3..6840e838 100644 --- a/src/cython/doc/bottleneck_distance_sum.inc +++ b/src/cython/doc/bottleneck_distance_sum.inc @@ -6,8 +6,8 @@ | ../../doc/Bottleneck_distance/perturb_pd.png | diagrams. It's the shortest distance b for which there exists a | | | :figclass: align-center | perfect matching between the points of the two diagrams (+ all the | :Introduced in: GUDHI 2.0.0 | | | diagonal points) such that any couple of matched points are at | | - | Bottleneck distance is the length of | distance at most b. | :Copyright: GPL v3 | - | the longest edge | | | + | Bottleneck distance is the length of | distance at most b, where the distance between points is the sup | :Copyright: GPL v3 | + | the longest edge | norm in :math:`\mathbb{R}^2`. | | | | | :Requires: CGAL :math:`\geq` 4.8.0 | +-----------------------------------------------------------------+----------------------------------------------------------------------+-----------------------------------------------+ | * :doc:`bottleneck_distance_user` | | diff --git a/src/cython/doc/bottleneck_distance_user.rst b/src/cython/doc/bottleneck_distance_user.rst index a6a4426f..9435c7f1 100644 --- a/src/cython/doc/bottleneck_distance_user.rst +++ b/src/cython/doc/bottleneck_distance_user.rst @@ -9,6 +9,10 @@ Definition .. include:: bottleneck_distance_sum.inc +This implementation is based on ideas from "Geometry Helps in Bottleneck Matching and Related Problems" +:cite:`DBLP:journals/algorithmica/EfratIK01`. Another relevant publication, although it was not used is +"Geometry Helps to Compare Persistence Diagrams" :cite:`Kerber:2017:GHC:3047249.3064175`. + Function -------- .. autofunction:: gudhi.bottleneck_distance @@ -16,7 +20,7 @@ Function Distance computation -------------------- -Bottleneck distance does not use Euclidean distance, like explained in the following example: +The following example explains how the distance is computed: .. testcode:: @@ -33,14 +37,14 @@ Bottleneck distance does not use Euclidean distance, like explained in the follo ../../doc/Bottleneck_distance/bottleneck_distance_example.png :figclass: align-center - The point (0, 13) is at 6.5 distance from the diagonal and more + The point (0, 13) is at distance 6.5 from the diagonal and more specifically from the point (6.5, 6.5) Basic example ------------- -This another example computes the bottleneck distance from 2 persistence diagrams: +This other example computes the bottleneck distance from 2 persistence diagrams: .. testcode:: -- cgit v1.2.3