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.max_dist_to_diagonal();
39  int siz = g.size();
40  if (siz <= 1)
41  // The value of alpha would be wrong in this case
42  return b_upper_bound;
43  const double alpha = std::pow(siz, 1. / 5.);
44  Graph_matching m(g);
45  Graph_matching biggest_unperfect(g);
46  while (b_upper_bound - b_lower_bound > 2 * e) {
47  double step = b_lower_bound + (b_upper_bound - b_lower_bound) / alpha;
48 #if !defined FLT_EVAL_METHOD || FLT_EVAL_METHOD < 0 || FLT_EVAL_METHOD > 1
49  // On platforms where double computation is done with excess precision,
50  // we force it to its true precision so the following test is reliable.
51  volatile double drop_excess_precision = step;
52  step = drop_excess_precision;
53  // Alternative: step = CGAL::IA_force_to_double(step);
54 #endif
55  if (step <= b_lower_bound || step >= b_upper_bound) // Avoid precision problem
56  break;
57  m.set_r(step);
58  while (m.multi_augment()) {} // compute a maximum matching (in the graph corresponding to the current r)
59  if (m.perfect()) {
60  m = biggest_unperfect;
61  b_upper_bound = step;
62  } else {
63  biggest_unperfect = m;
64  b_lower_bound = step;
65  }
66  }
67  return (b_lower_bound + b_upper_bound) / 2.;
68 }
69 
70 inline double bottleneck_distance_exact(Persistence_graph& g) {
71  std::vector<double> sd = g.sorted_distances();
72  long lower_bound_i = 0;
73  long upper_bound_i = sd.size() - 1;
74  const double alpha = std::pow(g.size(), 1. / 5.);
75  Graph_matching m(g);
76  Graph_matching biggest_unperfect(g);
77  while (lower_bound_i != upper_bound_i) {
78  long step = lower_bound_i + static_cast<long> ((upper_bound_i - lower_bound_i - 1) / alpha);
79  m.set_r(sd.at(step));
80  while (m.multi_augment()) {} // compute a maximum matching (in the graph corresponding to the current r)
81  if (m.perfect()) {
82  m = biggest_unperfect;
83  upper_bound_i = step;
84  } else {
85  biggest_unperfect = m;
86  lower_bound_i = step + 1;
87  }
88  }
89  return sd.at(lower_bound_i);
90 }
91 
115 template<typename Persistence_diagram1, typename Persistence_diagram2>
116 double bottleneck_distance(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2,
117  double e = (std::numeric_limits<double>::min)()) {
118  Persistence_graph g(diag1, diag2, e);
119  if (g.bottleneck_alive() == std::numeric_limits<double>::infinity())
120  return std::numeric_limits<double>::infinity();
121  return (std::max)(g.bottleneck_alive(), e == 0. ? bottleneck_distance_exact(g) : bottleneck_distance_approx(g, e));
122 }
123 
124 } // namespace persistence_diagram
125 
126 } // namespace Gudhi
127 
128 #endif // BOTTLENECK_H_
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:116
GUDHIdev  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Wed Apr 6 2022 19:26:28 for GUDHIdev by Doxygen 1.9.1