11 #ifndef SKELETON_BLOCKER_COMPLEX_H_
12 #define SKELETON_BLOCKER_COMPLEX_H_
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>
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>
43 namespace skeleton_blocker {
50 template<
class SkeletonBlockerDS>
53 template<
class ComplexType>
friend class Neighbors_vertices_iterator;
55 template<
class ComplexType>
friend class Edge_around_vertex_iterator;
78 typedef typename Root_vertex_handle::boost_vertex_handle boost_vertex_handle;
91 typedef typename Root_simplex_handle::Simplex_vertex_const_iterator Root_simplex_iterator;
92 typedef typename Simplex::Simplex_vertex_const_iterator Simplex_handle_iterator;
95 typedef typename boost::adjacency_list<boost::setS,
104 typedef typename boost::graph_traits<Graph>::vertex_iterator boost_vertex_iterator;
105 typedef typename boost::graph_traits<Graph>::edge_iterator boost_edge_iterator;
108 typedef typename boost::graph_traits<Graph>::adjacency_iterator boost_adjacency_iterator;
114 typedef typename boost::graph_traits<Graph>::edge_descriptor
Edge_handle;
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;
123 size_t num_vertices_;
124 size_t num_blockers_;
138 std::vector<boost_vertex_handle> degree_;
142 BlockerMap blocker_map_;
154 : visitor(visitor_) {
156 for (
size_t i = 0; i < num_vertices_; ++i) {
163 typedef Trie<Simplex> STrie;
170 template<
typename SimpleHandleOutputIterator>
172 bool is_flag_complex =
false,
Visitor* visitor_ = NULL)
176 add_vertices_and_edges(simplices_begin, simplices_end);
178 if (!is_flag_complex)
180 add_blockers(simplices_begin, simplices_end);
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;
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());
198 for (
const auto& e : edges)
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());
208 while (!simplices.empty()) {
209 simplices = tries.next_dimension_simplices();
210 for (
auto& sigma : simplices) {
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));
218 for (
auto x : common_positive_neighbors) {
220 bool all_edges_here =
true;
223 all_edges_here =
false;
226 if (!all_edges_here)
continue;
234 if (!tries.contains(sigma) && !blocks(sigma))
236 sigma.remove_vertex(x);
248 degree_ = copy.degree_;
249 skeleton = Graph(copy.skeleton);
250 num_vertices_ = copy.num_vertices_;
254 for (
auto blocker : copy.const_blocker_range()) {
264 degree_ = copy.degree_;
265 skeleton = Graph(copy.skeleton);
266 num_vertices_ = copy.num_vertices_;
270 for (
auto blocker : copy.const_blocker_range())
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;
284 if (!other.contains_vertex(v))
return false;
296 return !(*
this == other);
328 visitor = other_visitor;
354 0 <= address.vertex && address.vertex < boost::num_vertices(skeleton));
355 return skeleton[address.vertex];
364 0 <= address.vertex && address.vertex < boost::num_vertices(skeleton));
365 return skeleton[address.vertex];
375 (*this)[address].activate();
379 degree_.push_back(0);
381 visitor->on_add_vertex(address);
391 assert(contains_vertex(address));
393 boost::clear_vertex(address.vertex, skeleton);
394 (*this)[address].deactivate();
396 degree_[address.vertex] = -1;
398 visitor->on_remove_vertex(address);
405 if (u.vertex < 0 || u.vertex >= num_vertices)
407 return (*
this)[u].is_active();
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();
422 for (
auto vertex : sigma)
423 if (!contains_vertex(vertex))
433 boost::optional<Vertex_handle> res;
434 int num_vertices = boost::num_vertices(skeleton);
435 if (
id.vertex < num_vertices)
444 assert(0 <= local.vertex && local.vertex < boost::num_vertices(skeleton));
445 return (*
this)[local].get_id();
461 assert(vh_in_current_complex);
462 return *vh_in_current_complex;
469 assert(0 <= local.vertex && local.vertex < boost::num_vertices(skeleton));
470 return degree_[local.vertex];
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;
498 return skeleton[edge_handle];
505 return skeleton[edge_handle];
513 return static_cast<Vertex_handle> (source(edge_handle, skeleton));
521 return static_cast<Vertex_handle> (target(edge_handle, skeleton));
530 auto edge((*
this)[edge_handle]);
531 return Simplex((*
this)[edge.first()], (*
this)[edge.second()]);
545 return *((*this)[std::make_pair(a, b)]);
547 add_blockers_after_simplex_insertion(
Simplex(a, b));
555 for (
auto i = s.begin(); i != s.end(); ++i)
556 for (
auto j = i; ++j != s.end(); )
567 assert(contains_vertex(a) && contains_vertex(b));
570 auto edge_handle((*
this)[std::make_pair(a, b)]);
572 edge_handle = boost::add_edge(a.vertex, b.vertex, skeleton).first;
577 visitor->on_add_edge_without_blockers(a, b);
586 for (
auto i = s.begin(); i != s.end(); ++i) {
587 for (
auto j = i; ++j != s.end(); )
599 tie(edge, found) = boost::edge(a.vertex, b.vertex, skeleton);
602 visitor->on_remove_edge(a, b);
603 boost::remove_edge(a.vertex, b.vertex, skeleton);
627 while (this->
degree(u) > 0) {
628 Vertex_handle v(*(adjacent_vertices(u.vertex, this->skeleton).first));
640 return boost::edge(a.vertex, b.vertex, skeleton).second;
648 for (
auto i = sigma.begin(); i != sigma.end(); ++i) {
649 if (!contains_vertex(*i))
651 for (
auto j = i; ++j != sigma.end();) {
675 visitor->on_add_blocker(blocker);
678 auto vertex = blocker_pt->begin();
679 while (vertex != blocker_pt->end()) {
680 blocker_map_.insert(BlockerPair(*vertex, blocker_pt));
697 visitor->on_add_blocker(*blocker);
699 auto vertex = blocker->begin();
700 while (vertex != blocker->end()) {
701 blocker_map_.insert(BlockerPair(*vertex, blocker));
712 Complex_blocker_around_vertex_iterator blocker;
715 if (*blocker == sigma)
718 if (*blocker != sigma) {
720 <<
"bug ((*blocker).second == sigma) ie try to remove a blocker not present\n";
723 blocker_map_.erase(blocker.current_position());
733 for (
auto vertex : *sigma)
734 remove_blocker(sigma, vertex);
744 while (!blocker_map_.empty()) {
748 blocker_map_.clear();
758 void remove_blocker(
const Simplex& sigma) {
760 for (
auto vertex : sigma)
761 remove_blocker(sigma, vertex);
772 visitor->on_delete_blocker(sigma);
773 remove_blocker(sigma);
814 bool blocks(
const Simplex & sigma)
const {
817 if (sigma.contains(*blocker))
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;
835 if (keep_only_superior) {
836 if (value > v.vertex) {
854 bool keep_only_superior =
false)
const {
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();
860 keep_neighbours(*alpha_vertex, res, keep_only_superior);
869 bool keep_only_superior =
false)
const {
871 add_neighbours(v, nv, keep_only_superior);
872 res.intersection(nv);
881 bool keep_only_superior =
false)
const {
883 add_neighbours(v, nv, keep_only_superior);
888 typedef Skeleton_blocker_link_complex<Skeleton_blocker_complex> Link_complex;
921 boost::optional<Simplex> res;
925 for (
auto i = s.begin(); i != s.end(); ++i) {
926 boost::optional<Vertex_handle> address =
get_address(*i);
942 for (
auto x = local_simplex.begin(); x != local_simplex.end(); ++x) {
945 return global_simplex;
966 return num_vertices() == 0;
972 int num_vertices()
const {
974 return num_vertices_;
983 int num_edges()
const {
984 return boost::num_edges(skeleton);
987 int num_triangles()
const {
989 return std::distance(triangles.begin(), triangles.end());
995 size_t num_simplices()
const {
997 return std::distance(simplices.begin(), simplices.end());
1003 size_t num_simplices(
int dimension)
const {
1007 if (s.dimension() == dimension)
1015 size_t num_blockers()
const {
1016 return num_blockers_;
1022 bool complete()
const {
1023 return (num_vertices() * (num_vertices() - 1)) / 2 == num_edges();
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;
1041 if (num_vertices() == 0)
1043 if (num_vertices() == 1)
1047 if (blocker_map_.find(vi) == blocker_map_.end()) {
1050 if (degree_[vi.vertex] == num_vertices() - 1)
1101 void update_blockers_after_remove_star_of_vertex_or_edge(
const Simplex& simplex_to_be_removed);
1127 void add_blockers_after_simplex_insertion(
Simplex s);
1132 void remove_blocker_containing_simplex(
const Simplex& sigma);
1137 void remove_blocker_include_in_simplex(
const Simplex& sigma);
1140 enum simplifiable_status {
1141 NOT_HOMOTOPY_EQ, MAYBE_HOMOTOPY_EQ, HOMOTOPY_EQ
1144 simplifiable_status is_remove_star_homotopy_preserving(
const Simplex& simplex) {
1148 return MAYBE_HOMOTOPY_EQ;
1151 enum contractible_status {
1152 NOT_CONTRACTIBLE, MAYBE_CONTRACTIBLE, CONTRACTIBLE
1166 return CONTRACTIBLE;
1168 return MAYBE_CONTRACTIBLE;
1186 if (blocker->contains(b)) {
1259 std::set<Simplex>& blockers_to_add);
1279 typedef boost::iterator_range<Complex_vertex_iterator> Complex_vertex_range;
1287 return Complex_vertex_range(begin, end);
1290 typedef Neighbors_vertices_iterator<Skeleton_blocker_complex> Complex_neighbors_vertices_iterator;
1293 typedef boost::iterator_range<Complex_neighbors_vertices_iterator> Complex_neighbors_vertices_range;
1299 auto begin = Complex_neighbors_vertices_iterator(
this, v);
1300 auto end = Complex_neighbors_vertices_iterator(
this, v, 0);
1301 return Complex_neighbors_vertices_range(begin, end);
1313 typedef boost::iterator_range<Complex_edge_iterator> Complex_edge_range;
1321 return Complex_edge_range(begin, end);
1325 typedef Edge_around_vertex_iterator<Skeleton_blocker_complex> Complex_edge_around_vertex_iterator;
1328 typedef boost::iterator_range <Complex_edge_around_vertex_iterator> Complex_edge_around_vertex_range;
1335 auto begin = Complex_edge_around_vertex_iterator(
this, v);
1336 auto end = Complex_edge_around_vertex_iterator(
this, v, 0);
1337 return Complex_edge_around_vertex_range(begin, end);
1351 Superior_triangle_around_vertex_iterator;
1352 typedef boost::iterator_range < Triangle_around_vertex_iterator<Skeleton_blocker_complex, Link> >
1353 Complex_triangle_around_vertex_range;
1363 return Complex_triangle_around_vertex_range(begin, end);
1366 typedef boost::iterator_range<Triangle_iterator<Skeleton_blocker_complex> > Complex_triangle_range;
1377 return Complex_triangle_range(end, end);
1380 return Complex_triangle_range(begin, end);
1401 assert(contains_vertex(v));
1424 typedef Simplex_iterator<Skeleton_blocker_complex> Complex_simplex_iterator;
1426 typedef boost::iterator_range < Complex_simplex_iterator > Complex_simplex_range;
1432 Complex_simplex_iterator end(
this,
true);
1434 return Complex_simplex_range(end, end);
1436 Complex_simplex_iterator begin(
this);
1437 return Complex_simplex_range(begin, end);
1451 typename std::multimap<Vertex_handle, Simplex *>::iterator,
1453 Complex_blocker_around_vertex_iterator;
1459 typename std::multimap<Vertex_handle, Simplex *>::const_iterator,
1461 Const_complex_blocker_around_vertex_iterator;
1463 typedef boost::iterator_range <Complex_blocker_around_vertex_iterator> Complex_blocker_around_vertex_range;
1464 typedef boost::iterator_range <Const_complex_blocker_around_vertex_iterator>
1465 Const_complex_blocker_around_vertex_range;
1474 return Complex_blocker_around_vertex_range(begin, end);
1483 return Const_complex_blocker_around_vertex_range(begin, end);
1491 typename std::multimap<Vertex_handle, Simplex *>::iterator,
1493 Complex_blocker_iterator;
1499 typename std::multimap<Vertex_handle, Simplex *>::const_iterator,
1501 Const_complex_blocker_iterator;
1503 typedef boost::iterator_range <Complex_blocker_iterator> Complex_blocker_range;
1504 typedef boost::iterator_range <Const_complex_blocker_iterator> Const_complex_blocker_range;
1513 return Complex_blocker_range(begin, end);
1522 return Const_complex_blocker_range(begin, end);
1532 std::string to_string()
const {
1533 std::ostringstream stream;
1534 stream << num_vertices() <<
" vertices:\n" << vertices_to_string() << std::endl;
1535 stream << num_edges() <<
" edges:\n" << edges_to_string() << std::endl;
1536 stream << num_blockers() <<
" blockers:\n" << blockers_to_string() << std::endl;
1537 return stream.str();
1540 std::string vertices_to_string()
const {
1541 std::ostringstream stream;
1543 stream <<
"{" << (*this)[vertex].get_id() <<
"} ";
1545 stream << std::endl;
1546 return stream.str();
1549 std::string edges_to_string()
const {
1550 std::ostringstream stream;
1552 stream <<
"{" << (*this)[edge].first() <<
"," << (*this)[edge].second() <<
"} ";
1553 stream << std::endl;
1554 return stream.str();
1557 std::string blockers_to_string()
const {
1558 std::ostringstream stream;
1561 stream << *b << std::endl;
1562 return stream.str();
1572 template<
typename Complex,
typename SimplexHandleIterator>
1573 Complex make_complex_from_top_faces(SimplexHandleIterator simplices_begin, SimplexHandleIterator simplices_end,
1574 bool is_flag_complex =
false) {
1576 typedef typename Complex::Simplex Simplex;
1577 std::vector<Simplex> simplices;
1578 for (
auto top_face = simplices_begin; top_face != simplices_end; ++top_face) {
1579 auto subfaces_topface = subfaces(*top_face);
1580 simplices.insert(simplices.end(), subfaces_topface.begin(), subfaces_topface.end());
1582 return Complex(simplices.begin(), simplices.end(), is_flag_complex);
1587 namespace skbl = skeleton_blocker;
1591 #include "Skeleton_blocker_simplifiable_complex.h"
1593 #endif // SKELETON_BLOCKER_COMPLEX_H_