diff options
-rw-r--r-- | README.md | 2 | ||||
-rw-r--r-- | src/Bottleneck_distance/doc/Intro_bottleneck_distance.h | 41 | ||||
-rw-r--r-- | src/Bottleneck_distance/doc/bottleneck_distance_example.ipe | 287 | ||||
-rw-r--r-- | src/Bottleneck_distance/doc/bottleneck_distance_example.png | bin | 0 -> 19485 bytes | |||
-rw-r--r-- | src/Bottleneck_distance/example/bottleneck_basic_example.cpp | 12 | ||||
-rw-r--r-- | src/Bottleneck_distance/include/gudhi/Bottleneck.h | 5 | ||||
-rw-r--r-- | src/common/doc/main_page.md | 4 | ||||
-rw-r--r-- | src/cython/doc/bottleneck_distance_sum.inc | 4 | ||||
-rw-r--r-- | src/cython/doc/bottleneck_distance_user.rst | 37 |
9 files changed, 371 insertions, 21 deletions
@@ -1,6 +1,8 @@ [![Build Status](https://travis-ci.org/GUDHI/gudhi-devel.svg?branch=master)](https://travis-ci.org/GUDHI/gudhi-devel) [![CircleCI](https://circleci.com/gh/GUDHI/gudhi-devel/tree/master.svg?style=svg)](https://circleci.com/gh/GUDHI/gudhi-devel/tree/master) +[![Build status](https://ci.appveyor.com/api/projects/status/976j2uut8xgalvx2/branch/master?svg=true)](https://ci.appveyor.com/project/GUDHI/gudhi-devel/branch/master) + ![GUDHI](src/common/doc/Gudhi_banner.png "Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding") diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index 48078903..d58392ae 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -8,6 +8,7 @@ * * Modification(s): * - YYYY/MM Author: Description of the modification + * - 2019/06 Vincent Rouvreau : Fix #11 - Distance computation shall be better documented. */ #ifndef DOC_BOTTLENECK_DISTANCE_INTRO_BOTTLENECK_DISTANCE_H_ @@ -27,13 +28,51 @@ 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. * * 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 + * + * The following example explains how the distance is computed: + * + * \code{.cpp} +#include <gudhi/Bottleneck.h> + +#include <iostream> +#include <vector> +#include <utility> // for pair + +int main() { + std::vector< std::pair<double, double> > 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 distance 6.5 from the diagonal and more specifically from the point (6.5, 6.5) + * + * \section bottleneckbasicexample Basic example + * + * This other 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.ipe b/src/Bottleneck_distance/doc/bottleneck_distance_example.ipe new file mode 100644 index 00000000..2033ea56 --- /dev/null +++ b/src/Bottleneck_distance/doc/bottleneck_distance_example.ipe @@ -0,0 +1,287 @@ +<?xml version="1.0"?> +<!DOCTYPE ipe SYSTEM "ipe.dtd"> +<ipe version="70206" creator="Ipe 7.2.7"> +<info created="D:20190606115351" modified="D:20190607172542"/> +<ipestyle name="basic"> +<symbol name="arrow/arc(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/farc(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/ptarc(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/fptarc(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="mark/circle(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</symbol> +<symbol name="mark/disk(sx)" transformations="translations"> +<path fill="sym-stroke"> +0.6 0 0 0.6 0 0 e +</path> +</symbol> +<symbol name="mark/fdisk(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +0.5 0 0 0.5 0 0 e +</path> +<path fill="sym-stroke" fillrule="eofill"> +0.6 0 0 0.6 0 0 e +0.4 0 0 0.4 0 0 e +</path> +</group> +</symbol> +<symbol name="mark/box(sx)" transformations="translations"> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</symbol> +<symbol name="mark/square(sx)" transformations="translations"> +<path fill="sym-stroke"> +-0.6 -0.6 m +0.6 -0.6 l +0.6 0.6 l +-0.6 0.6 l +h +</path> +</symbol> +<symbol name="mark/fsquare(sfx)" transformations="translations"> +<group> +<path fill="sym-fill"> +-0.5 -0.5 m +0.5 -0.5 l +0.5 0.5 l +-0.5 0.5 l +h +</path> +<path fill="sym-stroke" fillrule="eofill"> +-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 +</path> +</group> +</symbol> +<symbol name="mark/cross(sx)" transformations="translations"> +<group> +<path fill="sym-stroke"> +-0.43 -0.57 m +0.57 0.43 l +0.43 0.57 l +-0.57 -0.43 l +h +</path> +<path fill="sym-stroke"> +-0.43 0.57 m +0.57 -0.43 l +0.43 -0.57 l +-0.57 0.43 l +h +</path> +</group> +</symbol> +<symbol name="arrow/fnormal(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/pointed(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/fpointed(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-0.8 0 l +-1 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/linear(spx)"> +<path stroke="sym-stroke" pen="sym-pen"> +-1 0.333 m +0 0 l +-1 -0.333 l +</path> +</symbol> +<symbol name="arrow/fdouble(spx)"> +<path stroke="sym-stroke" fill="white" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<symbol name="arrow/double(spx)"> +<path stroke="sym-stroke" fill="sym-stroke" pen="sym-pen"> +0 0 m +-1 0.333 l +-1 -0.333 l +h +-1 0 m +-2 0.333 l +-2 -0.333 l +h +</path> +</symbol> +<pen name="heavier" value="0.8"/> +<pen name="fat" value="1.2"/> +<pen name="ultrafat" value="2"/> +<symbolsize name="large" value="5"/> +<symbolsize name="small" value="2"/> +<symbolsize name="tiny" value="1.1"/> +<arrowsize name="large" value="10"/> +<arrowsize name="small" value="5"/> +<arrowsize name="tiny" value="3"/> +<color name="red" value="1 0 0"/> +<color name="green" value="0 1 0"/> +<color name="blue" value="0 0 1"/> +<color name="yellow" value="1 1 0"/> +<color name="orange" value="1 0.647 0"/> +<color name="gold" value="1 0.843 0"/> +<color name="purple" value="0.627 0.125 0.941"/> +<color name="gray" value="0.745"/> +<color name="brown" value="0.647 0.165 0.165"/> +<color name="navy" value="0 0 0.502"/> +<color name="pink" value="1 0.753 0.796"/> +<color name="seagreen" value="0.18 0.545 0.341"/> +<color name="turquoise" value="0.251 0.878 0.816"/> +<color name="violet" value="0.933 0.51 0.933"/> +<color name="darkblue" value="0 0 0.545"/> +<color name="darkcyan" value="0 0.545 0.545"/> +<color name="darkgray" value="0.663"/> +<color name="darkgreen" value="0 0.392 0"/> +<color name="darkmagenta" value="0.545 0 0.545"/> +<color name="darkorange" value="1 0.549 0"/> +<color name="darkred" value="0.545 0 0"/> +<color name="lightblue" value="0.678 0.847 0.902"/> +<color name="lightcyan" value="0.878 1 1"/> +<color name="lightgray" value="0.827"/> +<color name="lightgreen" value="0.565 0.933 0.565"/> +<color name="lightyellow" value="1 1 0.878"/> +<dashstyle name="dashed" value="[4] 0"/> +<dashstyle name="dotted" value="[1 3] 0"/> +<dashstyle name="dash dotted" value="[4 2 1 2] 0"/> +<dashstyle name="dash dot dotted" value="[4 2 1 2 1 2] 0"/> +<textsize name="large" value="\large"/> +<textsize name="small" value="\small"/> +<textsize name="tiny" value="\tiny"/> +<textsize name="Large" value="\Large"/> +<textsize name="LARGE" value="\LARGE"/> +<textsize name="huge" value="\huge"/> +<textsize name="Huge" value="\Huge"/> +<textsize name="footnote" value="\footnotesize"/> +<textstyle name="center" begin="\begin{center}" end="\end{center}"/> +<textstyle name="itemize" begin="\begin{itemize}" end="\end{itemize}"/> +<textstyle name="item" begin="\begin{itemize}\item{}" end="\end{itemize}"/> +<gridsize name="4 pts" value="4"/> +<gridsize name="8 pts (~3 mm)" value="8"/> +<gridsize name="16 pts (~6 mm)" value="16"/> +<gridsize name="32 pts (~12 mm)" value="32"/> +<gridsize name="10 pts (~3.5 mm)" value="10"/> +<gridsize name="20 pts (~7 mm)" value="20"/> +<gridsize name="14 pts (~5 mm)" value="14"/> +<gridsize name="28 pts (~10 mm)" value="28"/> +<gridsize name="56 pts (~20 mm)" value="56"/> +<anglesize name="90 deg" value="90"/> +<anglesize name="60 deg" value="60"/> +<anglesize name="45 deg" value="45"/> +<anglesize name="30 deg" value="30"/> +<anglesize name="22.5 deg" value="22.5"/> +<opacity name="10%" value="0.1"/> +<opacity name="30%" value="0.3"/> +<opacity name="50%" value="0.5"/> +<opacity name="75%" value="0.75"/> +<tiling name="falling" angle="-60" step="4" width="1"/> +<tiling name="rising" angle="30" step="4" width="1"/> +</ipestyle> +<page> +<layer name="alpha"/> +<view layers="alpha" active="alpha"/> +<path layer="alpha" stroke="black" arrow="normal/normal"> +160 256 m +288 256 l +</path> +<path stroke="black" arrow="normal/normal"> +160 256 m +160 384 l +</path> +<path stroke="navy"> +160 256 m +264 360 l +264 360 l +</path> +<use name="mark/fdisk(sfx)" pos="160 256" size="normal" stroke="red" fill="red"/> +<use name="mark/fdisk(sfx)" pos="160 360" size="normal" stroke="navy" fill="navy"/> +<path stroke="red"> +200 296 m +224 320 l +</path> +<text matrix="1 0 0 1 -32 8" transformations="translations" pos="164 248" stroke="red" type="label" width="23.8" height="7.473" depth="2.49" valign="baseline">(0, 0)</text> +<text matrix="1 0 0 1 -4 4" transformations="translations" pos="132 356" stroke="navy" type="label" width="28.781" height="7.473" depth="2.49" valign="baseline">(0, 13)</text> +<text transformations="translations" pos="216 300" stroke="black" type="label" width="39.297" height="7.473" depth="2.49" valign="baseline">(6.5, 6.5)</text> +<path stroke="black" arrow="normal/normal" rarrow="normal/normal"> +160.433 359.995 m +213.999 309.986 l +</path> +<use name="mark/cross(sx)" pos="214.209 309.567" size="normal" stroke="black"/> +<text matrix="1 0 0 1 6.00021 -25.5247" transformations="translations" pos="174.375 385.835" stroke="black" type="minipage" width="73.2406" height="11.924" depth="6.95" valign="top">Bottleneck +distance is 6.5</text> +</page> +</ipe> diff --git a/src/Bottleneck_distance/doc/bottleneck_distance_example.png b/src/Bottleneck_distance/doc/bottleneck_distance_example.png Binary files differnew file mode 100644 index 00000000..1d3b91aa --- /dev/null +++ b/src/Bottleneck_distance/doc/bottleneck_distance_example.png diff --git a/src/Bottleneck_distance/example/bottleneck_basic_example.cpp b/src/Bottleneck_distance/example/bottleneck_basic_example.cpp index b74c8245..61778a55 100644 --- a/src/Bottleneck_distance/example/bottleneck_basic_example.cpp +++ b/src/Bottleneck_distance/example/bottleneck_basic_example.cpp @@ -1,15 +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 - * - * Modification(s): - * - YYYY/MM Author: Description of the modification - */ - #include <gudhi/Bottleneck.h> #include <iostream> diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index c56dcb2d..105f1a93 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -8,6 +8,7 @@ * * Modification(s): * - YYYY/MM Author: Description of the modification + * - 2019/06 Vincent Rouvreau : Fix doxygen warning. */ #ifndef BOTTLENECK_H_ @@ -82,6 +83,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/common/doc/main_page.md b/src/common/doc/main_page.md index 47d0583a..98169f82 100644 --- a/src/common/doc/main_page.md +++ b/src/common/doc/main_page.md @@ -347,7 +347,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). </td> <td width="15%"> <b>Author:</b> François Godi<br> 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 605db022..9435c7f1 100644 --- a/src/cython/doc/bottleneck_distance_user.rst +++ b/src/cython/doc/bottleneck_distance_user.rst @@ -9,15 +9,42 @@ 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 +Distance computation +-------------------- + +The following example explains how the distance is computed: + +.. testcode:: + + import gudhi + + message = "Bottleneck distance = " + '%.1f' % 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 distance 6.5 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 other example computes the bottleneck distance from 2 persistence diagrams: .. testcode:: @@ -26,15 +53,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 |