Skeleton_blocker_simplifiable_complex.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(s): David Salinas
4 *
5 * Copyright (C) 2014 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
11#ifndef SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_
12#define SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_
13
14#include <gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h>
15
16#include <list>
17#include <vector>
18#include <set>
19
20namespace Gudhi {
21
22namespace skeleton_blocker {
23
32template<typename SkeletonBlockerDS>
34 assert(this->contains_blocker(*sigma));
36 build_link_of_blocker(*this, *sigma, link_blocker_sigma);
37 return link_blocker_sigma.is_contractible() == CONTRACTIBLE;
38}
39
43template<typename SkeletonBlockerDS>
45 std::list<Vertex_handle> vertex_to_check;
46 for (auto v : this->vertex_range())
47 vertex_to_check.push_front(v);
48
49 while (!vertex_to_check.empty()) {
50 Vertex_handle v = vertex_to_check.front();
51 vertex_to_check.pop_front();
52
53 bool blocker_popable_found = true;
54 while (blocker_popable_found) {
55 blocker_popable_found = false;
56 for (auto block : this->blocker_range(v)) {
57 if (this->is_popable_blocker(block)) {
58 for (Vertex_handle nv : *block)
59 if (nv != v) vertex_to_check.push_back(nv);
60 this->delete_blocker(block);
61 blocker_popable_found = true;
62 break;
63 }
64 }
65 }
66 }
67}
68
72template<typename SkeletonBlockerDS>
74 bool blocker_popable_found = true;
75 while (blocker_popable_found) {
76 blocker_popable_found = false;
77 for (auto block : this->blocker_range(v)) {
78 if (is_popable_blocker(block)) {
79 this->delete_blocker(block);
80 blocker_popable_found = true;
81 }
82 }
83 }
84}
85
91template<typename SkeletonBlockerDS>
93 std::list<Vertex_handle> vertex_to_check;
94 vertex_to_check.push_front(v);
95
96 while (!vertex_to_check.empty()) {
97 Vertex_handle v = vertex_to_check.front();
98 vertex_to_check.pop_front();
99
100 bool blocker_popable_found = true;
101 while (blocker_popable_found) {
102 blocker_popable_found = false;
103 for (auto block : this->blocker_range(v)) {
104 if (this->is_popable_blocker(block)) {
105 for (Vertex_handle nv : *block)
106 if (nv != v) vertex_to_check.push_back(nv);
107 this->delete_blocker(block);
108 blocker_popable_found = true;
109 break;
110 }
111 }
112 }
113 }
114}
115
119template<typename SkeletonBlockerDS>
121 // we remove the blockers that are not consistent anymore
122 update_blockers_after_remove_star_of_vertex_or_edge(Simplex(v));
123 while (this->degree(v) > 0) {
124 Vertex_handle w(* (adjacent_vertices(v.vertex, this->skeleton).first));
125 this->remove_edge(v, w);
126 }
127 this->remove_vertex(v);
128}
129
135template<typename SkeletonBlockerDS>
137 std::list <Blocker_handle> blockers_to_update;
138 if (simplex_to_be_removed.empty()) return;
139
140 auto v0 = simplex_to_be_removed.first_vertex();
141 for (auto blocker : this->blocker_range(v0)) {
142 if (blocker->contains(simplex_to_be_removed))
143 blockers_to_update.push_back(blocker);
144 }
145
146 for (auto blocker_to_update : blockers_to_update) {
147 Simplex sub_blocker_to_be_added;
148 bool sub_blocker_need_to_be_added =
149 (blocker_to_update->dimension() - simplex_to_be_removed.dimension()) >= 2;
150 if (sub_blocker_need_to_be_added) {
151 sub_blocker_to_be_added = *blocker_to_update;
152 sub_blocker_to_be_added.difference(simplex_to_be_removed);
153 }
154 this->delete_blocker(blocker_to_update);
155 if (sub_blocker_need_to_be_added)
156 this->add_blocker(sub_blocker_to_be_added);
157 }
158}
159
163template<typename SkeletonBlockerDS>
165 update_blockers_after_remove_star_of_vertex_or_edge(Simplex(a, b));
166 // we remove the edge
167 this->remove_edge(a, b);
168}
169
173template<typename SkeletonBlockerDS>
175 return remove_star(this->first_vertex(e), this->second_vertex(e));
176}
177
181template<typename SkeletonBlockerDS>
183 assert(this->contains(sigma));
184 if (sigma.dimension() == 0) {
185 remove_star(sigma.first_vertex());
186 } else if (sigma.dimension() == 1) {
187 remove_star(sigma.first_vertex(), sigma.last_vertex());
188 } else {
189 remove_blocker_containing_simplex(sigma);
190 this->add_blocker(sigma);
191 }
192}
193
194template<typename SkeletonBlockerDS>
196 // to add a simplex s, all blockers included in s are first removed
197 // and then all simplex in the coboundary of s are added as blockers
198 assert(!this->contains(sigma));
199 assert(sigma.dimension() > 1);
200 if (!contains_vertices(sigma)) {
201 std::cerr << "add_simplex: Some vertices were not present in the complex, adding them" << std::endl;
202 size_t num_vertices_to_add = sigma.last_vertex() - this->num_vertices() + 1;
203 for (size_t i = 0; i < num_vertices_to_add; ++i)
204 this->add_vertex();
205 }
206 assert(contains_vertices(sigma));
207 if (!contains_edges(sigma))
208 add_edge(sigma);
209 remove_blocker_include_in_simplex(sigma);
210 add_blockers_after_simplex_insertion(sigma);
211}
212
213template<typename SkeletonBlockerDS>
215 if (sigma.dimension() < 1) return;
216
217 for (auto s : coboundary_range(sigma)) {
218 this->add_blocker(s);
219 }
220}
221
225template<typename SkeletonBlockerDS>
226void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_containing_simplex(const Simplex& sigma) {
227 std::vector <Blocker_handle> blockers_to_remove;
228 for (auto blocker : this->blocker_range(sigma.first_vertex())) {
229 if (blocker->contains(sigma))
230 blockers_to_remove.push_back(blocker);
231 }
232 for (auto blocker_to_update : blockers_to_remove)
233 this->delete_blocker(blocker_to_update);
234}
235
239template<typename SkeletonBlockerDS>
240void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_include_in_simplex(const Simplex& sigma) {
241 // TODO(DS): write efficiently by using only superior blockers
242 // eg for all s, check blockers whose vertices are all greater than s
243 std::set <Blocker_handle> blockers_to_remove;
244 for (auto s : sigma) {
245 for (auto blocker : this->blocker_range(s)) {
246 if (sigma.contains(*blocker))
247 blockers_to_remove.insert(blocker);
248 }
249 }
250 for (auto blocker_to_update : blockers_to_remove) {
251 auto s = *blocker_to_update;
252 this->delete_blocker(blocker_to_update);
253 // now if there is a vertex v in the link of s
254 // and v is not included in sigma then v.s is a blocker
255 // (all faces of v.s are there since v belongs to the link of s)
256 for (const auto& b : coboundary_range(s))
257 if (!sigma.contains(b))
258 this->add_blocker(b);
259 }
260}
261
267template<typename SkeletonBlockerDS>
268void Skeleton_blocker_complex<SkeletonBlockerDS>::tip_blockers(Vertex_handle a, Vertex_handle b,
269 std::vector<Simplex> & buffer) const {
270 for (auto const & blocker : this->const_blocker_range(a)) {
271 Simplex beta = (*blocker);
272 beta.remove_vertex(a);
273 buffer.push_back(beta);
274 }
275
276 Simplex n;
277 this->add_neighbours(b, n);
278 this->remove_neighbours(a, n);
279 n.remove_vertex(a);
280
281
282 for (Vertex_handle y : n) {
283 Simplex beta;
284 beta.add_vertex(y);
285 buffer.push_back(beta);
286 }
287}
288
297template<typename SkeletonBlockerDS>
298void
299Skeleton_blocker_complex<SkeletonBlockerDS>::swap_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) {
300 this->add_edge_without_blockers(a, x);
301 if (this->visitor) this->visitor->on_swaped_edge(a, b, x);
302 this->remove_edge(b, x);
303}
304
305template<typename SkeletonBlockerDS>
306void
307Skeleton_blocker_complex<SkeletonBlockerDS>::delete_blockers_around_vertex(Vertex_handle v) {
308 std::list <Blocker_handle> blockers_to_delete;
309 for (auto blocker : this->blocker_range(v)) {
310 blockers_to_delete.push_back(blocker);
311 }
312 while (!blockers_to_delete.empty()) {
313 this->remove_blocker(blockers_to_delete.back());
314 blockers_to_delete.pop_back();
315 }
316}
317
321template<typename SkeletonBlockerDS>
322void
323Skeleton_blocker_complex<SkeletonBlockerDS>::delete_blockers_around_edge(Vertex_handle a, Vertex_handle b) {
324 std::list<Blocker_handle> blocker_to_delete;
325 for (auto blocker : this->blocker_range(a))
326 if (blocker->contains(b)) blocker_to_delete.push_back(blocker);
327 while (!blocker_to_delete.empty()) {
328 this->delete_blocker(blocker_to_delete.back());
329 blocker_to_delete.pop_back();
330 }
331}
332
338template<typename SkeletonBlockerDS>
339void
341 assert(this->contains_vertex(a));
342 assert(this->contains_vertex(b));
343
344 if (this->contains_edge(a, b))
345 this->add_edge_without_blockers(a, b);
346
347 // if some blockers passes through 'ab', we need to remove them.
348 if (!link_condition(a, b))
349 delete_blockers_around_edge(a, b);
350
351 std::set<Simplex> blockers_to_add;
352
353 get_blockers_to_be_added_after_contraction(a, b, blockers_to_add);
354
355 delete_blockers_around_vertices(a, b);
356
357 update_edges_after_contraction(a, b);
358
359 this->remove_vertex(b);
360
361 notify_changed_edges(a);
362
363 for (auto block : blockers_to_add)
364 this->add_blocker(block);
365
366 assert(this->contains_vertex(a));
367 assert(!this->contains_vertex(b));
368}
369
370template<typename SkeletonBlockerDS>
373 std::set<Simplex>& blockers_to_add) {
374 blockers_to_add.clear();
375
377
378 LinkComplexType link_a(*this, a);
379 LinkComplexType link_b(*this, b);
380
381 std::vector<Simplex> vector_alpha, vector_beta;
382
383 tip_blockers(a, b, vector_alpha);
384 tip_blockers(b, a, vector_beta);
385
386 for (auto alpha = vector_alpha.begin(); alpha != vector_alpha.end(); ++alpha) {
387 for (auto beta = vector_beta.begin(); beta != vector_beta.end(); ++beta) {
388 Simplex sigma = *alpha;
389 sigma.union_vertices(*beta);
390 Root_simplex_handle sigma_id = this->get_id(sigma);
391 if (this->contains(sigma) &&
392 proper_faces_in_union<Skeleton_blocker_complex < SkeletonBlockerDS >> (sigma_id, link_a, link_b)) {
393 // Blocker_handle blocker = new Simplex(sigma);
394 sigma.add_vertex(a);
395 blockers_to_add.insert(sigma);
396 }
397 }
398 }
399}
400
404template<typename SkeletonBlockerDS>
405void
406Skeleton_blocker_complex<SkeletonBlockerDS>::delete_blockers_around_vertices(Vertex_handle a, Vertex_handle b) {
407 std::vector<Blocker_handle> blocker_to_delete;
408 for (auto bl : this->blocker_range(a))
409 blocker_to_delete.push_back(bl);
410 for (auto bl : this->blocker_range(b))
411 blocker_to_delete.push_back(bl);
412 while (!blocker_to_delete.empty()) {
413 this->delete_blocker(blocker_to_delete.back());
414 blocker_to_delete.pop_back();
415 }
416}
417
418template<typename SkeletonBlockerDS>
419void
420Skeleton_blocker_complex<SkeletonBlockerDS>::update_edges_after_contraction(Vertex_handle a, Vertex_handle b) {
421 // We update the set of edges
422 this->remove_edge(a, b);
423
424 // For all edges {b,x} incident to b,
425 // we remove {b,x} and add {a,x} if not already there.
426 while (this->degree(b) > 0) {
427 Vertex_handle x(*(adjacent_vertices(b.vertex, this->skeleton).first));
428 if (!this->contains_edge(a, x))
429 // we 'replace' the edge 'bx' by the edge 'ax'
430 this->swap_edge(a, b, x);
431 else
432 this->remove_edge(b, x);
433 }
434}
435
436template<typename SkeletonBlockerDS>
437void
438Skeleton_blocker_complex<SkeletonBlockerDS>::notify_changed_edges(Vertex_handle a) {
439 // We notify the visitor that all edges incident to 'a' had changed
440 boost_adjacency_iterator v, v_end;
441
442 for (tie(v, v_end) = adjacent_vertices(a.vertex, this->skeleton); v != v_end; ++v)
443 if (this->visitor) this->visitor->on_changed_edge(a, Vertex_handle(*v));
444}
445
446
447} // namespace skeleton_blocker
448
449namespace skbl = skeleton_blocker;
450
451} // namespace Gudhi
452
453#endif // SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_
Abstract Simplicial Complex represented with a skeleton/blockers pair.
Definition: Skeleton_blocker_complex.h:51
virtual contractible_status is_contractible() const
Test if the complex is reducible using a strategy defined in the class (by default it tests if the co...
Definition: Skeleton_blocker_complex.h:1162
Vertex_handle first_vertex(Edge_handle edge_handle) const
returns the first vertex of an edge
Definition: Skeleton_blocker_complex.h:512
void contract_edge(Edge_handle edge)
Definition: Skeleton_blocker_complex.h:1244
void add_simplex(const Simplex &sigma)
add a simplex and all its faces.
Definition: Skeleton_blocker_simplifiable_complex.h:195
void remove_all_popable_blockers(Vertex_handle v)
Removes all the popable blockers of the complex passing through v and delete them....
Definition: Skeleton_blocker_simplifiable_complex.h:92
void remove_popable_blockers()
Definition: Skeleton_blocker_simplifiable_complex.h:44
virtual void clear()
Definition: Skeleton_blocker_complex.h:311
void remove_star(Vertex_handle v)
Definition: Skeleton_blocker_simplifiable_complex.h:120
bool is_popable_blocker(Blocker_handle sigma) const
Definition: Skeleton_blocker_simplifiable_complex.h:33
boost::graph_traits< Graph >::edge_descriptor Edge_handle
Handle to an edge of the complex.
Definition: Skeleton_blocker_complex.h:114
Abstract simplex used in Skeleton blockers data-structure.
Definition: Skeleton_blocker_simplex.h:38
T first_vertex() const
Definition: Skeleton_blocker_simplex.h:210
T last_vertex() const
Definition: Skeleton_blocker_simplex.h:220
int dimension() const
Definition: Skeleton_blocker_simplex.h:197
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15