Graph_matching.h
1 /* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2  * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3  * Author: Francois Godi
4  *
5  * Copyright (C) 2015 Inria
6  *
7  * Modification(s):
8  * - YYYY/MM Author: Description of the modification
9  */
10 
11 #ifndef GRAPH_MATCHING_H_
12 #define GRAPH_MATCHING_H_
13 
14 #include <gudhi/Neighbors_finder.h>
15 
16 #include <vector>
17 #include <unordered_set>
18 #include <algorithm>
19 
20 namespace Gudhi {
21 
22 namespace persistence_diagram {
23 
28 class Graph_matching {
29  public:
31  explicit Graph_matching(Persistence_graph &g);
33  bool perfect() const;
35  bool multi_augment();
37  void set_r(double r);
38 
39  private:
40  Persistence_graph* gp;
41  double r;
43  std::vector<int> v_to_u;
45  std::unordered_set<int> unmatched_in_u;
46 
48  Layered_neighbors_finder layering() const;
50  bool augment(Layered_neighbors_finder & layered_nf, int u_start_index, int max_depth);
52  void update(std::vector<int> & path);
53 };
54 
55 inline Graph_matching::Graph_matching(Persistence_graph& g)
56  : gp(&g), r(0.), v_to_u(g.size(), null_point_index()), unmatched_in_u(g.size()) {
57  for (int u_point_index = 0; u_point_index < g.size(); ++u_point_index)
58  unmatched_in_u.insert(u_point_index);
59 }
60 
61 inline bool Graph_matching::perfect() const {
62  return unmatched_in_u.empty();
63 }
64 
65 inline bool Graph_matching::multi_augment() {
66  if (perfect())
67  return false;
68  Layered_neighbors_finder layered_nf(layering());
69  int max_depth = layered_nf.vlayers_number()*2 - 1;
70  double rn = sqrt(gp->size());
71  // verification of a necessary criterion in order to shortcut if possible
72  if (max_depth < 0 || (unmatched_in_u.size() > rn && max_depth >= rn))
73  return false;
74  bool successful = false;
75  std::vector<int> tries(unmatched_in_u.cbegin(), unmatched_in_u.cend());
76  for (auto it = tries.cbegin(); it != tries.cend(); it++)
77  // 'augment' has side-effects which have to be always executed, don't change order
78  successful = augment(layered_nf, *it, max_depth) || successful;
79  return successful;
80 }
81 
82 inline void Graph_matching::set_r(double r) {
83  this->r = r;
84 }
85 
86 inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u_start_index, int max_depth) {
87  // V vertices have at most one successor, thus when we backtrack from U we can directly pop_back 2 vertices.
88  std::vector<int> path;
89  path.emplace_back(u_start_index);
90  do {
91  if (static_cast<int> (path.size()) > max_depth) {
92  path.pop_back();
93  path.pop_back();
94  }
95  if (path.empty())
96  return false;
97  path.emplace_back(layered_nf.pull_near(path.back(), static_cast<int> (path.size()) / 2));
98  while (path.back() == null_point_index()) {
99  path.pop_back();
100  path.pop_back();
101  if (path.empty())
102  return false;
103  path.pop_back();
104  path.emplace_back(layered_nf.pull_near(path.back(), path.size() / 2));
105  }
106  path.emplace_back(v_to_u.at(path.back()));
107  } while (path.back() != null_point_index());
108  // if v_to_u.at(path.back()) has no successor, path.back() is an exposed vertex
109  path.pop_back();
110  update(path);
111  return true;
112 }
113 
114 inline Layered_neighbors_finder Graph_matching::layering() const {
115  std::vector<int> u_vertices(unmatched_in_u.cbegin(), unmatched_in_u.cend());
116  std::vector<int> v_vertices;
117  Neighbors_finder nf(*gp, r);
118  for (int v_point_index = 0; v_point_index < gp->size(); ++v_point_index)
119  nf.add(v_point_index);
120  Layered_neighbors_finder layered_nf(*gp, r);
121  for (int layer = 0; !u_vertices.empty(); layer++) {
122  // one layer is one step in the BFS
123  for (auto it1 = u_vertices.cbegin(); it1 != u_vertices.cend(); ++it1) {
124  std::vector<int> u_succ(nf.pull_all_near(*it1));
125  for (auto it2 = u_succ.begin(); it2 != u_succ.end(); ++it2) {
126  layered_nf.add(*it2, layer);
127  v_vertices.emplace_back(*it2);
128  }
129  }
130  // When the above for finishes, we have progress of one half-step (from U to V) in the BFS
131  u_vertices.clear();
132  bool end = false;
133  for (auto it = v_vertices.cbegin(); it != v_vertices.cend(); it++)
134  if (v_to_u.at(*it) == null_point_index())
135  // we stop when a nearest exposed V vertex (from U exposed vertices) has been found
136  end = true;
137  else
138  u_vertices.emplace_back(v_to_u.at(*it));
139  // When the above for finishes, we have progress of one half-step (from V to U) in the BFS
140  if (end)
141  return layered_nf;
142  v_vertices.clear();
143  }
144  return layered_nf;
145 }
146 
147 inline void Graph_matching::update(std::vector<int>& path) {
148  // Must return 1.
149  unmatched_in_u.erase(path.front());
150  for (auto it = path.cbegin(); it != path.cend(); ++it) {
151  // Be careful, the iterator is incremented twice each time
152  int tmp = *it;
153  v_to_u[*(++it)] = tmp;
154  }
155 }
156 
157 
158 } // namespace persistence_diagram
159 
160 } // namespace Gudhi
161 
162 #endif // GRAPH_MATCHING_H_
GUDHIdev  Version 3.5.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Wed Apr 6 2022 19:26:28 for GUDHIdev by Doxygen 1.9.1