diff options
Diffstat (limited to 'src')
4 files changed, 110 insertions, 142 deletions
diff --git a/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h b/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h index 46a5f375..9cd8d75a 100644 --- a/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h +++ b/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h @@ -27,7 +27,7 @@ #include <list> #include <vector> -#include "Layered_neighbors_finder.h" +#include "Neighbors_finder.h" namespace Gudhi { diff --git a/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h b/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h index 6a970b16..8745e6eb 100644 --- a/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h +++ b/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h @@ -63,14 +63,10 @@ private: Corner_tree xi_yd_order; Corner_tree xd_yi_order; Corner_tree xd_yd_order; - void remove_aux(Corner_tree t, int v_point_index, bool reverse); - template <typename Contiguous_tree t> - int pull_contiguous_aux(); - int pull_corner_aux(); - void build_xi_yi(); - void build_xi_yd(); - void build_xd_yi(); - void build_xd_yd(); + void remove_aux(Corner_tree t, int v_point_index); + template <typename Contiguous_tree> + int pull_contiguous_aux(Contiguous_tree t, bool reverse, int u_point_index); + //int pull_corner_aux(Corner_tree t, bool reverse, int u_point_index); }; @@ -86,7 +82,7 @@ inline bool Grid_cell::contains(int v_point_index) const{ return (xi_order.count(v_point_index) > 0); } -inline void Grid_cell::remove_aux(Corner_tree t, int v_point_index, bool reverse){ +inline void Grid_cell::remove_aux(Corner_tree t, int v_point_index){ if(t.empty()) return; std::list<Hidden_points_tree> hidden_points = t.at(v_point_index); @@ -105,8 +101,8 @@ inline void Grid_cell::remove(int v_point_index){ remove_aux(xd_yd_order,v_point_index); } -template <typename Contiguous_tree t> -inline int Grid_cell::pull_contiguous_aux(Contiguous_tree t, bool reverse){ +template <typename Contiguous_tree> +inline int Grid_cell::pull_contiguous_aux(Contiguous_tree t, bool reverse, int u_point_index){ if(xi_order.empty()) return null_point_index(); if(t.empty()) @@ -120,85 +116,95 @@ inline int Grid_cell::pull_contiguous_aux(Contiguous_tree t, bool reverse){ return null_point_index(); } -//factorization needed \/ \/ \/ - inline int Grid_cell::pull_center(){ if(xi_order.empty()) return null_point_index(); - int v_point_index = *xi_order.begin(); + int v_point_index = *(xi_order.begin()); remove(v_point_index); return v_point_index; } inline int Grid_cell::pull_xi(int u_point_index){ - if(xi_order.empty()) - return null_point_index(); - int v_point_index = *xi_order.begin(); //! - if(G::distance(u_point_index,v_point_index)<=r){ - remove(v_point_index); - return v_point_index; - } - return null_point_index(); + return pull_contiguous_aux(xi_order, false, u_point_index); } inline int Grid_cell::pull_xd(int u_point_index){ - if(xi_order.empty()) - return null_point_index(); - int v_point_index = *xi_order.rbegin(); //! - if(G::distance(u_point_index,v_point_index)<=r){ - remove(v_point_index); - return v_point_index; - } - return null_point_index(); + return pull_contiguous_aux(xi_order, true, u_point_index); } inline int Grid_cell::pull_yi(int u_point_index){ - if(xi_order.empty()) - return null_point_index(); - if(yi_order.empty()) - for(auto it = xi_order.begin(); it!= xi_order.end(); ++it) - yi_order.emplace(*it); - int v_point_index = *yi_order.begin(); //! - if(G::distance(u_point_index,v_point_index)<=r){ - remove(v_point_index); - return v_point_index; - } - return null_point_index(); + return pull_contiguous_aux(yi_order, false, u_point_index); } inline int Grid_cell::pull_yd(int u_point_index){ - if(xi_order.empty()) - return null_point_index(); - if(yi_order.empty()) - for(auto it = xi_order.begin(); it!= xi_order.end(); ++it) - yi_order.emplace(*it); - int v_point_index = *yi_order.rbegin(); //! - if(G::distance(u_point_index,v_point_index)<=r){ - remove(v_point_index); - return v_point_index; - } - return null_point_index(); + return pull_contiguous_aux(yi_order, true, u_point_index); } - -inline int Grid_cell::pull_xi_yi(int u_point_index){ - if(xi_order.empty()) +/* +inline int Grid_cell::pull_corner_aux(Corner_tree t, bool reverse, int u_point_index){ + if(xi_order.empty()) return null_point_index(); - if(xi_yi_order.empty()) - build_xi_yi(); - auto it = xi_yi_order.upper_bound(u_point_index+G::size()); - if(it==xi_yi_order.cbegin()) //! + if(t.empty()) + build_corner(t); + auto it = t.upper_bound(u_point_index+G::size()); + if(it == (reverse ? t.end() : t.begin())) return null_point_index(); - it--; //! + if(!reverse) + it--; int v_point_index = it->first; for(auto it2=it->second.begin();it2!=it->second.end();it2++) - xi_yi_order.emplace(it2->point,it2->hidden); + t.emplace(it2->point,it2->hidden); if(G::distance(u_point_index,v_point_index)<=r){ remove(v_point_index); return v_point_index; } return null_point_index(); +}*/ + +inline int Grid_cell::pull_xi_yi(int u_point_index){ + for(auto it = xi_order.begin(); it!=xi_order.end(); ++it) + if(G::distance(u_point_index,*it)<=r){ + int tmp = *it; + remove(tmp); + return tmp; + } + return(null_point_index()); + //return pull_corner_aux(xi_yi_order, false, u_point_index); +} + +inline int Grid_cell::pull_xi_yd(int u_point_index){ + for(auto it = xi_order.begin(); it!=xi_order.end(); ++it) + if(G::distance(u_point_index,*it)<=r){ + int tmp = *it; + remove(tmp); + return tmp; + } + return(null_point_index()); + //return pull_corner_aux(xi_yd_order, false, u_point_index); } +inline int Grid_cell::pull_xd_yi(int u_point_index){ + for(auto it = xi_order.rbegin(); it!=xi_order.rend(); ++it) + if(G::distance(u_point_index,*it)<=r){ + int tmp = *it; + remove(tmp); + return tmp; + } + return(null_point_index()); + //return pull_corner_aux(xd_yi_order, true, u_point_index); +} + +inline int Grid_cell::pull_xd_yd(int u_point_index){ + for(auto it = xi_order.begin(); it!=xi_order.end(); ++it) + if(G::distance(u_point_index,*it)<=r){ + int tmp = *it; + remove(tmp); + return tmp; + } + return(null_point_index()); + //return pull_corner_aux(xd_yd_order, true, u_point_index); +} + + } // namespace bipartite_graph_matching } // namespace Gudhi diff --git a/src/Bipartite_graph_matching/include/gudhi/Layered_neighbors_finder.h b/src/Bipartite_graph_matching/include/gudhi/Layered_neighbors_finder.h deleted file mode 100644 index 8303627a..00000000 --- a/src/Bipartite_graph_matching/include/gudhi/Layered_neighbors_finder.h +++ /dev/null @@ -1,80 +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 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 SRC_BOTTLENECK_INCLUDE_GUDHI_LAYERED_NEIGHBORS_FINDER_H_ -#define SRC_BOTTLENECK_INCLUDE_GUDHI_LAYERED_NEIGHBORS_FINDER_H_ - -#include <vector> - -#include "Neighbors_finder.h" - -namespace Gudhi { - -namespace bipartite_graph_matching { - -/** \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> neighbors_finder; -}; - -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(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<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 static_cast<int>(neighbors_finder.size()); -} - -} // namespace bipartite_graph_matching - -} // namespace Gudhi - -#endif // SRC_BOTTLENECK_INCLUDE_GUDHI_LAYERED_NEIGHBORS_FINDER_H_ diff --git a/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h b/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h index 879ba300..cae47793 100644 --- a/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h +++ b/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h @@ -58,6 +58,29 @@ private: 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> neighbors_finder; +}; + inline Neighbors_finder::Neighbors_finder(double r) : r(r), planar_neighbors_f(r), projections_f() { } @@ -107,6 +130,25 @@ inline std::unique_ptr< std::list<int> > Neighbors_finder::pull_all_near(int u_p 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(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<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 static_cast<int>(neighbors_finder.size()); +} + } // namespace bipartite_graph_matching } // namespace Gudhi |