Skeleton_blocker_link_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_LINK_COMPLEX_H_
12#define SKELETON_BLOCKER_LINK_COMPLEX_H_
13
14#include <gudhi/Skeleton_blocker_complex.h>
15#include <gudhi/Debug_utils.h>
16
17namespace Gudhi {
18
19namespace skeleton_blocker {
20
21template<class ComplexType> class Skeleton_blocker_sub_complex;
22
29template<typename ComplexType>
31ComplexType> {
32 template<typename T> friend class Skeleton_blocker_link_superior;
33 typedef typename ComplexType::Edge_handle Edge_handle;
34
35 typedef typename ComplexType::boost_vertex_handle boost_vertex_handle;
36
37 private:
38 bool only_superior_vertices_;
39
40 public:
41 typedef typename ComplexType::Vertex_handle Vertex_handle;
42 typedef typename ComplexType::Root_vertex_handle Root_vertex_handle;
43
44 typedef typename ComplexType::Simplex Simplex;
45 typedef typename ComplexType::Root_simplex_handle Root_simplex_handle;
46
47 typedef typename ComplexType::Blocker_handle Blocker_handle;
48
49 typedef typename ComplexType::Root_simplex_handle::Simplex_vertex_const_iterator Root_simplex_handle_iterator;
50
51 explicit Skeleton_blocker_link_complex(bool only_superior_vertices = false)
52 : only_superior_vertices_(only_superior_vertices) { }
53
59 Skeleton_blocker_link_complex(const ComplexType & parent_complex,
60 const Simplex& alpha_parent_adress,
61 bool only_superior_vertices = false,
62 bool only_vertices = false)
63 : only_superior_vertices_(only_superior_vertices) {
64 if (!alpha_parent_adress.empty())
65 build_link(parent_complex, alpha_parent_adress, only_vertices);
66 }
67
72 Skeleton_blocker_link_complex(const ComplexType & parent_complex,
73 Vertex_handle a_parent_adress,
74 bool only_superior_vertices = false)
75 : only_superior_vertices_(only_superior_vertices) {
76 Simplex alpha_simplex(a_parent_adress);
77 build_link(parent_complex, alpha_simplex);
78 }
79
84 Skeleton_blocker_link_complex(const ComplexType & parent_complex,
85 Edge_handle edge, bool only_superior_vertices =
86 false)
87 : only_superior_vertices_(only_superior_vertices) {
88 Simplex alpha_simplex(parent_complex.first_vertex(edge),
89 parent_complex.second_vertex(edge));
90 build_link(parent_complex, alpha_simplex);
91 }
92
93 protected:
99 void compute_link_vertices(const ComplexType & parent_complex,
100 const Simplex& alpha_parent_adress,
101 bool only_superior_vertices,
102 bool is_alpha_blocker = false) {
103 if (alpha_parent_adress.dimension() == 0) {
104 // for a vertex we know exactly the number of vertices of the link (and the size of the corresponding vector)
105 // thus we call a specific function that will reserve a vector with appropriate size
106 this->compute_link_vertices(parent_complex,
107 alpha_parent_adress.first_vertex(),
108 only_superior_vertices_);
109 } else {
110 // we compute the intersection of neighbors of alpha and store it in link_vertices
111 Simplex link_vertices_parent;
112 parent_complex.add_neighbours(alpha_parent_adress, link_vertices_parent,
113 only_superior_vertices);
114 // For all vertex 'v' in this intersection, we go through all its adjacent blockers.
115 // If one blocker minus 'v' is included in alpha then the vertex is not in the link complex.
116 for (auto v_parent : link_vertices_parent) {
117 bool new_vertex = true;
118 for (auto beta : parent_complex.const_blocker_range(v_parent)) {
119 if (!is_alpha_blocker || *beta != alpha_parent_adress) {
120 new_vertex = !(alpha_parent_adress.contains_difference(*beta,
121 v_parent));
122 if (!new_vertex)
123 break;
124 }
125 }
126 if (new_vertex)
127 this->add_vertex(parent_complex.get_id(v_parent));
128 }
129 }
130 }
131
137 void compute_link_vertices(const ComplexType & parent_complex,
138 Vertex_handle alpha_parent_adress,
139 bool only_superior_vertices) {
140 // for a vertex we know exactly the number of vertices of the link (and the size of the corresponding vector
141 this->skeleton.m_vertices.reserve(
142 parent_complex.degree(alpha_parent_adress));
143
144 // For all vertex 'v' in this intersection, we go through all its adjacent blockers.
145 // If one blocker minus 'v' is included in alpha then the vertex is not in the link complex.
146 for (auto v_parent : parent_complex.vertex_range(alpha_parent_adress)) {
147 if (!only_superior_vertices
148 || v_parent.vertex > alpha_parent_adress.vertex)
149 this->add_vertex(parent_complex.get_id(v_parent));
150 }
151 }
152
153 void compute_link_edges(const ComplexType & parent_complex,
154 const Simplex& alpha_parent_adress,
155 bool is_alpha_blocker = false) {
156 if (this->num_vertices() <= 1)
157 return;
158
159 for (auto x_link = this->vertex_range().begin();
160 x_link != this->vertex_range().end(); ++x_link) {
161 for (auto y_link = x_link; ++y_link != this->vertex_range().end();) {
162 Vertex_handle x_parent = *parent_complex.get_address(
163 this->get_id(*x_link));
164 Vertex_handle y_parent = *parent_complex.get_address(
165 this->get_id(*y_link));
166 if (parent_complex.contains_edge(x_parent, y_parent)) {
167 // we check that there is no blocker subset of alpha passing trough x and y
168 bool new_edge = true;
169 for (auto blocker_parent : parent_complex.const_blocker_range(
170 x_parent)) {
171 if (!is_alpha_blocker || *blocker_parent != alpha_parent_adress) {
172 if (blocker_parent->contains(y_parent)) {
173 new_edge = !(alpha_parent_adress.contains_difference(
174 *blocker_parent, x_parent, y_parent));
175 if (!new_edge)
176 break;
177 }
178 }
179 }
180 if (new_edge)
181 this->add_edge_without_blockers(*x_link, *y_link);
182 }
183 }
184 }
185 }
186
192 boost::optional<Vertex_handle> give_equivalent_vertex(const ComplexType & other_complex,
193 Vertex_handle address) const {
194 Root_vertex_handle id((*this)[address].get_id());
195 return other_complex.get_address(id);
196 }
197
198 /*
199 * compute the blockers of the link if is_alpha_blocker is false.
200 * Otherwise, alpha is a blocker, and the link is computed in the complex where
201 * the blocker is anticollapsed.
202 */
203 void compute_link_blockers(const ComplexType & parent_complex,
204 const Simplex& alpha_parent,
205 bool is_alpha_blocker = false) {
206 for (auto x_link : this->vertex_range()) {
207 Vertex_handle x_parent = *this->give_equivalent_vertex(parent_complex,
208 x_link);
209
210 for (auto blocker_parent : parent_complex.const_blocker_range(x_parent)) {
211 if (!is_alpha_blocker || *blocker_parent != alpha_parent) {
212 Simplex sigma_parent(*blocker_parent);
213
214 sigma_parent.difference(alpha_parent);
215
216 if (sigma_parent.dimension() >= 2
217 && sigma_parent.first_vertex() == x_parent) {
218 Root_simplex_handle sigma_id(parent_complex.get_id(sigma_parent));
219 auto sigma_link = this->get_simplex_address(sigma_id);
220 // ie if the vertices of sigma are vertices of the link
221 if (sigma_link) {
222 bool is_new_blocker = true;
223 for (auto a : alpha_parent) {
224 for (auto eta_parent : parent_complex.const_blocker_range(a)) {
225 if (!is_alpha_blocker || *eta_parent != alpha_parent) {
226 Simplex eta_minus_alpha(*eta_parent);
227 eta_minus_alpha.difference(alpha_parent);
228 if (eta_minus_alpha != sigma_parent
229 && sigma_parent.contains_difference(*eta_parent,
230 alpha_parent)) {
231 is_new_blocker = false;
232 break;
233 }
234 }
235 }
236 if (!is_new_blocker)
237 break;
238 }
239 if (is_new_blocker)
240 this->add_blocker(new Simplex(*sigma_link));
241 }
242 }
243 }
244 }
245 }
246 }
247
248 public:
254 void build_link(const ComplexType & parent_complex,
255 const Simplex& alpha_parent_adress,
256 bool is_alpha_blocker = false,
257 bool only_vertices = false) {
258 assert(is_alpha_blocker || parent_complex.contains(alpha_parent_adress));
259 compute_link_vertices(parent_complex, alpha_parent_adress, only_superior_vertices_);
260 if (!only_vertices) {
261 compute_link_edges(parent_complex, alpha_parent_adress, is_alpha_blocker);
262 compute_link_blockers(parent_complex, alpha_parent_adress, is_alpha_blocker);
263 }
264 }
265
271 friend void build_link_of_blocker(const ComplexType & parent_complex,
272 Simplex& blocker,
274 assert(blocker.dimension() >= 2);
275 assert(parent_complex.contains_blocker(blocker));
276 result.clear();
277 result.build_link(parent_complex, blocker, true);
278 }
279};
280
281} // namespace skeleton_blocker
282
283namespace skbl = skeleton_blocker;
284
285} // namespace Gudhi
286
287#endif // SKELETON_BLOCKER_LINK_COMPLEX_H_
Vertex_handle add_vertex()
Adds a vertex to the simplicial complex and returns its Vertex_handle.
Definition: Skeleton_blocker_complex.h:372
Complex_vertex_range vertex_range() const
Returns a Complex_vertex_range over all vertices of the complex.
Definition: Skeleton_blocker_complex.h:1282
Root_vertex_handle get_id(Vertex_handle local) const
Definition: Skeleton_blocker_complex.h:443
boost::optional< Simplex > get_simplex_address(const Root_simplex_handle &s) const
Compute the local vertices of 's' in the current complex If one of them is not present in the complex...
Definition: Skeleton_blocker_complex.h:919
Abstract simplex used in Skeleton blockers data-structure.
Definition: Skeleton_blocker_simplex.h:38
Simplicial subcomplex of a complex represented by a skeleton/blockers pair.
Definition: Skeleton_blocker_sub_complex.h:46
void clear()
Definition: Skeleton_blocker_sub_complex.h:156
void add_blocker(const Root_simplex_handle &blocker_root)
Definition: Skeleton_blocker_sub_complex.h:112
void add_edge_without_blockers(Root_vertex_handle v1_root, Root_vertex_handle v2_root)
Definition: Skeleton_blocker_sub_complex.h:100
Root_vertex_handle and Vertex_handle are similar to global and local vertex descriptor used in boost ...
Definition: SkeletonBlockerDS.h:47
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15