diff options
Diffstat (limited to 'src')
7 files changed, 32 insertions, 43 deletions
diff --git a/src/Bottleneck_distance/include/gudhi/Bottleneck.h b/src/Bottleneck_distance/include/gudhi/Bottleneck.h index 6b6b1552..1ae7788c 100644 --- a/src/Bottleneck_distance/include/gudhi/Bottleneck.h +++ b/src/Bottleneck_distance/include/gudhi/Bottleneck.h @@ -43,16 +43,16 @@ double compute_exactly(const Persistence_diagram1& diag1, const Persistence_diag template<typename Persistence_diagram1, typename Persistence_diagram2> double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diagram2 &diag2) { G::initialize(diag1, diag2, 0.); - std::shared_ptr< std::vector<double> > sd(G::sorted_distances()); + std::vector<double> sd(G::sorted_distances()); int idmin = 0; - int idmax = sd->size() - 1; + int idmax = sd.size() - 1; // alpha can be modified, this will change the complexity - double alpha = pow(sd->size(), 0.25); + double alpha = pow(sd.size(), 0.25); Graph_matching m; Graph_matching biggest_unperfect; while (idmin != idmax) { int step = static_cast<int>((idmax - idmin) / alpha); - m.set_r(sd->at(idmin + step)); + 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()) { @@ -63,7 +63,7 @@ double compute_exactly(const Persistence_diagram1 &diag1, const Persistence_diag idmin = idmin + step + 1; } } - return sd->at(idmin); + return sd.at(idmin); } template<typename Persistence_diagram1, typename Persistence_diagram2> diff --git a/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree.h b/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree.h index 7b1676cf..9db9b8b6 100644 --- a/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree.h +++ b/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree.h @@ -28,7 +28,6 @@ #include <vector> #include <CGAL/algorithm.h> -#include <CGAL/Splitters.h> #include <CGAL/internal/Get_dimension_tag.h> #include <CGAL/Search_traits.h> diff --git a/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree_node.h b/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree_node.h index acefe926..d6d01439 100644 --- a/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree_node.h +++ b/src/Bottleneck_distance/include/gudhi/CGAL/Kd_tree_node.h @@ -21,7 +21,8 @@ #ifndef CGAL_KD_TREE_NODE_H #define CGAL_KD_TREE_NODE_H -#include <CGAL/Splitters.h> +#include "Splitters.h" + #include <CGAL/Compact_container.h> #include <boost/cstdint.hpp> diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h index a8d68a9d..c50c3a9e 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -23,8 +23,6 @@ #ifndef GRAPH_MATCHING_H_ #define GRAPH_MATCHING_H_ -#include <deque> - #include <gudhi/Neighbors_finder.h> namespace Gudhi { @@ -56,11 +54,11 @@ private: std::list<int> unmatched_in_u; /** \internal \brief Provides a Layered_neighbors_finder dividing the graph in layers. Basically a BFS. */ - std::shared_ptr<Layered_neighbors_finder> layering() const; + Layered_neighbors_finder 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<int> & path); + void update(std::vector<int> & path); }; inline Graph_matching::Graph_matching() @@ -83,7 +81,7 @@ inline bool Graph_matching::perfect() const { inline bool Graph_matching::multi_augment() { if (perfect()) return false; - Layered_neighbors_finder layered_nf = *layering(); + 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 @@ -103,7 +101,7 @@ inline void Graph_matching::set_r(double 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<int> path; + std::vector<int> path; path.emplace_back(u_start_index); do { if (static_cast<int>(path.size()) > max_depth) { @@ -129,19 +127,19 @@ inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u return true; } -inline std::shared_ptr<Layered_neighbors_finder> Graph_matching::layering() const { +inline Layered_neighbors_finder Graph_matching::layering() const { std::list<int> u_vertices(unmatched_in_u); std::list<int> 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_neighbors_finder> layered_nf(new Layered_neighbors_finder(r)); + Layered_neighbors_finder layered_nf(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<std::list<int>> u_succ(nf.pull_all_near(*it1)); - for (auto it2 = u_succ->begin(); it2 != u_succ->end(); ++it2) { - layered_nf->add(*it2, layer); + std::vector<int> 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); } } @@ -162,7 +160,7 @@ inline std::shared_ptr<Layered_neighbors_finder> Graph_matching::layering() cons return layered_nf; } -inline void Graph_matching::update(std::deque<int>& path) { +inline void Graph_matching::update(std::vector<int>& 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 diff --git a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h index 1bd5879c..e8560559 100644 --- a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h +++ b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h @@ -46,7 +46,7 @@ public: /** \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<int> > pull_all_near(int u_point_index); + std::vector<int> pull_all_near(int u_point_index); private: const double r; @@ -118,11 +118,11 @@ inline int Neighbors_finder::pull_near(int u_point_index) { return tmp; } -inline std::shared_ptr< std::list<int> > Neighbors_finder::pull_all_near(int u_point_index) { - std::shared_ptr< std::list<int> > all_pull(planar_neighbors_f.pull_all_near(u_point_index)); +inline std::vector<int> Neighbors_finder::pull_all_near(int u_point_index) { + std::vector<int> 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); + all_pull.emplace_back(last_pull); last_pull = pull_near(u_point_index); } return all_pull; diff --git a/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h index 1f6d6683..7af149e4 100644 --- a/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h +++ b/src/Bottleneck_distance/include/gudhi/Persistence_diagrams_graph.h @@ -25,11 +25,6 @@ #include <vector> #include <set> -#include <cmath> -#include <utility> -#include <algorithm> -#include <math.h> -#include <memory> #include <gudhi/Internal_point.h> namespace Gudhi { @@ -60,7 +55,7 @@ public: /** \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<double> > sorted_distances(); + static std::vector<double> sorted_distances(); /** \internal \brief Returns an upper bound of the diameter of the convex hull */ static double diameter(); @@ -126,15 +121,14 @@ inline int G::size() { return static_cast<int> (u.size() + v.size()); } -inline std::shared_ptr< std::vector<double> > G::sorted_distances() { +inline std::vector<double> G::sorted_distances() { // could be optimized std::set<double> sorted_distances; sorted_distances.emplace(0.); 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<double> > sd_up(new std::vector<double>(sorted_distances.cbegin(), sorted_distances.cend())); - return sd_up; + return std::vector<double>(sorted_distances.begin(),sorted_distances.end()); } inline Internal_point G::get_u_point(int u_point_index) { diff --git a/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h index 8bd21267..f574231e 100644 --- a/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h +++ b/src/Bottleneck_distance/include/gudhi/Planar_neighbors_finder.h @@ -23,9 +23,6 @@ #ifndef PLANAR_NEIGHBORS_FINDER_H_ #define PLANAR_NEIGHBORS_FINDER_H_ -#include <list> -#include <map> - // Inclusion order is important for CGAL patch #include "CGAL/Kd_tree_node.h" #include "CGAL/Kd_tree.h" @@ -62,7 +59,7 @@ public: /** \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<int> > pull_all_near(int u_point_index); + std::vector<int> pull_all_near(int u_point_index); private: double r; @@ -91,7 +88,7 @@ public: /** \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<int> > pull_all_near(int u_point_index); + virtual std::vector<int> pull_all_near(int u_point_index); private: double r; @@ -148,8 +145,8 @@ inline int Naive_pnf::pull_near(int u_point_index) { return null_point_index(); } -inline std::shared_ptr< std::list<int> > Naive_pnf::pull_all_near(int u_point_index) { - std::shared_ptr< std::list<int> > all_pull(new std::list<int>); +inline std::vector<int> Naive_pnf::pull_all_near(int u_point_index) { + std::vector<int> all_pull; Internal_point u_point = G::get_u_point(u_point_index); int i0 = static_cast<int>(u_point.x()/r); int j0 = static_cast<int>(u_point.y()/r); @@ -157,7 +154,7 @@ inline std::shared_ptr< std::list<int> > Naive_pnf::pull_all_near(int u_point_in 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); + all_pull.emplace_back(it->second); it = grid.erase(it); } else it++; @@ -206,11 +203,11 @@ inline int Cgal_pnf::pull_near(int u_point_index){ return tmp; } -inline std::shared_ptr< std::list<int> > Cgal_pnf::pull_all_near(int u_point_index) { - std::shared_ptr< std::list<int> > all_pull(new std::list<int>); +inline std::vector<int> Cgal_pnf::pull_all_near(int u_point_index) { + std::vector<int> all_pull; int last_pull = pull_near(u_point_index); while (last_pull != null_point_index()) { - all_pull->emplace_back(last_pull); + all_pull.emplace_back(last_pull); last_pull = pull_near(u_point_index); } return all_pull; |