From ba53634524e92a89e7785853088b6ad6d0eccdc5 Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 5 Apr 2017 23:03:38 +0000 Subject: Use an unordered_set for unmatched_in_u instead of an open-coded flat_set. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/bottleneck-glisse@2312 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 37137a43f781e4646c4149d9528a6a95e1c642be --- .../include/gudhi/Graph_matching.h | 30 ++++++---------------- 1 file changed, 8 insertions(+), 22 deletions(-) (limited to 'src/Bottleneck_distance/include') diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h index c4775b07..f51e22e9 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -26,6 +26,7 @@ #include #include +#include #include namespace Gudhi { @@ -53,7 +54,7 @@ class Graph_matching { /** \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; /** \internal \brief All the unmatched points in U. */ - std::vector unmatched_in_u; + std::unordered_set unmatched_in_u; /** \internal \brief Provides a Layered_neighbors_finder dividing the graph in layers. Basically a BFS. */ Layered_neighbors_finder layering() const; @@ -64,10 +65,9 @@ class Graph_matching { }; inline Graph_matching::Graph_matching(Persistence_graph& g) - : gp(&g), r(0.), v_to_u(g.size(), null_point_index()), unmatched_in_u() { - unmatched_in_u.reserve(g.size()); + : gp(&g), r(0.), v_to_u(g.size(), null_point_index()), unmatched_in_u(g.size()) { for (int u_point_index = 0; u_point_index < g.size(); ++u_point_index) - unmatched_in_u.emplace_back(u_point_index); + unmatched_in_u.insert(u_point_index); } inline bool Graph_matching::perfect() const { @@ -84,7 +84,7 @@ inline bool Graph_matching::multi_augment() { if (max_depth < 0 || (unmatched_in_u.size() > rn && max_depth >= rn)) return false; bool successful = false; - std::vector tries(unmatched_in_u); + std::vector tries(unmatched_in_u.cbegin(), unmatched_in_u.cend()); for (auto it = tries.cbegin(); it != tries.cend(); it++) // 'augment' has side-effects which have to be always executed, don't change order successful = augment(layered_nf, *it, max_depth) || successful; @@ -124,7 +124,7 @@ inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u } inline Layered_neighbors_finder Graph_matching::layering() const { - std::vector u_vertices(unmatched_in_u); + std::vector u_vertices(unmatched_in_u.cbegin(), unmatched_in_u.cend()); std::vector v_vertices; Neighbors_finder nf(*gp, r); for (int v_point_index = 0; v_point_index < gp->size(); ++v_point_index) @@ -157,22 +157,8 @@ inline Layered_neighbors_finder Graph_matching::layering() const { } inline void Graph_matching::update(std::vector& path) { - // Making unmatched_in_u an unordered_set is simpler and almost as fast. -#if 0 - // Avoid an expensive erase in the middle of the vector, but break the - // ordering, so the search needs to be linear. - auto p = std::find(unmatched_in_u.begin(), unmatched_in_u.end(), path.front()); - assert(p != unmatched_in_u.end()); - std::swap(*p, unmatched_in_u.back()); - unmatched_in_u.pop_back(); -#else - // Take advantage of the vector being sorted, but pay an expensive erase to - // maintain the order. This is essentially the same as making unmatched_in_u - // a boost flat_set. - auto p = std::lower_bound(unmatched_in_u.begin(), unmatched_in_u.end(), path.front()); - assert(p != unmatched_in_u.end() && *p == path.front()); - unmatched_in_u.erase(p); -#endif + // Must return 1. + unmatched_in_u.erase(path.front()); for (auto it = path.cbegin(); it != path.cend(); ++it) { // Be careful, the iterator is incremented twice each time int tmp = *it; -- cgit v1.2.3