Bottleneck.h
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2  * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3  * Author: Francois Godi
4  *
5  * Copyright (C) 2015 Inria
6  *
7  * Modification(s):
8  * - 2019/06 Vincent Rouvreau : Fix doxygen warning.
9  * - 2019/08 Vincent Rouvreau: Fix issue #10 for CGAL
10  * - YYYY/MM Author: Description of the modification
11  */
12 
13 #ifndef BOTTLENECK_H_
14 #define BOTTLENECK_H_
15 
16 #include <gudhi/Graph_matching.h>
17 
18 #include <CGAL/version.h> // for CGAL_VERSION_NR
19 
20 #include <vector>
21 #include <algorithm> // for max
22 #include <limits> // for numeric_limits
23 
24 #include <cmath>
25 #include <cfloat> // FLT_EVAL_METHOD
26 
27 // Make compilation fail - required for external projects - https://github.com/GUDHI/gudhi-devel/issues/10
28 #if CGAL_VERSION_NR < 1041101000
29 # error bottleneck_distance is only available for CGAL >= 4.11
30 #endif
31 
32 namespace Gudhi {
33 
34 namespace persistence_diagram {
35 
36 inline double bottleneck_distance_approx(Persistence_graph& g, double e) {
37  double b_lower_bound = 0.;
38  double b_upper_bound = g.diameter_bound();
39  const double alpha = std::pow(g.size(), 1. / 5.);
40  Graph_matching m(g);
41  Graph_matching biggest_unperfect(g);
42  while (b_upper_bound - b_lower_bound > 2 * e) {
43  double step = b_lower_bound + (b_upper_bound - b_lower_bound) / alpha;
44 #if !defined FLT_EVAL_METHOD || FLT_EVAL_METHOD < 0 || FLT_EVAL_METHOD > 1
45  // On platforms where double computation is done with excess precision,
46  // we force it to its true precision so the following test is reliable.
47  volatile double drop_excess_precision = step;
48  step = drop_excess_precision;
49  // Alternative: step = CGAL::IA_force_to_double(step);
50 #endif
51  if (step <= b_lower_bound || step >= b_upper_bound) // Avoid precision problem
52  break;
53  m.set_r(step);
54  while (m.multi_augment()) {} // compute a maximum matching (in the graph corresponding to the current r)
55  if (m.perfect()) {
56  m = biggest_unperfect;
57  b_upper_bound = step;
58  } else {
59  biggest_unperfect = m;
60  b_lower_bound = step;
61  }
62  }
63  return (b_lower_bound + b_upper_bound) / 2.;
64 }
65 
66 inline double bottleneck_distance_exact(Persistence_graph& g) {
67  std::vector<double> sd = g.sorted_distances();
68  long lower_bound_i = 0;
69  long upper_bound_i = sd.size() - 1;
70  const double alpha = std::pow(g.size(), 1. / 5.);
71  Graph_matching m(g);
72  Graph_matching biggest_unperfect(g);
73  while (lower_bound_i != upper_bound_i) {
74  long step = lower_bound_i + static_cast<long> ((upper_bound_i - lower_bound_i - 1) / alpha);
75  m.set_r(sd.at(step));
76  while (m.multi_augment()) {} // compute a maximum matching (in the graph corresponding to the current r)
77  if (m.perfect()) {
78  m = biggest_unperfect;
79  upper_bound_i = step;
80  } else {
81  biggest_unperfect = m;
82  lower_bound_i = step + 1;
83  }
84  }
85  return sd.at(lower_bound_i);
86 }
87 
111 template<typename Persistence_diagram1, typename Persistence_diagram2>
112 double bottleneck_distance(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2,
113  double e = (std::numeric_limits<double>::min)()) {
114  Persistence_graph g(diag1, diag2, e);
115  if (g.bottleneck_alive() == std::numeric_limits<double>::infinity())
116  return std::numeric_limits<double>::infinity();
117  return (std::max)(g.bottleneck_alive(), e == 0. ? bottleneck_distance_exact(g) : bottleneck_distance_approx(g, e));
118 }
119 
120 } // namespace persistence_diagram
121 
122 } // namespace Gudhi
123 
124 #endif // BOTTLENECK_H_
Gudhi::persistence_diagram::bottleneck_distance
double bottleneck_distance(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e=(std::numeric_limits< double >::min)())
Function to compute the Bottleneck distance between two persistence diagrams.
Definition: Bottleneck.h:112
GUDHI  Version 3.1.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Tue Jan 21 2020 09:26:33 for GUDHI by Doxygen 1.8.16