Skeleton_blocker_sub_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_SKELETON_BLOCKER_SUB_COMPLEX_H_
12 #define SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_COMPLEX_H_
13 
14 #include <gudhi/Skeleton_blocker_complex.h>
15 #include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h>
16 #include <gudhi/Debug_utils.h>
17 
18 #include <map>
19 #include <vector>
20 
21 namespace Gudhi {
22 
23 namespace skeleton_blocker {
24 
45 template<typename ComplexType>
46 class Skeleton_blocker_sub_complex : public ComplexType {
47  protected:
48  template<class T> friend class Skeleton_blocker_link_complex;
49 
50  typedef typename ComplexType::Graph Graph;
51  typedef typename ComplexType::Edge_handle Edge_handle;
52 
53  typedef typename ComplexType::boost_vertex_handle boost_vertex_handle;
54 
55  public:
56  using ComplexType::add_vertex;
57  using ComplexType::add_edge_without_blockers;
58  using ComplexType::add_blocker;
59 
60  typedef typename ComplexType::Vertex_handle Vertex_handle;
61  typedef typename ComplexType::Root_vertex_handle Root_vertex_handle;
62  typedef typename ComplexType::Simplex Simplex;
63  typedef typename ComplexType::Root_simplex_handle Root_simplex_handle;
64 
65  protected:
70  typedef std::map<Root_vertex_handle, Vertex_handle> IdAddressMap;
71  typedef typename IdAddressMap::value_type AddressPair;
72  typedef typename IdAddressMap::iterator IdAddressMapIterator;
73  typedef typename IdAddressMap::const_iterator IdAddressMapConstIterator;
74  std::map<Root_vertex_handle, Vertex_handle> adresses;
75 
76  public:
84  Vertex_handle add_vertex(Root_vertex_handle global) {
85  assert(!this->contains_vertex(global));
86  Vertex_handle address(boost::add_vertex(this->skeleton));
87  this->num_vertices_++;
88  (*this)[address].activate();
89  (*this)[address].set_id(global);
90  adresses.insert(AddressPair(global, address));
91  this->degree_.push_back(0);
92  return address;
93  }
94 
100  void add_edge_without_blockers(Root_vertex_handle v1_root, Root_vertex_handle v2_root) {
101  auto v1_sub(this->get_address(v1_root));
102  auto v2_sub(this->get_address(v2_root));
103  assert(v1_sub && v2_sub);
104  this->ComplexType::add_edge_without_blockers(*v1_sub, *v2_sub);
105  }
106 
112  void add_blocker(const Root_simplex_handle& blocker_root) {
113  auto blocker_sub = this->get_address(blocker_root);
114  assert(blocker_sub);
115  this->add_blocker(new Simplex(*blocker_sub));
116  }
117 
118  public:
123  void make_restricted_complex(const ComplexType & parent_complex,
124  const Simplex& simplex) {
125  this->clear();
126  // add vertices to the sub complex
127  for (auto x : simplex) {
128  assert(parent_complex.contains_vertex(x));
129  auto x_local = this->add_vertex(parent_complex[x].get_id());
130  (*this)[x_local] = parent_complex[x];
131  }
132 
133  // add edges to the sub complex
134  for (auto x : simplex) {
135  // x_neigh is the neighbor of x intersected with vertices_simplex
136  Simplex x_neigh;
137  parent_complex.add_neighbours(x, x_neigh, true);
138  x_neigh.intersection(simplex);
139  for (auto y : x_neigh) {
140  this->add_edge_without_blockers(parent_complex[x].get_id(), parent_complex[y].get_id());
141  }
142  }
143 
144  // add blockers to the sub complex
145  for (auto blocker : parent_complex.const_blocker_range()) {
146  // check if it is the first time we encounter the blocker
147  if (simplex.contains(*blocker)) {
148  Root_simplex_handle blocker_root(parent_complex.get_id(*(blocker)));
149  Simplex blocker_restr(
150  *(this->get_simplex_address(blocker_root)));
151  this->add_blocker(new Simplex(blocker_restr));
152  }
153  }
154  }
155 
156  void clear() {
157  adresses.clear();
158  ComplexType::clear();
159  }
160 
165  boost::optional<Vertex_handle> get_address(Root_vertex_handle global) const {
166  boost::optional < Vertex_handle > res;
167  IdAddressMapConstIterator it = adresses.find(global);
168  if (it == adresses.end())
169  res.reset();
170  else
171  res = (*it).second;
172  return res;
173  }
174 
175  // /**
176  // * Allocates a simplex in L corresponding to the simplex s in K
177  // * with its local adresses and returns an AddressSimplex.
178  // */
179  // boost::optional<Simplex> get_address(const Root_simplex_handle & s) const;
180 
181  // private:
186  // @remark should be private but problem with VS
187 
188  std::vector<boost::optional<Vertex_handle> > get_addresses(
189  const Root_simplex_handle & s) const {
190  std::vector < boost::optional<Vertex_handle> > res;
191  for (auto i : s) {
192  res.push_back(get_address(i));
193  }
194  return res;
195  }
196 };
197 
204 template<typename ComplexType>
205 bool proper_face_in_union(
207  std::vector<boost::optional<typename ComplexType::Vertex_handle> > & addresses_sigma_in_link,
208  std::size_t vertex_to_be_ignored) {
209  // we test that all vertices of 'addresses_sigma_in_link' but 'vertex_to_be_ignored'
210  // are in link1 if it is the case we construct the corresponding simplex
211  bool vertices_sigma_are_in_link = true;
212  typename ComplexType::Simplex sigma_in_link;
213  for (std::size_t i = 0; i < addresses_sigma_in_link.size(); ++i) {
214  if (i != vertex_to_be_ignored) {
215  if (!addresses_sigma_in_link[i]) {
216  vertices_sigma_are_in_link = false;
217  break;
218  } else {
219  sigma_in_link.add_vertex(*addresses_sigma_in_link[i]);
220  }
221  }
222  }
223  // If one of vertices of the simplex is not in the complex then it returns false
224  // Otherwise, it tests if the simplex is in the complex
225  return vertices_sigma_are_in_link && link.contains(sigma_in_link);
226 }
227 
228 // Remark: this function should be friend in order to leave get_adresses private
229 // however doing so seemes currently not possible due to a visual studio bug c2668
230 // "the compiler does not support partial ordering of template functions as specified in the C++ Standard"
231 // http://www.serkey.com/error-c2668-ambiguous-call-to-overloaded-function-bb45ft.html
232 
233 template<typename ComplexType>
234 bool proper_faces_in_union(
238  typedef typename ComplexType::Vertex_handle Vertex_handle;
239  std::vector < boost::optional<Vertex_handle> > addresses_sigma_in_link1 =
240  link1.get_addresses(sigma);
241  std::vector < boost::optional<Vertex_handle> > addresses_sigma_in_link2 =
242  link2.get_addresses(sigma);
243 
244  for (std::size_t current_index = 0; current_index < addresses_sigma_in_link1.size();
245  ++current_index) {
246  if (!proper_face_in_union(link1, addresses_sigma_in_link1, current_index)
247  && !proper_face_in_union(link2, addresses_sigma_in_link2,
248  current_index)) {
249  return false;
250  }
251  }
252  return true;
253 }
254 
255 } // namespace skeleton_blocker
256 
257 namespace skbl = skeleton_blocker;
258 
259 } // namespace Gudhi
260 
261 #endif // SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_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
boost::optional< Vertex_handle > get_address(Root_vertex_handle global) const
Definition: Skeleton_blocker_sub_complex.h:165
std::vector< boost::optional< Vertex_handle > > get_addresses(const Root_simplex_handle &s) const
Definition: Skeleton_blocker_sub_complex.h:188
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
Link_complex link(Vertex_handle v) const
Definition: Skeleton_blocker_complex.h:893
Vertex_handle add_vertex(Root_vertex_handle global)
Definition: Skeleton_blocker_sub_complex.h:84
void clear()
Definition: Skeleton_blocker_sub_complex.h:156
void make_restricted_complex(const ComplexType &parent_complex, const Simplex &simplex)
Definition: Skeleton_blocker_sub_complex.h:123
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