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 
17 namespace Gudhi {
18 
19 namespace skeleton_blocker {
20 
21 template<class ComplexType> class Skeleton_blocker_sub_complex;
22 
29 template<typename ComplexType>
31 ComplexType> {
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 
283 namespace skbl = skeleton_blocker;
284 
285 } // namespace Gudhi
286 
287 #endif // SKELETON_BLOCKER_LINK_COMPLEX_H_
Simplicial subcomplex of a complex represented by a skeleton/blockers pair.
Definition: Skeleton_blocker_link_superior.h:20
Abstract simplex used in Skeleton blockers data-structure.
Definition: Skeleton_blocker_simplex.h:38
void add_blocker(const Root_simplex_handle &blocker_root)
Definition: Skeleton_blocker_sub_complex.h:112
Definition: SimplicialComplexForAlpha.h:14
Root_vertex_handle get_id(Vertex_handle local) const
Definition: Skeleton_blocker_complex.h:443
void add_edge_without_blockers(Root_vertex_handle v1_root, Root_vertex_handle v2_root)
Definition: Skeleton_blocker_sub_complex.h:100
boost::optional< Simplex > get_simplex_address(const Root_simplex_handle &s) const
Compute the local vertices of &#39;s&#39; in the current complex If one of them is not present in the complex...
Definition: Skeleton_blocker_complex.h:919
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:1284
void clear()
Definition: Skeleton_blocker_sub_complex.h:156
GUDHI  Version 3.1.1  - C++ library for Topological Data Analysis (TDA) and Higher Dimensional Geometry Understanding.  - Copyright : MIT Generated on Fri Feb 7 2020 16:35:36 for GUDHI by Doxygen 1.8.13