From ef48b9447c7270ba63d45a76e4d2e6ecb1a7d199 Mon Sep 17 00:00:00 2001 From: fgodi Date: Thu, 25 Jun 2015 10:19:49 +0000 Subject: tests unitaires terminés MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneckDistance@647 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: aca61ea029d72ddfbf8eca3e4db00da3e7b268c3 --- src/Bottleneck/include/gudhi/Graph_matching.h | 284 +++++++++++---------- .../include/gudhi/Layered_neighbors_finder.h | 8 +- src/Bottleneck/include/gudhi/Neighbors_finder.h | 93 ++++--- .../include/gudhi/Persistence_diagrams_graph.h | 27 +- .../include/gudhi/Planar_neighbors_finder.h | 16 +- 5 files changed, 231 insertions(+), 197 deletions(-) (limited to 'src/Bottleneck/include') diff --git a/src/Bottleneck/include/gudhi/Graph_matching.h b/src/Bottleneck/include/gudhi/Graph_matching.h index 4cd3180e..9f36e936 100644 --- a/src/Bottleneck/include/gudhi/Graph_matching.h +++ b/src/Bottleneck/include/gudhi/Graph_matching.h @@ -22,12 +22,12 @@ #ifndef SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ #define SRC_BOTTLENECK_INCLUDE_GUDHI_GRAPH_MATCHING_H_ - +//#define DEBUG #include #include #include -#include "gudhi/Layered_neighbors_finder.h" +#include "Layered_neighbors_finder.h" namespace Gudhi { @@ -37,158 +37,182 @@ template double bottleneck_distance(const Persistence_diagram1& diag1, const Persistence_diagram2& diag2, double e = 0.); class Graph_matching { - public: - explicit 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 v_to_u; - std::list 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* path); +public: + explicit 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 v_to_u; + std::list unmatched_in_u; + + std::unique_ptr layering() const; + bool augment(Layered_neighbors_finder & layered_nf, int u_start_index, int max_depth); + void update(std::deque & 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); + : 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); } 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; + 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::perfect() const { +#ifdef DEBUG + std::cout << " perfect? unmatched_in_u.size = " << unmatched_in_u.size() << std::endl << std::flush; +#endif + 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* tries = new std::list(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 */ bool Graph_matching::multi_augment() { + if (perfect()) + return false; +#ifdef DEBUG + std::cout << " multi augment" << std::endl << std::flush; +#endif + Layered_neighbors_finder layered_nf = *layering(); + double rn = sqrt(g.size()); + int max_depth = layered_nf.vlayers_number()*2 - 1; +#ifdef DEBUG + std::cout<< " nb_max_layer = " << max_depth << std::endl << std::flush; +#endif + // verification of a necessary criterion + 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++){ + const bool tmp = augment(layered_nf, *it, max_depth); //force augment evaluation even if successful is already true + successful = successful || tmp; + } + return successful; } -inline void Graph_matching::set_r(double r) { - this->r = r; +/* 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 u_vertices(unmatched_in_u); - std::list 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* 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) { +#ifdef DEBUG + std::cout << " augment" << std::endl << std::flush; +#endif +#ifdef DEBUG + std::cout << " u_start_index = " << u_start_index << std::endl << std::flush; +#endif + std::deque path; + path.emplace_back(u_start_index); + // u_start is a point from U + do { +#ifdef DEBUG + std::cout << " do" << std::endl << std::flush; + std::cout << " path.size = " << static_cast(path.size()) << std::endl << std::flush; +#endif + 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())); +#ifdef DEBUG + std::cout << " v_to_u = " << path.back() << std::endl << std::flush; +#endif + } while (path.back() != null_point_index()); + path.pop_back(); + update(path); + return true; } -bool Graph_matching::augment(Layered_neighbors_finder *layered_nf, int u_start_index, int max_depth) { - std::deque* path = new std::deque(); - path->emplace_back(u_start_index); - // start is a point from U - do { - if (static_cast(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)); +std::unique_ptr Graph_matching::layering() const { +#ifdef DEBUG + std::cout << " layering" << std::endl << std::flush; +#endif + bool end = false; + int layer = 0; + std::list u_vertices(unmatched_in_u); + std::list v_vertices; + Neighbors_finder nf(g, r); + for (int v_point_index = 0; v_point_index < g.size(); ++v_point_index) + nf.add(v_point_index); + std::unique_ptr layered_nf(new Layered_neighbors_finder(g, r)); + while (!u_vertices.empty()) { + for (auto it = u_vertices.cbegin(); it != u_vertices.cend(); ++it) { + std::unique_ptr< std::list > u_succ = std::move(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); + } + } + 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++; } - path->emplace_back(v_to_u.at(path->back())); - } while (path->back() != null_point_index()); - path->pop_back(); - update(path); - delete path; - return true; + return layered_nf; } -void Graph_matching::update(std::deque *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; - } +void Graph_matching::update(std::deque& path) { +#ifdef DEBUG + std::cout << " update" << std::endl << std::flush; +#endif + 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 double bottleneck_distance(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2, double e) { - Persistence_diagrams_graph g(diag1, diag2, e); - std::vector* 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(g); - while (idmin != idmax) { - int pas = static_cast((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; + Persistence_diagrams_graph g(diag1, diag2, e); + std::unique_ptr< std::vector > sd = std::move(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(g); + while (idmin != idmax) { + int pas = static_cast((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; + double b = sd->at(idmin); + return b; } } // namespace bottleneck diff --git a/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h b/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h index 80e5b5ed..1cf83393 100644 --- a/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h +++ b/src/Bottleneck/include/gudhi/Layered_neighbors_finder.h @@ -51,20 +51,20 @@ class Layered_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) { +/* 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) { +/* 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 neighbors_finder.size(); +/* inline */ int Layered_neighbors_finder::vlayers_number() const { + return static_cast(neighbors_finder.size()); } } // namespace bottleneck diff --git a/src/Bottleneck/include/gudhi/Neighbors_finder.h b/src/Bottleneck/include/gudhi/Neighbors_finder.h index 6a05e1a0..0fad9889 100644 --- a/src/Bottleneck/include/gudhi/Neighbors_finder.h +++ b/src/Bottleneck/include/gudhi/Neighbors_finder.h @@ -26,7 +26,7 @@ #include #include -#include "gudhi/Planar_neighbors_finder.h" +#include "Planar_neighbors_finder.h" namespace Gudhi { @@ -37,56 +37,65 @@ namespace bottleneck { // 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* 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 projections_f; +public: + Neighbors_finder(const Persistence_diagrams_graph& g, double r); + void add(int v_point_index); + int pull_near(int u_point_index); + std::unique_ptr< std::list > 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 projections_f; + void remove(int v_point_index); + bool contains(int v_point_index); }; 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 */ 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 */ 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 std::list* Neighbors_finder::pull_all_near(int u_point_index) { - 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 */ 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.cbegin()!=projections_f.cend()) + tmp = *projections_f.cbegin(); + else if (contains(c) && (g.distance(u_point_index, c) <= r)) + tmp = c; + else + tmp = planar_neighbors_f.pull_near(u_point_index); + remove(tmp); + return tmp; +} + +std::unique_ptr< std::list > Neighbors_finder::pull_all_near(int u_point_index) { + std::unique_ptr< std::list > all_pull = std::move(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 diff --git a/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h b/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h index 105f9059..644c1cd8 100644 --- a/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h +++ b/src/Bottleneck/include/gudhi/Persistence_diagrams_graph.h @@ -55,7 +55,7 @@ class Persistence_diagrams_graph { 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* sorted_distances(); + std::unique_ptr< std::vector > sorted_distances(); private: std::vector u; @@ -64,7 +64,7 @@ class Persistence_diagrams_graph { Diagram_point get_v_point(int v_point_index) const; }; -inline int null_point_index() { +/* inline */ int null_point_index() { return -1; } @@ -85,47 +85,48 @@ Persistence_diagrams_graph::Persistence_diagrams_graph(const Persistence_diagram Persistence_diagrams_graph::Persistence_diagrams_graph() : u(), v() { } -inline bool Persistence_diagrams_graph::on_the_u_diagonal(int u_point_index) const { +/* inline */ bool Persistence_diagrams_graph::on_the_u_diagonal(int u_point_index) const { return u_point_index >= static_cast (u.size()); } -inline bool Persistence_diagrams_graph::on_the_v_diagonal(int v_point_index) const { +/* inline */ bool Persistence_diagrams_graph::on_the_v_diagonal(int v_point_index) const { return v_point_index >= static_cast (v.size()); } -inline int Persistence_diagrams_graph::corresponding_point_in_u(int v_point_index) const { +/* 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 (v.size()) : v_point_index + static_cast (u.size()); } -inline int Persistence_diagrams_graph::corresponding_point_in_v(int u_point_index) const { +/* 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 (u.size()) : u_point_index + static_cast (v.size()); } -inline double Persistence_diagrams_graph::distance(int u_point_index, int v_point_index) const { +/* 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)); + 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 { +/* inline */ int Persistence_diagrams_graph::size() const { return static_cast (u.size() + v.size()); } -inline std::vector* Persistence_diagrams_graph::sorted_distances() { +/* inline */ std::unique_ptr< std::vector > Persistence_diagrams_graph::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)); - return new std::vector(sorted_distances.cbegin(), sorted_distances.cend()); + std::unique_ptr< std::vector > sd_up(new std::vector(sorted_distances.cbegin(), sorted_distances.cend())); + return sd_up; } -inline Diagram_point Persistence_diagrams_graph::get_u_point(int u_point_index) const { +/* 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)); @@ -133,7 +134,7 @@ inline Diagram_point Persistence_diagrams_graph::get_u_point(int u_point_index) return Diagram_point(x, x); } -inline Diagram_point Persistence_diagrams_graph::get_v_point(int v_point_index) const { +/* 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)); diff --git a/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h b/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h index 3d04aa97..e558239d 100644 --- a/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h +++ b/src/Bottleneck/include/gudhi/Planar_neighbors_finder.h @@ -45,7 +45,7 @@ class Abstract_planar_neighbors_finder { 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* pull_all_near(int u_point_index); + virtual std::unique_ptr< std::list > pull_all_near(int u_point_index); protected: const Persistence_diagrams_graph& g; @@ -74,10 +74,10 @@ 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 */ Abstract_planar_neighbors_finder::~Abstract_planar_neighbors_finder() { } -inline std::list* Abstract_planar_neighbors_finder::pull_all_near(int u_point_index) { - std::list* all_pull = new std::list(); +/* inline */ std::unique_ptr< std::list > Abstract_planar_neighbors_finder::pull_all_near(int u_point_index) { + std::unique_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); @@ -89,19 +89,19 @@ inline std::list* Abstract_planar_neighbors_finder::pull_all_near(int u_poi 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) { +/* inline */ void Naive_pnf::add(int v_point_index) { candidates.emplace(v_point_index); } -inline void Naive_pnf::remove(int 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 { +/* 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) { +/* 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; -- cgit v1.2.3