Bottleneck.h
1 /* This file is part of the Gudhi Library. The Gudhi library
2  * (Geometric Understanding in Higher Dimensions) is a generic C++
3  * library for computational topology.
4  *
5  * Author: Francois Godi
6  *
7  * Copyright (C) 2015 Inria
8  *
9  * This program is free software: you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #ifndef BOTTLENECK_H_
24 #define BOTTLENECK_H_
25 
26 #include <gudhi/Graph_matching.h>
27 
28 #include <vector>
29 #include <algorithm> // for max
30 #include <limits> // for numeric_limits
31 
32 #include <cmath>
33 #include <cfloat> // FLT_EVAL_METHOD
34 
35 namespace Gudhi {
36 
37 namespace persistence_diagram {
38 
39 inline double bottleneck_distance_approx(Persistence_graph& g, double e) {
40  double b_lower_bound = 0.;
41  double b_upper_bound = g.diameter_bound();
42  const double alpha = std::pow(g.size(), 1. / 5.);
43  Graph_matching m(g);
44  Graph_matching biggest_unperfect(g);
45  while (b_upper_bound - b_lower_bound > 2 * e) {
46  double step = b_lower_bound + (b_upper_bound - b_lower_bound) / alpha;
47 #if !defined FLT_EVAL_METHOD || FLT_EVAL_METHOD < 0 || FLT_EVAL_METHOD > 1
48  // On platforms where double computation is done with excess precision,
49  // we force it to its true precision so the following test is reliable.
50  volatile double drop_excess_precision = step;
51  step = drop_excess_precision;
52  // Alternative: step = CGAL::IA_force_to_double(step);
53 #endif
54  if (step <= b_lower_bound || step >= b_upper_bound) // Avoid precision problem
55  break;
56  m.set_r(step);
57  while (m.multi_augment()) {} // compute a maximum matching (in the graph corresponding to the current r)
58  if (m.perfect()) {
59  m = biggest_unperfect;
60  b_upper_bound = step;
61  } else {
62  biggest_unperfect = m;
63  b_lower_bound = step;
64  }
65  }
66  return (b_lower_bound + b_upper_bound) / 2.;
67 }
68 
69 inline double bottleneck_distance_exact(Persistence_graph& g) {
70  std::vector<double> sd = g.sorted_distances();
71  long lower_bound_i = 0;
72  long upper_bound_i = sd.size() - 1;
73  const double alpha = std::pow(g.size(), 1. / 5.);
74  Graph_matching m(g);
75  Graph_matching biggest_unperfect(g);
76  while (lower_bound_i != upper_bound_i) {
77  long step = lower_bound_i + static_cast<long> ((upper_bound_i - lower_bound_i - 1) / alpha);
78  m.set_r(sd.at(step));
79  while (m.multi_augment()) {} // compute a maximum matching (in the graph corresponding to the current r)
80  if (m.perfect()) {
81  m = biggest_unperfect;
82  upper_bound_i = step;
83  } else {
84  biggest_unperfect = m;
85  lower_bound_i = step + 1;
86  }
87  }
88  return sd.at(lower_bound_i);
89 }
90 
110 template<typename Persistence_diagram1, typename Persistence_diagram2>
111 double bottleneck_distance(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2,
112  double e = (std::numeric_limits<double>::min)()) {
113  Persistence_graph g(diag1, diag2, e);
114  if (g.bottleneck_alive() == std::numeric_limits<double>::infinity())
115  return std::numeric_limits<double>::infinity();
116  return (std::max)(g.bottleneck_alive(), e == 0. ? bottleneck_distance_exact(g) : bottleneck_distance_approx(g, e));
117 }
118 
119 } // namespace persistence_diagram
120 
121 } // namespace Gudhi
122 
123 #endif // BOTTLENECK_H_
Definition: SimplicialComplexForAlpha.h:26
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:111
GUDHI  Version 2.3.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : GPL v3 Generated on Fri Oct 5 2018 15:05:03 for GUDHI by Doxygen 1.8.13