From cc1e554f26765bf9993079bef608d9bc4a3308c8 Mon Sep 17 00:00:00 2001 From: fgodi Date: Mon, 28 Nov 2016 14:15:22 +0000 Subject: graph no longer static git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck_integration@1790 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 6bbb8dfaffd09a81ccafac6919e073ed74b9c7e6 --- src/Bottleneck_distance/include/gudhi/Bottleneck.h | 22 ++++++------ .../include/gudhi/Construct_coord_iterator.h | 42 ---------------------- .../include/gudhi/Graph_matching.h | 18 +++++----- .../include/gudhi/Internal_point.h | 18 ++++++++-- .../include/gudhi/Neighbors_finder.h | 36 ++++++++++--------- 5 files changed, 56 insertions(+), 80 deletions(-) delete mode 100644 src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h (limited to 'src/Bottleneck_distance/include') diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index bb0a13d2..52de30be 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -31,14 +31,14 @@ namespace bottleneck_distance { template double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2) { - G::initialize(diag1, diag2, 0.); - std::vector sd(G::sorted_distances()); + Persistence_graph g(diag1, diag2, 0.); + std::vector sd(g.sorted_distances()); int idmin = 0; int idmax = sd.size() - 1; - // alpha can be modified, this will change the complexity + // alpha can change the complexity double alpha = pow(sd.size(), 0.25); - Graph_matching m; - Graph_matching biggest_unperfect; + Graph_matching m(g); + Graph_matching biggest_unperfect(g); while (idmin != idmax) { int step = static_cast((idmax - idmin) / alpha); m.set_r(sd.at(idmin + step)); @@ -64,14 +64,14 @@ template double compute(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e=0.) { if(e == 0.) return compute_exactly(diag1, diag2); - G::initialize(diag1, diag2, e); - int in = G::diameter()/e + 1; + Persistence_graph g(diag1, diag2, e); + int in = g.diameter_bound()/e + 1; 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; + // alpha can change the complexity + double alpha = pow(in, 0.10); + Graph_matching m(g); + Graph_matching biggest_unperfect(g); while (idmin != idmax) { int step = static_cast((idmax - idmin) / alpha); m.set_r(e*(idmin + step)); diff --git a/src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h b/src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h deleted file mode 100644 index 0959dd03..00000000 --- a/src/Bottleneck_distance/include/gudhi/Construct_coord_iterator.h +++ /dev/null @@ -1,42 +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: Francois Godi - * - * Copyright (C) 2015 INRIA (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::bottleneck_distance::Internal_point Internal_point; - -struct Construct_coord_iterator { - typedef const double* result_type; - const double* operator()(const Internal_point& p) const - { return p.vec; } - const double* operator()(const Internal_point& p, int) const - { return 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 index fa20b2a2..10b7073a 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -36,7 +36,7 @@ namespace bottleneck_distance { class Graph_matching { public: /** \internal \brief Constructor constructing an empty matching. */ - explicit Graph_matching(); + explicit Graph_matching(Persistence_graph &g); /** \internal \brief Copy operator. */ Graph_matching& operator=(const Graph_matching& m); /** \internal \brief Is the matching perfect ? */ @@ -47,6 +47,7 @@ public: void set_r(double r); private: + Persistence_graph& g; 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; @@ -61,13 +62,14 @@ private: void update(std::vector & 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) +inline Graph_matching::Graph_matching(Persistence_graph& g) + : g(g), 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) { + g = m.g; r = m.r; v_to_u = m.v_to_u; unmatched_in_u = m.unmatched_in_u; @@ -83,7 +85,7 @@ inline bool Graph_matching::multi_augment() { return false; Layered_neighbors_finder layered_nf(layering()); int max_depth = layered_nf.vlayers_number()*2 - 1; - double rn = sqrt(G::size()); + 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; @@ -130,10 +132,10 @@ inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u inline Layered_neighbors_finder 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) + Neighbors_finder nf(g, r); + for (int v_point_index = 0; v_point_index < g.size(); ++v_point_index) nf.add(v_point_index); - Layered_neighbors_finder layered_nf(r); + Layered_neighbors_finder layered_nf(g, 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) { diff --git a/src/Bottleneck_distance/include/gudhi/Internal_point.h b/src/Bottleneck_distance/include/gudhi/Internal_point.h index 78aad470..1a050d48 100644 --- a/src/Bottleneck_distance/include/gudhi/Internal_point.h +++ b/src/Bottleneck_distance/include/gudhi/Internal_point.h @@ -35,7 +35,7 @@ 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; } + Internal_point(double x, double y, int p_i) { 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 ]; } @@ -44,7 +44,7 @@ struct Internal_point { { return point_index==p.point_index; } - bool operator!=(const Internal_point& p) const { return ! (*this == p); } + bool operator!=(const Internal_point& p) const { return !(*this == p); } }; inline int null_point_index() { @@ -55,4 +55,18 @@ inline int null_point_index() { } // namespace Gudhi +namespace CGAL { + +typedef Gudhi::bottleneck_distance::Internal_point Internal_point; + +struct Construct_coord_iterator { + typedef const double* result_type; + const double* operator()(const Internal_point& p) const + { return p.vec; } + const double* operator()(const Internal_point& p, int) const + { return p.vec+2; } +}; + +} //namespace CGAL + #endif // INTERNAL_POINT_H_ diff --git a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h index f2d9abb2..f28e21a2 100644 --- a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h +++ b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h @@ -31,8 +31,8 @@ #include #include -#include -#include +#include +#include #include @@ -57,7 +57,7 @@ class Neighbors_finder { public: /** \internal \brief Constructor taking the near distance definition as parameter. */ - Neighbors_finder(double r); + Neighbors_finder(const Persistence_graph& g, 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. */ @@ -66,6 +66,7 @@ public: std::vector pull_all_near(int u_point_index); private: + const Persistence_graph& g; const double r; Kd_tree kd_t; std::unordered_set projections_f; @@ -81,7 +82,7 @@ private: class Layered_neighbors_finder { public: /** \internal \brief Constructor taking the near distance definition as parameter. */ - Layered_neighbors_finder(double r); + Layered_neighbors_finder(const Persistence_graph& g, 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. */ @@ -90,43 +91,44 @@ public: int vlayers_number() const; private: + const Persistence_graph& g; const double r; std::vector> neighbors_finder; }; -inline Neighbors_finder::Neighbors_finder(double r) : - r(r), kd_t(), projections_f() { } +inline Neighbors_finder::Neighbors_finder(const Persistence_graph& g, double r) : + g(g), r(r), kd_t(), projections_f() { } inline void Neighbors_finder::add(int v_point_index) { - if (G::on_the_v_diagonal(v_point_index)) + if (g.on_the_v_diagonal(v_point_index)) projections_f.emplace(v_point_index); else - kd_t.insert(G::get_v_point(v_point_index)); + kd_t.insert(g.get_v_point(v_point_index)); } 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()){ + 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(); projections_f.erase(tmp); } - else if (projections_f.count(c) && (G::distance(u_point_index, c) <= r)){ + else if (projections_f.count(c) && (g.distance(u_point_index, c) <= r)){ //Is the query point near to its projection ? tmp = c; projections_f.erase(tmp); } else{ //Is the query point near to a V point in the plane ? - Internal_point u_point = G::get_u_point(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) + if(it==search.end() || g.distance(u_point_index, it->first.point_index) > r) return null_point_index(); tmp = it->first.point_index; - kd_t.remove(G::get_v_point(tmp)); + kd_t.remove(g.get_v_point(tmp)); } return tmp; } @@ -141,12 +143,12 @@ inline std::vector Neighbors_finder::pull_all_near(int u_point_index) { return all_pull; } -inline Layered_neighbors_finder::Layered_neighbors_finder(double r) : - r(r), neighbors_finder() { } +inline Layered_neighbors_finder::Layered_neighbors_finder(const Persistence_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(std::shared_ptr(new Neighbors_finder(r))); + neighbors_finder.emplace_back(std::shared_ptr(new Neighbors_finder(g, r))); neighbors_finder.at(vlayer)->add(v_point_index); } -- cgit v1.2.3