From 3b5b94c90c81ae4938a89b2b4df8b1173f100ee3 Mon Sep 17 00:00:00 2001 From: fgodi Date: Thu, 2 Jun 2016 17:09:48 +0000 Subject: renaming git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneckDistance@1240 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 53bcbf20e176a21dc41ef3c4d4295b1e9aa959b0 --- .../include/CGAL/Miscellaneous.h | 51 +++++ .../include/gudhi/Graph_matching.h | 233 +++++++++++++++++++++ .../include/gudhi/Internal_point.h | 74 +++++++ .../include/gudhi/Neighbors_finder.h | 154 ++++++++++++++ .../include/gudhi/Persistence_diagrams_graph.h | 168 +++++++++++++++ .../include/gudhi/Planar_neighbors_finder.h | 218 +++++++++++++++++++ 6 files changed, 898 insertions(+) create mode 100644 src/Bottleneck_distance/include/CGAL/Miscellaneous.h create mode 100644 src/Bottleneck_distance/include/gudhi/Graph_matching.h create mode 100644 src/Bottleneck_distance/include/gudhi/Internal_point.h create mode 100644 src/Bottleneck_distance/include/gudhi/Neighbors_finder.h create mode 100644 src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h create mode 100644 src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h (limited to 'src/Bottleneck_distance/include') diff --git a/src/Bottleneck_distance/include/CGAL/Miscellaneous.h b/src/Bottleneck_distance/include/CGAL/Miscellaneous.h new file mode 100644 index 00000000..4de787fb --- /dev/null +++ b/src/Bottleneck_distance/include/CGAL/Miscellaneous.h @@ -0,0 +1,51 @@ +/* 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 . + */ + +#ifndef SRC_BOTTLENECK_INCLUDE_CGAL_MISCELLANEOUS_H_ +#define SRC_BOTTLENECK_INCLUDE_CGAL_MISCELLANEOUS_H_ + +#include + +namespace CGAL { + +typedef Gudhi::bipartite_graph_matching::Internal_point Internal_point; + +template <> +struct Kernel_traits { + struct Kernel { + typedef double FT; + typedef double RT; + }; +}; + + +struct Construct_coord_iterator { + typedef const double* result_type; + const double* operator()(const Internal_point& p) const + { return static_cast(p.vec); } + const double* operator()(const Internal_point& p, int) const + { return static_cast(p.vec+2); } +}; + +} //namespace CGAL + +#endif // SRC_BOTTLENECK_INCLUDE_CGAL_MISCELLANEOUS_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h new file mode 100644 index 00000000..d8860841 --- /dev/null +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -0,0 +1,233 @@ +/* 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 . + */ + +#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ +#define SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ + +#include + +#include + +namespace Gudhi { + +namespace Bottleneck_distance { + +/** \brief Function to use in order to compute the Bottleneck distance between two persistence diagrams. + * + * + * + * \ingroup bottleneck_distance + */ +template +double compute(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2, double e = 0.); + +/** \internal \brief Structure representing a graph matching. The graph is a Persistence_diagrams_graph. + * + * \ingroup bottleneck_distance + */ +class Graph_matching { +public: + /** \internal \brief Constructor constructing an empty matching. */ + explicit Graph_matching(); + /** \internal \brief Copy operator. */ + Graph_matching& operator=(const Graph_matching& m); + /** \internal \brief Is the matching perfect ? */ + bool perfect() const; + /** \internal \brief Augments the matching with a maximal set of edge-disjoint shortest augmenting paths. */ + bool multi_augment(); + /** \internal \brief Sets the maximum length of the edges allowed to be added in the matching, 0 initially. */ + void set_r(double r); + +private: + double r; + /** \internal \brief Given a point from V, provides its matched point in U, null_point_index() if there isn't. */ + std::vector v_to_u; + /** \internal \brief All the unmatched points in U. */ + std::list unmatched_in_u; + + /** \internal \brief Provides a Layered_neighbors_finder dividing the graph in layers. Basically a BFS. */ + std::shared_ptr layering() const; + /** \internal \brief Augments the matching with a simple path no longer than max_depth. Basically a DFS. */ + bool augment(Layered_neighbors_finder & layered_nf, int u_start_index, int max_depth); + /** \internal \brief Update the matching with the simple augmenting path given as parameter. */ + void update(std::deque & path); +}; + +inline Graph_matching::Graph_matching() + : r(0.), v_to_u(G::size(), null_point_index()), 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); +} + +inline 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(); + int max_depth = layered_nf.vlayers_number()*2 - 1; + double rn = sqrt(G::size()); + // verification of a necessary criterion in order to shortcut if possible + if (max_depth <0 || (unmatched_in_u.size() > rn && max_depth >= rn)) + return false; + bool successful = false; + std::list tries(unmatched_in_u); + for (auto it = tries.cbegin(); it != tries.cend(); it++) + // 'augment' has side-effects which have to be always executed, don't change order + successful = augment(layered_nf, *it, max_depth) || successful; + return successful; +} + +inline void Graph_matching::set_r(double r) { + this->r = r; +} + +inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u_start_index, int max_depth) { + //V vertices have at most one successor, thus when we backtrack from U we can directly pop_back 2 vertices. + std::deque path; + path.emplace_back(u_start_index); + do { + if (static_cast(path.size()) > max_depth) { + path.pop_back(); + path.pop_back(); + } + if (path.empty()) + return false; + path.emplace_back(layered_nf.pull_near(path.back(), static_cast(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()); + //if v_to_u.at(path.back()) has no successor, path.back() is an exposed vertex + path.pop_back(); + update(path); + return true; +} + +inline std::shared_ptr Graph_matching::layering() const { + std::list u_vertices(unmatched_in_u); + std::list v_vertices; + Neighbors_finder nf(r); + for (int v_point_index = 0; v_point_index < G::size(); ++v_point_index) + nf.add(v_point_index); + std::shared_ptr layered_nf(new Layered_neighbors_finder(r)); + for(int layer = 0; !u_vertices.empty(); layer++) { + // one layer is one step in the BFS + for (auto it1 = u_vertices.cbegin(); it1 != u_vertices.cend(); ++it1) { + std::shared_ptr> u_succ(nf.pull_all_near(*it1)); + for (auto it2 = u_succ->begin(); it2 != u_succ->end(); ++it2) { + layered_nf->add(*it2, layer); + v_vertices.emplace_back(*it2); + } + } + // When the above for finishes, we have progress of one half-step (from U to V) in the BFS + u_vertices.clear(); + bool end = false; + for (auto it = v_vertices.cbegin(); it != v_vertices.cend(); it++) + if (v_to_u.at(*it) == null_point_index()) + // we stop when a nearest exposed V vertex (from U exposed vertices) has been found + end = true; + else + u_vertices.emplace_back(v_to_u.at(*it)); + // When the above for finishes, we have progress of one half-step (from V to U) in the BFS + if (end) + return layered_nf; + v_vertices.clear(); + } + return layered_nf; +} + +inline void Graph_matching::update(std::deque& path) { + unmatched_in_u.remove(path.front()); + for (auto it = path.cbegin(); it != path.cend(); ++it) { + // Be careful, the iterator is incremented twice each time + int tmp = *it; + v_to_u[*(++it)] = tmp; + } +} + +template +double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2) { + G::initialize(diag1, diag2, 0.); + std::shared_ptr< std::vector > 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((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 +double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { + if(e< std::numeric_limits::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; +} + +} // namespace Bottleneck_distance + +} // namespace Gudhi + +#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Internal_point.h b/src/Bottleneck_distance/include/gudhi/Internal_point.h new file mode 100644 index 00000000..2080900d --- /dev/null +++ b/src/Bottleneck_distance/include/gudhi/Internal_point.h @@ -0,0 +1,74 @@ +/* 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 . + */ + +#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_INTERNAL_POINT_H_ +#define SRC_BOTTLENECK_INCLUDE_GUDHI_INTERNAL_POINT_H_ + +namespace Gudhi { + +namespace Bottleneck_distance { + +/** \internal \brief Returns the used index for encoding none of the points */ +int null_point_index(); + +/** \internal \typedef \brief Internal_point is the internal points representation, indexes used outside. */ +struct Internal_point { + double vec[2]; + int point_index; + Internal_point() {} + Internal_point(double x, double y, int p_i = null_point_index()) { vec[0]=x; vec[1]=y; point_index = p_i; } + double x() const { return vec[ 0 ]; } + double y() const { return vec[ 1 ]; } + double& x() { return vec[ 0 ]; } + double& y() { return vec[ 1 ]; } + bool operator==(const Internal_point& p) const + { + return point_index==p.point_index; + } + bool operator!=(const Internal_point& p) const { return ! (*this == p); } +/* +Useless + friend void swap(Internal_point& a, Internal_point& b) + { + using std::swap; + double x_tmp = a.vec[0]; + double y_tmp = a.vec[1]; + int pi_tmp = a.point_index; + a.vec[0] = b.vec[0]; + a.vec[1] = b.vec[1]; + a.point_index = b.point_index; + b.vec[0] = x_tmp; + b.vec[1] = y_tmp; + b.point_index = pi_tmp; + } +*/ +}; + +inline int null_point_index() { + return -1; +} + +} // namespace Bottleneck_distance + +} // namespace Gudhi + +#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_INTERNAL_POINT_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h new file mode 100644 index 00000000..7ad79126 --- /dev/null +++ b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h @@ -0,0 +1,154 @@ +/* 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 . + */ + +#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ +#define SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ + +#include +#include + +namespace Gudhi { + +namespace Bottleneck_distance { + +/** \internal \brief data structure used to find any point (including projections) in V near to a query point from U + * (which can be a projection). + * + * V points have to be added manually using their index and before the first pull. A neighbor pulled is automatically removed. + * + * \ingroup bottleneck_distance + */ +class Neighbors_finder { +public: + /** \internal \brief Constructor taking the near distance definition as parameter. */ + Neighbors_finder(double r); + /** \internal \brief A point added will be possibly pulled. */ + void add(int v_point_index); + /** \internal \brief Returns and remove a V point near to the U point given as parameter, null_point_index() if there isn't such a point. */ + int pull_near(int u_point_index); + /** \internal \brief Returns and remove all the V points near to the U point given as parameter. */ + std::shared_ptr< std::list > pull_all_near(int u_point_index); + +private: + const double r; + Planar_neighbors_finder planar_neighbors_f; + std::unordered_set projections_f; + void remove(int v_point_index); + bool contains(int v_point_index); +}; + +/** \internal \brief data structure used to find any point (including projections) in V near to a query point from U + * (which can be a projection) in a layered graph layer given as parmeter. + * + * V points have to be added manually using their index and before the first pull. A neighbor pulled is automatically removed. + * + * \ingroup bottleneck_distance + */ +class Layered_neighbors_finder { +public: + /** \internal \brief Constructor taking the near distance definition as parameter. */ + Layered_neighbors_finder(double r); + /** \internal \brief A point added will be possibly pulled. */ + void add(int v_point_index, int vlayer); + /** \internal \brief Returns and remove a V point near to the U point given as parameter, null_point_index() if there isn't such a point. */ + int pull_near(int u_point_index, int vlayer); + /** \internal \brief Returns the number of layers. */ + int vlayers_number() const; + +private: + const double r; + std::vector> neighbors_finder; +}; + +inline Neighbors_finder::Neighbors_finder(double r) : + r(r), planar_neighbors_f(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 void Neighbors_finder::remove(int v_point_index) { + if(v_point_index == null_point_index()) + return; + if (G::on_the_v_diagonal(v_point_index)) + projections_f.erase(v_point_index); + else + planar_neighbors_f.remove(v_point_index); +} + +inline bool Neighbors_finder::contains(int v_point_index) { + return planar_neighbors_f.contains(v_point_index) || (projections_f.count(v_point_index)>0); +} + +inline int Neighbors_finder::pull_near(int u_point_index) { + int tmp; + int c = G::corresponding_point_in_v(u_point_index); + if (G::on_the_u_diagonal(u_point_index) && !projections_f.empty()) + //Any pair of projection is at distance 0 + tmp = *projections_f.cbegin(); + else if (contains(c) && (G::distance(u_point_index, c) <= r)) + //Is the query point near to its projection ? + tmp = c; + else + //Is the query point near to a V point in the plane ? + tmp = planar_neighbors_f.pull_near(u_point_index); + remove(tmp); + return tmp; +} + +inline std::shared_ptr< std::list > Neighbors_finder::pull_all_near(int u_point_index) { + std::shared_ptr< std::list > 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; +} + +inline Layered_neighbors_finder::Layered_neighbors_finder(double r) : + 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(std::shared_ptr(new Neighbors_finder(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 (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 static_cast(neighbors_finder.size()); +} + +} // namespace Bottleneck_distance + +} // namespace Gudhi + +#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h new file mode 100644 index 00000000..e8a46f1c --- /dev/null +++ b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h @@ -0,0 +1,168 @@ +/* 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 . + */ + +#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_PERSISTENCE_DIAGRAMS_GRAPH_H_ +#define SRC_BOTTLENECK_INCLUDE_GUDHI_PERSISTENCE_DIAGRAMS_GRAPH_H_ + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace Gudhi { + +namespace Bottleneck_distance { + + +/** \internal \brief Structure representing an euclidean bipartite graph containing + * the points from the two persistence diagrams (including the projections). + * + * \ingroup bottleneck_distance + */ +class Persistence_diagrams_graph { +public: + /** \internal \brief Initializer taking 2 Point (concept) ranges as parameters. */ + template + static void initialize(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2, double e); + /** \internal \brief Is the given point from U the projection of a point in V ? */ + static bool on_the_u_diagonal(int u_point_index); + /** \internal \brief Is the given point from V the projection of a point in U ? */ + static bool on_the_v_diagonal(int v_point_index); + /** \internal \brief Given a point from V, returns the corresponding (projection or projector) point in U. */ + static int corresponding_point_in_u(int v_point_index); + /** \internal \brief Given a point from U, returns the corresponding (projection or projector) point in V. */ + static int corresponding_point_in_v(int u_point_index); + /** \internal \brief Given a point from U and a point from V, returns the distance between those points. */ + static double distance(int u_point_index, int v_point_index); + /** \internal \brief Returns size = |U| = |V|. */ + static int size(); + /** \internal \brief Returns the O(n^2) sorted distances between the points. */ + static std::shared_ptr< std::vector > sorted_distances(); + /** \internal \brief Returns an upper bound of the diameter of the convex hull */ + static double diameter(); + +private: + static std::vector u; + static std::vector v; + static Internal_point get_u_point(int u_point_index); + static Internal_point get_v_point(int v_point_index); + + friend class Naive_pnf; + friend class Cgal_pnf; +}; + +/** \internal \typedef \brief Shorter alias */ +typedef Persistence_diagrams_graph G; + +// static initialization +std::vector G::u = [] {return std::vector();}(); +std::vector G::v = [] {return std::vector();}(); + +template +inline void G::initialize(const Persistence_diagram1 &diag1, + const Persistence_diagram2 &diag2, double e){ + u.clear(); + v.clear(); + for (auto it = diag1.cbegin(); it != diag1.cend(); ++it) + if (it->second - it->first > e) + u.push_back(Internal_point(it->first, it->second, u.size())); + for (auto it = diag2.cbegin(); it != diag2.cend(); ++it) + if (it->second - it->first > e) + v.push_back(Internal_point(it->first, it->second, v.size())); + if (u.size() < v.size()) + swap(u, v); +} + +inline bool G::on_the_u_diagonal(int u_point_index) { + return u_point_index >= static_cast (u.size()); +} + +inline bool G::on_the_v_diagonal(int v_point_index) { + return v_point_index >= static_cast (v.size()); +} + +inline int G::corresponding_point_in_u(int v_point_index) { + return on_the_v_diagonal(v_point_index) ? + v_point_index - static_cast (v.size()) : v_point_index + static_cast (u.size()); +} + +inline int G::corresponding_point_in_v(int u_point_index) { + return on_the_u_diagonal(u_point_index) ? + u_point_index - static_cast (u.size()) : u_point_index + static_cast (v.size()); +} + +inline double G::distance(int u_point_index, int v_point_index) { + if (on_the_u_diagonal(u_point_index) && on_the_v_diagonal(v_point_index)) + return 0; + Internal_point p_u = get_u_point(u_point_index); + Internal_point p_v = get_v_point(v_point_index); + return std::max(std::fabs(p_u.x() - p_v.x()), std::fabs(p_u.y() - p_v.y())); +} + +inline int G::size() { + return static_cast (u.size() + v.size()); +} + +inline std::shared_ptr< std::vector > G::sorted_distances() { + // could be optimized + std::set 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)); + std::shared_ptr< std::vector > sd_up(new std::vector(sorted_distances.cbegin(), sorted_distances.cend())); + return sd_up; +} + +inline Internal_point G::get_u_point(int u_point_index) { + if (!on_the_u_diagonal(u_point_index)) + return u.at(u_point_index); + Internal_point projector = v.at(corresponding_point_in_v(u_point_index)); + double m = (projector.x() + projector.y()) / 2; + return Internal_point(m,m,u_point_index); +} + +inline Internal_point G::get_v_point(int v_point_index) { + if (!on_the_v_diagonal(v_point_index)) + return v.at(v_point_index); + Internal_point projector = u.at(corresponding_point_in_u(v_point_index)); + double m = (projector.x() + projector.y()) / 2; + return Internal_point(m,m,v_point_index); +} + +inline double G::diameter() { + double max = 0.; + for(it = u.cbegin(); it != u.cend(); it++) + max = std::max(max,it->y()); + for(it = v.cbegin(); it != v.cend(); it++) + max = std::max(max,it->y()); + return max; +} + +} // namespace Bottleneck_distance + +} // namespace Gudhi + +#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_PERSISTENCE_DIAGRAMS_GRAPH_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h new file mode 100644 index 00000000..c0b6383f --- /dev/null +++ b/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h @@ -0,0 +1,218 @@ +/* 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 . + */ + +#ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ +#define SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ + +#include +#include +#include +#include +#include +#include +#include + + +namespace Gudhi { + +namespace Bottleneck_distance { + +/** \internal \brief Structure used to find any point in V near (according to the planar distance) to a query point from U. + * + * V points have to be added manually using their index and before the first remove/pull. A neighbor pulled is automatically removed. but we can also + * remove points manually using their index. + * + * \ingroup bottleneck_distance + */ +class Naive_pnf { +public: + /** \internal \brief Constructor taking the near distance definition as parameter. */ + Naive_pnf(double r_); + /** \internal \brief A point added will be possibly pulled. */ + void add(int v_point_index); + /** \internal \brief A point manually removed will no longer be possibly pulled. */ + void remove(int v_point_index); + /** \internal \brief Can the point given as parameter be returned ? */ + bool contains(int v_point_index) const; + /** \internal \brief Provide and remove a V point near to the U point given as parameter, null_point_index() if there isn't such a point. */ + int pull_near(int u_point_index); + /** \internal \brief Provide and remove all the V points near to the U point given as parameter. */ + virtual std::shared_ptr< std::list > pull_all_near(int u_point_index); + +private: + double r; + std::pair get_v_key(int v_point_index) const; + std::multimap,int> grid; +}; + +class Cgal_pnf { + + typedef CGAL::Dimension_tag<2> D; + typedef CGAL::Search_traits Traits; + typedef CGAL::Weighted_Minkowski_distance Distance; + typedef CGAL::Orthogonal_incremental_neighbor_search K_neighbor_search; + typedef K_neighbor_search::Tree Kd_tree; + + +public: + /** \internal \brief Constructor taking the near distance definition as parameter. */ + Cgal_pnf(double r_); + /** \internal \brief A point added will be possibly pulled. */ + void add(int v_point_index); + /** \internal \brief A point manually removed will no longer be possibly pulled. */ + void remove(int v_point_index); + /** \internal \brief Can the point given as parameter be returned ? */ + bool contains(int v_point_index) const; + /** \internal \brief Provide a V point near to the U point given as parameter, null_point_index() if there isn't such a point. */ + int pull_near(int u_point_index); + /** \internal \brief Provide and remove all the V points near to the U point given as parameter. */ + virtual std::shared_ptr< std::list > pull_all_near(int u_point_index); + +private: + double r; + std::set contents; + Kd_tree kd_t; +}; + +/** \internal \typedef \brief Planar_neighbors_finder is the used implementation. */ +typedef Naive_pnf Planar_neighbors_finder; + +inline Naive_pnf::Naive_pnf(double r_) : + r(r_), grid() { } + + +inline std::pair Naive_pnf::get_v_key(int v_point_index) const{ + Internal_point v_point = G::get_v_point(v_point_index); + return std::make_pair(static_cast(v_point.x()/r), static_cast(v_point.y()/r)); +} + +inline void Naive_pnf::add(int v_point_index) { + grid.emplace(get_v_key(v_point_index),v_point_index); +} + +inline void Naive_pnf::remove(int v_point_index) { + if(v_point_index != null_point_index()) + for(auto it = grid.find(get_v_key(v_point_index)); it!=grid.end(); it++) + if(it->second==v_point_index){ + grid.erase(it); + return; + } +} + +inline bool Naive_pnf::contains(int v_point_index) const { + if(v_point_index == null_point_index()) + return false; + for(auto it = grid.find(get_v_key(v_point_index)); it!=grid.end(); it++) + if(it->second==v_point_index) + return true; + return false; +} + +inline int Naive_pnf::pull_near(int u_point_index) { + Internal_point u_point = G::get_u_point(u_point_index); + int i0 = static_cast(u_point.x()/r); + int j0 = static_cast(u_point.y()/r); + for(int i = 1; i<= 3; i++) + for(int j = 1; j<= 3; j++) + for(auto it = grid.find(std::make_pair(i0 +(i%3)-1, j0+(j%3)-1)); it!=grid.end(); it++) + if (G::distance(u_point_index, it->second) <= r) { + int tmp = it->second; + grid.erase(it); + return tmp; + } + return null_point_index(); +} + +inline std::shared_ptr< std::list > Naive_pnf::pull_all_near(int u_point_index) { + std::shared_ptr< std::list > all_pull(new std::list); + Internal_point u_point = G::get_u_point(u_point_index); + int i0 = static_cast(u_point.x()/r); + int j0 = static_cast(u_point.y()/r); + for(int i = 1; i<= 3; i++) + for(int j = 1; j<= 3; j++) + for(auto it = grid.find(std::make_pair(i0 +(i%3)-1, j0+(j%3)-1)); it!=grid.end();) + if (G::distance(u_point_index, it->second) <= r) { + all_pull->emplace_back(it->second); + it = grid.erase(it); + } + else it++; + return all_pull; +} + + +/** \internal \brief Constructor taking the near distance definition as parameter. */ +inline Cgal_pnf::Cgal_pnf(double r_) + : r(r_), contents(), kd_t() {} + + +/** \internal \brief A point added will be possibly pulled. */ +inline void Cgal_pnf::add(int v_point_index){ + if(v_point_index == null_point_index()) + return; + contents.insert(v_point_index); + kd_t.insert(G::get_v_point(v_point_index)); +} + +/** \internal \brief A point manually removed will no longer be possibly pulled. */ +inline void Cgal_pnf::remove(int v_point_index){ + if(contains(v_point_index)){ + contents.erase(v_point_index); + kd_t.remove(G::get_v_point(v_point_index)); + } +} + +/** \internal \brief Can the point given as parameter be returned ? */ +inline bool Cgal_pnf::contains(int v_point_index) const{ + if(v_point_index == null_point_index()) + return false; + return contents.count(v_point_index)>0; +} + +/** \internal \brief Provide and remove a V point near to the U point given as parameter, null_point_index() if there isn't such a point. */ +inline int Cgal_pnf::pull_near(int u_point_index){ + Internal_point u_point = G::get_u_point(u_point_index); + std::vector w = {1., 1.}; + K_neighbor_search search(kd_t, u_point, 0., true, Distance(0, 2, w)); + auto it = search.begin(); + if(it==search.end() || G::distance(u_point_index, it->first.point_index) > r) + return null_point_index(); + int tmp = it->first.point_index; + remove(tmp); + return tmp; +} + +inline std::shared_ptr< std::list > Cgal_pnf::pull_all_near(int u_point_index) { + std::shared_ptr< std::list > all_pull(new std::list); + 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_distance + +} // namespace Gudhi + +#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ -- cgit v1.2.3