From ff6ad8b959f6c20380f3d68ebb1bbbf1224adcfd Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 13 Oct 2015 15:34:28 +0000 Subject: Manual merge of skb_simplex_insertion after last trunk big modifications on Skbl git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/skb_simplex_insertion_merge@855 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: d7f7721e2963de439a28040196423d4c0df07d3f --- .../include/gudhi/Skeleton_blocker.h | 33 ++-- .../Skeleton_blocker_complex_visitor.h | 10 +- .../Skeleton_blocker_link_superior.h | 6 +- .../Skeleton_blocker/Skeleton_blocker_off_io.h | 8 +- .../Skeleton_blocker_sub_complex.h | 24 +-- .../include/gudhi/Skeleton_blocker/internal/Trie.h | 34 ++-- .../Skeleton_blockers_blockers_iterators.h | 4 +- .../Skeleton_blockers_simplices_iterators.h | 109 +++++++++++-- .../Skeleton_blockers_triangles_iterators.h | 18 +-- .../include/gudhi/Skeleton_blocker_complex.h | 176 +++++++++++++-------- .../gudhi/Skeleton_blocker_geometric_complex.h | 10 +- .../include/gudhi/Skeleton_blocker_link_complex.h | 53 +++---- .../gudhi/Skeleton_blocker_simplifiable_complex.h | 92 ++++++----- 13 files changed, 361 insertions(+), 216 deletions(-) (limited to 'src/Skeleton_blocker/include/gudhi') diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index 792a7994..e1f53f48 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h @@ -129,7 +129,7 @@ of a simplicial complex. \code{.cpp} typedef Skeleton_blocker_complex Complex; typedef Complex::Vertex_handle Vertex_handle; - typedef Complex::Simplex_handle Simplex; + typedef Complex::Simplex Simplex; const int n = 15; @@ -139,8 +139,7 @@ of a simplicial complex. complex.add_vertex(); for(int i=0;i simplices; + std::vector simplices; //add 4 triangles of a tetrahedron 0123 - simplices.push_back(Simplex_handle(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3))); - simplices.push_back(Simplex_handle(Vertex_handle(3),Vertex_handle(0),Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(3),Vertex_handle(0),Vertex_handle(1))); + simplices.push_back(Simplex(Vertex_handle(0),Vertex_handle(1),Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(1),Vertex_handle(2),Vertex_handle(3))); + simplices.push_back(Simplex(Vertex_handle(3),Vertex_handle(0),Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(3),Vertex_handle(0),Vertex_handle(1))); Complex complex; //get complex from top faces make_complex_from_top_faces(complex,simplices.begin(),simplices.end()); std::cout << "Simplices:"<(parent_complex, alpha_parent_adress, true) { } diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h index ec000986..ad2d2f85 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h @@ -61,7 +61,7 @@ class Skeleton_blocker_off_flag_visitor_reader { if (!load_only_points_) { for (size_t i = 0; i < face.size(); ++i) for (size_t j = i + 1; j < face.size(); ++j) { - complex_.add_edge(Vertex_handle(face[i]), Vertex_handle(face[j])); + complex_.add_edge_without_blockers(Vertex_handle(face[i]), Vertex_handle(face[j])); } } } @@ -76,12 +76,12 @@ template class Skeleton_blocker_off_visitor_reader { Complex& complex_; typedef typename Complex::Vertex_handle Vertex_handle; - typedef typename Complex::Simplex_handle Simplex_handle; + typedef typename Complex::Simplex Simplex; typedef typename Complex::Point Point; const bool load_only_points_; std::vector points_; - std::vector maximal_faces_; + std::vector maximal_faces_; public: explicit Skeleton_blocker_off_visitor_reader(Complex& complex, bool load_only_points = false) : @@ -99,7 +99,7 @@ class Skeleton_blocker_off_visitor_reader { void maximal_face(const std::vector& face) { if (!load_only_points_) { - Simplex_handle s; + Simplex s; for (auto x : face) s.add_vertex(Vertex_handle(x)); maximal_faces_.emplace_back(s); diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h index b33b9606..50a83345 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h @@ -66,12 +66,12 @@ class Skeleton_blocker_sub_complex : public ComplexType { public: using ComplexType::add_vertex; - using ComplexType::add_edge; + using ComplexType::add_edge_without_blockers; using ComplexType::add_blocker; typedef typename ComplexType::Vertex_handle Vertex_handle; typedef typename ComplexType::Root_vertex_handle Root_vertex_handle; - typedef typename ComplexType::Simplex_handle Simplex_handle; + typedef typename ComplexType::Simplex Simplex; typedef typename ComplexType::Root_simplex_handle Root_simplex_handle; protected: @@ -109,11 +109,11 @@ class Skeleton_blocker_sub_complex : public ComplexType { * It assumes that both vertices corresponding to v1_root and v2_root are present * in the sub-complex. */ - void add_edge(Root_vertex_handle v1_root, Root_vertex_handle v2_root) { + void add_edge_without_blockers(Root_vertex_handle v1_root, Root_vertex_handle v2_root) { auto v1_sub(this->get_address(v1_root)); auto v2_sub(this->get_address(v2_root)); assert(v1_sub && v2_sub); - this->ComplexType::add_edge(*v1_sub, *v2_sub); + this->ComplexType::add_edge_without_blockers(*v1_sub, *v2_sub); } /** @@ -124,7 +124,7 @@ class Skeleton_blocker_sub_complex : public ComplexType { void add_blocker(const Root_simplex_handle& blocker_root) { auto blocker_sub = this->get_address(blocker_root); assert(blocker_sub); - this->add_blocker(new Simplex_handle(*blocker_sub)); + this->add_blocker(new Simplex(*blocker_sub)); } public: @@ -133,7 +133,7 @@ class Skeleton_blocker_sub_complex : public ComplexType { * vertices of 'simplex'. */ void make_restricted_complex(const ComplexType & parent_complex, - const Simplex_handle& simplex) { + const Simplex& simplex) { this->clear(); // add vertices to the sub complex for (auto x : simplex) { @@ -145,11 +145,11 @@ class Skeleton_blocker_sub_complex : public ComplexType { // add edges to the sub complex for (auto x : simplex) { // x_neigh is the neighbor of x intersected with vertices_simplex - Simplex_handle x_neigh; + Simplex x_neigh; parent_complex.add_neighbours(x, x_neigh, true); x_neigh.intersection(simplex); for (auto y : x_neigh) { - this->add_edge(parent_complex[x].get_id(), parent_complex[y].get_id()); + this->add_edge_without_blockers(parent_complex[x].get_id(), parent_complex[y].get_id()); } } @@ -158,9 +158,9 @@ class Skeleton_blocker_sub_complex : public ComplexType { // check if it is the first time we encounter the blocker if (simplex.contains(*blocker)) { Root_simplex_handle blocker_root(parent_complex.get_id(*(blocker))); - Simplex_handle blocker_restr( + Simplex blocker_restr( *(this->get_simplex_address(blocker_root))); - this->add_blocker(new Simplex_handle(blocker_restr)); + this->add_blocker(new Simplex(blocker_restr)); } } } @@ -188,7 +188,7 @@ class Skeleton_blocker_sub_complex : public ComplexType { // * Allocates a simplex in L corresponding to the simplex s in K // * with its local adresses and returns an AddressSimplex. // */ - // boost::optional get_address(const Root_simplex_handle & s) const; + // boost::optional get_address(const Root_simplex_handle & s) const; // private: /** @@ -220,7 +220,7 @@ bool proper_face_in_union( // we test that all vertices of 'addresses_sigma_in_link' but 'vertex_to_be_ignored' // are in link1 if it is the case we construct the corresponding simplex bool vertices_sigma_are_in_link = true; - typename ComplexType::Simplex_handle sigma_in_link; + typename ComplexType::Simplex sigma_in_link; for (int i = 0; i < addresses_sigma_in_link.size(); ++i) { if (i != vertex_to_be_ignored) { if (!addresses_sigma_in_link[i]) { diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h index aa0416ef..499980c4 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h @@ -36,7 +36,7 @@ namespace skbl { template struct Trie { - typedef SimplexHandle Simplex_handle; + typedef SimplexHandle Simplex; typedef typename SimplexHandle::Vertex_handle Vertex_handle; Vertex_handle v; @@ -64,7 +64,7 @@ struct Trie { } } - typedef typename Simplex_handle::Simplex_vertex_const_iterator Simplex_vertex_const_iterator; + typedef typename Simplex::Simplex_vertex_const_iterator Simplex_vertex_const_iterator; Trie* make_trie(Simplex_vertex_const_iterator s_it, Simplex_vertex_const_iterator s_end) { if (s_it == s_end) { @@ -97,7 +97,7 @@ struct Trie { return; } - void maximal_faces_helper(std::vector& res) const { + void maximal_faces_helper(std::vector& res) const { if (is_leaf()) res.push_back(simplex()); else for (auto child : childs) @@ -108,14 +108,14 @@ struct Trie { /** * adds the simplex to the trie */ - void add_simplex(const Simplex_handle& s) { + void add_simplex(const Simplex& s) { if (s.empty()) return; assert(v == s.first_vertex()); add_simplex_helper(s.begin(), s.end()); } - std::vector maximal_faces() const { - std::vector res; + std::vector maximal_faces() const { + std::vector res; maximal_faces_helper(res); return res; } @@ -123,14 +123,14 @@ struct Trie { /** * Goes to the root in the trie to consitute simplex */ - void add_vertices_up_to_the_root(Simplex_handle& res) const { + void add_vertices_up_to_the_root(Simplex& res) const { res.add_vertex(v); if (parent_) parent_->add_vertices_up_to_the_root(res); } - Simplex_handle simplex() const { - Simplex_handle res; + Simplex simplex() const { + Simplex res; add_vertices_up_to_the_root(res); return res; } @@ -156,7 +156,7 @@ struct Trie { /** * true iff the simplex corresponds to one node in the trie */ - bool contains(const Simplex_handle& s) const { + bool contains(const Simplex& s) const { Trie const* current = this; if (s.empty()) return true; if (current->v != s.first_vertex()) return false; @@ -196,9 +196,9 @@ struct Trie { template struct Tries { typedef typename SimplexHandle::Vertex_handle Vertex_handle; - typedef SimplexHandle Simplex_handle; + typedef SimplexHandle Simplex; - typedef Trie STrie; + typedef Trie STrie; template Tries(unsigned num_vertices, SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) : @@ -218,14 +218,14 @@ struct Tries { // return a simplex that consists in all u such uv is an edge and u>v - Simplex_handle positive_neighbors(Vertex_handle v) const { - Simplex_handle res; + Simplex positive_neighbors(Vertex_handle v) const { + Simplex res; for (auto child : cofaces_[v]->childs) res.add_vertex(child->v); return res; } - bool contains(const Simplex_handle& s) const { + bool contains(const Simplex& s) const { auto first_v = s.first_vertex(); return cofaces_[first_v]->contains(s); } @@ -238,8 +238,8 @@ struct Tries { // init_next_dimension must be called first - std::vector next_dimension_simplices() const { - std::vector res; + std::vector next_dimension_simplices() const { + std::vector res; while (!to_see_.empty() && to_see_.front()->simplex().dimension() == current_dimension_) { res.emplace_back(to_see_.front()->simplex()); for (auto child : to_see_.front()->childs) diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h index 56a20a24..4a437ac6 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h @@ -31,7 +31,7 @@ namespace skbl { /** * @brief Iterator through the blockers of a vertex. */ -// ReturnType = const Simplex_handle* or Simplex_handle* +// ReturnType = const Simplex* or Simplex* // MapIteratorType = BlockerMapConstIterator or BlockerMapIterator template @@ -83,7 +83,7 @@ ReturnType /** * @brief Iterator through the blockers of a vertex */ -// ReturnType = const Simplex_handle* or Simplex_handle* +// ReturnType = const Simplex* or Simplex* // MapIteratorType = BlockerMapConstIterator or BlockerMapIterator template diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h index 4d71b3f5..ce565166 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h @@ -48,20 +48,20 @@ namespace skbl { template class Simplex_around_vertex_iterator : public boost::iterator_facade < Simplex_around_vertex_iterator -, typename SkeletonBlockerComplex::Simplex_handle +, typename SkeletonBlockerComplex::Simplex , boost::forward_traversal_tag -, typename SkeletonBlockerComplex::Simplex_handle +, typename SkeletonBlockerComplex::Simplex > { friend class boost::iterator_core_access; typedef SkeletonBlockerComplex Complex; typedef typename Complex::Vertex_handle Vertex_handle; typedef typename Complex::Edge_handle Edge_handle; - typedef typename Complex::Simplex_handle Simplex_handle; + typedef typename Complex::Simplex Simplex; // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion typedef typename Link::Vertex_handle Link_vertex_handle; - typedef typename Gudhi::skbl::Trie Trie; + typedef typename Gudhi::skbl::Trie Trie; private: const Complex* complex; @@ -120,7 +120,7 @@ public boost::iterator_facade < Simplex_around_vertex_iteratorvertex_range(link_vh)) { if (link_vh < nv) { - Simplex_handle simplex_node_plus_nv(res->simplex()); + Simplex simplex_node_plus_nv(res->simplex()); simplex_node_plus_nv.add_vertex(parent_vertex(nv)); if (complex->contains(simplex_node_plus_nv)) { res->add_child(build_trie(nv, res)); @@ -176,13 +176,13 @@ public boost::iterator_facade < Simplex_around_vertex_iteratorsimplex(); } - Simplex_handle get_trie_address() const { + Simplex get_trie_address() const { assert(!nodes_to_be_seen.empty()); return nodes_to_be_seen.front(); } @@ -200,9 +200,9 @@ public boost::iterator_facade < Simplex_around_vertex_iterator class Simplex_iterator : public boost::iterator_facade < Simplex_iterator -, typename SkeletonBlockerComplex::Simplex_handle +, typename SkeletonBlockerComplex::Simplex , boost::forward_traversal_tag -, typename SkeletonBlockerComplex::Simplex_handle +, typename SkeletonBlockerComplex::Simplex > { typedef Skeleton_blocker_link_superior Link; @@ -213,7 +213,7 @@ public boost::iterator_facade < Simplex_iterator typedef SkeletonBlockerComplex Complex; typedef typename Complex::Vertex_handle Vertex_handle; typedef typename Complex::Edge_handle Edge_handle; - typedef typename Complex::Simplex_handle Simplex_handle; + typedef typename Complex::Simplex Simplex; typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator; typedef typename Link::Vertex_handle Link_vertex_handle; @@ -290,7 +290,7 @@ public boost::iterator_facade < Simplex_iterator } } - Simplex_handle dereference() const { + Simplex dereference() const { return current_simplex_around_current_vertex_.dereference(); } @@ -304,6 +304,93 @@ public boost::iterator_facade < Simplex_iterator } }; +/** + * Iterator through the maximal faces of the coboundary of a simplex. + */ +template +class Simplex_coboundary_iterator : +public boost::iterator_facade < Simplex_coboundary_iterator +, typename SkeletonBlockerComplex::Simplex, boost::forward_traversal_tag, typename SkeletonBlockerComplex::Simplex> { + friend class boost::iterator_core_access; + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Edge_handle Edge_handle; + typedef typename Complex::Simplex Simplex; + typedef typename Complex::Complex_vertex_iterator Complex_vertex_iterator; + + // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion + typedef typename Link::Vertex_handle Link_vertex_handle; + + private: + const Complex* complex; + const Simplex& sigma; + std::shared_ptr link; + Complex_vertex_iterator current_vertex; + Complex_vertex_iterator link_vertex_end; + + public: + Simplex_coboundary_iterator() : complex(0) {} + + Simplex_coboundary_iterator(const Complex* complex_, const Simplex& sigma_) : + complex(complex_), + sigma(sigma_), + //need only vertices of the link hence the true flag + link(new Link(*complex_, sigma_, false, true)) { + auto link_vertex_range = link->vertex_range(); + current_vertex = link_vertex_range.begin(); + link_vertex_end = link_vertex_range.end(); + } + + Simplex_coboundary_iterator(const Simplex_coboundary_iterator& other) : + complex(other.complex), + sigma(other.sigma), + link(other.link), + current_vertex(other.current_vertex), + link_vertex_end(other.link_vertex_end) { } + + // returns an iterator to the end + Simplex_coboundary_iterator(const Complex* complex_,const Simplex& sigma_, bool end) : + complex(complex_), + sigma(sigma_) { + // to represent an end iterator without having to build a useless link, we use + // the convection that link is not initialized. + } + + private: + Vertex_handle parent_vertex(Link_vertex_handle link_vh) const { + return complex->convert_handle_from_another_complex(*link, link_vh); + } + +public: + friend std::ostream& operator<<(std::ostream& stream, const Simplex_coboundary_iterator& sci) { + return stream; + } + + // assume that iterator points to the same complex and comes from the same simplex + bool equal(const Simplex_coboundary_iterator& other) const { + assert(complex == other.complex && sigma == other.sigma); + if(is_end()) return other.is_end(); + if(other.is_end()) return is_end(); + return *current_vertex == *(other.current_vertex); + } + + void increment() { + ++current_vertex; + } + + Simplex dereference() const { + Simplex res(sigma); + res.add_vertex(parent_vertex(*current_vertex)); + return res; + } + +private: + bool is_end() const { + return !link || current_vertex == link_vertex_end; + } +}; + + } // namespace skbl } // namespace Gudhi diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h index 28f5805d..116023d7 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h @@ -37,15 +37,15 @@ namespace skbl { template class Triangle_around_vertex_iterator : public boost::iterator_facade < Triangle_around_vertex_iterator -, typename Complex::Simplex_handle const +, typename Complex::Simplex const , boost::forward_traversal_tag -, typename Complex::Simplex_handle const> { +, typename Complex::Simplex const> { friend class boost::iterator_core_access; template friend class Triangle_iterator; private: typedef typename LinkType::Vertex_handle Vertex_handle; typedef typename LinkType::Root_vertex_handle Root_vertex_handle; - typedef typename LinkType::Simplex_handle Simplex_handle; + typedef typename LinkType::Simplex Simplex; typedef typename Complex::Complex_edge_iterator Complex_edge_iterator_; const Complex* complex_; @@ -87,10 +87,10 @@ class Triangle_around_vertex_iterator : public boost::iterator_facade return (complex_ == other.complex_) && ((finished() && other.finished()) || current_edge_ == other.current_edge_); } - Simplex_handle dereference() const { + Simplex dereference() const { Root_vertex_handle v1 = (*link_)[*current_edge_].first(); Root_vertex_handle v2 = (*link_)[*current_edge_].second(); - return Simplex_handle(v_, *(complex_->get_address(v1)), *(complex_->get_address(v2))); + return Simplex(v_, *(complex_->get_address(v1)), *(complex_->get_address(v2))); } void increment() { @@ -112,14 +112,14 @@ class Triangle_around_vertex_iterator : public boost::iterator_facade template class Triangle_iterator : public boost::iterator_facade< Triangle_iterator , -typename SkeletonBlockerComplex::Simplex_handle const +typename SkeletonBlockerComplex::Simplex const , boost::forward_traversal_tag -, typename SkeletonBlockerComplex::Simplex_handle const> { +, typename SkeletonBlockerComplex::Simplex const> { friend class boost::iterator_core_access; private: typedef typename SkeletonBlockerComplex::Vertex_handle Vertex_handle; typedef typename SkeletonBlockerComplex::Root_vertex_handle Root_vertex_handle; - typedef typename SkeletonBlockerComplex::Simplex_handle Simplex_handle; + typedef typename SkeletonBlockerComplex::Simplex Simplex; typedef typename SkeletonBlockerComplex::Superior_triangle_around_vertex_iterator STAVI; typedef typename SkeletonBlockerComplex::Complex_vertex_iterator Complex_vertex_iterator; @@ -175,7 +175,7 @@ typename SkeletonBlockerComplex::Simplex_handle const current_vertex_ == other.current_vertex_ && current_triangle_ == other.current_triangle_)); } - Simplex_handle dereference() const { + Simplex dereference() const { return *current_triangle_; } diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h index 07f371a2..78384abf 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h @@ -94,16 +94,16 @@ class Skeleton_blocker_complex { /** * @brief A ordered set of integers that represents a simplex. */ - typedef Skeleton_blocker_simplex Simplex_handle; + typedef Skeleton_blocker_simplex Simplex; typedef Skeleton_blocker_simplex Root_simplex_handle; /** * @brief Handle to a blocker of the complex. */ - typedef Simplex_handle* Blocker_handle; + typedef Simplex* Blocker_handle; typedef typename Root_simplex_handle::Simplex_vertex_const_iterator Root_simplex_iterator; - typedef typename Simplex_handle::Simplex_vertex_const_iterator Simplex_handle_iterator; + typedef typename Simplex::Simplex_vertex_const_iterator Simplex_handle_iterator; protected: typedef typename boost::adjacency_list::edge_descriptor Edge_handle; protected: - typedef std::multimap BlockerMap; - typedef typename std::multimap::value_type BlockerPair; - typedef typename std::multimap::iterator BlockerMapIterator; - typedef typename std::multimap::const_iterator BlockerMapConstIterator; + typedef std::multimap BlockerMap; + typedef typename std::multimap::value_type BlockerPair; + typedef typename std::multimap::iterator BlockerMapIterator; + typedef typename std::multimap::const_iterator BlockerMapConstIterator; protected: int num_vertices_; @@ -174,7 +174,7 @@ class Skeleton_blocker_complex { private: // typedef Trie> STrie; - typedef Trie STrie; + typedef Trie STrie; public: /** @@ -207,12 +207,12 @@ class Skeleton_blocker_complex { while (num_vertex-- >= 0) add_vertex(); for (const auto& e : edges) - add_edge(e.first, e.second); + add_edge_without_blockers(e.first, e.second); } template void add_blockers(SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) { - Tries tries(num_vertices(), simplex_begin, simplex_end); + Tries tries(num_vertices(), simplex_begin, simplex_end); tries.init_next_dimension(); auto simplices(tries.next_dimension_simplices()); @@ -221,7 +221,7 @@ class Skeleton_blocker_complex { for (auto& sigma : simplices) { // common_positive_neighbors is the set of vertices u such that // for all s in sigma, us is an edge and u>s - Simplex_handle common_positive_neighbors(tries.positive_neighbors(sigma.last_vertex())); + Simplex common_positive_neighbors(tries.positive_neighbors(sigma.last_vertex())); for (auto sigma_it = sigma.rbegin(); sigma_it != sigma.rend(); ++sigma_it) if (sigma_it != sigma.rbegin()) common_positive_neighbors.intersection(tries.positive_neighbors(*sigma_it)); @@ -427,7 +427,7 @@ class Skeleton_blocker_complex { * @return true iff the simplicial complex contains all vertices * of simplex sigma */ - bool contains_vertices(const Simplex_handle & sigma) const { + bool contains_vertices(const Simplex & sigma) const { for (auto vertex : sigma) if (!contains_vertex(vertex)) return false; @@ -535,41 +535,68 @@ class Skeleton_blocker_complex { * @details it assumes that the edge is present in the complex */ - Simplex_handle get_vertices(Edge_handle edge_handle) const { + Simplex get_vertices(Edge_handle edge_handle) const { auto edge((*this)[edge_handle]); - return Simplex_handle((*this)[edge.first()], (*this)[edge.second()]); + return Simplex((*this)[edge.first()], (*this)[edge.second()]); } /** - * @brief Adds an edge between vertices a and b and all its cofaces. + * @brief Adds an edge between vertices a and b. + * @details For instance, the complex contains edge 01 and 12, then calling + * add_edge with vertex 0 and 2 will create a complex containing + * the edges 01, 12, 20 but not the triangle 012 (and hence this complex + * will contains a blocker 012). */ - Edge_handle add_edge(Vertex_handle a, Vertex_handle b) { + Edge_handle add_edge(Vertex_handle a, Vertex_handle b) { + //if the edge is already there we musnt go further + //as we may add blockers that should not be here + if(contains_edge(a,b)) + return *((*this)[std::make_pair(a,b)]); + auto res = add_edge_without_blockers(a,b); + add_blockers_after_simplex_insertion(Simplex(a,b)); + return res; + } + + /** + * @brief Adds all edges of s in the complex. + */ + void add_edge(const Simplex& s) { + for(auto i = s.begin(); i != s.end(); ++i) + for(auto j = i; ++j != s.end(); /**/) + add_edge(*i,*j); + } + + /** + * @brief Adds an edge between vertices a and b without blockers. + * @details For instance, the complex contains edge 01 and 12, then calling + * add_edge with vertex 0 and 2 will create a complex containing + * the triangle 012. + */ + Edge_handle add_edge_without_blockers(Vertex_handle a, Vertex_handle b) { assert(contains_vertex(a) && contains_vertex(b)); assert(a != b); auto edge_handle((*this)[std::make_pair(a, b)]); - // std::pair pair_descr_bool = (*this)[std::make_pair(a,b)]; - // Edge_handle edge_descr; - // bool edge_present = pair_descr_bool.second; if (!edge_handle) { edge_handle = boost::add_edge(a.vertex, b.vertex, skeleton).first; (*this)[*edge_handle].setId(get_id(a), get_id(b)); degree_[a.vertex]++; degree_[b.vertex]++; if (visitor) - visitor->on_add_edge(a, b); + visitor->on_add_edge_without_blockers(a, b); } return *edge_handle; } + /** - * @brief Adds all edges and their cofaces of a simplex to the simplicial complex. + * @brief Adds all edges of s in the complex without adding blockers. */ - void add_edges(const Simplex_handle & sigma) { - Simplex_handle_iterator i, j; - for (i = sigma.begin(); i != sigma.end(); ++i) - for (j = i, j++; j != sigma.end(); ++j) - add_edge(*i, *j); + void add_edge_without_blockers(Simplex s) { + for(auto i = s.begin(); i != s.end(); ++i){ + for(auto j = i; ++j != s.end(); /**/) + add_edge_without_blockers(*i,*j); + } } /** @@ -627,7 +654,7 @@ class Skeleton_blocker_complex { * @return true iff the simplicial complex contains all vertices * and all edges of simplex sigma */ - bool contains_edges(const Simplex_handle & sigma) const { + bool contains_edges(const Simplex & sigma) const { for (auto i = sigma.begin(); i != sigma.end(); ++i) { if (!contains_vertex(*i)) return false; @@ -649,15 +676,14 @@ class Skeleton_blocker_complex { * @brief Adds the simplex to the set of blockers and * returns a Blocker_handle toward it if was not present before and 0 otherwise. */ - Blocker_handle add_blocker(const Simplex_handle& blocker) { + Blocker_handle add_blocker(const Simplex& blocker) { assert(blocker.dimension() > 1); if (contains_blocker(blocker)) { - // std::cerr << "ATTEMPT TO ADD A BLOCKER ALREADY THERE ---> BLOCKER IGNORED" << endl; return 0; } else { if (visitor) visitor->on_add_blocker(blocker); - Blocker_handle blocker_pt = new Simplex_handle(blocker); + Blocker_handle blocker_pt = new Simplex(blocker); num_blockers_++; auto vertex = blocker_pt->begin(); while (vertex != blocker_pt->end()) { @@ -739,7 +765,7 @@ class Skeleton_blocker_complex { * * @remark contrarily to delete_blockers does not call the destructor */ - void remove_blocker(const Simplex_handle& sigma) { + void remove_blocker(const Simplex& sigma) { assert(contains_blocker(sigma)); for (auto vertex : sigma) remove_blocker(sigma, vertex); @@ -777,7 +803,7 @@ class Skeleton_blocker_complex { /** * @return true iff s is a blocker of the simplicial complex */ - bool contains_blocker(const Simplex_handle & s) const { + bool contains_blocker(const Simplex & s) const { if (s.dimension() < 2) return false; @@ -795,7 +821,7 @@ class Skeleton_blocker_complex { * @return true iff a blocker of the simplicial complex * is a face of sigma. */ - bool blocks(const Simplex_handle & sigma) const { + bool blocks(const Simplex & sigma) const { for (auto s : sigma) for (auto blocker : const_blocker_range(s)) if (sigma.contains(*blocker)) @@ -810,7 +836,7 @@ class Skeleton_blocker_complex { * @details Adds to simplex the neighbours of v e.g. \f$ n \leftarrow n \cup N(v) \f$. * If keep_only_superior is true then only vertices that are greater than v are added. */ - virtual void add_neighbours(Vertex_handle v, Simplex_handle & n, + virtual void add_neighbours(Vertex_handle v, Simplex & n, bool keep_only_superior = false) const { boost_adjacency_iterator ai, ai_end; for (tie(ai, ai_end) = adjacent_vertices(v.vertex, skeleton); ai != ai_end; @@ -833,7 +859,7 @@ class Skeleton_blocker_complex { * todo revoir * */ - virtual void add_neighbours(const Simplex_handle &alpha, Simplex_handle & res, + virtual void add_neighbours(const Simplex &alpha, Simplex & res, bool keep_only_superior = false) const { res.clear(); auto alpha_vertex = alpha.begin(); @@ -848,9 +874,9 @@ class Skeleton_blocker_complex { * not neighbours of v e.g. \f$ res \leftarrow res \cap N(v) \f$. * If 'keep_only_superior' is true then only vertices that are greater than v are keeped. */ - virtual void keep_neighbours(Vertex_handle v, Simplex_handle& res, + virtual void keep_neighbours(Vertex_handle v, Simplex& res, bool keep_only_superior = false) const { - Simplex_handle nv; + Simplex nv; add_neighbours(v, nv, keep_only_superior); res.intersection(nv); } @@ -860,9 +886,9 @@ class Skeleton_blocker_complex { * neighbours of v eg \f$ res \leftarrow res \setminus N(v) \f$. * If 'keep_only_superior' is true then only vertices that are greater than v are added. */ - virtual void remove_neighbours(Vertex_handle v, Simplex_handle & res, + virtual void remove_neighbours(Vertex_handle v, Simplex & res, bool keep_only_superior = false) const { - Simplex_handle nv; + Simplex nv; add_neighbours(v, nv, keep_only_superior); res.difference(nv); } @@ -874,7 +900,7 @@ class Skeleton_blocker_complex { * Constructs the link of 'simplex' with points coordinates. */ Link_complex link(Vertex_handle v) const { - return Link_complex(*this, Simplex_handle(v)); + return Link_complex(*this, Simplex(v)); } /** @@ -887,7 +913,7 @@ class Skeleton_blocker_complex { /** * Constructs the link of 'simplex' with points coordinates. */ - Link_complex link(const Simplex_handle& simplex) const { + Link_complex link(const Simplex& simplex) const { return Link_complex(*this, simplex); } @@ -899,11 +925,11 @@ class Skeleton_blocker_complex { */ // xxx rename get_address et place un using dans sub_complex - boost::optional get_simplex_address( + boost::optional get_simplex_address( const Root_simplex_handle& s) const { - boost::optional res; + boost::optional res; - Simplex_handle s_address; + Simplex s_address; // Root_simplex_const_iterator i; for (auto i = s.begin(); i != s.end(); ++i) { boost::optional address = get_address(*i); @@ -920,7 +946,7 @@ class Skeleton_blocker_complex { * @brief returns a simplex with vertices which are the id of vertices of the * argument. */ - Root_simplex_handle get_id(const Simplex_handle& local_simplex) const { + Root_simplex_handle get_id(const Simplex& local_simplex) const { Root_simplex_handle global_simplex; for (auto x = local_simplex.begin(); x != local_simplex.end(); ++x) { global_simplex.add_vertex(get_id(*x)); @@ -932,7 +958,7 @@ class Skeleton_blocker_complex { * @brief returns true iff the simplex s belongs to the simplicial * complex. */ - virtual bool contains(const Simplex_handle & s) const { + virtual bool contains(const Simplex & s) const { if (s.dimension() == -1) { return false; } else if (s.dimension() == 0) { @@ -1061,7 +1087,7 @@ class Skeleton_blocker_complex { * Furthermore, all simplices tau of the form sigma \setminus simplex_to_be_removed must be added * whenever the dimension of tau is at least 2. */ - void update_blockers_after_remove_star_of_vertex_or_edge(const Simplex_handle& simplex_to_be_removed); + void update_blockers_after_remove_star_of_vertex_or_edge(const Simplex& simplex_to_be_removed); public: /** @@ -1078,31 +1104,36 @@ class Skeleton_blocker_complex { /** * Remove the star of the simplex 'sigma' which needs to belong to the complex */ - void remove_star(const Simplex_handle& sigma); + void remove_star(const Simplex& sigma); /** - * @brief add a maximal simplex plus all its cofaces. - * @details the simplex must have dimension greater than one (otherwise use add_vertex or add_edge). + * @brief add a simplex. + * @details the simplex must have dimension greater than one (otherwise use add_vertex or add_edge_without_blockers). + * and all vertices lower than the higher vertex of sigma must already be in the complex. + * if some edges of sigma are not in the complex, then insert_edges_of_sigma flag must be + * set to true. */ - void add_simplex(const Simplex_handle& sigma); + void add_simplex(const Simplex& sigma, bool insert_edges_of_sigma = false); private: + void add_blockers_after_simplex_insertion(Simplex s); + /** * remove all blockers that contains sigma */ - void remove_blocker_containing_simplex(const Simplex_handle& sigma); + void remove_blocker_containing_simplex(const Simplex& sigma); /** * remove all blockers that contains sigma */ - void remove_blocker_include_in_simplex(const Simplex_handle& sigma); + void remove_blocker_include_in_simplex(const Simplex& sigma); public: enum simplifiable_status { NOT_HOMOTOPY_EQ, MAYBE_HOMOTOPY_EQ, HOMOTOPY_EQ }; - simplifiable_status is_remove_star_homotopy_preserving(const Simplex_handle& simplex) { + simplifiable_status is_remove_star_homotopy_preserving(const Simplex& simplex) { // todo write a virtual method 'link' in Skeleton_blocker_complex which will be overloaded by the current one of // Skeleton_blocker_geometric_complex // then call it there to build the link and return the value of link.is_contractible() @@ -1174,7 +1205,7 @@ class Skeleton_blocker_complex { * that may be used to construct a new blocker after contracting ab. * It requires that the link condition is satisfied. */ - void tip_blockers(Vertex_handle a, Vertex_handle b, std::vector & buffer) const; + void tip_blockers(Vertex_handle a, Vertex_handle b, std::vector & buffer) const; private: /** @@ -1217,7 +1248,7 @@ class Skeleton_blocker_complex { private: void get_blockers_to_be_added_after_contraction(Vertex_handle a, Vertex_handle b, - std::set& blockers_to_add); + std::set& blockers_to_add); /** * delete all blockers that passes through a or b */ @@ -1358,12 +1389,28 @@ class Skeleton_blocker_complex { /** * @brief Returns a Complex_simplex_around_vertex_range over all the simplices around a vertex of the complex */ - Complex_simplex_around_vertex_range simplex_range(Vertex_handle v) const { + Complex_simplex_around_vertex_range star_simplex_range(Vertex_handle v) const { assert(contains_vertex(v)); return Complex_simplex_around_vertex_range( Complex_simplex_around_vertex_iterator(this, v), Complex_simplex_around_vertex_iterator(this, v, true)); } + typedef Simplex_coboundary_iterator Complex_simplex_coboundary_iterator; + + /** + * @brief Range over the simplices of the coboundary of a simplex. + * Methods .begin() and .end() return a Complex_simplex_coboundary_iterator. + */ + typedef boost::iterator_range < Complex_simplex_coboundary_iterator > Complex_coboundary_range; + + /** + * @brief Returns a Complex_simplex_coboundary_iterator over the simplices of the coboundary of a simplex. + */ + Complex_coboundary_range coboundary_range(const Simplex& s) const { + assert(contains(s)); + return Complex_coboundary_range(Complex_simplex_coboundary_iterator(this, s), + Complex_simplex_coboundary_iterator(this, s, true)); + } // typedef Simplex_iterator Complex_simplex_iterator; typedef Simplex_iterator Complex_simplex_iterator; @@ -1373,7 +1420,7 @@ class Skeleton_blocker_complex { /** * @brief Returns a Complex_simplex_range over all the simplices of the complex */ - Complex_simplex_range simplex_range() const { + Complex_simplex_range complex_simplex_range() const { Complex_simplex_iterator end(this, true); if (empty()) { return Complex_simplex_range(end, end); @@ -1393,7 +1440,7 @@ class Skeleton_blocker_complex { * @brief Iterator over the blockers adjacent to a vertex */ typedef Blocker_iterator_around_vertex_internal< - typename std::multimap::iterator, + typename std::multimap::iterator, Blocker_handle> Complex_blocker_around_vertex_iterator; @@ -1401,7 +1448,7 @@ class Skeleton_blocker_complex { * @brief Iterator over (constant) blockers adjacent to a vertex */ typedef Blocker_iterator_around_vertex_internal< - typename std::multimap::const_iterator, + typename std::multimap::const_iterator, const Blocker_handle> Const_complex_blocker_around_vertex_iterator; @@ -1433,7 +1480,7 @@ class Skeleton_blocker_complex { * @brief Iterator over the blockers. */ typedef Blocker_iterator_internal< - typename std::multimap::iterator, + typename std::multimap::iterator, Blocker_handle> Complex_blocker_iterator; @@ -1441,7 +1488,7 @@ class Skeleton_blocker_complex { * @brief Iterator over the (constant) blockers. */ typedef Blocker_iterator_internal< - typename std::multimap::const_iterator, + typename std::multimap::const_iterator, const Blocker_handle> Const_complex_blocker_iterator; @@ -1517,8 +1564,9 @@ class Skeleton_blocker_complex { template Complex make_complex_from_top_faces(SimplexHandleIterator simplex_begin, SimplexHandleIterator simplex_end, bool is_flag_complex = false) { - typedef typename Complex::Simplex_handle Simplex_handle; - std::vector simplices; + //todo use add_simplex instead! should be more efficient and more elegant :) + typedef typename Complex::Simplex Simplex; + std::vector simplices; for (auto top_face = simplex_begin; top_face != simplex_end; ++top_face) { auto subfaces_topface = subfaces(*top_face); simplices.insert(simplices.end(), subfaces_topface.begin(), subfaces_topface.end()); diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h index b8395251..5c898152 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h @@ -46,7 +46,7 @@ public Skeleton_blocker_complex { typedef typename SimplifiableSkeletonblocker::Vertex_handle Vertex_handle; typedef typename SimplifiableSkeletonblocker::Root_vertex_handle Root_vertex_handle; typedef typename SimplifiableSkeletonblocker::Edge_handle Edge_handle; - typedef typename SimplifiableSkeletonblocker::Simplex_handle Simplex_handle; + typedef typename SimplifiableSkeletonblocker::Simplex Simplex; typedef typename SimplifiableSkeletonblocker::Graph_vertex Graph_vertex; @@ -140,7 +140,7 @@ public Skeleton_blocker_complex { * Constructs the link of 'simplex' with points coordinates. */ Geometric_link link(Vertex_handle v) const { - Geometric_link link(*this, Simplex_handle(v)); + Geometric_link link(*this, Simplex(v)); // we now add the point info add_points_to_link(link); return link; @@ -149,7 +149,7 @@ public Skeleton_blocker_complex { /** * Constructs the link of 'simplex' with points coordinates. */ - Geometric_link link(const Simplex_handle& simplex) const { + Geometric_link link(const Simplex& simplex) const { Geometric_link link(*this, simplex); // we now add the point info add_points_to_link(link); @@ -172,13 +172,13 @@ public Skeleton_blocker_complex { * Constructs the abstract link of v (without points coordinates). */ Abstract_link abstract_link(Vertex_handle v) const { - return Abstract_link(*this, Simplex_handle(v)); + return Abstract_link(*this, Simplex(v)); } /** * Constructs the link of 'simplex' with points coordinates. */ - Abstract_link abstract_link(const Simplex_handle& simplex) const { + Abstract_link abstract_link(const Simplex& simplex) const { return Abstract_link(*this, simplex); } diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h index 95d8fa97..85a6b0b5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h @@ -52,12 +52,11 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< typedef typename ComplexType::Vertex_handle Vertex_handle; typedef typename ComplexType::Root_vertex_handle Root_vertex_handle; - typedef typename ComplexType::Simplex_handle Simplex_handle; + typedef typename ComplexType::Simplex Simplex; typedef typename ComplexType::Root_simplex_handle Root_simplex_handle; typedef typename ComplexType::Blocker_handle Blocker_handle; - typedef typename ComplexType::Simplex_handle::Simplex_vertex_const_iterator Simplex_handle_iterator; typedef typename ComplexType::Root_simplex_handle::Simplex_vertex_const_iterator Root_simplex_handle_iterator; explicit Skeleton_blocker_link_complex(bool only_superior_vertices = false) @@ -67,13 +66,15 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< /** * If the parameter only_superior_vertices is true, * only vertices greater than the one of alpha are added. + * Only vertices are computed if only_vertices is true. */ Skeleton_blocker_link_complex(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent_adress, - bool only_superior_vertices = false) + const Simplex& alpha_parent_adress, + bool only_superior_vertices = false, + bool only_vertices = false) : only_superior_vertices_(only_superior_vertices) { if (!alpha_parent_adress.empty()) - build_link(parent_complex, alpha_parent_adress); + build_link(parent_complex, alpha_parent_adress, only_vertices); } /** @@ -84,7 +85,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< Vertex_handle a_parent_adress, bool only_superior_vertices = false) : only_superior_vertices_(only_superior_vertices) { - Simplex_handle alpha_simplex(a_parent_adress); + Simplex alpha_simplex(a_parent_adress); build_link(parent_complex, alpha_simplex); } @@ -96,7 +97,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< Edge_handle edge, bool only_superior_vertices = false) : only_superior_vertices_(only_superior_vertices) { - Simplex_handle alpha_simplex(parent_complex.first_vertex(edge), + Simplex alpha_simplex(parent_complex.first_vertex(edge), parent_complex.second_vertex(edge)); build_link(parent_complex, alpha_simplex); } @@ -108,7 +109,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< * are greater than vertices of alpha_parent_adress are added. */ void compute_link_vertices(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent_adress, + const Simplex& alpha_parent_adress, bool only_superior_vertices, bool is_alpha_blocker = false) { if (alpha_parent_adress.dimension() == 0) { @@ -119,7 +120,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< only_superior_vertices_); } else { // we compute the intersection of neighbors of alpha and store it in link_vertices - Simplex_handle link_vertices_parent; + Simplex link_vertices_parent; parent_complex.add_neighbours(alpha_parent_adress, link_vertices_parent, only_superior_vertices); // For all vertex 'v' in this intersection, we go through all its adjacent blockers. @@ -162,13 +163,8 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< } void compute_link_edges(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent_adress, + const Simplex& alpha_parent_adress, bool is_alpha_blocker = false) { - Simplex_handle_iterator y_link, x_parent, y_parent; - // ---------------------------- - // Compute edges in the link - // ------------------------- - if (this->num_vertices() <= 1) return; @@ -194,7 +190,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< } } if (new_edge) - this->add_edge(*x_link, *y_link); + this->add_edge_without_blockers(*x_link, *y_link); } } } @@ -217,7 +213,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< * the blocker is anticollapsed. */ void compute_link_blockers(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent, + const Simplex& alpha_parent, bool is_alpha_blocker = false) { for (auto x_link : this->vertex_range()) { Vertex_handle x_parent = *this->give_equivalent_vertex(parent_complex, @@ -225,7 +221,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< for (auto blocker_parent : parent_complex.const_blocker_range(x_parent)) { if (!is_alpha_blocker || *blocker_parent != alpha_parent) { - Simplex_handle sigma_parent(*blocker_parent); + Simplex sigma_parent(*blocker_parent); sigma_parent.difference(alpha_parent); @@ -239,7 +235,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< for (auto a : alpha_parent) { for (auto eta_parent : parent_complex.const_blocker_range(a)) { if (!is_alpha_blocker || *eta_parent != alpha_parent) { - Simplex_handle eta_minus_alpha(*eta_parent); + Simplex eta_minus_alpha(*eta_parent); eta_minus_alpha.difference(alpha_parent); if (eta_minus_alpha != sigma_parent && sigma_parent.contains_difference(*eta_parent, @@ -253,7 +249,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< break; } if (is_new_blocker) - this->add_blocker(new Simplex_handle(*sigma_link)); + this->add_blocker(new Simplex(*sigma_link)); } } } @@ -268,14 +264,15 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< * with vertices that are greater than vertices of alpha_parent_adress. */ void build_link(const ComplexType & parent_complex, - const Simplex_handle& alpha_parent_adress, - bool is_alpha_blocker = false) { + const Simplex& alpha_parent_adress, + bool is_alpha_blocker = false, + bool only_vertices = false) { assert(is_alpha_blocker || parent_complex.contains(alpha_parent_adress)); - compute_link_vertices(parent_complex, alpha_parent_adress, - only_superior_vertices_); - compute_link_edges(parent_complex, alpha_parent_adress, is_alpha_blocker); - compute_link_blockers(parent_complex, alpha_parent_adress, - is_alpha_blocker); + compute_link_vertices(parent_complex, alpha_parent_adress, only_superior_vertices_); + if(!only_vertices) { + compute_link_edges(parent_complex, alpha_parent_adress, is_alpha_blocker); + compute_link_blockers(parent_complex, alpha_parent_adress, is_alpha_blocker); + } } /** @@ -284,7 +281,7 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< * removed from the blockers of the complex. */ friend void build_link_of_blocker(const ComplexType & parent_complex, - Simplex_handle& blocker, + Simplex& blocker, Skeleton_blocker_link_complex & result) { assert(blocker.dimension() >= 2); assert(parent_complex.contains_blocker(blocker)); diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h index 17a237a7..49a1ea8b 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h @@ -133,7 +133,7 @@ void Skeleton_blocker_complex::remove_all_popable_blockers(Ve template void Skeleton_blocker_complex::remove_star(Vertex_handle v) { // we remove the blockers that are not consistent anymore - update_blockers_after_remove_star_of_vertex_or_edge(Simplex_handle(v)); + update_blockers_after_remove_star_of_vertex_or_edge(Simplex(v)); while (this->degree(v) > 0) { Vertex_handle w(* (adjacent_vertices(v.vertex, this->skeleton).first)); this->remove_edge(v, w); @@ -148,7 +148,7 @@ void Skeleton_blocker_complex::remove_star(Vertex_handle v) { */ template void Skeleton_blocker_complex::update_blockers_after_remove_star_of_vertex_or_edge( - const Simplex_handle& simplex_to_be_removed) { + const Simplex& simplex_to_be_removed) { std::list blockers_to_update; if (simplex_to_be_removed.empty()) return; @@ -159,7 +159,7 @@ void Skeleton_blocker_complex::update_blockers_after_remove_s } for (auto blocker_to_update : blockers_to_update) { - Simplex_handle sub_blocker_to_be_added; + Simplex sub_blocker_to_be_added; bool sub_blocker_need_to_be_added = (blocker_to_update->dimension() - simplex_to_be_removed.dimension()) >= 2; if (sub_blocker_need_to_be_added) { @@ -178,7 +178,7 @@ void Skeleton_blocker_complex::update_blockers_after_remove_s */ template void Skeleton_blocker_complex::remove_star(Vertex_handle a, Vertex_handle b) { - update_blockers_after_remove_star_of_vertex_or_edge(Simplex_handle(a, b)); + update_blockers_after_remove_star_of_vertex_or_edge(Simplex(a, b)); // we remove the edge this->remove_edge(a, b); } @@ -195,7 +195,7 @@ void Skeleton_blocker_complex::remove_star(Edge_handle e) { * Remove the star of the simplex 'sigma' which needs to belong to the complex */ template -void Skeleton_blocker_complex::remove_star(const Simplex_handle& sigma) { +void Skeleton_blocker_complex::remove_star(const Simplex& sigma) { assert(this->contains(sigma)); if (sigma.dimension() == 0) { remove_star(sigma.first_vertex()); @@ -207,34 +207,36 @@ void Skeleton_blocker_complex::remove_star(const Simplex_hand } } -/** - * @brief add a maximal simplex plus all its cofaces. All vertices lower than the higher vertex of - * sigma must already be present. - * @details the simplex must have dimension greater than one (otherwise use add_vertex or add_edge). - */ template -void Skeleton_blocker_complex::add_simplex(const Simplex_handle& sigma) { +void Skeleton_blocker_complex::add_simplex(const Simplex& sigma, bool insert_edges_of_sigma) { + // to add a simplex s, all blockers included in s are first removed + // and then all simplex in the coboundary of s are added as blockers assert(!this->contains(sigma)); assert(sigma.dimension() > 1); + assert(contains_vertices(sigma)); - int num_vertex_to_add = 0; - for (auto v : sigma) - if (!contains_vertex(v)) ++num_vertex_to_add; - while (num_vertex_to_add--) add_vertex(); - - for (auto u_it = sigma.begin(); u_it != sigma.end(); ++u_it) - for (auto v_it = u_it; ++v_it != sigma.end(); /**/) { - // std::cout << "add edge" << *u_it << " " << *v_it << std::endl; - add_edge(*u_it, *v_it); - } + if(insert_edges_of_sigma) + add_edge(sigma); + else + assert(contains_edges(sigma)); remove_blocker_include_in_simplex(sigma); + add_blockers_after_simplex_insertion(sigma); +} + +template +void Skeleton_blocker_complex::add_blockers_after_simplex_insertion(Simplex sigma){ + if(sigma.dimension() < 1) return; + + for(auto s : coboundary_range(sigma)) { + this->add_blocker(s); + } } /** * remove all blockers that contains sigma */ template -void Skeleton_blocker_complex::remove_blocker_containing_simplex(const Simplex_handle& sigma) { +void Skeleton_blocker_complex::remove_blocker_containing_simplex(const Simplex& sigma) { std::vector blockers_to_remove; for (auto blocker : this->blocker_range(sigma.first_vertex())) { if (blocker->contains(sigma)) @@ -248,14 +250,26 @@ void Skeleton_blocker_complex::remove_blocker_containing_simp * remove all blockers that contains sigma */ template -void Skeleton_blocker_complex::remove_blocker_include_in_simplex(const Simplex_handle& sigma) { - std::vector blockers_to_remove; - for (auto blocker : this->blocker_range(sigma.first_vertex())) { - if (sigma.contains(*blocker)) - blockers_to_remove.push_back(blocker); +void Skeleton_blocker_complex::remove_blocker_include_in_simplex(const Simplex& sigma) { + //todo write efficiently by using only superior blockers + //eg for all s, check blockers whose vertices are all greater than s + std::set blockers_to_remove; + for(auto s : sigma) { + for (auto blocker : this->blocker_range(s)) { + if (sigma.contains(*blocker)) + blockers_to_remove.insert(blocker); + } } - for (auto blocker_to_update : blockers_to_remove) + for (auto blocker_to_update : blockers_to_remove) { + auto s = *blocker_to_update; this->delete_blocker(blocker_to_update); + //now if there is a vertex v in the link of s + //and v is not included in sigma then v.s is a blocker + //(all faces of v.s are there since v belongs to the link of s) + for(const auto& b : coboundary_range(s)) + if(!sigma.contains(b)) + this->add_blocker(b); + } } /** @@ -265,21 +279,21 @@ void Skeleton_blocker_complex::remove_blocker_include_in_simp */ template void Skeleton_blocker_complex::tip_blockers(Vertex_handle a, Vertex_handle b, - std::vector & buffer) const { + std::vector & buffer) const { for (auto const & blocker : this->const_blocker_range(a)) { - Simplex_handle beta = (*blocker); + Simplex beta = (*blocker); beta.remove_vertex(a); buffer.push_back(beta); } - Simplex_handle n; + Simplex n; this->add_neighbours(b, n); this->remove_neighbours(a, n); n.remove_vertex(a); for (Vertex_handle y : n) { - Simplex_handle beta; + Simplex beta; beta.add_vertex(y); buffer.push_back(beta); } @@ -296,7 +310,7 @@ void Skeleton_blocker_complex::tip_blockers(Vertex_handle a, template void Skeleton_blocker_complex::swap_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) { - this->add_edge(a, x); + this->add_edge_without_blockers(a, x); if (this->visitor) this->visitor->on_swaped_edge(a, b, x); this->remove_edge(b, x); } @@ -341,13 +355,13 @@ Skeleton_blocker_complex::contract_edge(Vertex_handle a, Vert assert(this->contains_vertex(b)); if (this->contains_edge(a, b)) - this->add_edge(a, b); + this->add_edge_without_blockers(a, b); // if some blockers passes through 'ab', we need to remove them. if (!link_condition(a, b)) delete_blockers_around_edge(a, b); - std::set blockers_to_add; + std::set blockers_to_add; get_blockers_to_be_added_after_contraction(a, b, blockers_to_add); @@ -369,7 +383,7 @@ Skeleton_blocker_complex::contract_edge(Vertex_handle a, Vert template void Skeleton_blocker_complex::get_blockers_to_be_added_after_contraction(Vertex_handle a, Vertex_handle b, - std::set& blockers_to_add) { + std::set& blockers_to_add) { blockers_to_add.clear(); typedef Skeleton_blocker_link_complex > LinkComplexType; @@ -377,19 +391,19 @@ Skeleton_blocker_complex::get_blockers_to_be_added_after_cont LinkComplexType link_a(*this, a); LinkComplexType link_b(*this, b); - std::vector vector_alpha, vector_beta; + std::vector vector_alpha, vector_beta; tip_blockers(a, b, vector_alpha); tip_blockers(b, a, vector_beta); for (auto alpha = vector_alpha.begin(); alpha != vector_alpha.end(); ++alpha) { for (auto beta = vector_beta.begin(); beta != vector_beta.end(); ++beta) { - Simplex_handle sigma = *alpha; + Simplex sigma = *alpha; sigma.union_vertices(*beta); Root_simplex_handle sigma_id = this->get_id(sigma); if (this->contains(sigma) && proper_faces_in_union> (sigma_id, link_a, link_b)) { - // Blocker_handle blocker = new Simplex_handle(sigma); + // Blocker_handle blocker = new Simplex(sigma); sigma.add_vertex(a); blockers_to_add.insert(sigma); } -- cgit v1.2.3