Graph_matching.h
1 /* This file is part of the Gudhi Library. The Gudhi library
2  * (Geometric Understanding in Higher Dimensions) is a generic C++
3  * library for computational topology.
4  *
5  * Author: Francois Godi
6  *
7  * Copyright (C) 2015 Inria
8  *
9  * This program is free software: you can redistribute it and/or modify
10  * it under the terms of the GNU General Public License as published by
11  * the Free Software Foundation, either version 3 of the License, or
12  * (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program. If not, see <http://www.gnu.org/licenses/>.
21  */
22 
23 #ifndef GRAPH_MATCHING_H_
24 #define GRAPH_MATCHING_H_
25 
26 #include <gudhi/Neighbors_finder.h>
27 
28 #include <vector>
29 #include <unordered_set>
30 #include <algorithm>
31 
32 namespace Gudhi {
33 
34 namespace persistence_diagram {
35 
40 class Graph_matching {
41  public:
43  explicit Graph_matching(Persistence_graph &g);
45  bool perfect() const;
47  bool multi_augment();
49  void set_r(double r);
50 
51  private:
52  Persistence_graph* gp;
53  double r;
55  std::vector<int> v_to_u;
57  std::unordered_set<int> unmatched_in_u;
58 
60  Layered_neighbors_finder layering() const;
62  bool augment(Layered_neighbors_finder & layered_nf, int u_start_index, int max_depth);
64  void update(std::vector<int> & path);
65 };
66 
67 inline Graph_matching::Graph_matching(Persistence_graph& g)
68  : gp(&g), r(0.), v_to_u(g.size(), null_point_index()), unmatched_in_u(g.size()) {
69  for (int u_point_index = 0; u_point_index < g.size(); ++u_point_index)
70  unmatched_in_u.insert(u_point_index);
71 }
72 
73 inline bool Graph_matching::perfect() const {
74  return unmatched_in_u.empty();
75 }
76 
77 inline bool Graph_matching::multi_augment() {
78  if (perfect())
79  return false;
80  Layered_neighbors_finder layered_nf(layering());
81  int max_depth = layered_nf.vlayers_number()*2 - 1;
82  double rn = sqrt(gp->size());
83  // verification of a necessary criterion in order to shortcut if possible
84  if (max_depth < 0 || (unmatched_in_u.size() > rn && max_depth >= rn))
85  return false;
86  bool successful = false;
87  std::vector<int> tries(unmatched_in_u.cbegin(), unmatched_in_u.cend());
88  for (auto it = tries.cbegin(); it != tries.cend(); it++)
89  // 'augment' has side-effects which have to be always executed, don't change order
90  successful = augment(layered_nf, *it, max_depth) || successful;
91  return successful;
92 }
93 
94 inline void Graph_matching::set_r(double r) {
95  this->r = r;
96 }
97 
98 inline bool Graph_matching::augment(Layered_neighbors_finder & layered_nf, int u_start_index, int max_depth) {
99  // V vertices have at most one successor, thus when we backtrack from U we can directly pop_back 2 vertices.
100  std::vector<int> path;
101  path.emplace_back(u_start_index);
102  do {
103  if (static_cast<int> (path.size()) > max_depth) {
104  path.pop_back();
105  path.pop_back();
106  }
107  if (path.empty())
108  return false;
109  path.emplace_back(layered_nf.pull_near(path.back(), static_cast<int> (path.size()) / 2));
110  while (path.back() == null_point_index()) {
111  path.pop_back();
112  path.pop_back();
113  if (path.empty())
114  return false;
115  path.pop_back();
116  path.emplace_back(layered_nf.pull_near(path.back(), path.size() / 2));
117  }
118  path.emplace_back(v_to_u.at(path.back()));
119  } while (path.back() != null_point_index());
120  // if v_to_u.at(path.back()) has no successor, path.back() is an exposed vertex
121  path.pop_back();
122  update(path);
123  return true;
124 }
125 
126 inline Layered_neighbors_finder Graph_matching::layering() const {
127  std::vector<int> u_vertices(unmatched_in_u.cbegin(), unmatched_in_u.cend());
128  std::vector<int> v_vertices;
129  Neighbors_finder nf(*gp, r);
130  for (int v_point_index = 0; v_point_index < gp->size(); ++v_point_index)
131  nf.add(v_point_index);
132  Layered_neighbors_finder layered_nf(*gp, r);
133  for (int layer = 0; !u_vertices.empty(); layer++) {
134  // one layer is one step in the BFS
135  for (auto it1 = u_vertices.cbegin(); it1 != u_vertices.cend(); ++it1) {
136  std::vector<int> u_succ(nf.pull_all_near(*it1));
137  for (auto it2 = u_succ.begin(); it2 != u_succ.end(); ++it2) {
138  layered_nf.add(*it2, layer);
139  v_vertices.emplace_back(*it2);
140  }
141  }
142  // When the above for finishes, we have progress of one half-step (from U to V) in the BFS
143  u_vertices.clear();
144  bool end = false;
145  for (auto it = v_vertices.cbegin(); it != v_vertices.cend(); it++)
146  if (v_to_u.at(*it) == null_point_index())
147  // we stop when a nearest exposed V vertex (from U exposed vertices) has been found
148  end = true;
149  else
150  u_vertices.emplace_back(v_to_u.at(*it));
151  // When the above for finishes, we have progress of one half-step (from V to U) in the BFS
152  if (end)
153  return layered_nf;
154  v_vertices.clear();
155  }
156  return layered_nf;
157 }
158 
159 inline void Graph_matching::update(std::vector<int>& path) {
160  // Must return 1.
161  unmatched_in_u.erase(path.front());
162  for (auto it = path.cbegin(); it != path.cend(); ++it) {
163  // Be careful, the iterator is incremented twice each time
164  int tmp = *it;
165  v_to_u[*(++it)] = tmp;
166  }
167 }
168 
169 
170 } // namespace persistence_diagram
171 
172 } // namespace Gudhi
173 
174 #endif // GRAPH_MATCHING_H_
Definition: SimplicialComplexForAlpha.h:26
GUDHI  Version 2.3.0  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : GPL v3 Generated on Fri Oct 18 2019 18:40:54 for GUDHI by Doxygen 1.8.13