Skeleton_blocker_simplex.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_SIMPLEX_H_
12 #define SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_
13 
14 #include <cassert>
15 #include <iostream>
16 #include <set>
17 #include <vector>
18 #include <initializer_list>
19 #include <string>
20 #include <algorithm>
21 
22 namespace Gudhi {
23 
24 namespace skeleton_blocker {
25 
36 template<typename T>
37 
39  private:
40  std::set<T> simplex_set;
41 
42  public:
43  typedef typename T::boost_vertex_handle boost_vertex_handle;
44 
45  typedef T Vertex_handle;
46 
47  typedef typename std::set<T>::const_iterator Simplex_vertex_const_iterator;
48  typedef typename std::set<T>::iterator Simplex_vertex_iterator;
49 
53 
54  void clear() {
55  simplex_set.clear();
56  }
57 
58  Skeleton_blocker_simplex(std::initializer_list<T>& list) {
59  std::for_each(list.begin(), list.end(), [&] (T const& elt) {
60  add_vertex(elt);
61  });
62  }
63 
64  template<typename ... Args>
65  explicit Skeleton_blocker_simplex(Args ... args) {
66  add_vertices(args...);
67  }
68 
69  template<typename ... Args>
70  void add_vertices(T v, Args ... args) {
71  add_vertex(v);
72  add_vertices(args...);
73  }
74 
75  void add_vertices(T v) {
76  add_vertex(v);
77  }
78 
79  void add_vertices() { }
80 
84  explicit Skeleton_blocker_simplex(std::string token) {
85  clear();
86  if ((token[0] == '{') && (token[token.size() - 1] == '}')) {
87  token.erase(0, 1);
88  token.erase(token.size() - 1, 1);
89  while (token.size() != 0) {
90  int coma_position = token.find_first_of(',');
91  // cout << "coma_position:"<<coma_position<<endl;
92  std::string n = token.substr(0, coma_position);
93  // cout << "token:"<<token<<endl;
94  token.erase(0, n.size() + 1);
95  add_vertex((T) (atoi(n.c_str())));
96  }
97  }
98  }
99 
101 
110  void add_vertex(T v) {
111  simplex_set.insert(v);
112  }
113 
117  void remove_vertex(T v) {
118  simplex_set.erase(v);
119  }
120 
125  std::vector<T> v;
126  v.reserve((std::min)(simplex_set.size(), a.simplex_set.size()));
127 
128  set_intersection(simplex_set.begin(), simplex_set.end(),
129  a.simplex_set.begin(), a.simplex_set.end(),
130  std::back_inserter(v));
131  clear();
132  for (auto i : v)
133  simplex_set.insert(i);
134  }
135 
140  std::vector<T> v;
141  v.reserve(simplex_set.size());
142 
143  set_difference(simplex_set.begin(), simplex_set.end(),
144  a.simplex_set.begin(), a.simplex_set.end(),
145  std::back_inserter(v));
146 
147  clear();
148  for (auto i : v)
149  simplex_set.insert(i);
150  }
151 
156  std::vector<T> v;
157  v.reserve(simplex_set.size() + a.simplex_set.size());
158 
159  set_union(simplex_set.begin(), simplex_set.end(), a.simplex_set.begin(),
160  a.simplex_set.end(), std::back_inserter(v));
161  clear();
162  simplex_set.insert(v.begin(), v.end());
163  }
164 
165  typename std::set<T>::const_iterator begin() const {
166  return simplex_set.cbegin();
167  }
168 
169  typename std::set<T>::const_iterator end() const {
170  return simplex_set.cend();
171  }
172 
173  typename std::set<T>::const_reverse_iterator rbegin() const {
174  return simplex_set.crbegin();
175  }
176 
177  typename std::set<T>::const_reverse_iterator rend() const {
178  return simplex_set.crend();
179  }
180 
181  typename std::set<T>::iterator begin() {
182  return simplex_set.begin();
183  }
184 
185  typename std::set<T>::iterator end() {
186  return simplex_set.end();
187  }
188 
190 
197  int dimension() const {
198  return (simplex_set.size() - 1);
199  }
200 
201  bool empty() const {
202  return simplex_set.empty();
203  }
204 
210  T first_vertex() const {
211  assert(!empty());
212  return *(begin());
213  }
214 
220  T last_vertex() const {
221  assert(!empty());
222  return *(simplex_set.rbegin());
223  }
224 
228  bool contains(const Skeleton_blocker_simplex & a) const {
229  return includes(simplex_set.cbegin(), simplex_set.cend(),
230  a.simplex_set.cbegin(), a.simplex_set.cend());
231  }
232 
237  const Skeleton_blocker_simplex& b) const {
238  auto first1 = begin();
239  auto last1 = end();
240 
241  auto first2 = a.begin();
242  auto last2 = a.end();
243 
244  while (first2 != last2) {
245  // we ignore vertices of b
246  if (b.contains(*first2)) {
247  ++first2;
248  } else {
249  if ((first1 == last1) || (*first2 < *first1))
250  return false;
251  if (!(*first1 < *first2))
252  ++first2;
253  ++first1;
254  }
255  }
256  return true;
257  }
258 
262  bool contains_difference(const Skeleton_blocker_simplex& a, T x) const {
263  auto first1 = begin();
264  auto last1 = end();
265 
266  auto first2 = a.begin();
267  auto last2 = a.end();
268 
269  while (first2 != last2) {
270  // we ignore vertices x
271  if (x == *first2) {
272  ++first2;
273  } else {
274  if ((first1 == last1) || (*first2 < *first1))
275  return false;
276  if (!(*first1 < *first2))
277  ++first2;
278  ++first1;
279  }
280  }
281  return true;
282  }
283 
287  bool contains_difference(const Skeleton_blocker_simplex& a, T x, T y) const {
288  auto first1 = begin();
289  auto last1 = end();
290 
291  auto first2 = a.begin();
292  auto last2 = a.end();
293 
294  while (first2 != last2) {
295  // we ignore vertices of x,y
296  if (x == *first2 || y == *first2) {
297  ++first2;
298  } else {
299  if ((first1 == last1) || (*first2 < *first1))
300  return false;
301  if (!(*first1 < *first2))
302  ++first2;
303  ++first1;
304  }
305  }
306  return true;
307  }
308 
309  bool contains(T v) const {
310  return (simplex_set.find(v) != simplex_set.end());
311  }
312 
313  bool disjoint(const Skeleton_blocker_simplex& a) const {
314  std::vector<T> v;
315  v.reserve(std::min(simplex_set.size(), a.simplex_set.size()));
316 
317  set_intersection(simplex_set.cbegin(), simplex_set.cend(),
318  a.simplex_set.cbegin(), a.simplex_set.cend(),
319  std::back_inserter(v));
320 
321  return (v.size() == 0);
322  }
323 
324  bool operator==(const Skeleton_blocker_simplex& other) const {
325  return (this->simplex_set == other.simplex_set);
326  }
327 
328  bool operator!=(const Skeleton_blocker_simplex& other) const {
329  return (this->simplex_set != other.simplex_set);
330  }
331 
332  bool operator<(const Skeleton_blocker_simplex& other) const {
333  return (std::lexicographical_compare(this->simplex_set.begin(),
334  this->simplex_set.end(), other.begin(),
335  other.end()));
336  }
337 
339 
340  friend std::ostream& operator<<(std::ostream& o,
341  const Skeleton_blocker_simplex & sigma) {
342  bool first = true;
343  o << "{";
344  for (auto i : sigma) {
345  if (first)
346  first = false;
347  else
348  o << ",";
349  o << i;
350  }
351  o << "}";
352  return o;
353  }
354 };
355 
356 } // namespace skeleton_blocker
357 
358 namespace skbl = skeleton_blocker;
359 
360 } // namespace Gudhi
361 
362 #endif // SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_
Abstract simplex used in Skeleton blockers data-structure.
Definition: Skeleton_blocker_simplex.h:38
T first_vertex() const
Definition: Skeleton_blocker_simplex.h:210
bool contains_difference(const Skeleton_blocker_simplex &a, T x, T y) const
Definition: Skeleton_blocker_simplex.h:287
void union_vertices(const Skeleton_blocker_simplex &a)
Definition: Skeleton_blocker_simplex.h:155
bool contains(const Skeleton_blocker_simplex &a) const
Definition: Skeleton_blocker_simplex.h:228
void intersection(const Skeleton_blocker_simplex &a)
Definition: Skeleton_blocker_simplex.h:124
Skeleton_blocker_simplex(std::string token)
Definition: Skeleton_blocker_simplex.h:84
T last_vertex() const
Definition: Skeleton_blocker_simplex.h:220
void remove_vertex(T v)
Definition: Skeleton_blocker_simplex.h:117
bool contains_difference(const Skeleton_blocker_simplex &a, T x) const
Definition: Skeleton_blocker_simplex.h:262
bool contains_difference(const Skeleton_blocker_simplex &a, const Skeleton_blocker_simplex &b) const
Definition: Skeleton_blocker_simplex.h:236
void difference(const Skeleton_blocker_simplex &a)
Definition: Skeleton_blocker_simplex.h:139
int dimension() const
Definition: Skeleton_blocker_simplex.h:197
void add_vertex(T v)
Definition: Skeleton_blocker_simplex.h:110
Gudhi namespace.
Definition: SimplicialComplexForAlpha.h:14