diff options
Diffstat (limited to 'src/Bottleneck/include')
| -rw-r--r-- | src/Bottleneck/include/gudhi/Graph_matching.h | 197 | ||||
| -rw-r--r-- | src/Bottleneck/include/gudhi/Layered_neighbors_finder.h | 74 | ||||
| -rw-r--r-- | src/Bottleneck/include/gudhi/Neighbors_finder.h | 96 | ||||
| -rw-r--r-- | src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h | 147 | ||||
| -rw-r--r-- | src/Bottleneck/include/gudhi/Planar_neighbors_finder.h | 119 |
5 files changed, 0 insertions, 633 deletions
diff --git a/src/Bottleneck/include/gudhi/Graph_matching.h b/src/Bottleneck/include/gudhi/Graph_matching.h deleted file mode 100644 index ea47e1d5..00000000 --- a/src/Bottleneck/include/gudhi/Graph_matching.h +++ /dev/null @@ -1,197 +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(s): Francois Godi - * - * Copyright (C) 2015 INRIA Saclay (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 SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ - -#include <deque> -#include <list> -#include <vector> - -#include "gudhi/Layered_neighbors_finder.h" - -namespace Gudhi { - -namespace bottleneck { - -template<typename Persistence_diagram1, typename Persistence_diagram2> -double bottleneck_distance(Persistence_diagram1& diag1, Persistence_diagram2& diag2, double e = 0.); - -class Graph_matching { - public: - Graph_matching(const Persistence_diagrams_graph& g); - Graph_matching& operator=(const Graph_matching& m); - bool perfect() const; - bool multi_augment(); - void set_r(double r); - - private: - const Persistence_diagrams_graph& g; - double r; - std::vector<int> v_to_u; - std::list<int> unmatched_in_u; - - Layered_neighbors_finder* layering() const; - bool augment(Layered_neighbors_finder* layered_nf, int u_start_index, int max_depth); - void update(std::deque<int>& path); -}; - -Graph_matching::Graph_matching(const Persistence_diagrams_graph& g) - : g(g), r(0), v_to_u(g.size()), unmatched_in_u() { - for (int u_point_index = 0; u_point_index < g.size(); ++u_point_index) - unmatched_in_u.emplace_back(u_point_index); -} - -Graph_matching& Graph_matching::operator=(const Graph_matching& m) { - r = m.r; - v_to_u = m.v_to_u; - unmatched_in_u = m.unmatched_in_u; - return *this; -} - -inline bool Graph_matching::perfect() const { - return unmatched_in_u.empty(); -} - -inline bool Graph_matching::multi_augment() { - if (perfect()) - return false; - Layered_neighbors_finder* layered_nf = layering(); - double rn = sqrt(g.size()); - int nblmax = layered_nf->vlayers_number()*2 + 1; - // verification of a necessary criterion - if ((unmatched_in_u.size() > rn && nblmax > rn) || nblmax == 0) - return false; - bool successful = false; - std::list<int>* tries = new std::list<int>(unmatched_in_u); - for (auto it = tries->cbegin(); it != tries->cend(); it++) - successful = successful || augment(layered_nf, *it, nblmax); - delete tries; - delete layered_nf; - return successful; -} - -inline void Graph_matching::set_r(double r) { - this->r = r; -} - -Layered_neighbors_finder* Graph_matching::layering() const { - bool end = false; - int layer = 0; - std::list<int> u_vertices(unmatched_in_u); - std::list<int> v_vertices; - Neighbors_finder nf(g, r); - Layered_neighbors_finder* layered_nf = new Layered_neighbors_finder(g, r); - for (int v_point_index = 0; v_point_index < g.size(); ++v_point_index) - nf.add(v_point_index); - while (!u_vertices.empty()) { - for (auto it = u_vertices.cbegin(); it != u_vertices.cend(); ++it) { - std::list<int>* u_succ = nf.pull_all_near(*it); - for (auto it = u_succ->cbegin(); it != u_succ->cend(); ++it) { - layered_nf->add(*it, layer); - v_vertices.emplace_back(*it); - } - delete u_succ; - } - u_vertices.clear(); - for (auto it = v_vertices.cbegin(); it != v_vertices.cend(); it++) { - if (v_to_u.at(*it) == null_point_index()) - end = true; - else - u_vertices.emplace_back(v_to_u.at(*it)); - } - if (end) - return layered_nf; - v_vertices.clear(); - layer++; - } - return layered_nf; -} - -bool Graph_matching::augment(Layered_neighbors_finder *layered_nf, int u_start_index, int max_depth) { - std::deque<int> path; - path.emplace_back(u_start_index); - // start is a point from U - do { - if (static_cast<int>(path.size()) > max_depth) { - path.pop_back(); - path.pop_back(); - } - if (path.empty()) - return false; - int w = path.back(); - path.emplace_back(layered_nf->pull_near(w, path.size() / 2)); - while (path.back() == null_point_index()) { - path.pop_back(); - path.pop_back(); - if (path.empty()) - return false; - path.pop_back(); - path.emplace_back(layered_nf->pull_near(path.back(), path.size() / 2)); - } - path.emplace_back(v_to_u.at(path.back())); - } while (path.back() != null_point_index()); - path.pop_back(); - update(path); - return true; -} - -void Graph_matching::update(std::deque<int>& path) { - unmatched_in_u.remove(path.front()); - for (auto it = path.cbegin(); it != path.cend(); ++it) { - int tmp = *it; - ++it; - v_to_u[*it] = tmp; - } -} - -template<typename Persistence_diagram1, typename Persistence_diagram2> -double bottleneck_distance(Persistence_diagram1& diag1, Persistence_diagram2& diag2, double e) { - Persistence_diagrams_graph g(diag1, diag2, e); - std::vector<double>* sd = g.sorted_distances(); - int idmin = 0; - int idmax = sd->size() - 1; - double alpha = pow(sd->size(), 0.25); - Graph_matching m(g); - Graph_matching biggest_unperfect = m; - while (idmin != idmax) { - int pas = static_cast<int>((idmax - idmin) / alpha); - m.set_r(sd->at(idmin + pas)); - while (m.multi_augment()) {} - if (m.perfect()) { - idmax = idmin + pas; - m = biggest_unperfect; - } else { - biggest_unperfect = m; - idmin = idmin + pas + 1; - } - } - double b = sd->at(idmin); - delete sd; - return b; -} - -} // namespace bottleneck - -} // namespace Gudhi - -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ diff --git a/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h b/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h deleted file mode 100644 index de36e00b..00000000 --- a/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h +++ /dev/null @@ -1,74 +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(s): Francois Godi - * - * Copyright (C) 2015 INRIA Saclay (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 SRC_BOTTLENECK_INCLUDE_GUDHI_LAYERED_NEIGHBORS_FINDER_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_LAYERED_NEIGHBORS_FINDER_H_ - -#include <vector> - -#include "Neighbors_finder.h" - -// Layered_neighbors_finder is a data structure used to find if a query point from U has neighbors in V in a given -// vlayer of the vlayered persistence diagrams graph. V's points have to be added manually using their index. -// A neighbor returned is automatically removed. - -namespace Gudhi { - -namespace bottleneck { - -class Layered_neighbors_finder { - public: - Layered_neighbors_finder(const Persistence_diagrams_graph& g, double r); - void add(int v_point_index, int vlayer); - int pull_near(int u_point_index, int vlayer); - int vlayers_number() const; - - private: - const Persistence_diagrams_graph& g; - const double r; - std::vector<Neighbors_finder> neighbors_finder; -}; - -Layered_neighbors_finder::Layered_neighbors_finder(const Persistence_diagrams_graph& g, double r) : - g(g), r(r), neighbors_finder() { } - -inline void Layered_neighbors_finder::add(int v_point_index, int vlayer) { - for (int l = neighbors_finder.size(); l <= vlayer; l++) - neighbors_finder.emplace_back(Neighbors_finder(g, r)); - neighbors_finder.at(vlayer).add(v_point_index); -} - -inline int Layered_neighbors_finder::pull_near(int u_point_index, int vlayer) { - if (static_cast<int> (neighbors_finder.size()) <= vlayer) - return null_point_index(); - return neighbors_finder.at(vlayer).pull_near(u_point_index); -} - -inline int Layered_neighbors_finder::vlayers_number() const { - return neighbors_finder.size(); -} - -} // namespace bottleneck - -} // namespace Gudhi - -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_LAYERED_NEIGHBORS_FINDER_H_ diff --git a/src/Bottleneck/include/gudhi/Neighbors_finder.h b/src/Bottleneck/include/gudhi/Neighbors_finder.h deleted file mode 100644 index 98256571..00000000 --- a/src/Bottleneck/include/gudhi/Neighbors_finder.h +++ /dev/null @@ -1,96 +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(s): Francois Godi - * - * Copyright (C) 2015 INRIA Saclay (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 SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ - -#include <unordered_set> -#include <list> - -#include "gudhi/Planar_neighbors_finder.h" - -namespace Gudhi { - -namespace bottleneck { - -// Neighbors_finder is a data structure used to find if a query point from U has neighbors in V -// in the persistence diagrams graph. -// V's points have to be added manually using their index. A neighbor returned is automatically removed. - -class Neighbors_finder { - public: - Neighbors_finder(const Persistence_diagrams_graph& g, double r); - void add(int v_point_index); - int pull_near(int u_point_index); - std::list<int>* pull_all_near(int u_point_index); - - private: - const Persistence_diagrams_graph& g; - const double r; - Planar_neighbors_finder planar_neighbors_f; - std::unordered_set<int> projections_f; -}; - -Neighbors_finder::Neighbors_finder(const Persistence_diagrams_graph& g, double r) : - g(g), r(r), planar_neighbors_f(g, r), projections_f() { } - -inline void Neighbors_finder::add(int v_point_index) { - if (g.on_the_v_diagonal(v_point_index)) - projections_f.emplace(v_point_index); - else - planar_neighbors_f.add(v_point_index); -} - -inline int Neighbors_finder::pull_near(int u_point_index) { - int v_challenger = g.corresponding_point_in_v(u_point_index); - if (planar_neighbors_f.contains(v_challenger) && g.distance(u_point_index, v_challenger) < r) { - planar_neighbors_f.remove(v_challenger); - return v_challenger; - } - if (g.on_the_u_diagonal(u_point_index)) { - auto it = projections_f.cbegin(); - if (it != projections_f.cend()) { - int tmp = *it; - projections_f.erase(it); - return tmp; - } - } else { - return planar_neighbors_f.pull_near(u_point_index); - } - return null_point_index(); -} - -inline std::list<int>* Neighbors_finder::pull_all_near(int u_point_index) { - std::list<int>* all_pull = planar_neighbors_f.pull_all_near(u_point_index); - int last_pull = pull_near(u_point_index); - while (last_pull != null_point_index()) { - all_pull->emplace_back(last_pull); - last_pull = pull_near(u_point_index); - } - return all_pull; -} - -} // namespace bottleneck - -} // namespace Gudhi - -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ diff --git a/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h b/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h deleted file mode 100644 index 73ad940b..00000000 --- a/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h +++ /dev/null @@ -1,147 +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(s): Francois Godi - * - * Copyright (C) 2015 INRIA Saclay (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 SRC_BOTTLENECK_INCLUDE_GUDHI_PERSISTENCE_DIAGRAMS_GRAPH_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_PERSISTENCE_DIAGRAMS_GRAPH_H_ - -#include <vector> -#include <set> -#include <cmath> -#include <utility> // for pair<> -#include <algorithm> // for max - -namespace Gudhi { - -namespace bottleneck { - -// Diagram_point is the type of the persistence diagram's points -typedef std::pair<double, double> Diagram_point; - -// Return the used index for encoding none of the points -int null_point_index(); - -// Persistence_diagrams_graph is the interface beetwen any external representation of the two persistence diagrams and -// the bottleneck distance computation. An interface is necessary to ensure basic functions complexity. - -class Persistence_diagrams_graph { - public: - // Persistence_diagram1 and 2 are the types of any externals representations of persistence diagrams. - // They have to have an iterator over points, which have to have fields first (for birth) and second (for death). - template<typename Persistence_diagram1, typename Persistence_diagram2> - Persistence_diagrams_graph(Persistence_diagram1& diag1, Persistence_diagram2& diag2, double e = 0.); - Persistence_diagrams_graph(); - bool on_the_u_diagonal(int u_point_index) const; - bool on_the_v_diagonal(int v_point_index) const; - int corresponding_point_in_u(int v_point_index) const; - int corresponding_point_in_v(int u_point_index) const; - double distance(int u_point_index, int v_point_index) const; - int size() const; - std::vector<double>* sorted_distances(); - - private: - std::vector<Diagram_point> u; - std::vector<Diagram_point> v; - Diagram_point get_u_point(int u_point_index) const; - Diagram_point get_v_point(int v_point_index) const; -}; - -inline int null_point_index() { - return -1; -} - -template<typename Persistence_diagram1, typename Persistence_diagram2> -Persistence_diagrams_graph::Persistence_diagrams_graph(Persistence_diagram1& diag1, Persistence_diagram2& diag2, double e) - : u(), v() { - for (auto it = diag1.cbegin(); it != diag1.cend(); ++it) - if (it->second - it->first > e) - u.emplace_back(*it); - for (auto it = diag2.cbegin(); it != diag2.cend(); ++it) - if (it->second - it->first > e) - v.emplace_back(*it); - if (u.size() < v.size()) - swap(u, v); -} - -Persistence_diagrams_graph::Persistence_diagrams_graph() - : u(), v() { } - -inline bool Persistence_diagrams_graph::on_the_u_diagonal(int u_point_index) const { - return u_point_index >= static_cast<int> (u.size()); -} - -inline bool Persistence_diagrams_graph::on_the_v_diagonal(int v_point_index) const { - return v_point_index >= static_cast<int> (v.size()); -} - -inline int Persistence_diagrams_graph::corresponding_point_in_u(int v_point_index) const { - return on_the_v_diagonal(v_point_index) ? - v_point_index - static_cast<int> (v.size()) : v_point_index + static_cast<int> (u.size()); -} - -inline int Persistence_diagrams_graph::corresponding_point_in_v(int u_point_index) const { - return on_the_u_diagonal(u_point_index) ? - u_point_index - static_cast<int> (u.size()) : u_point_index + static_cast<int> (v.size()); -} - -inline double Persistence_diagrams_graph::distance(int u_point_index, int v_point_index) const { - // could be optimized for the case where one point is the projection of the other - if (on_the_u_diagonal(u_point_index) && on_the_v_diagonal(v_point_index)) - return 0; - Diagram_point p_u = get_u_point(u_point_index); - Diagram_point p_v = get_v_point(v_point_index); - return (std::max)(std::fabs(p_u.first - p_v.first), std::fabs(p_u.second - p_v.second)); -} - -inline int Persistence_diagrams_graph::size() const { - return static_cast<int> (u.size() + v.size()); -} - -inline std::vector<double>* Persistence_diagrams_graph::sorted_distances() { - // could be optimized - std::set<double> sorted_distances; - for (int u_point_index = 0; u_point_index < size(); ++u_point_index) - for (int v_point_index = 0; v_point_index < size(); ++v_point_index) - sorted_distances.emplace(distance(u_point_index, v_point_index)); - return new std::vector<double>(sorted_distances.cbegin(), sorted_distances.cend()); -} - -inline Diagram_point Persistence_diagrams_graph::get_u_point(int u_point_index) const { - if (!on_the_u_diagonal(u_point_index)) - return u.at(u_point_index); - Diagram_point projector = v.at(corresponding_point_in_v(u_point_index)); - double x = (projector.first + projector.second) / 2; - return Diagram_point(x, x); -} - -inline Diagram_point Persistence_diagrams_graph::get_v_point(int v_point_index) const { - if (!on_the_v_diagonal(v_point_index)) - return v.at(v_point_index); - Diagram_point projector = u.at(corresponding_point_in_u(v_point_index)); - double x = (projector.first + projector.second) / 2; - return Diagram_point(x, x); -} - -} // namespace bottleneck - -} // namespace Gudhi - -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_PERSISTENCE_DIAGRAMS_GRAPH_H_ diff --git a/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h b/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h deleted file mode 100644 index 4af672e4..00000000 --- a/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h +++ /dev/null @@ -1,119 +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(s): Francois Godi - * - * Copyright (C) 2015 INRIA Saclay (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 SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ - -#include <list> -#include <iostream> -#include <set> - -#include "Persistence_diagrams_graph.h" - -namespace Gudhi { - -namespace bottleneck { - -// Planar_neighbors_finder is a data structure used to find if a query point from U has planar neighbors in V with the -// planar distance. -// V's points have to be added manually using their index. A neighbor returned is automatically removed but we can also -// remove points manually using their index. - -class Abstract_planar_neighbors_finder { - public: - Abstract_planar_neighbors_finder(const Persistence_diagrams_graph& g, double r); - virtual ~Abstract_planar_neighbors_finder() = 0; - virtual void add(int v_point_index) = 0; - virtual void remove(int v_point_index) = 0; - virtual bool contains(int v_point_index) const = 0; - virtual int pull_near(int u_point_index) = 0; - virtual std::list<int>* pull_all_near(int u_point_index); - - protected: - const Persistence_diagrams_graph& g; - const double r; -}; - - -// Naive_pnf is a nave implementation of Abstract_planar_neighbors_finder - -class Naive_pnf : public Abstract_planar_neighbors_finder { - public: - Naive_pnf(const Persistence_diagrams_graph& g, double r); - void add(int v_point_index); - void remove(int v_point_index); - bool contains(int v_point_index) const; - int pull_near(int u_point_index); - - private: - std::set<int> candidates; -}; - - -// Planar_neighbors_finder is the used Abstract_planar_neighbors_finder's implementation -typedef Naive_pnf Planar_neighbors_finder; - -Abstract_planar_neighbors_finder::Abstract_planar_neighbors_finder(const Persistence_diagrams_graph& g, double r) : - g(g), r(r) { } - -inline Abstract_planar_neighbors_finder::~Abstract_planar_neighbors_finder() { } - -inline std::list<int>* Abstract_planar_neighbors_finder::pull_all_near(int u_point_index) { - std::list<int>* all_pull = new std::list<int>(); - int last_pull = pull_near(u_point_index); - while (last_pull != null_point_index()) { - all_pull->emplace_back(last_pull); - last_pull = pull_near(u_point_index); - } - return all_pull; -} - -Naive_pnf::Naive_pnf(const Persistence_diagrams_graph& g, double r) : - Abstract_planar_neighbors_finder(g, r), candidates() { } - -inline void Naive_pnf::add(int v_point_index) { - candidates.emplace(v_point_index); -} - -inline void Naive_pnf::remove(int v_point_index) { - candidates.erase(v_point_index); -} - -inline bool Naive_pnf::contains(int v_point_index) const { - return (candidates.count(v_point_index) > 0); -} - -inline int Naive_pnf::pull_near(int u_point_index) { - for (auto it = candidates.begin(); it != candidates.end(); ++it) - if (g.distance(u_point_index, *it) <= r) { - int tmp = *it; - candidates.erase(it); - return tmp; - } - return null_point_index(); -} - -} // namespace bottleneck - -} // namespace Gudhi - -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ |