Skeleton_blocker_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_COMPLEX_H_
12#define SKELETON_BLOCKER_COMPLEX_H_
13
14#include <gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h>
15#include <gudhi/Skeleton_blocker_link_complex.h>
16#include <gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h>
17#include <gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h>
18#include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h>
19#include <gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h>
20#include <gudhi/Skeleton_blocker/internal/Top_faces.h>
21#include <gudhi/Skeleton_blocker/internal/Trie.h>
22#include <gudhi/Debug_utils.h>
23
24#include <boost/graph/adjacency_list.hpp>
25#include <boost/graph/connected_components.hpp>
26#include <boost/iterator/transform_iterator.hpp>
27#include <boost/range/adaptor/map.hpp>
28
29#include <iostream>
30#include <fstream>
31#include <sstream>
32#include <memory>
33#include <map>
34#include <list>
35#include <set>
36#include <vector>
37#include <string>
38#include <algorithm>
39#include <utility>
40
41namespace Gudhi {
42
43namespace skeleton_blocker {
44
50template<class SkeletonBlockerDS>
52 template<class ComplexType> friend class Vertex_iterator;
53 template<class ComplexType> friend class Neighbors_vertices_iterator;
54 template<class ComplexType> friend class Edge_iterator;
55 template<class ComplexType> friend class Edge_around_vertex_iterator;
56
57 template<class ComplexType> friend class Skeleton_blocker_link_complex;
58 template<class ComplexType> friend class Skeleton_blocker_link_superior;
59 template<class ComplexType> friend class Skeleton_blocker_sub_complex;
60
61 public:
66
71
73
78 typedef typename Root_vertex_handle::boost_vertex_handle boost_vertex_handle;
79
85
90
91 typedef typename Root_simplex_handle::Simplex_vertex_const_iterator Root_simplex_iterator;
92 typedef typename Simplex::Simplex_vertex_const_iterator Simplex_handle_iterator;
93
94 protected:
95 typedef typename boost::adjacency_list<boost::setS, // edges
96 boost::vecS, // vertices
97 boost::undirectedS, Graph_vertex, Graph_edge> Graph;
98 // todo/remark : edges are not sorted, it heavily penalizes computation for SuperiorLink
99 // (eg Link with greater vertices)
100 // that burdens simplex iteration / complex initialization via list of simplices.
101 // to avoid that, one should modify the graph by storing two lists of adjacency for every
102 // vertex, the one with superior and the one with lower vertices, that way there is
103 // no more extra cost for computation of SuperiorLink
104 typedef typename boost::graph_traits<Graph>::vertex_iterator boost_vertex_iterator;
105 typedef typename boost::graph_traits<Graph>::edge_iterator boost_edge_iterator;
106
107 protected:
108 typedef typename boost::graph_traits<Graph>::adjacency_iterator boost_adjacency_iterator;
109
110 public:
114 typedef typename boost::graph_traits<Graph>::edge_descriptor Edge_handle;
115
116 protected:
117 typedef std::multimap<Vertex_handle, Simplex *> BlockerMap;
118 typedef typename std::multimap<Vertex_handle, Simplex *>::value_type BlockerPair;
119 typedef typename std::multimap<Vertex_handle, Simplex *>::iterator BlockerMapIterator;
120 typedef typename std::multimap<Vertex_handle, Simplex *>::const_iterator BlockerMapConstIterator;
121
122 protected:
123 size_t num_vertices_;
124 size_t num_blockers_;
125
127 // typedef Visitor* Visitor_ptr;
128 Visitor* visitor;
129
138 std::vector<boost_vertex_handle> degree_;
139 Graph skeleton;
142 BlockerMap blocker_map_;
143
144 public:
146
149
153 explicit Skeleton_blocker_complex(size_t num_vertices_ = 0, Visitor* visitor_ = NULL)
154 : visitor(visitor_) {
155 clear();
156 for (size_t i = 0; i < num_vertices_; ++i) {
157 add_vertex();
158 }
159 }
160
161 private:
162 // typedef Trie<Skeleton_blocker_complex<SkeletonBlockerDS>> STrie;
163 typedef Trie<Simplex> STrie;
164
165 public:
170 template<typename SimpleHandleOutputIterator>
171 Skeleton_blocker_complex(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end,
172 bool is_flag_complex = false, Visitor* visitor_ = NULL)
173 : num_vertices_(0),
174 num_blockers_(0),
175 visitor(visitor_) {
176 add_vertices_and_edges(simplices_begin, simplices_end);
177
178 if (!is_flag_complex)
179 // need to compute blockers
180 add_blockers(simplices_begin, simplices_end);
181 }
182
183 private:
187 template<typename SimpleHandleOutputIterator>
188 void add_vertices_and_edges(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end) {
189 std::vector<std::pair<Vertex_handle, Vertex_handle>> edges;
190 // first pass to add vertices and edges
191 int num_vertex = -1;
192 for (auto s_it = simplices_begin; s_it != simplices_end; ++s_it) {
193 if (s_it->dimension() == 0) num_vertex = (std::max)(num_vertex, s_it->first_vertex().vertex);
194 if (s_it->dimension() == 1) edges.emplace_back(s_it->first_vertex(), s_it->last_vertex());
195 }
196 while (num_vertex-- >= 0) add_vertex();
197
198 for (const auto& e : edges)
199 add_edge_without_blockers(e.first, e.second);
200 }
201
202 template<typename SimpleHandleOutputIterator>
203 void add_blockers(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end) {
204 Tries<Simplex> tries(num_vertices(), simplices_begin, simplices_end);
205 tries.init_next_dimension();
206 auto simplices(tries.next_dimension_simplices());
207
208 while (!simplices.empty()) {
209 simplices = tries.next_dimension_simplices();
210 for (auto& sigma : simplices) {
211 // common_positive_neighbors is the set of vertices u such that
212 // for all s in sigma, us is an edge and u>s
213 Simplex common_positive_neighbors(tries.positive_neighbors(sigma.last_vertex()));
214 for (auto sigma_it = sigma.rbegin(); sigma_it != sigma.rend(); ++sigma_it)
215 if (sigma_it != sigma.rbegin())
216 common_positive_neighbors.intersection(tries.positive_neighbors(*sigma_it));
217
218 for (auto x : common_positive_neighbors) {
219 // first test that all edges sx are here for all s in sigma
220 bool all_edges_here = true;
221 for (auto s : sigma)
222 if (!contains_edge(x, s)) {
223 all_edges_here = false;
224 break;
225 }
226 if (!all_edges_here) continue;
227
228 // all edges of sigma \cup x are here
229 // we have a blocker if all proper faces of sigma \cup x
230 // are in the complex and if sigma \cup x is not in the complex
231 // the first is equivalent at checking if blocks(sigma \cup x) is true
232 // as all blockers of lower dimension have already been computed
233 sigma.add_vertex(x);
234 if (!tries.contains(sigma) && !blocks(sigma))
235 add_blocker(sigma);
236 sigma.remove_vertex(x);
237 }
238 }
239 }
240 }
241
242 public:
243 // We cannot use the default copy constructor since we need
244 // to make a copy of each of the blockers
245
247 visitor = NULL;
248 degree_ = copy.degree_;
249 skeleton = Graph(copy.skeleton);
250 num_vertices_ = copy.num_vertices_;
251
252 num_blockers_ = 0;
253 // we copy the blockers
254 for (auto blocker : copy.const_blocker_range()) {
255 add_blocker(*blocker);
256 }
257 }
258
261 Skeleton_blocker_complex& operator=(const Skeleton_blocker_complex& copy) {
262 clear();
263 visitor = NULL;
264 degree_ = copy.degree_;
265 skeleton = Graph(copy.skeleton);
266 num_vertices_ = copy.num_vertices_;
267
268 num_blockers_ = 0;
269 // we copy the blockers
270 for (auto blocker : copy.const_blocker_range())
271 add_blocker(*blocker);
272 return *this;
273 }
274
278 bool operator==(const Skeleton_blocker_complex& other) const {
279 if (other.num_vertices() != num_vertices()) return false;
280 if (other.num_edges() != num_edges()) return false;
281 if (other.num_blockers() != num_blockers()) return false;
282
283 for (auto v : vertex_range())
284 if (!other.contains_vertex(v)) return false;
285
286 for (auto e : edge_range())
287 if (!other.contains_edge(first_vertex(e), second_vertex(e))) return false;
288
289 for (const auto b : const_blocker_range())
290 if (!other.contains_blocker(*b)) return false;
291
292 return true;
293 }
294
295 bool operator!=(const Skeleton_blocker_complex& other) const {
296 return !(*this == other);
297 }
298
303 clear();
304 }
305
311 virtual void clear() {
312 // xxx for now the responsabilty of freeing the visitor is for
313 // the user
314 visitor = NULL;
315
316 degree_.clear();
317 num_vertices_ = 0;
318
320
321 skeleton.clear();
322 }
323
327 void set_visitor(Visitor* other_visitor) {
328 visitor = other_visitor;
329 }
330
332
334
337 public:
343 auto local(get_address(global));
344 assert(local);
345 return *local;
346 }
347
353 assert(
354 0 <= address.vertex && address.vertex < boost::num_vertices(skeleton));
355 return skeleton[address.vertex];
356 }
357
362 const Graph_vertex& operator[](Vertex_handle address) const {
363 assert(
364 0 <= address.vertex && address.vertex < boost::num_vertices(skeleton));
365 return skeleton[address.vertex];
366 }
367
373 Vertex_handle address(boost::add_vertex(skeleton));
374 num_vertices_++;
375 (*this)[address].activate();
376 // safe since we now that we are in the root complex and the field 'address' and 'id'
377 // are identical for every vertices
378 (*this)[address].set_id(Root_vertex_handle(address.vertex));
379 degree_.push_back(0);
380 if (visitor)
381 visitor->on_add_vertex(address);
382 return address;
383 }
384
391 assert(contains_vertex(address));
392 // We remove b
393 boost::clear_vertex(address.vertex, skeleton);
394 (*this)[address].deactivate();
395 num_vertices_--;
396 degree_[address.vertex] = -1;
397 if (visitor)
398 visitor->on_remove_vertex(address);
399 }
400
403 bool contains_vertex(Vertex_handle u) const {
404 Vertex_handle num_vertices(boost::num_vertices(skeleton));
405 if (u.vertex < 0 || u.vertex >= num_vertices)
406 return false;
407 return (*this)[u].is_active();
408 }
409
412 bool contains_vertex(Root_vertex_handle u) const {
413 boost::optional<Vertex_handle> address = get_address(u);
414 return address && (*this)[*address].is_active();
415 }
416
421 bool contains_vertices(const Simplex & sigma) const {
422 for (auto vertex : sigma)
423 if (!contains_vertex(vertex))
424 return false;
425 return true;
426 }
427
432 virtual boost::optional<Vertex_handle> get_address(Root_vertex_handle id) const {
433 boost::optional<Vertex_handle> res;
434 int num_vertices = boost::num_vertices(skeleton);
435 if (id.vertex < num_vertices)
436 res = Vertex_handle(id.vertex);
437 return res;
438 }
439
444 assert(0 <= local.vertex && local.vertex < boost::num_vertices(skeleton));
445 return (*this)[local].get_id();
446 }
447
459 Vertex_handle vh_in_other) const {
460 auto vh_in_current_complex = get_address(other.get_id(vh_in_other));
461 assert(vh_in_current_complex);
462 return *vh_in_current_complex;
463 }
464
468 int degree(Vertex_handle local) const {
469 assert(0 <= local.vertex && local.vertex < boost::num_vertices(skeleton));
470 return degree_[local.vertex];
471 }
472
474
476
479 public:
484 boost::optional<Edge_handle> operator[](
485 const std::pair<Vertex_handle, Vertex_handle>& ab) const {
486 boost::optional<Edge_handle> res;
487 std::pair<Edge_handle, bool> edge_pair(
488 boost::edge(ab.first.vertex, ab.second.vertex, skeleton));
489 if (edge_pair.second)
490 res = edge_pair.first;
491 return res;
492 }
493
498 return skeleton[edge_handle];
499 }
500
504 const Graph_edge& operator[](Edge_handle edge_handle) const {
505 return skeleton[edge_handle];
506 }
507
513 return static_cast<Vertex_handle> (source(edge_handle, skeleton));
514 }
515
521 return static_cast<Vertex_handle> (target(edge_handle, skeleton));
522 }
523
529 Simplex get_vertices(Edge_handle edge_handle) const {
530 auto edge((*this)[edge_handle]);
531 return Simplex((*this)[edge.first()], (*this)[edge.second()]);
532 }
533
542 // if the edge is already there we musnt go further
543 // as we may add blockers that should not be here
544 if (contains_edge(a, b))
545 return *((*this)[std::make_pair(a, b)]);
546 auto res = add_edge_without_blockers(a, b);
547 add_blockers_after_simplex_insertion(Simplex(a, b));
548 return res;
549 }
550
554 void add_edge(const Simplex& s) {
555 for (auto i = s.begin(); i != s.end(); ++i)
556 for (auto j = i; ++j != s.end(); )
557 add_edge(*i, *j);
558 }
559
567 assert(contains_vertex(a) && contains_vertex(b));
568 assert(a != b);
569
570 auto edge_handle((*this)[std::make_pair(a, b)]);
571 if (!edge_handle) {
572 edge_handle = boost::add_edge(a.vertex, b.vertex, skeleton).first;
573 (*this)[*edge_handle].setId(get_id(a), get_id(b));
574 degree_[a.vertex]++;
575 degree_[b.vertex]++;
576 if (visitor)
577 visitor->on_add_edge_without_blockers(a, b);
578 }
579 return *edge_handle;
580 }
581
586 for (auto i = s.begin(); i != s.end(); ++i) {
587 for (auto j = i; ++j != s.end(); )
589 }
590 }
591
597 bool found;
598 Edge_handle edge;
599 tie(edge, found) = boost::edge(a.vertex, b.vertex, skeleton);
600 if (found) {
601 if (visitor)
602 visitor->on_remove_edge(a, b);
603 boost::remove_edge(a.vertex, b.vertex, skeleton);
604 degree_[a.vertex]--;
605 degree_[b.vertex]--;
606 }
607 return edge;
608 }
609
614 assert(contains_vertex(first_vertex(edge)));
615 assert(contains_vertex(second_vertex(edge)));
617 }
618
625
626 for (auto u : vertex_range()) {
627 while (this->degree(u) > 0) {
628 Vertex_handle v(*(adjacent_vertices(u.vertex, this->skeleton).first));
629 this->remove_edge(u, v);
630 }
631 }
632 }
633
639 // if (a.vertex<0 || b.vertex <0) return false;
640 return boost::edge(a.vertex, b.vertex, skeleton).second;
641 }
642
647 bool contains_edges(const Simplex & sigma) const {
648 for (auto i = sigma.begin(); i != sigma.end(); ++i) {
649 if (!contains_vertex(*i))
650 return false;
651 for (auto j = i; ++j != sigma.end();) {
652 if (!contains_edge(*i, *j))
653 return false;
654 }
655 }
656 return true;
657 }
659
661
664
670 assert(blocker.dimension() > 1);
671 if (contains_blocker(blocker)) {
672 return 0;
673 } else {
674 if (visitor)
675 visitor->on_add_blocker(blocker);
676 Blocker_handle blocker_pt = new Simplex(blocker);
677 num_blockers_++;
678 auto vertex = blocker_pt->begin();
679 while (vertex != blocker_pt->end()) {
680 blocker_map_.insert(BlockerPair(*vertex, blocker_pt));
681 ++vertex;
682 }
683 return blocker_pt;
684 }
685 }
686
687 protected:
691 void add_blocker(Blocker_handle blocker) {
692 if (contains_blocker(*blocker)) {
693 // std::cerr << "ATTEMPT TO ADD A BLOCKER ALREADY THERE ---> BLOCKER IGNORED" << endl;
694 return;
695 } else {
696 if (visitor)
697 visitor->on_add_blocker(*blocker);
698 num_blockers_++;
699 auto vertex = blocker->begin();
700 while (vertex != blocker->end()) {
701 blocker_map_.insert(BlockerPair(*vertex, blocker));
702 ++vertex;
703 }
704 }
705 }
706
707 protected:
711 void remove_blocker(const Blocker_handle sigma, Vertex_handle v) {
712 Complex_blocker_around_vertex_iterator blocker;
713 for (blocker = blocker_range(v).begin(); blocker != blocker_range(v).end();
714 ++blocker) {
715 if (*blocker == sigma)
716 break;
717 }
718 if (*blocker != sigma) {
719 std::cerr
720 << "bug ((*blocker).second == sigma) ie try to remove a blocker not present\n";
721 assert(false);
722 } else {
723 blocker_map_.erase(blocker.current_position());
724 }
725 }
726
727 public:
732 void remove_blocker(const Blocker_handle sigma) {
733 for (auto vertex : *sigma)
734 remove_blocker(sigma, vertex);
735 num_blockers_--;
736 }
737
743 // Deallocate the blockers
744 while (!blocker_map_.empty()) {
745 delete_blocker(blocker_map_.begin()->second);
746 }
747 num_blockers_ = 0;
748 blocker_map_.clear();
749 }
750
751 protected:
758 void remove_blocker(const Simplex& sigma) {
759 assert(contains_blocker(sigma));
760 for (auto vertex : sigma)
761 remove_blocker(sigma, vertex);
762 num_blockers_--;
763 }
764
765 public:
771 if (visitor)
772 visitor->on_delete_blocker(sigma);
773 remove_blocker(sigma);
774 delete sigma;
775 }
776
780 bool contains_blocker(const Blocker_handle s) const {
781 if (s->dimension() < 2)
782 return false;
783
785
786 for (const auto blocker : const_blocker_range(a)) {
787 if (s == *blocker)
788 return true;
789 }
790 return false;
791 }
792
796 bool contains_blocker(const Simplex & s) const {
797 if (s.dimension() < 2)
798 return false;
799
801
802 for (auto blocker : const_blocker_range(a)) {
803 if (s == *blocker)
804 return true;
805 }
806 return false;
807 }
808
809 private:
814 bool blocks(const Simplex & sigma) const {
815 for (auto s : sigma)
816 for (auto blocker : const_blocker_range(s))
817 if (sigma.contains(*blocker))
818 return true;
819 return false;
820 }
821
823
824 protected:
829 virtual void add_neighbours(Vertex_handle v, Simplex & n,
830 bool keep_only_superior = false) const {
831 boost_adjacency_iterator ai, ai_end;
832 for (tie(ai, ai_end) = adjacent_vertices(v.vertex, skeleton); ai != ai_end;
833 ++ai) {
834 Vertex_handle value(*ai);
835 if (keep_only_superior) {
836 if (value > v.vertex) {
837 n.add_vertex(value);
838 }
839 } else {
840 n.add_vertex(value);
841 }
842 }
843 }
844
853 virtual void add_neighbours(const Simplex &alpha, Simplex & res,
854 bool keep_only_superior = false) const {
855 res.clear();
856 auto alpha_vertex = alpha.begin();
857 add_neighbours(*alpha_vertex, res, keep_only_superior);
858 for (alpha_vertex = (alpha.begin())++; alpha_vertex != alpha.end();
859 ++alpha_vertex)
860 keep_neighbours(*alpha_vertex, res, keep_only_superior);
861 }
862
868 virtual void keep_neighbours(Vertex_handle v, Simplex& res,
869 bool keep_only_superior = false) const {
870 Simplex nv;
871 add_neighbours(v, nv, keep_only_superior);
872 res.intersection(nv);
873 }
874
880 virtual void remove_neighbours(Vertex_handle v, Simplex & res,
881 bool keep_only_superior = false) const {
882 Simplex nv;
883 add_neighbours(v, nv, keep_only_superior);
884 res.difference(nv);
885 }
886
887 public:
888 typedef Skeleton_blocker_link_complex<Skeleton_blocker_complex> Link_complex;
889
894 return Link_complex(*this, Simplex(v));
895 }
896
901 return Link_complex(*this, edge);
902 }
903
907 Link_complex link(const Simplex& simplex) const {
908 return Link_complex(*this, simplex);
909 }
910
917 // xxx rename get_address et place un using dans sub_complex
918
919 boost::optional<Simplex> get_simplex_address(
920 const Root_simplex_handle& s) const {
921 boost::optional<Simplex> res;
922
923 Simplex s_address;
924 // Root_simplex_const_iterator i;
925 for (auto i = s.begin(); i != s.end(); ++i) {
926 boost::optional<Vertex_handle> address = get_address(*i);
927 if (!address)
928 return res;
929 else
930 s_address.add_vertex(*address);
931 }
932 res = s_address;
933 return res;
934 }
935
940 Root_simplex_handle get_id(const Simplex& local_simplex) const {
941 Root_simplex_handle global_simplex;
942 for (auto x = local_simplex.begin(); x != local_simplex.end(); ++x) {
943 global_simplex.add_vertex(get_id(*x));
944 }
945 return global_simplex;
946 }
947
952 virtual bool contains(const Simplex & s) const {
953 if (s.dimension() == -1) {
954 return false;
955 } else if (s.dimension() == 0) {
956 return contains_vertex(s.first_vertex());
957 } else {
958 return (contains_edges(s) && !blocks(s));
959 }
960 }
961
962 /*
963 * @brief returns true iff the complex is empty.
964 */
965 bool empty() const {
966 return num_vertices() == 0;
967 }
968
969 /*
970 * @brief returns the number of vertices in the complex.
971 */
972 int num_vertices() const {
973 // remark boost::num_vertices(skeleton) counts deactivated vertices
974 return num_vertices_;
975 }
976
977 /*
978 * @brief returns the number of edges in the complex.
979 * @details currently in O(n)
980 */
981 // todo cache the value
982
983 int num_edges() const {
984 return boost::num_edges(skeleton);
985 }
986
987 int num_triangles() const {
988 auto triangles = triangle_range();
989 return std::distance(triangles.begin(), triangles.end());
990 }
991
992 /*
993 * @brief returns the number of simplices of a given dimension in the complex.
994 */
995 size_t num_simplices() const {
996 auto simplices = complex_simplex_range();
997 return std::distance(simplices.begin(), simplices.end());
998 }
999
1000 /*
1001 * @brief returns the number of simplices of a given dimension in the complex.
1002 */
1003 size_t num_simplices(int dimension) const {
1004 // TODO(DS): iterator on k-simplices
1005 size_t res = 0;
1006 for (const auto& s : complex_simplex_range())
1007 if (s.dimension() == dimension)
1008 ++res;
1009 return res;
1010 }
1011
1012 /*
1013 * @brief returns the number of blockers in the complex.
1014 */
1015 size_t num_blockers() const {
1016 return num_blockers_;
1017 }
1018
1019 /*
1020 * @brief returns true iff the graph of the 1-skeleton of the complex is complete.
1021 */
1022 bool complete() const {
1023 return (num_vertices() * (num_vertices() - 1)) / 2 == num_edges();
1024 }
1025
1030 int num_vert_collapsed = skeleton.vertex_set().size() - num_vertices();
1031 std::vector<int> component(skeleton.vertex_set().size());
1032 return boost::connected_components(this->skeleton, &component[0])
1033 - num_vert_collapsed;
1034 }
1035
1040 bool is_cone() const {
1041 if (num_vertices() == 0)
1042 return false;
1043 if (num_vertices() == 1)
1044 return true;
1045 for (auto vi : vertex_range()) {
1046 // xxx todo create a method: bool is_in_blocker(Vertex_handle)
1047 if (blocker_map_.find(vi) == blocker_map_.end()) {
1048 // no blocker passes through the vertex, we just need to
1049 // check if the current vertex is linked to all others vertices of the complex
1050 if (degree_[vi.vertex] == num_vertices() - 1)
1051 return true;
1052 }
1053 }
1054 return false;
1055 }
1056
1058
1061
1070 bool is_popable_blocker(Blocker_handle sigma) const;
1071
1076
1081
1088
1092 void remove_star(Vertex_handle v);
1093
1094 private:
1100 void update_blockers_after_remove_star_of_vertex_or_edge(const Simplex& simplex_to_be_removed);
1101
1102 public:
1107
1111 void remove_star(Edge_handle e);
1112
1116 void remove_star(const Simplex& sigma);
1117
1122 void add_simplex(const Simplex& sigma);
1123
1124 private:
1125 void add_blockers_after_simplex_insertion(Simplex s);
1126
1130 void remove_blocker_containing_simplex(const Simplex& sigma);
1131
1135 void remove_blocker_include_in_simplex(const Simplex& sigma);
1136
1137 public:
1138 enum simplifiable_status {
1139 NOT_HOMOTOPY_EQ, MAYBE_HOMOTOPY_EQ, HOMOTOPY_EQ
1140 };
1141
1142 simplifiable_status is_remove_star_homotopy_preserving(const Simplex& simplex) {
1143 // todo write a virtual method 'link' in Skeleton_blocker_complex which will be overloaded by the current one of
1144 // Skeleton_blocker_geometric_complex
1145 // then call it there to build the link and return the value of link.is_contractible()
1146 return MAYBE_HOMOTOPY_EQ;
1147 }
1148
1149 enum contractible_status {
1150 NOT_CONTRACTIBLE, MAYBE_CONTRACTIBLE, CONTRACTIBLE
1151 };
1152
1162 virtual contractible_status is_contractible() const {
1163 if (this->is_cone()) {
1164 return CONTRACTIBLE;
1165 } else {
1166 return MAYBE_CONTRACTIBLE;
1167 }
1168 }
1170
1174
1182 bool link_condition(Vertex_handle a, Vertex_handle b, bool ignore_popable_blockers = false) const {
1183 for (auto blocker : this->const_blocker_range(a))
1184 if (blocker->contains(b)) {
1185 // false if ignore_popable_blockers is false
1186 // otherwise the blocker has to be popable
1187 return ignore_popable_blockers && is_popable_blocker(blocker);
1188 }
1189 return true;
1190 }
1191
1199 bool link_condition(Edge_handle e, bool ignore_popable_blockers = false) const {
1200 const Graph_edge& edge = (*this)[e];
1201 assert(this->get_address(edge.first()));
1202 assert(this->get_address(edge.second()));
1203 Vertex_handle a(*this->get_address(edge.first()));
1204 Vertex_handle b(*this->get_address(edge.second()));
1205 return link_condition(a, b, ignore_popable_blockers);
1206 }
1207
1208 protected:
1214 void tip_blockers(Vertex_handle a, Vertex_handle b, std::vector<Simplex> & buffer) const;
1215
1216 private:
1225 void swap_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x);
1226
1227 private:
1231 void delete_blockers_around_vertex(Vertex_handle v);
1232
1236 void delete_blockers_around_edge(Vertex_handle a, Vertex_handle b);
1237
1238 public:
1245 contract_edge(this->first_vertex(edge), this->second_vertex(edge));
1246 }
1247
1254
1255 private:
1256 void get_blockers_to_be_added_after_contraction(Vertex_handle a, Vertex_handle b,
1257 std::set<Simplex>& blockers_to_add);
1261 void delete_blockers_around_vertices(Vertex_handle a, Vertex_handle b);
1262 void update_edges_after_contraction(Vertex_handle a, Vertex_handle b);
1263 void notify_changed_edges(Vertex_handle a);
1265
1266 public:
1268
1271 typedef Vertex_iterator<Skeleton_blocker_complex> Complex_vertex_iterator;
1272
1273 //
1274 // Range over the vertices of the simplicial complex.
1275 // Methods .begin() and .end() return a Complex_vertex_iterator.
1276 //
1277 typedef boost::iterator_range<Complex_vertex_iterator> Complex_vertex_range;
1278
1282 Complex_vertex_range vertex_range() const {
1283 auto begin = Complex_vertex_iterator(this);
1284 auto end = Complex_vertex_iterator(this, 0);
1285 return Complex_vertex_range(begin, end);
1286 }
1287
1288 typedef Neighbors_vertices_iterator<Skeleton_blocker_complex> Complex_neighbors_vertices_iterator;
1289
1290
1291 typedef boost::iterator_range<Complex_neighbors_vertices_iterator> Complex_neighbors_vertices_range;
1292
1296 Complex_neighbors_vertices_range vertex_range(Vertex_handle v) const {
1297 auto begin = Complex_neighbors_vertices_iterator(this, v);
1298 auto end = Complex_neighbors_vertices_iterator(this, v, 0);
1299 return Complex_neighbors_vertices_range(begin, end);
1300 }
1301
1303
1307
1308 typedef Edge_iterator<Skeleton_blocker_complex> Complex_edge_iterator;
1309
1310
1311 typedef boost::iterator_range<Complex_edge_iterator> Complex_edge_range;
1312
1316 Complex_edge_range edge_range() const {
1317 auto begin = Complex_edge_iterator(this);
1318 auto end = Complex_edge_iterator(this, 0);
1319 return Complex_edge_range(begin, end);
1320 }
1321
1322
1323 typedef Edge_around_vertex_iterator<Skeleton_blocker_complex> Complex_edge_around_vertex_iterator;
1324
1325
1326 typedef boost::iterator_range <Complex_edge_around_vertex_iterator> Complex_edge_around_vertex_range;
1327
1332 Complex_edge_around_vertex_range edge_range(Vertex_handle v) const {
1333 auto begin = Complex_edge_around_vertex_iterator(this, v);
1334 auto end = Complex_edge_around_vertex_iterator(this, v, 0);
1335 return Complex_edge_around_vertex_range(begin, end);
1336 }
1337
1339
1343 private:
1346
1347 public:
1349 Superior_triangle_around_vertex_iterator;
1350 typedef boost::iterator_range < Triangle_around_vertex_iterator<Skeleton_blocker_complex, Link> >
1351 Complex_triangle_around_vertex_range;
1352
1358 Complex_triangle_around_vertex_range triangle_range(Vertex_handle v) const {
1361 return Complex_triangle_around_vertex_range(begin, end);
1362 }
1363
1364 typedef boost::iterator_range<Triangle_iterator<Skeleton_blocker_complex> > Complex_triangle_range;
1365 typedef Triangle_iterator<Skeleton_blocker_complex> Complex_triangle_iterator;
1366
1372 Complex_triangle_range triangle_range() const {
1374 if (empty()) {
1375 return Complex_triangle_range(end, end);
1376 } else {
1378 return Complex_triangle_range(begin, end);
1379 }
1380 }
1381
1383
1387 typedef Simplex_around_vertex_iterator<Skeleton_blocker_complex, Link> Complex_simplex_around_vertex_iterator;
1388
1393 typedef boost::iterator_range < Complex_simplex_around_vertex_iterator > Complex_simplex_around_vertex_range;
1394
1399 assert(contains_vertex(v));
1403 }
1404 typedef Simplex_coboundary_iterator<Skeleton_blocker_complex, Link> Complex_simplex_coboundary_iterator;
1405
1410 typedef boost::iterator_range < Complex_simplex_coboundary_iterator > Complex_coboundary_range;
1411
1416 assert(contains(s));
1419 }
1420
1421 // typedef Simplex_iterator<Skeleton_blocker_complex,Superior_link> Complex_simplex_iterator;
1422 typedef Simplex_iterator<Skeleton_blocker_complex> Complex_simplex_iterator;
1423
1424 typedef boost::iterator_range < Complex_simplex_iterator > Complex_simplex_range;
1425
1429 Complex_simplex_range complex_simplex_range() const {
1430 Complex_simplex_iterator end(this, true);
1431 if (empty()) {
1432 return Complex_simplex_range(end, end);
1433 } else {
1434 Complex_simplex_iterator begin(this);
1435 return Complex_simplex_range(begin, end);
1436 }
1437 }
1438
1440
1444 private:
1449 typename std::multimap<Vertex_handle, Simplex *>::iterator,
1451 Complex_blocker_around_vertex_iterator;
1452
1457 typename std::multimap<Vertex_handle, Simplex *>::const_iterator,
1458 const Blocker_handle>
1459 Const_complex_blocker_around_vertex_iterator;
1460
1461 typedef boost::iterator_range <Complex_blocker_around_vertex_iterator> Complex_blocker_around_vertex_range;
1462 typedef boost::iterator_range <Const_complex_blocker_around_vertex_iterator>
1463 Const_complex_blocker_around_vertex_range;
1464
1465 public:
1469 Complex_blocker_around_vertex_range blocker_range(Vertex_handle v) {
1470 auto begin = Complex_blocker_around_vertex_iterator(blocker_map_.lower_bound(v));
1471 auto end = Complex_blocker_around_vertex_iterator(blocker_map_.upper_bound(v));
1472 return Complex_blocker_around_vertex_range(begin, end);
1473 }
1474
1478 Const_complex_blocker_around_vertex_range const_blocker_range(Vertex_handle v) const {
1479 auto begin = Const_complex_blocker_around_vertex_iterator(blocker_map_.lower_bound(v));
1480 auto end = Const_complex_blocker_around_vertex_iterator(blocker_map_.upper_bound(v));
1481 return Const_complex_blocker_around_vertex_range(begin, end);
1482 }
1483
1484 private:
1489 typename std::multimap<Vertex_handle, Simplex *>::iterator,
1491 Complex_blocker_iterator;
1492
1497 typename std::multimap<Vertex_handle, Simplex *>::const_iterator,
1498 const Blocker_handle>
1499 Const_complex_blocker_iterator;
1500
1501 typedef boost::iterator_range <Complex_blocker_iterator> Complex_blocker_range;
1502 typedef boost::iterator_range <Const_complex_blocker_iterator> Const_complex_blocker_range;
1503
1504 public:
1508 Complex_blocker_range blocker_range() {
1509 auto begin = Complex_blocker_iterator(blocker_map_.begin(), blocker_map_.end());
1510 auto end = Complex_blocker_iterator(blocker_map_.end(), blocker_map_.end());
1511 return Complex_blocker_range(begin, end);
1512 }
1513
1517 Const_complex_blocker_range const_blocker_range() const {
1518 auto begin = Const_complex_blocker_iterator(blocker_map_.begin(), blocker_map_.end());
1519 auto end = Const_complex_blocker_iterator(blocker_map_.end(), blocker_map_.end());
1520 return Const_complex_blocker_range(begin, end);
1521 }
1522
1524
1526
1529 public:
1530 std::string to_string() const {
1531 std::ostringstream stream;
1532 stream << num_vertices() << " vertices:\n" << vertices_to_string() << std::endl;
1533 stream << num_edges() << " edges:\n" << edges_to_string() << std::endl;
1534 stream << num_blockers() << " blockers:\n" << blockers_to_string() << std::endl;
1535 return stream.str();
1536 }
1537
1538 std::string vertices_to_string() const {
1539 std::ostringstream stream;
1540 for (auto vertex : vertex_range()) {
1541 stream << "{" << (*this)[vertex].get_id() << "} ";
1542 }
1543 stream << std::endl;
1544 return stream.str();
1545 }
1546
1547 std::string edges_to_string() const {
1548 std::ostringstream stream;
1549 for (auto edge : edge_range())
1550 stream << "{" << (*this)[edge].first() << "," << (*this)[edge].second() << "} ";
1551 stream << std::endl;
1552 return stream.str();
1553 }
1554
1555 std::string blockers_to_string() const {
1556 std::ostringstream stream;
1557
1558 for (auto b : const_blocker_range())
1559 stream << *b << std::endl;
1560 return stream.str();
1561 }
1563};
1564
1570template<typename Complex, typename SimplexHandleIterator>
1571Complex make_complex_from_top_faces(SimplexHandleIterator simplices_begin, SimplexHandleIterator simplices_end,
1572 bool is_flag_complex = false) {
1573 // TODO(DS): use add_simplex instead! should be more efficient and more elegant :)
1574 typedef typename Complex::Simplex Simplex;
1575 std::vector<Simplex> simplices;
1576 for (auto top_face = simplices_begin; top_face != simplices_end; ++top_face) {
1577 auto subfaces_topface = subfaces(*top_face);
1578 simplices.insert(simplices.end(), subfaces_topface.begin(), subfaces_topface.end());
1579 }
1580 return Complex(simplices.begin(), simplices.end(), is_flag_complex);
1581}
1582
1583} // namespace skeleton_blocker
1584
1585namespace skbl = skeleton_blocker;
1586
1587} // namespace Gudhi
1588
1589#include "Skeleton_blocker_simplifiable_complex.h"
1590
1591#endif // SKELETON_BLOCKER_COMPLEX_H_
Iterator through the blockers of a vertex.
Definition: Skeleton_blockers_blockers_iterators.h:84
Iterator through the blockers of a vertex.
Definition: Skeleton_blockers_blockers_iterators.h:32
Iterator on the edges of a simplicial complex.
Definition: Skeleton_blockers_edges_iterators.h:88
Definition: Skeleton_blockers_simplices_iterators.h:43
Definition: Skeleton_blockers_simplices_iterators.h:304
Interface for a visitor of a simplicial complex.
Definition: Skeleton_blocker_complex_visitor.h:26
Abstract Simplicial Complex represented with a skeleton/blockers pair.
Definition: Skeleton_blocker_complex.h:51
virtual contractible_status is_contractible() const
Test if the complex is reducible using a strategy defined in the class (by default it tests if the co...
Definition: Skeleton_blocker_complex.h:1162
Complex_blocker_around_vertex_range blocker_range(Vertex_handle v)
Returns a range of the blockers of the complex passing through a vertex.
Definition: Skeleton_blocker_complex.h:1469
void remove_edge(Edge_handle edge)
Removes edge and its cofaces from the simplicial complex.
Definition: Skeleton_blocker_complex.h:613
Const_complex_blocker_around_vertex_range const_blocker_range(Vertex_handle v) const
Returns a range of the blockers of the complex passing through a vertex.
Definition: Skeleton_blocker_complex.h:1478
bool contains_vertices(const Simplex &sigma) const
Definition: Skeleton_blocker_complex.h:421
Edge_handle add_edge_without_blockers(Vertex_handle a, Vertex_handle b)
Adds an edge between vertices a and b without blockers.
Definition: Skeleton_blocker_complex.h:566
Complex_simplex_around_vertex_range star_simplex_range(Vertex_handle v) const
Returns a Complex_simplex_around_vertex_range over all the simplices around a vertex of the complex.
Definition: Skeleton_blocker_complex.h:1398
Link_complex link(const Simplex &simplex) const
Definition: Skeleton_blocker_complex.h:907
void keep_only_vertices()
The complex is reduced to its set of vertices. All the edges and blockers are removed.
Definition: Skeleton_blocker_complex.h:623
Complex_edge_around_vertex_range edge_range(Vertex_handle v) const
Returns a Complex_edge_range over all edges of the simplicial complex that passes through 'v'.
Definition: Skeleton_blocker_complex.h:1332
Complex_edge_range edge_range() const
Returns a Complex_edge_range over all edges of the simplicial complex.
Definition: Skeleton_blocker_complex.h:1316
Vertex_handle first_vertex(Edge_handle edge_handle) const
returns the first vertex of an edge
Definition: Skeleton_blocker_complex.h:512
Link_complex link(Vertex_handle v) const
Definition: Skeleton_blocker_complex.h:893
virtual Edge_handle remove_edge(Vertex_handle a, Vertex_handle b)
Removes an edge from the simplicial complex and all its cofaces.
Definition: Skeleton_blocker_complex.h:596
boost::iterator_range< Complex_simplex_around_vertex_iterator > Complex_simplex_around_vertex_range
Range over the simplices of the simplicial complex around a vertex. Methods .begin() and ....
Definition: Skeleton_blocker_complex.h:1393
void contract_edge(Edge_handle edge)
Definition: Skeleton_blocker_complex.h:1244
int degree(Vertex_handle local) const
return the graph degree of a vertex.
Definition: Skeleton_blocker_complex.h:468
Complex_coboundary_range coboundary_range(const Simplex &s) const
Returns a Complex_simplex_coboundary_iterator over the simplices of the coboundary of a simplex.
Definition: Skeleton_blocker_complex.h:1415
bool link_condition(Vertex_handle a, Vertex_handle b, bool ignore_popable_blockers=false) const
Definition: Skeleton_blocker_complex.h:1182
bool contains_blocker(const Simplex &s) const
Definition: Skeleton_blocker_complex.h:796
boost::optional< Edge_handle > operator[](const std::pair< Vertex_handle, Vertex_handle > &ab) const
return an edge handle if the two vertices forms an edge in the complex
Definition: Skeleton_blocker_complex.h:484
Vertex_handle second_vertex(Edge_handle edge_handle) const
returns the first vertex of an edge
Definition: Skeleton_blocker_complex.h:520
Complex_triangle_around_vertex_range triangle_range(Vertex_handle v) const
Range over triangles around a vertex of the simplicial complex. Methods .begin() and ....
Definition: Skeleton_blocker_complex.h:1358
void add_simplex(const Simplex &sigma)
add a simplex and all its faces.
Definition: Skeleton_blocker_simplifiable_complex.h:195
void remove_all_popable_blockers(Vertex_handle v)
Removes all the popable blockers of the complex passing through v and delete them....
Definition: Skeleton_blocker_simplifiable_complex.h:92
const Graph_edge & operator[](Edge_handle edge_handle) const
returns the stored node associated to an edge
Definition: Skeleton_blocker_complex.h:504
virtual bool contains(const Simplex &s) const
returns true iff the simplex s belongs to the simplicial complex.
Definition: Skeleton_blocker_complex.h:952
void remove_popable_blockers()
Definition: Skeleton_blocker_simplifiable_complex.h:44
void remove_blockers()
Remove all blockers, in other words, it expand the simplicial complex to the smallest flag complex th...
Definition: Skeleton_blocker_complex.h:742
int num_connected_components() const
returns the number of connected components in the graph of the 1-skeleton.
Definition: Skeleton_blocker_complex.h:1029
Graph_edge & operator[](Edge_handle edge_handle)
returns the stored node associated to an edge
Definition: Skeleton_blocker_complex.h:497
Blocker_handle add_blocker(const Simplex &blocker)
Adds the simplex to the set of blockers and returns a Blocker_handle toward it if was not present bef...
Definition: Skeleton_blocker_complex.h:669
bool contains_edges(const Simplex &sigma) const
Definition: Skeleton_blocker_complex.h:647
virtual void clear()
Definition: Skeleton_blocker_complex.h:311
Skeleton_blocker_simplex< Vertex_handle > Simplex
A ordered set of integers that represents a simplex.
Definition: Skeleton_blocker_complex.h:83
virtual boost::optional< Vertex_handle > get_address(Root_vertex_handle id) const
Given an Id return the address of the vertex having this Id in the complex.
Definition: Skeleton_blocker_complex.h:432
void remove_blocker(const Blocker_handle sigma)
Removes the simplex from the set of blockers.
Definition: Skeleton_blocker_complex.h:732
SkeletonBlockerDS::Graph_vertex Graph_vertex
The type of stored vertex node, specified by the template SkeletonBlockerDS.
Definition: Skeleton_blocker_complex.h:65
Vertex_handle add_vertex()
Adds a vertex to the simplicial complex and returns its Vertex_handle.
Definition: Skeleton_blocker_complex.h:372
void set_visitor(Visitor *other_visitor)
allows to change the visitor.
Definition: Skeleton_blocker_complex.h:327
void add_edge_without_blockers(Simplex s)
Adds all edges of s in the complex without adding blockers.
Definition: Skeleton_blocker_complex.h:585
Simplex get_vertices(Edge_handle edge_handle) const
returns the simplex made with the two vertices of the edge
Definition: Skeleton_blocker_complex.h:529
Simplex * Blocker_handle
Handle to a blocker of the complex.
Definition: Skeleton_blocker_complex.h:89
bool link_condition(Edge_handle e, bool ignore_popable_blockers=false) const
Definition: Skeleton_blocker_complex.h:1199
void remove_star(Vertex_handle v)
Definition: Skeleton_blocker_simplifiable_complex.h:120
Vertex_handle operator[](Root_vertex_handle global) const
Return a local Vertex_handle of a vertex given a global one.
Definition: Skeleton_blocker_complex.h:342
void delete_blocker(Blocker_handle sigma)
Definition: Skeleton_blocker_complex.h:770
Complex_blocker_range blocker_range()
Returns a range of the blockers of the complex.
Definition: Skeleton_blocker_complex.h:1508
bool is_popable_blocker(Blocker_handle sigma) const
Definition: Skeleton_blocker_simplifiable_complex.h:33
const Graph_vertex & operator[](Vertex_handle address) const
Return the vertex node associated to local Vertex_handle.
Definition: Skeleton_blocker_complex.h:362
bool operator==(const Skeleton_blocker_complex &other) const
Definition: Skeleton_blocker_complex.h:278
Skeleton_blocker_complex(size_t num_vertices_=0, Visitor *visitor_=NULL)
constructs a simplicial complex with a given number of vertices and a visitor.
Definition: Skeleton_blocker_complex.h:153
void add_edge(const Simplex &s)
Adds all edges of s in the complex.
Definition: Skeleton_blocker_complex.h:554
void remove_vertex(Vertex_handle address)
Remove a vertex from the simplicial complex.
Definition: Skeleton_blocker_complex.h:390
Complex_vertex_range vertex_range() const
Returns a Complex_vertex_range over all vertices of the complex.
Definition: Skeleton_blocker_complex.h:1282
Vertex_handle convert_handle_from_another_complex(const Skeleton_blocker_complex &other, Vertex_handle vh_in_other) const
Convert an address of a vertex of a complex to the address in the current complex.
Definition: Skeleton_blocker_complex.h:458
Edge_handle add_edge(Vertex_handle a, Vertex_handle b)
Adds an edge between vertices a and b.
Definition: Skeleton_blocker_complex.h:541
Link_complex link(Edge_handle edge) const
Definition: Skeleton_blocker_complex.h:900
SkeletonBlockerDS::Vertex_handle Vertex_handle
The type of an handle to a vertex of the complex.
Definition: Skeleton_blocker_complex.h:77
bool is_cone() const
Test if the complex is a cone.
Definition: Skeleton_blocker_complex.h:1040
bool contains_edge(Vertex_handle a, Vertex_handle b) const
Definition: Skeleton_blocker_complex.h:638
SkeletonBlockerDS::Graph_edge Graph_edge
The type of stored edge node, specified by the template SkeletonBlockerDS.
Definition: Skeleton_blocker_complex.h:70
Complex_triangle_range triangle_range() const
Range over triangles of the simplicial complex. Methods .begin() and .end() return a Triangle_around_...
Definition: Skeleton_blocker_complex.h:1372
Root_vertex_handle get_id(Vertex_handle local) const
Definition: Skeleton_blocker_complex.h:443
bool contains_blocker(const Blocker_handle s) const
Definition: Skeleton_blocker_complex.h:780
boost::graph_traits< Graph >::edge_descriptor Edge_handle
Handle to an edge of the complex.
Definition: Skeleton_blocker_complex.h:114
Complex_simplex_range complex_simplex_range() const
Returns a Complex_simplex_range over all the simplices of the complex.
Definition: Skeleton_blocker_complex.h:1429
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
boost::iterator_range< Complex_simplex_coboundary_iterator > Complex_coboundary_range
Range over the simplices of the coboundary of a simplex. Methods .begin() and .end() return a Complex...
Definition: Skeleton_blocker_complex.h:1410
virtual ~Skeleton_blocker_complex()
Definition: Skeleton_blocker_complex.h:302
Const_complex_blocker_range const_blocker_range() const
Returns a range of the blockers of the complex.
Definition: Skeleton_blocker_complex.h:1517
Skeleton_blocker_complex(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end, bool is_flag_complex=false, Visitor *visitor_=NULL)
Constructor with a list of simplices.
Definition: Skeleton_blocker_complex.h:171
Root_simplex_handle get_id(const Simplex &local_simplex) const
returns a simplex with vertices which are the id of vertices of the argument.
Definition: Skeleton_blocker_complex.h:940
Complex_neighbors_vertices_range vertex_range(Vertex_handle v) const
Returns a Complex_edge_range over all edges of the simplicial complex that passes trough v.
Definition: Skeleton_blocker_complex.h:1296
Graph_vertex & operator[](Vertex_handle address)
Return the vertex node associated to local Vertex_handle.
Definition: Skeleton_blocker_complex.h:352
Class that represents a geometric complex that can be simplified. The class allows access to points o...
Definition: Skeleton_blocker_geometric_complex.h:29
Abstract simplex used in Skeleton blockers data-structure.
Definition: Skeleton_blocker_simplex.h:38
T first_vertex() const
Definition: Skeleton_blocker_simplex.h:210
int dimension() const
Definition: Skeleton_blocker_simplex.h:197
void add_vertex(T v)
Definition: Skeleton_blocker_simplex.h:110
Simplicial subcomplex of a complex represented by a skeleton/blockers pair.
Definition: Skeleton_blocker_sub_complex.h:46
Iterator over the triangles that are adjacent to a vertex of the simplicial complex.
Definition: Skeleton_blockers_triangles_iterators.h:31
Iterator over the triangles of the simplicial complex.
Definition: Skeleton_blockers_triangles_iterators.h:106
Iterator on the vertices of a simplicial complex.
Definition: Skeleton_blockers_vertices_iterators.h:31
The type of edges that are stored the boost graph. An Edge must be Default Constructible and Equality...
Definition: SkeletonBlockerDS.h:91
Root_vertex_handle first() const
Returns the first vertex of the edge.
Root_vertex_handle second() const
Returns the second vertex of the edge.
The type of vertices that are stored the boost graph. A Vertex must be Default Constructible and Equa...
Definition: SkeletonBlockerDS.h:67
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