From 7f2eefc474cb32dc5d566c5c370b03478c1996ac Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sat, 17 Oct 2020 19:14:09 +0200 Subject: Replace diameter (actually max y) with max distance to diagonal --- src/Bottleneck_distance/include/gudhi/Bottleneck.h | 2 +- .../include/gudhi/Persistence_graph.h | 16 ++++++++-------- 2 files changed, 9 insertions(+), 9 deletions(-) diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index e466828a..ad437710 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -35,7 +35,7 @@ namespace persistence_diagram { inline double bottleneck_distance_approx(Persistence_graph& g, double e) { double b_lower_bound = 0.; - double b_upper_bound = g.diameter_bound(); + double b_upper_bound = g.max_dist_to_diagonal(); const double alpha = std::pow(g.size(), 1. / 5.); Graph_matching m(g); Graph_matching biggest_unperfect(g); diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h index e1e3522e..04c7c118 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h @@ -51,8 +51,8 @@ class Persistence_graph { double bottleneck_alive() const; /** \internal \brief Returns the O(n^2) sorted distances between the points. */ std::vector sorted_distances() const; - /** \internal \brief Returns an upper bound for the diameter of the convex hull of all non infinite points */ - double diameter_bound() const; + /** \internal \brief Returns an upper bound for the bottleneck distance of the finite points. */ + double max_dist_to_diagonal() const; /** \internal \brief Returns the corresponding internal point */ Internal_point get_u_point(int u_point_index) const; /** \internal \brief Returns the corresponding internal point */ @@ -160,13 +160,13 @@ inline Internal_point Persistence_graph::get_v_point(int v_point_index) const { return Internal_point(m, m, v_point_index); } -inline double Persistence_graph::diameter_bound() const { +inline double Persistence_graph::max_dist_to_diagonal() const { double max = 0.; - for (auto it = u.cbegin(); it != u.cend(); it++) - max = (std::max)(max, it->y()); - for (auto it = v.cbegin(); it != v.cend(); it++) - max = (std::max)(max, it->y()); - return max; + for (auto& p : u) + max = (std::max)(max, p.y() - p.x()); + for (auto& p : v) + max = (std::max)(max, p.y() - p.x()); + return max / 2; } } // namespace persistence_diagram -- cgit v1.2.3 From 27a488386c6a3b2b4dbac43534a36f18ef04ac80 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sat, 17 Oct 2020 19:15:58 +0200 Subject: Don't put a (useless) point on the diagonal in the example --- src/python/doc/bottleneck_distance_user.rst | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/src/python/doc/bottleneck_distance_user.rst b/src/python/doc/bottleneck_distance_user.rst index 6c6e08d9..418dd11f 100644 --- a/src/python/doc/bottleneck_distance_user.rst +++ b/src/python/doc/bottleneck_distance_user.rst @@ -35,19 +35,19 @@ The following example explains how the distance is computed: import gudhi - message = "Bottleneck distance = " + '%.1f' % gudhi.bottleneck_distance([[0., 0.]], [[0., 13.]]) + message = "Bottleneck distance = " + '%.1f' % gudhi.bottleneck_distance([[0., 2.]], [[1., 13.]]) print(message) .. testoutput:: - Bottleneck distance = 6.5 + Bottleneck distance = 6.0 .. 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) + The point (1, 13) is at distance 6 from the diagonal and more + specifically from the point (7, 7). Basic example -- cgit v1.2.3 From 911b589081831c98040448c489264fabfe8b5558 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Sat, 17 Oct 2020 23:29:39 +0200 Subject: Handle diagrams with a single point --- src/Bottleneck_distance/include/gudhi/Bottleneck.h | 6 +++++- src/Bottleneck_distance/include/gudhi/Persistence_graph.h | 2 +- src/Bottleneck_distance/test/bottleneck_unit_test.cpp | 5 +++++ src/python/doc/bottleneck_distance_user.rst | 2 +- 4 files changed, 12 insertions(+), 3 deletions(-) diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index ad437710..c916898d 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -36,7 +36,11 @@ namespace persistence_diagram { inline double bottleneck_distance_approx(Persistence_graph& g, double e) { double b_lower_bound = 0.; double b_upper_bound = g.max_dist_to_diagonal(); - const double alpha = std::pow(g.size(), 1. / 5.); + int siz = g.size(); + if (siz <= 1) + // The value of alpha would be wrong in this case + return b_upper_bound; + const double alpha = std::pow(siz, 1. / 5.); Graph_matching m(g); Graph_matching biggest_unperfect(g); while (b_upper_bound - b_lower_bound > 2 * e) { diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h index 04c7c118..33f03b9c 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h @@ -45,7 +45,7 @@ class Persistence_graph { int corresponding_point_in_v(int u_point_index) const; /** \internal \brief Given a point from U and a point from V, returns the distance between those points. */ double distance(int u_point_index, int v_point_index) const; - /** \internal \brief Returns size = |U| = |V|. */ + /** \internal \brief Returns size = |U| + |V|. */ int size() const; /** \internal \brief Is there as many infinite points (alive components) in both diagrams ? */ double bottleneck_alive() const; diff --git a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp index 2c520045..44141baa 100644 --- a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp +++ b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp @@ -153,4 +153,9 @@ BOOST_AUTO_TEST_CASE(global) { BOOST_CHECK(bottleneck_distance(v1, v2, 0.) <= upper_bound / 100.); BOOST_CHECK(bottleneck_distance(v1, v2, upper_bound / 10000.) <= upper_bound / 100. + upper_bound / 10000.); BOOST_CHECK(std::abs(bottleneck_distance(v1, v2, 0.) - bottleneck_distance(v1, v2, upper_bound / 10000.)) <= upper_bound / 10000.); + + std::vector< std::pair > empty; + std::vector< std::pair > one = {{8, 10}}; + BOOST_CHECK(bottleneck_distance(empty, empty) == 0); + BOOST_CHECK(bottleneck_distance(empty, one) == 1); } diff --git a/src/python/doc/bottleneck_distance_user.rst b/src/python/doc/bottleneck_distance_user.rst index 418dd11f..2c74c6dd 100644 --- a/src/python/doc/bottleneck_distance_user.rst +++ b/src/python/doc/bottleneck_distance_user.rst @@ -72,6 +72,6 @@ The output is: .. testoutput:: - Bottleneck distance approximation = 0.81 + Bottleneck distance approximation = 0.72 Bottleneck distance value = 0.75 -- cgit v1.2.3 From b4df19e0555c0b60c4f074ed0baf642a7d1bdc8b Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Tue, 10 Nov 2020 00:55:34 +0100 Subject: Revert change to the example It would require updating the figure. --- src/python/doc/bottleneck_distance_user.rst | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/src/python/doc/bottleneck_distance_user.rst b/src/python/doc/bottleneck_distance_user.rst index 2c74c6dd..7baa76cc 100644 --- a/src/python/doc/bottleneck_distance_user.rst +++ b/src/python/doc/bottleneck_distance_user.rst @@ -35,19 +35,19 @@ The following example explains how the distance is computed: import gudhi - message = "Bottleneck distance = " + '%.1f' % gudhi.bottleneck_distance([[0., 2.]], [[1., 13.]]) + message = "Bottleneck distance = " + '%.1f' % gudhi.bottleneck_distance([[0., 0.]], [[0., 13.]]) print(message) .. testoutput:: - Bottleneck distance = 6.0 + Bottleneck distance = 6.5 .. figure:: ../../doc/Bottleneck_distance/bottleneck_distance_example.png :figclass: align-center - The point (1, 13) is at distance 6 from the diagonal and more - specifically from the point (7, 7). + The point (0, 13) is at distance 6.5 from the diagonal and more + specifically from the point (6.5, 6.5). Basic example -- cgit v1.2.3 From 53376fde3f35576af18fac33d731e8398da7522e Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Fri, 13 Nov 2020 12:39:27 +0100 Subject: Test with negative coordinates --- src/python/test/test_bottleneck_distance.py | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/src/python/test/test_bottleneck_distance.py b/src/python/test/test_bottleneck_distance.py index 6915bea8..07fcc9cc 100755 --- a/src/python/test/test_bottleneck_distance.py +++ b/src/python/test/test_bottleneck_distance.py @@ -25,3 +25,15 @@ def test_basic_bottleneck(): assert gudhi.bottleneck_distance(diag1, diag2, 0.1) == pytest.approx(0.75, abs=0.1) assert gudhi.hera.bottleneck_distance(diag1, diag2, 0) == 0.75 assert gudhi.hera.bottleneck_distance(diag1, diag2, 0.1) == pytest.approx(0.75, rel=0.1) + + import numpy as np + + # Translating both diagrams along the diagonal should not affect the distance, + # checks that negative numbers are not an issue + diag1 = np.array(diag1) - 100 + diag2 = np.array(diag2) - 100 + + assert gudhi.bottleneck_distance(diag1, diag2) == 0.75 + assert gudhi.bottleneck_distance(diag1, diag2, 0.1) == pytest.approx(0.75, abs=0.1) + assert gudhi.hera.bottleneck_distance(diag1, diag2, 0) == 0.75 + assert gudhi.hera.bottleneck_distance(diag1, diag2, 0.1) == pytest.approx(0.75, rel=0.1) -- cgit v1.2.3