Merge pull request #405 from mglisse/botneg

Bottleneck distance for one point or negative coordinates

5 files changed, 34 insertions, 13 deletions

diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h
index e466828a..c916898d 100644
--- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h
+++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h
@@ -35,8 +35,12 @@ 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();
-  const double alpha = std::pow(g.size(), 1. / 5.);
+  double b_upper_bound = g.max_dist_to_diagonal();
+  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 e1e3522e..33f03b9c 100644
--- a/src/Bottleneck_distance/include/gudhi/Persistence_graph.h
+++ b/src/Bottleneck_distance/include/gudhi/Persistence_graph.h
@@ -45,14 +45,14 @@ 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;
   /** \internal \brief Returns the O(n^2) sorted distances between the points. */
   std::vector<double> 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
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<double, double> > empty;
+  std::vector< std::pair<double, double> > 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 6c6e08d9..7baa76cc 100644
--- a/src/python/doc/bottleneck_distance_user.rst
+++ b/src/python/doc/bottleneck_distance_user.rst
@@ -47,7 +47,7 @@ The following example explains how the distance is computed:
     :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)
+    specifically from the point (6.5, 6.5).
 
 
 Basic example
@@ -72,6 +72,6 @@ The output is:
 
 .. testoutput::
 
-    Bottleneck distance approximation = 0.81
+    Bottleneck distance approximation = 0.72
     Bottleneck distance value = 0.75
 
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)