diff options
7 files changed, 131 insertions, 94 deletions
diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index 00e614f6..ccb558c5 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -37,10 +37,10 @@ namespace bottleneck_distance { * * Bottleneck distance measures the similarity between two persistence diagrams. * It's the shortest distance b for which there exists a perfect matching between - * the points of the two diagrams (+ all the diagonal points) such that + * the points of the two diagrams (and also all the points of the diagonal) such that * any couple of matched points are at distance at most b. * - * \image html perturb_pd.png Bottleneck distance is the length of the longest edge. + * \image html perturb_pd.png Bottleneck distance is the length of the longest edge on this picture. * */ /** @} */ // end defgroup bottleneck_distance diff --git a/src/Bottleneck_distance/example/bottleneck_example.cpp b/src/Bottleneck_distance/example/bottleneck_example.cpp index 0bec9746..fd0f8ed5 100644 --- a/src/Bottleneck_distance/example/bottleneck_example.cpp +++ b/src/Bottleneck_distance/example/bottleneck_example.cpp @@ -22,7 +22,7 @@ #define CGAL_HAS_THREADS -#include <gudhi/Graph_matching.h> +#include <gudhi/Bottleneck.h> #include <iostream> #include <fstream> #include <sstream> diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h new file mode 100644 index 00000000..6b6b1552 --- /dev/null +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -0,0 +1,125 @@ +/* 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(s): Francois Godi + * + * Copyright (C) 2015 INRIA Sophia-Antipolis (France) + * + * 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> + +namespace Gudhi { + +namespace bottleneck_distance { + +/** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams. You get an additive e-approximation. + * + * + * \ingroup bottleneck_distance + */ +template<typename Persistence_diagram1, typename Persistence_diagram2> +double compute(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2, double e = 0.); + +template<typename Persistence_diagram1, typename Persistence_diagram2> +double compute_exactly(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2); + +template<typename Persistence_diagram1, typename Persistence_diagram2> +double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2) { + G::initialize(diag1, diag2, 0.); + std::shared_ptr< std::vector<double> > sd(G::sorted_distances()); + int idmin = 0; + int idmax = sd->size() - 1; + // alpha can be modified, this will change the complexity + double alpha = pow(sd->size(), 0.25); + Graph_matching m; + Graph_matching biggest_unperfect; + while (idmin != idmax) { + int step = static_cast<int>((idmax - idmin) / alpha); + m.set_r(sd->at(idmin + step)); + while (m.multi_augment()); + //The above while compute a maximum matching (according to the r setted before) + if (m.perfect()) { + idmax = idmin + step; + m = biggest_unperfect; + } else { + biggest_unperfect = m; + idmin = idmin + step + 1; + } + } + return sd->at(idmin); +} + +template<typename Persistence_diagram1, typename Persistence_diagram2> +double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { + if(e< std::numeric_limits<double>::min()) + return compute_exactly(diag1, diag2); + G::initialize(diag1, diag2, e); + int in = G::diameter()/e; + int idmin = 0; + int idmax = in; + // alpha can be modified, this will change the complexity + double alpha = pow(in, 0.25); + Graph_matching m; + Graph_matching biggest_unperfect; + while (idmin != idmax) { + int step = static_cast<int>((idmax - idmin) / alpha); + m.set_r(e*(idmin + step)); + while (m.multi_augment()); + //The above while compute a maximum matching (according to the r setted before) + if (m.perfect()) { + idmax = idmin + step; + m = biggest_unperfect; + } else { + biggest_unperfect = m; + idmin = idmin + step + 1; + } + } + return e*(idmin); +} + + + +} // namespace bottleneck_distance + +} // namespace Gudhi + +#endif // BOTTLENECK_H_ + +/* Dichotomic version +template<typename Persistence_diagram1, typename Persistence_diagram2> +double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { + if(e< std::numeric_limits<double>::min()) + return compute_exactly(diag1, diag2); + G::initialize(diag1, diag2, e); + double d = 0.; + double f = G::diameter(); + while (f-d > e){ + Graph_matching m; + m.set_r((d+f)/2.); + while (m.multi_augment()); + //The above while compute a maximum matching (according to the r setted before) + if (m.perfect()) + f = (d+f)/2.; + else + d= (d+f)/2.; + } + return d; +} */ + diff --git a/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree.h b/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree.h index 5b63b290..7b1676cf 100644 --- a/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree.h +++ b/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree.h @@ -21,7 +21,7 @@ #ifndef CGAL_KD_TREE_H #define CGAL_KD_TREE_H -#include "CGAL/Kd_tree_node.h" +#include "Kd_tree_node.h" #include <CGAL/basic.h> #include <CGAL/assertions.h> diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h index 5f579a0c..a8d68a9d 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -31,17 +31,6 @@ namespace Gudhi { namespace bottleneck_distance { -/** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams. You get an additive e-approximation. - * - * - * \ingroup bottleneck_distance - */ -template<typename Persistence_diagram1, typename Persistence_diagram2> -double compute(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2, double e = 0.); - -template<typename Persistence_diagram1, typename Persistence_diagram2> -double compute_exactly(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2); - /** \internal \brief Structure representing a graph matching. The graph is a Persistence_diagrams_graph. * * \ingroup bottleneck_distance @@ -182,86 +171,9 @@ inline void Graph_matching::update(std::deque<int>& path) { } } -template<typename Persistence_diagram1, typename Persistence_diagram2> -double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2) { - G::initialize(diag1, diag2, 0.); - std::shared_ptr< std::vector<double> > sd(G::sorted_distances()); - int idmin = 0; - int idmax = sd->size() - 1; - // alpha can be modified, this will change the complexity - double alpha = pow(sd->size(), 0.25); - Graph_matching m; - Graph_matching biggest_unperfect; - while (idmin != idmax) { - int step = static_cast<int>((idmax - idmin) / alpha); - m.set_r(sd->at(idmin + step)); - while (m.multi_augment()); - //The above while compute a maximum matching (according to the r setted before) - if (m.perfect()) { - idmax = idmin + step; - m = biggest_unperfect; - } else { - biggest_unperfect = m; - idmin = idmin + step + 1; - } - } - return sd->at(idmin); -} - -template<typename Persistence_diagram1, typename Persistence_diagram2> -double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { - if(e< std::numeric_limits<double>::min()) - return compute_exactly(diag1, diag2); - G::initialize(diag1, diag2, e); - int in = G::diameter()/e; - int idmin = 0; - int idmax = in; - // alpha can be modified, this will change the complexity - double alpha = pow(in, 0.25); - Graph_matching m; - Graph_matching biggest_unperfect; - while (idmin != idmax) { - int step = static_cast<int>((idmax - idmin) / alpha); - m.set_r(e*(idmin + step)); - while (m.multi_augment()); - //The above while compute a maximum matching (according to the r setted before) - if (m.perfect()) { - idmax = idmin + step; - m = biggest_unperfect; - } else { - biggest_unperfect = m; - idmin = idmin + step + 1; - } - } - return e*(idmin); -} - - } // namespace bottleneck_distance } // namespace Gudhi #endif // GRAPH_MATCHING_H_ - -/* Dichotomic version -template<typename Persistence_diagram1, typename Persistence_diagram2> -double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { - if(e< std::numeric_limits<double>::min()) - return compute_exactly(diag1, diag2); - G::initialize(diag1, diag2, e); - double d = 0.; - double f = G::diameter(); - while (f-d > e){ - Graph_matching m; - m.set_r((d+f)/2.); - while (m.multi_augment()); - //The above while compute a maximum matching (according to the r setted before) - if (m.perfect()) - f = (d+f)/2.; - else - d= (d+f)/2.; - } - return d; -} */ - diff --git a/src/Bottleneck_distance/test/bottleneck_chrono.cpp b/src/Bottleneck_distance/test/bottleneck_chrono.cpp index 6eed38c5..4c4f4ee6 100644 --- a/src/Bottleneck_distance/test/bottleneck_chrono.cpp +++ b/src/Bottleneck_distance/test/bottleneck_chrono.cpp @@ -20,7 +20,7 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#include <gudhi/Graph_matching.h> +#include <gudhi/Bottleneck.h> #include <chrono> #include <fstream> #include <random> diff --git a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp index 1d753dd8..a3d50ef8 100644 --- a/src/Bottleneck_distance/test/bottleneck_unit_test.cpp +++ b/src/Bottleneck_distance/test/bottleneck_unit_test.cpp @@ -26,7 +26,7 @@ #include <boost/test/unit_test.hpp> #include <random> -#include <gudhi/Graph_matching.h> +#include <gudhi/Bottleneck.h> using namespace Gudhi::bottleneck_distance; |