diff options
author | fgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2015-06-30 16:34:18 +0000 |
---|---|---|
committer | fgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2015-06-30 16:34:18 +0000 |
commit | 835b8ac56556a71e39738775d2d2572cba03a5e4 (patch) | |
tree | 1ac33993ca86e9b1efe1a7f7a29a158c9381fbd4 /src | |
parent | a79d06bc9ffb42e0281b5d25cb55170b564f5574 (diff) |
before rm Grid_Cell
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneckDistance@668 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: bfa8c56429a2d4a9f38822ac9cfbe4c4b360cede
Diffstat (limited to 'src')
5 files changed, 39 insertions, 51 deletions
diff --git a/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h b/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h index 9cd8d75a..5133646d 100644 --- a/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h +++ b/src/Bipartite_graph_matching/include/gudhi/Graph_matching.h @@ -24,8 +24,6 @@ #define SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ #include <deque> -#include <list> -#include <vector> #include "Neighbors_finder.h" diff --git a/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h b/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h index 8745e6eb..f0b09b52 100644 --- a/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h +++ b/src/Bipartite_graph_matching/include/gudhi/Grid_cell.h @@ -33,10 +33,7 @@ namespace Gudhi { namespace bipartite_graph_matching { -/** \internal \brief TODO - * - * \ingroup bottleneck_distance - */ + class Grid_cell { public: Grid_cell(double r); @@ -139,7 +136,7 @@ inline int Grid_cell::pull_yi(int u_point_index){ inline int Grid_cell::pull_yd(int u_point_index){ return pull_contiguous_aux(yi_order, true, u_point_index); } -/* + inline int Grid_cell::pull_corner_aux(Corner_tree t, bool reverse, int u_point_index){ if(xi_order.empty()) return null_point_index(); @@ -158,7 +155,7 @@ inline int Grid_cell::pull_corner_aux(Corner_tree t, bool reverse, int u_point_i 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) @@ -210,3 +207,4 @@ inline int Grid_cell::pull_xd_yd(int u_point_index){ } // namespace Gudhi #endif // SRC_BOTTLENECK_INCLUDE_GUDHI_GRID_CELL_H_ + diff --git a/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h b/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h index cae47793..78b9debc 100644 --- a/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h +++ b/src/Bipartite_graph_matching/include/gudhi/Neighbors_finder.h @@ -24,7 +24,6 @@ #define SRC_BOTTLENECK_INCLUDE_GUDHI_NEIGHBORS_FINDER_H_ #include <unordered_set> -#include <list> #include "Planar_neighbors_finder.h" diff --git a/src/Bipartite_graph_matching/include/gudhi/Persistence_diagrams_graph.h b/src/Bipartite_graph_matching/include/gudhi/Persistence_diagrams_graph.h index 1b23a1b2..a1fe9285 100644 --- a/src/Bipartite_graph_matching/include/gudhi/Persistence_diagrams_graph.h +++ b/src/Bipartite_graph_matching/include/gudhi/Persistence_diagrams_graph.h @@ -61,10 +61,6 @@ public: static int size(); /** \internal \brief Returns the O(n^2) sorted distances between the points. */ static std::unique_ptr< std::vector<double> > sorted_distances(); - /** \internal \brief Compare points regarding x%r coordinate. Use v_point_index for V points and u_point_index + G::size() for U points. */ - struct Compare_x{double r; Compare_x(double r); bool operator()(const int point_index_1, const int point_index_2) const;}; - /** \internal \brief Compare points regarding y%r coordinate. Use v_point_index for V points and u_point_index + G::size() for U points. */ - struct Compare_y{double r; Compare_y(double r);bool operator()(const int point_index_1, const int point_index_2) const;}; private: /** \internal \typedef \brief Internal_point is the internal points representation, indexes used outside. */ @@ -73,6 +69,8 @@ private: static std::vector<Internal_point> 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; }; /** \internal \typedef \brief Shorter alias */ @@ -157,32 +155,6 @@ inline G::Internal_point G::get_v_point(int v_point_index) { return Internal_point(x, x); } -G::Compare_x::Compare_x(double r) - : r(r){ } - -G::Compare_y::Compare_y(double r) - : r(r){ } - -inline bool G::Compare_x::operator()(const int point_index_1, const int point_index_2) const{ - G::Internal_point p1 = point_index_1 < G::size() ? G::get_v_point(point_index_1) : G::get_u_point(point_index_1 - G::size()); - G::Internal_point p2 = point_index_2 < G::size() ? G::get_v_point(point_index_2) : G::get_u_point(point_index_2 - G::size()); - double x1 = fmod(p1.first,r); - double x2 = fmod(p2.first,r); - if(x1 == x2) - return point_index_1 > point_index_2; - return x1 < x2; -} - -inline bool G::Compare_y::operator()(const int point_index_1, const int point_index_2) const{ - G::Internal_point p1 = point_index_1 < G::size() ? G::get_v_point(point_index_1) : G::get_u_point(point_index_1 - G::size()); - G::Internal_point p2 = point_index_2 < G::size() ? G::get_v_point(point_index_2) : G::get_u_point(point_index_2 - G::size()); - double y1 = fmod(p1.second,r); - double y2 = fmod(p2.second,r); - if(y1 == y2) - return point_index_1 > point_index_2; - return y1 < y2; -} - } // namespace bipartite_graph_matching } // namespace Gudhi diff --git a/src/Bipartite_graph_matching/include/gudhi/Planar_neighbors_finder.h b/src/Bipartite_graph_matching/include/gudhi/Planar_neighbors_finder.h index 60a1dd96..50829be6 100644 --- a/src/Bipartite_graph_matching/include/gudhi/Planar_neighbors_finder.h +++ b/src/Bipartite_graph_matching/include/gudhi/Planar_neighbors_finder.h @@ -24,7 +24,7 @@ #define SRC_BOTTLENECK_INCLUDE_GUDHI_PLANAR_NEIGHBORS_FINDER_H_ #include <list> -#include <set> +#include <map> #include "Persistence_diagrams_graph.h" #include "Grid_cell.h" @@ -78,7 +78,8 @@ public: int pull_near(int u_point_index); private: - std::set<int> candidates; + std::pair<int,int> get_v_key(int v_point_index) const; + std::multimap<std::pair<int,int>,int> grid; }; /** \internal \typedef \brief Planar_neighbors_finder is the used Abstract_planar_neighbors_finder's implementation. */ @@ -101,27 +102,47 @@ inline std::unique_ptr< std::list<int> > Abstract_planar_neighbors_finder::pull_ } inline Naive_pnf::Naive_pnf(double r) : - Abstract_planar_neighbors_finder(r), candidates() { } + Abstract_planar_neighbors_finder(r), grid() { } + + +inline std::pair<int,int> Naive_pnf::get_v_key(int v_point_index) const{ + G::Internal_point v_point = G::get_v_point(v_point_index); + return std::make_pair(static_cast<int>(v_point.first/r), static_cast<int>(v_point.second/r)); +} inline void Naive_pnf::add(int v_point_index) { - candidates.emplace(v_point_index); + grid.emplace(get_v_key(v_point_index),v_point_index); } inline void Naive_pnf::remove(int v_point_index) { - candidates.erase(v_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 { - return (candidates.count(v_point_index) > 0); + 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) { - 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; - } + G::Internal_point u_point = G::get_u_point(u_point_index); + int i0 = static_cast<int>(u_point.first/r); + int j0 = static_cast<int>(u_point.second/r); + for(int i = i0 -1; i<= i0 + 1; i++) + for(int j = j0 -1; j<= j0 + 1; j++) + for(auto it = grid.find(std::make_pair(i,j)); 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(); } |