diff options
Diffstat (limited to 'src/Bottleneck_distance/include/gudhi/Graph_matching.h')
-rw-r--r-- | src/Bottleneck_distance/include/gudhi/Graph_matching.h | 38 |
1 files changed, 15 insertions, 23 deletions
diff --git a/src/Bottleneck_distance/include/gudhi/Graph_matching.h b/src/Bottleneck_distance/include/gudhi/Graph_matching.h index e1708c5b..f51e22e9 100644 --- a/src/Bottleneck_distance/include/gudhi/Graph_matching.h +++ b/src/Bottleneck_distance/include/gudhi/Graph_matching.h @@ -26,7 +26,8 @@ #include <gudhi/Neighbors_finder.h> #include <vector> -#include <list> +#include <unordered_set> +#include <algorithm> namespace Gudhi { @@ -40,8 +41,6 @@ class Graph_matching { public: /** \internal \brief Constructor constructing an empty matching. */ explicit Graph_matching(Persistence_graph &g); - /** \internal \brief Copy operator. */ - Graph_matching& operator=(const Graph_matching& m); /** \internal \brief Is the matching perfect ? */ bool perfect() const; /** \internal \brief Augments the matching with a maximal set of edge-disjoint shortest augmenting paths. */ @@ -50,12 +49,12 @@ class Graph_matching { void set_r(double r); private: - Persistence_graph& g; + Persistence_graph* gp; double r; /** \internal \brief Given a point from V, provides its matched point in U, null_point_index() if there isn't. */ std::vector<int> v_to_u; /** \internal \brief All the unmatched points in U. */ - std::list<int> unmatched_in_u; + std::unordered_set<int> unmatched_in_u; /** \internal \brief Provides a Layered_neighbors_finder dividing the graph in layers. Basically a BFS. */ Layered_neighbors_finder layering() const; @@ -66,17 +65,9 @@ class Graph_matching { }; inline Graph_matching::Graph_matching(Persistence_graph& g) - : g(g), r(0.), v_to_u(g.size(), null_point_index()), unmatched_in_u() { + : 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); -} - -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; - return *this; + unmatched_in_u.insert(u_point_index); } inline bool Graph_matching::perfect() const { @@ -88,12 +79,12 @@ 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(gp->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; bool successful = false; - std::list<int> tries(unmatched_in_u); + std::vector<int> 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; @@ -133,12 +124,12 @@ inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u } inline Layered_neighbors_finder Graph_matching::layering() const { - std::list<int> u_vertices(unmatched_in_u); - std::list<int> v_vertices; - Neighbors_finder nf(g, r); - for (int v_point_index = 0; v_point_index < g.size(); ++v_point_index) + std::vector<int> u_vertices(unmatched_in_u.cbegin(), unmatched_in_u.cend()); + std::vector<int> v_vertices; + Neighbors_finder nf(*gp, r); + for (int v_point_index = 0; v_point_index < gp->size(); ++v_point_index) nf.add(v_point_index); - Layered_neighbors_finder layered_nf(g, r); + Layered_neighbors_finder layered_nf(*gp, 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) { @@ -166,7 +157,8 @@ inline Layered_neighbors_finder Graph_matching::layering() const { } inline void Graph_matching::update(std::vector<int>& path) { - unmatched_in_u.remove(path.front()); + // 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; |