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
21namespace Gudhi {
22
23namespace skeleton_blocker {
24
45template<typename ComplexType>
46class 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 addresses 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
204template<typename ComplexType>
205bool proper_face_in_union(
206 Skeleton_blocker_sub_complex<ComplexType> & link,
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 seems 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
233template<typename ComplexType>
234bool proper_faces_in_union(
235 Skeleton_blocker_simplex<typename ComplexType::Root_vertex_handle> & sigma,
236 Skeleton_blocker_sub_complex<ComplexType> & link1,
237 Skeleton_blocker_sub_complex<ComplexType> & link2) {
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
257namespace skbl = skeleton_blocker;
258
259} // namespace Gudhi
260
261#endif // SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_COMPLEX_H_
Vertex_handle add_vertex()
Adds a vertex to the simplicial complex and returns its Vertex_handle.
Definition: Skeleton_blocker_complex.h:372
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
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 make_restricted_complex(const ComplexType &parent_complex, const Simplex &simplex)
Definition: Skeleton_blocker_sub_complex.h:123
std::vector< boost::optional< Vertex_handle > > get_addresses(const Root_simplex_handle &s) const
Definition: Skeleton_blocker_sub_complex.h:188
void add_blocker(const Root_simplex_handle &blocker_root)
Definition: Skeleton_blocker_sub_complex.h:112
Vertex_handle add_vertex(Root_vertex_handle global)
Definition: Skeleton_blocker_sub_complex.h:84
void add_edge_without_blockers(Root_vertex_handle v1_root, Root_vertex_handle v2_root)
Definition: Skeleton_blocker_sub_complex.h:100
boost::optional< Vertex_handle > get_address(Root_vertex_handle global) const
Definition: Skeleton_blocker_sub_complex.h:165
Handle type for the vertices of a cell complex.
Definition: VertexHandle.h:15