diff options
Diffstat (limited to 'include/gudhi/Bottleneck.h')
-rw-r--r-- | include/gudhi/Bottleneck.h | 123 |
1 files changed, 0 insertions, 123 deletions
diff --git a/include/gudhi/Bottleneck.h b/include/gudhi/Bottleneck.h deleted file mode 100644 index 7a553006..00000000 --- a/include/gudhi/Bottleneck.h +++ /dev/null @@ -1,123 +0,0 @@ -/* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author: Francois Godi - * - * Copyright (C) 2015 Inria - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ - -#ifndef BOTTLENECK_H_ -#define BOTTLENECK_H_ - -#include <gudhi/Graph_matching.h> - -#include <vector> -#include <algorithm> // for max -#include <limits> // for numeric_limits - -#include <cmath> -#include <cfloat> // FLT_EVAL_METHOD - -namespace Gudhi { - -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.); - Graph_matching m(g); - Graph_matching biggest_unperfect(g); - while (b_upper_bound - b_lower_bound > 2 * e) { - double step = b_lower_bound + (b_upper_bound - b_lower_bound) / alpha; -#if !defined FLT_EVAL_METHOD || FLT_EVAL_METHOD < 0 || FLT_EVAL_METHOD > 1 - // On platforms where double computation is done with excess precision, - // we force it to its true precision so the following test is reliable. - volatile double drop_excess_precision = step; - step = drop_excess_precision; - // Alternative: step = CGAL::IA_force_to_double(step); -#endif - if (step <= b_lower_bound || step >= b_upper_bound) // Avoid precision problem - break; - m.set_r(step); - while (m.multi_augment()) {} // compute a maximum matching (in the graph corresponding to the current r) - if (m.perfect()) { - m = biggest_unperfect; - b_upper_bound = step; - } else { - biggest_unperfect = m; - b_lower_bound = step; - } - } - return (b_lower_bound + b_upper_bound) / 2.; -} - -inline double bottleneck_distance_exact(Persistence_graph& g) { - std::vector<double> sd = g.sorted_distances(); - long lower_bound_i = 0; - long upper_bound_i = sd.size() - 1; - const double alpha = std::pow(g.size(), 1. / 5.); - Graph_matching m(g); - Graph_matching biggest_unperfect(g); - while (lower_bound_i != upper_bound_i) { - long step = lower_bound_i + static_cast<long> ((upper_bound_i - lower_bound_i - 1) / alpha); - m.set_r(sd.at(step)); - while (m.multi_augment()) {} // compute a maximum matching (in the graph corresponding to the current r) - if (m.perfect()) { - m = biggest_unperfect; - upper_bound_i = step; - } else { - biggest_unperfect = m; - lower_bound_i = step + 1; - } - } - return sd.at(lower_bound_i); -} - -/** \brief Function to compute the Bottleneck distance between two persistence diagrams. - * - * \tparam Persistence_diagram1,Persistence_diagram2 - * models of the concept `PersistenceDiagram`. - * \param[in] e - * \parblock - * If `e` is 0, this uses an expensive algorithm to compute the exact distance. - * - * If `e` is not 0, it asks for an additive `e`-approximation, and currently - * also allows a small multiplicative error (the last 2 or 3 bits of the - * mantissa may be wrong). This version of the algorithm takes advantage of the - * limited precision of `double` and is usually a lot faster to compute, - * whatever the value of `e`. - * - * Thus, by default, `e` is the smallest positive double. - * \endparblock - * - * \ingroup bottleneck_distance - */ -template<typename Persistence_diagram1, typename Persistence_diagram2> -double bottleneck_distance(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, - double e = (std::numeric_limits<double>::min)()) { - Persistence_graph g(diag1, diag2, e); - if (g.bottleneck_alive() == std::numeric_limits<double>::infinity()) - return std::numeric_limits<double>::infinity(); - return (std::max)(g.bottleneck_alive(), e == 0. ? bottleneck_distance_exact(g) : bottleneck_distance_approx(g, e)); -} - -} // namespace persistence_diagram - -} // namespace Gudhi - -#endif // BOTTLENECK_H_ |