diff options
Diffstat (limited to 'src/Skeleton_blocker/include')
20 files changed, 1629 insertions, 1570 deletions
diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h index 289819b5..615b3a81 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker.h @@ -19,23 +19,24 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_H_ -#include "gudhi/Skeleton_blocker_complex.h" -#include "gudhi/Skeleton_blocker_geometric_complex.h" -#include "gudhi/Skeleton_blocker_simplifiable_complex.h" -#include "gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h" +#ifndef SKELETON_BLOCKER_H_ +#define SKELETON_BLOCKER_H_ -#include "gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h" -#include "gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h" +#include <gudhi/Skeleton_blocker_complex.h> +#include <gudhi/Skeleton_blocker_geometric_complex.h> +#include <gudhi/Skeleton_blocker_simplifiable_complex.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h> -#include "gudhi/Utils.h" // xxx - +#include <gudhi/Utils.h> // xxx namespace Gudhi { + namespace skbl { + /** \defgroup skbl Skeleton-Blocker \author David Salinas @@ -128,7 +129,7 @@ of a simplicial complex. \code{.cpp} typedef Skeleton_blocker_complex<Skeleton_blocker_simple_traits> Complex; typedef Complex::Vertex_handle Vertex_handle; - typedef Complex::Simplex_handle Simplex; + typedef Complex::Simplex Simplex; const int n = 15; @@ -138,8 +139,7 @@ of a simplicial complex. complex.add_vertex(); for(int i=0;i<n;i++) for(int j=0;j<i;j++) - //note that add_edge adds the edge and all its cofaces - complex.add_edge(Vertex_handle(i),Vertex_handle(j)); + complex.add_edge_without_blockers(Vertex_handle(i),Vertex_handle(j)); // this is just to illustrate iterators, to count number of vertices // or edges, complex.num_vertices() and complex.num_edges() are @@ -158,7 +158,7 @@ of a simplicial complex. // we use a reference to a simplex instead of a copy // value here because a simplex is a set of integers // and copying it cost time - for(const Simplex & s : complex.simplex_range()){ + for(const Simplex & s : complex.star_simplex_range()){ ++num_simplices; if(s.dimension()%2 == 0) euler += 1; @@ -181,20 +181,20 @@ The Euler Characteristic is 1 \subsection s Constructing a skeleton-blockers from a list of maximal faces or from a list of faces \code{.cpp} - std::vector<Simplex_handle> simplices; + std::vector<Simplex> 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:"<<std::endl; - for(const Simplex & s : complex.simplex_range()) + for(const Simplex & s : complex.star_simplex_range()) std::cout << s << " "; std::cout << std::endl; @@ -203,16 +203,16 @@ The Euler Characteristic is 1 //now build a complex from its full list of simplices simplices.clear(); - simplices.push_back(Simplex_handle(Vertex_handle(0))); - simplices.push_back(Simplex_handle(Vertex_handle(1))); - simplices.push_back(Simplex_handle(Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(0),Vertex_handle(1))); - simplices.push_back(Simplex_handle(Vertex_handle(1),Vertex_handle(2))); - simplices.push_back(Simplex_handle(Vertex_handle(2),Vertex_handle(0))); + simplices.push_back(Simplex(Vertex_handle(0))); + simplices.push_back(Simplex(Vertex_handle(1))); + simplices.push_back(Simplex(Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(0),Vertex_handle(1))); + simplices.push_back(Simplex(Vertex_handle(1),Vertex_handle(2))); + simplices.push_back(Simplex(Vertex_handle(2),Vertex_handle(0))); complex = Complex(simplices.begin(),simplices.end()); std::cout << "Simplices:"<<std::endl; - for(const Simplex & s : complex.simplex_range()) + for(const Simplex & s : complex.star_simplex_range()) std::cout << s << " "; std::cout << std::endl; @@ -240,14 +240,12 @@ their collaboration to write the two initial papers \copyright GNU General Public License v3. -\verbatim Contact: David Salinas, david.salinas@inria.fr \endverbatim +\verbatim Contact: gudhi-users@lists.gforge.inria.fr \endverbatim */ /** @} */ // end defgroup -} // namespace skbl -} // namespace Gudhi - - -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_H_ +} // namespace skbl +} // namespace Gudhi +#endif // SKELETON_BLOCKER_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h index 829ab1e8..4ade68e7 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h @@ -19,10 +19,10 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ -#include "gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h" +#include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h> namespace Gudhi { @@ -41,7 +41,7 @@ class Skeleton_blocker_complex_visitor { virtual void on_add_vertex(Vertex_handle) = 0; virtual void on_remove_vertex(Vertex_handle) = 0; - virtual void on_add_edge(Vertex_handle a, Vertex_handle b) = 0; + virtual void on_add_edge_without_blockers(Vertex_handle a, Vertex_handle b) = 0; virtual void on_remove_edge(Vertex_handle a, Vertex_handle b) = 0; /** @@ -54,12 +54,12 @@ class Skeleton_blocker_complex_visitor { * @brief Called when performing an edge contraction when * an edge bx is replaced by an edge ax (not already present). * Precisely, this methods is called this way in contract_edge : - * add_edge(a,x) + * add_edge_without_blockers(a,x) * on_swaped_edge(a,b,x) * remove_edge(b,x) */ virtual void on_swaped_edge(Vertex_handle a, Vertex_handle b, - Vertex_handle x)=0; + Vertex_handle x) = 0; virtual void on_add_blocker( const Skeleton_blocker_simplex<Vertex_handle>&) = 0; virtual void on_delete_blocker( @@ -79,7 +79,7 @@ class Dummy_complex_visitor : public Skeleton_blocker_complex_visitor< } void on_remove_vertex(Vertex_handle) { } - void on_add_edge(Vertex_handle a, Vertex_handle b) { + void on_add_edge_without_blockers(Vertex_handle a, Vertex_handle b) { } void on_remove_edge(Vertex_handle a, Vertex_handle b) { } @@ -108,8 +108,8 @@ class Print_complex_visitor : public Skeleton_blocker_complex_visitor< void on_remove_vertex(Vertex_handle v) { std::cerr << "on_remove_vertex:" << v << std::endl; } - void on_add_edge(Vertex_handle a, Vertex_handle b) { - std::cerr << "on_add_edge:" << a << "," << b << std::endl; + void on_add_edge_without_blockers(Vertex_handle a, Vertex_handle b) { + std::cerr << "on_add_edge_without_blockers:" << a << "," << b << std::endl; } void on_remove_edge(Vertex_handle a, Vertex_handle b) { std::cerr << "on_remove_edge:" << a << "," << b << std::endl; @@ -132,4 +132,4 @@ class Print_complex_visitor : public Skeleton_blocker_complex_visitor< } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ +#endif // SKELETON_BLOCKER_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h index 17d58956..876bdba9 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h @@ -19,10 +19,10 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_LINK_SUPERIOR_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_LINK_SUPERIOR_H_ +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_LINK_SUPERIOR_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_LINK_SUPERIOR_H_ -#include "gudhi/Skeleton_blocker_link_complex.h" +#include <gudhi/Skeleton_blocker_link_complex.h> namespace Gudhi { @@ -44,13 +44,13 @@ class Skeleton_blocker_link_superior : public Skeleton_blocker_link_complex< public: 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::BlockerMap BlockerMap; typedef typename ComplexType::BlockerPair BlockerPair; typedef typename ComplexType::BlockerMapIterator BlockerMapIterator; typedef typename ComplexType::BlockerMapConstIterator BlockerMapConstIterator; - typedef typename ComplexType::Simplex_handle::Simplex_vertex_const_iterator AddressSimplexConstIterator; + typedef typename ComplexType::Simplex::Simplex_vertex_const_iterator AddressSimplexConstIterator; typedef typename ComplexType::Root_simplex_handle::Simplex_vertex_const_iterator IdSimplexConstIterator; Skeleton_blocker_link_superior() @@ -58,7 +58,7 @@ class Skeleton_blocker_link_superior : public Skeleton_blocker_link_complex< } Skeleton_blocker_link_superior(const ComplexType & parent_complex, - Simplex_handle& alpha_parent_adress) + Simplex& alpha_parent_adress) : Skeleton_blocker_link_complex<ComplexType>(parent_complex, alpha_parent_adress, true) { } @@ -74,4 +74,4 @@ class Skeleton_blocker_link_superior : public Skeleton_blocker_link_complex< } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_LINK_SUPERIOR_H_ +#endif // SKELETON_BLOCKER_SKELETON_BLOCKER_LINK_SUPERIOR_H_ 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 aaaab8b0..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 @@ -19,15 +19,15 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_OFF_IO_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_OFF_IO_H_ +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_OFF_IO_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_OFF_IO_H_ + +#include <gudhi/Off_reader.h> #include <string> #include <vector> #include <map> -#include "gudhi/Off_reader.h" - namespace Gudhi { namespace skbl { @@ -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<typename Complex> 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<Point> points_; - std::vector<Simplex_handle> maximal_faces_; + std::vector<Simplex> 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<int>& 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); @@ -107,7 +107,7 @@ class Skeleton_blocker_off_visitor_reader { } void done() { - complex_ = make_complex_from_top_faces(maximal_faces_.begin(), maximal_faces_.end(), + complex_ = make_complex_from_top_faces<Complex>(maximal_faces_.begin(), maximal_faces_.end(), points_.begin(), points_.end() ); } }; @@ -197,4 +197,4 @@ class Skeleton_blocker_off_writer { } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_OFF_IO_H_ +#endif // SKELETON_BLOCKER_SKELETON_BLOCKER_OFF_IO_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h index d3a5b9d8..8508d9a5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h @@ -19,14 +19,14 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_GEOMETRIC_TRAITS_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_GEOMETRIC_TRAITS_H_ +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_GEOMETRIC_TRAITS_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_GEOMETRIC_TRAITS_H_ + +#include <gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h> #include <string> #include <sstream> -#include "gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h" - namespace Gudhi { namespace skbl { @@ -91,4 +91,4 @@ struct Skeleton_blocker_simple_geometric_traits : } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_GEOMETRIC_TRAITS_H_ +#endif // SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_GEOMETRIC_TRAITS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h index 52e454ea..0d2de767 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h @@ -19,12 +19,13 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_TRAITS_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_TRAITS_H_ +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_TRAITS_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_TRAITS_H_ + +#include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h> #include <string> #include <sstream> -#include "Skeleton_blocker_simplex.h" namespace Gudhi { @@ -77,7 +78,7 @@ struct Skeleton_blocker_simple_traits { : vertex(val) { } - operator int() const { return (int)vertex; } + operator int() const { return static_cast<int>(vertex); } boost_vertex_handle vertex; @@ -178,4 +179,4 @@ struct Skeleton_blocker_simple_traits { } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_TRAITS_H_ +#endif // SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLE_TRAITS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h index 10d64e98..714bf23c 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h @@ -20,8 +20,8 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_ +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_ #include <cassert> #include <iostream> @@ -69,7 +69,9 @@ class Skeleton_blocker_simplex { } Skeleton_blocker_simplex(std::initializer_list<T>& list) { - for_each(list.begin(), list.end(), add_vertex); + std::for_each(list.begin(), list.end(), [&] (T const& elt) { + add_vertex(elt); + }); } template<typename ... Args> @@ -216,7 +218,7 @@ class Skeleton_blocker_simplex { } /** - * Returns the first vertex of the (oriented) simplex. + * Returns the first and smallest vertex of the simplex. * * Be careful : assumes the simplex is non-empty. */ @@ -226,7 +228,7 @@ class Skeleton_blocker_simplex { } /** - * Returns the last vertex of the (oriented) simplex. + * Returns the last and greatest vertex of the simplex. * * Be careful : assumes the simplex is non-empty. */ @@ -369,5 +371,4 @@ class Skeleton_blocker_simplex { } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_ - +#endif // SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_ 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 e906df75..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 @@ -20,16 +20,16 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_COMPLEX_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_COMPLEX_H_ +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_COMPLEX_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_COMPLEX_H_ + +#include <gudhi/Skeleton_blocker_complex.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h> +#include <gudhi/Utils.h> #include <map> #include <vector> -#include "gudhi/Skeleton_blocker_complex.h" -#include "gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h" -#include "gudhi/Utils.h" - namespace Gudhi { namespace skbl { @@ -66,34 +66,19 @@ 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: - ///** - //* @brief Returns true iff the simplex formed by all vertices contained in 'addresses_sigma_in_link' - //* but 'vertex_to_be_ignored' is in 'link' - //*/ - /* - template<typename T> friend bool - proper_face_in_union( - Skeleton_blocker_sub_complex<T> & link, - std::vector<boost::optional<typename T::Vertex_handle> > & addresses_sigma_in_link, - int vertex_to_be_ignored);*/ - /** * @brief Determines whether all proper faces of simplex 'sigma' belong to 'link1' \cup 'link2' * where 'link1' and 'link2' are subcomplexes of the same complex of type ComplexType */ - // template<typename T> friend bool - // proper_faces_in_union(Skeleton_blocker_simplex<typename T::Root_vertex_handle> & sigma, Skeleton_blocker_sub_complex<T> & link1, Skeleton_blocker_sub_complex<T> & link2){ - // template<typename T> friend bool - // proper_faces_in_union(Skeleton_blocker_simplex<typename T::Root_vertex_handle> & sigma, Skeleton_blocker_sub_complex<T> & link1, Skeleton_blocker_sub_complex<T> & link2); typedef std::map<Root_vertex_handle, Vertex_handle> IdAddressMap; typedef typename IdAddressMap::value_type AddressPair; typedef typename IdAddressMap::iterator IdAddressMapIterator; @@ -124,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); } /** @@ -139,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: @@ -148,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) { @@ -160,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()); } } @@ -173,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)); } } } @@ -203,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<Simplex_handle> get_address(const Root_simplex_handle & s) const; + // boost::optional<Simplex> get_address(const Root_simplex_handle & s) const; // private: /** @@ -235,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]) { @@ -301,5 +286,5 @@ bool proper_faces_in_union( } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_COMPLEX_H_ +#endif // SKELETON_BLOCKER_SKELETON_BLOCKER_SUB_COMPLEX_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h index 32538f38..eb970195 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h @@ -1,67 +1,70 @@ - /* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): David Salinas - * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ -#ifndef TOP_FACES_H_ -#define TOP_FACES_H_ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef SKELETON_BLOCKER_INTERNAL_TOP_FACES_H_ +#define SKELETON_BLOCKER_INTERNAL_TOP_FACES_H_ #include <list> #include <vector> #include <set> +namespace Gudhi { + +namespace skbl { + template<typename SimplexHandle> -std::list<SimplexHandle> subfaces(SimplexHandle top_face){ - std::list<SimplexHandle> res; - if(top_face.dimension()==-1) return res; - if(top_face.dimension()==0) { - res.push_back(top_face); - return res; - } - else{ - auto first_vertex = top_face.first_vertex(); - top_face.remove_vertex(first_vertex); - res = subfaces(top_face); - std::list<SimplexHandle> copy = res; - for(auto& simplex : copy){ - simplex.add_vertex(first_vertex); - } - res.push_back(SimplexHandle(first_vertex)); - res.splice(res.end(),copy); - return res; - } +std::list<SimplexHandle> subfaces(SimplexHandle top_face) { + std::list<SimplexHandle> res; + if (top_face.dimension() == -1) return res; + if (top_face.dimension() == 0) { + res.push_back(top_face); + return res; + } else { + auto first_vertex = top_face.first_vertex(); + top_face.remove_vertex(first_vertex); + res = subfaces(top_face); + std::list<SimplexHandle> copy = res; + for (auto& simplex : copy) { + simplex.add_vertex(first_vertex); + } + res.push_back(SimplexHandle(first_vertex)); + res.splice(res.end(), copy); + return res; + } } /** * add all faces of top_face in simplices_per_dimension */ template<typename SimplexHandle> -void register_faces( - std::vector< std::set<SimplexHandle> >& simplices_per_dimension, - const SimplexHandle& top_face){ - std::list<SimplexHandle> subfaces_list = subfaces(top_face); - for(auto& simplex : subfaces_list ){ - simplices_per_dimension[simplex.dimension()].insert(simplex); - } +void register_faces(std::vector< std::set<SimplexHandle> >& simplices_per_dimension, + const SimplexHandle& top_face) { + std::list<SimplexHandle> subfaces_list = subfaces(top_face); + for (auto& simplex : subfaces_list) { + simplices_per_dimension[simplex.dimension()].insert(simplex); + } } +} // namespace skbl +} // namespace Gudhi - -#endif /* TOP_FACES_H_ */ +#endif // SKELETON_BLOCKER_INTERNAL_TOP_FACES_H_ 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 f2a443dc..499980c4 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h @@ -1,13 +1,10 @@ -/* - * Trie.h - * Created on: Jan 29, 2015 - * This file is part of the Gudhi Library. The Gudhi library +/* This file is part of the Gudhi Library. The Gudhi library * (Geometric Understanding in Higher Dimensions) is a generic C++ * library for computational topology. * * Author(s): David Salinas * - * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) + * Copyright (C) 2014 INRIA Sophia Antipolis-Méditerranée (France) * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -25,8 +22,8 @@ */ -#ifndef TRIE_H_ -#define TRIE_H_ +#ifndef SKELETON_BLOCKER_INTERNAL_TRIE_H_ +#define SKELETON_BLOCKER_INTERNAL_TRIE_H_ #include <memory> #include <vector> @@ -35,242 +32,237 @@ namespace Gudhi { - namespace skbl { - template<typename SimplexHandle> -struct Trie{ - typedef SimplexHandle Simplex_handle; - typedef typename SimplexHandle::Vertex_handle Vertex_handle; - - Vertex_handle v; - std::vector<std::shared_ptr<Trie> > childs; - //std::vector<std::unique_ptr<Trie> > childs; -> use of deleted function -private: - const Trie* parent_; -public: - Trie():parent_(0){} - Trie(Vertex_handle v_):v(v_),parent_(0){} - - Trie(Vertex_handle v_,Trie* parent):v(v_),parent_(parent){} - - - bool operator==(const Trie& other) const{ - return (v == other.v) ; - } - - void add_child(Trie* child){ - if(child){ - std::shared_ptr<Trie> ptr_to_add(child); - childs.push_back(ptr_to_add); - child->parent_ = this; - } - } - - typedef typename Simplex_handle::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) return 0; - else{ - Trie* res = new Trie(*s_it); - Trie* child = make_trie(++s_it,s_end); - res->add_child(child); - return res; - } - } -private: - //go down recursively in the tree while advancing the simplex iterator. - //when it reaches a leaf, it inserts the remaining that is not present - void add_simplex_helper(Simplex_vertex_const_iterator s_it,Simplex_vertex_const_iterator s_end){ - assert(*s_it == v); - ++s_it; - if(s_it==s_end) return ; - if(!is_leaf()){ - for(auto child : childs){ - if(child->v == *s_it) - return child->add_simplex_helper(s_it,s_end); - } - //s_it is not found and needs to be inserted - } - //not leaf -> remaining of s needs to be inserted - Trie* son_with_what_remains_of_s(make_trie(s_it,s_end)); - add_child(son_with_what_remains_of_s); - return; - } - - void maximal_faces_helper(std::vector<Simplex_handle>& res) const{ - if(is_leaf()) res.push_back(simplex()); - else - for(auto child : childs) - child->maximal_faces_helper(res); - } - -public: - /** - * adds the simplex to the trie - */ - void add_simplex(const Simplex_handle& s){ - if(s.empty()) return; - assert(v==s.first_vertex()); - add_simplex_helper(s.begin(),s.end()); - } - - std::vector<Simplex_handle> maximal_faces() const{ - std::vector<Simplex_handle> res; - maximal_faces_helper(res); - return res; - } - - /** - * Goes to the root in the trie to consitute simplex - */ - void add_vertices_up_to_the_root(Simplex_handle& res) const{ - res.add_vertex(v); - if(parent_) - parent_->add_vertices_up_to_the_root(res); - } - - Simplex_handle simplex() const{ - Simplex_handle res; - add_vertices_up_to_the_root(res); - return res; - } - - bool is_leaf() const{ - return childs.empty(); - } - - bool is_root() const{ - return parent_==0; - } - - const Trie* parent() { - return parent_; - } - - void remove_leaf() { - assert(is_leaf); - if(!is_root()) - parent_->childs.erase(this); - } - - /** - * true iff the simplex corresponds to one node in the trie - */ - bool contains(const Simplex_handle& s) const{ - Trie const* current = this; - if(s.empty()) return true; - if(current->v != s.first_vertex()) return false; - auto s_pos = s.begin(); - ++s_pos; - while(s_pos != s.end() && current != 0){ - bool found = false; - for(const auto child : current->childs){ - if(child->v == *s_pos) { - ++s_pos; - current = child.get(); - found = true; - break; - } - } - if(!found) return false; - } - return current!=0; - } - - Trie* go_bottom_left(){ - if(is_leaf()) - return this; - else - return (*childs.begin())->go_bottom_left(); - } - - friend std::ostream& operator<<(std::ostream& stream, const Trie& trie){ - stream<< "T( "<< trie.v<< " "; - for(auto t : trie.childs) - stream << *t ; - stream<<")"; - return stream; - } +struct Trie { + typedef SimplexHandle Simplex; + typedef typename SimplexHandle::Vertex_handle Vertex_handle; + + Vertex_handle v; + std::vector<std::shared_ptr<Trie> > childs; + // std::vector<std::unique_ptr<Trie> > childs; -> use of deleted function + private: + const Trie* parent_; + + public: + Trie() : parent_(0) { } + + Trie(Vertex_handle v_) : v(v_), parent_(0) { } + + Trie(Vertex_handle v_, Trie* parent) : v(v_), parent_(parent) { } + + bool operator==(const Trie& other) const { + return (v == other.v); + } + + void add_child(Trie* child) { + if (child) { + std::shared_ptr<Trie> ptr_to_add(child); + childs.push_back(ptr_to_add); + child->parent_ = this; + } + } + + 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) { + return 0; + } else { + Trie* res = new Trie(*s_it); + Trie* child = make_trie(++s_it, s_end); + res->add_child(child); + return res; + } + } + + private: + // go down recursively in the tree while advancing the simplex iterator. + // when it reaches a leaf, it inserts the remaining that is not present + void add_simplex_helper(Simplex_vertex_const_iterator s_it, Simplex_vertex_const_iterator s_end) { + assert(*s_it == v); + ++s_it; + if (s_it == s_end) return; + if (!is_leaf()) { + for (auto child : childs) { + if (child->v == *s_it) + return child->add_simplex_helper(s_it, s_end); + } + // s_it is not found and needs to be inserted + } + // not leaf -> remaining of s needs to be inserted + Trie * son_with_what_remains_of_s(make_trie(s_it, s_end)); + add_child(son_with_what_remains_of_s); + return; + } + + void maximal_faces_helper(std::vector<Simplex>& res) const { + if (is_leaf()) res.push_back(simplex()); + else + for (auto child : childs) + child->maximal_faces_helper(res); + } + + public: + /** + * adds the simplex to the trie + */ + void add_simplex(const Simplex& s) { + if (s.empty()) return; + assert(v == s.first_vertex()); + add_simplex_helper(s.begin(), s.end()); + } + + std::vector<Simplex> maximal_faces() const { + std::vector<Simplex> res; + maximal_faces_helper(res); + return res; + } + + /** + * Goes to the root in the trie to consitute simplex + */ + 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 simplex() const { + Simplex res; + add_vertices_up_to_the_root(res); + return res; + } + + bool is_leaf() const { + return childs.empty(); + } + + bool is_root() const { + return parent_ == 0; + } + + const Trie* parent() { + return parent_; + } + + void remove_leaf() { + assert(is_leaf); + if (!is_root()) + parent_->childs.erase(this); + } + + /** + * true iff the simplex corresponds to one node in the trie + */ + bool contains(const Simplex& s) const { + Trie const* current = this; + if (s.empty()) return true; + if (current->v != s.first_vertex()) return false; + auto s_pos = s.begin(); + ++s_pos; + while (s_pos != s.end() && current != 0) { + bool found = false; + for (const auto child : current->childs) { + if (child->v == *s_pos) { + ++s_pos; + current = child.get(); + found = true; + break; + } + } + if (!found) return false; + } + return current != 0; + } + + Trie* go_bottom_left() { + if (is_leaf()) + return this; + else + return (*childs.begin())->go_bottom_left(); + } + + friend std::ostream& operator<<(std::ostream& stream, const Trie& trie) { + stream << "T( " << trie.v << " "; + for (auto t : trie.childs) + stream << *t; + stream << ")"; + return stream; + } }; - template<typename SimplexHandle> -struct Tries{ - typedef typename SimplexHandle::Vertex_handle Vertex_handle; - typedef SimplexHandle Simplex_handle; - - typedef Trie<Simplex_handle> STrie; - - - template<typename SimpleHandleOutputIterator> - Tries(unsigned num_vertices,SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end): - cofaces_(num_vertices,0){ - for (auto i = 0u; i < num_vertices; ++i) - cofaces_[i] = new STrie(Vertex_handle(i)); - for (auto s_it = simplex_begin; s_it != simplex_end; ++s_it) { - if (s_it->dimension() >= 1) - cofaces_[s_it->first_vertex()]->add_simplex(*s_it); - } - } - - ~Tries(){ - for(STrie* t : cofaces_) - delete t; - } - - //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; - for(auto child : cofaces_[v]->childs) - res.add_vertex(child->v); - return res; - } - - bool contains(const Simplex_handle& s) const{ - auto first_v = s.first_vertex(); - return cofaces_[first_v]->contains(s); - } - - friend std::ostream& operator<<(std::ostream& stream, const Tries& tries){ - for(auto trie : tries.cofaces_) - stream<<*trie<<std::endl; - return stream; - } - - //init_next_dimension must be called first - std::vector<Simplex_handle> next_dimension_simplices() const{ - std::vector<Simplex_handle> 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) - to_see_.push_back(child.get()); - to_see_.pop_front(); - } - ++current_dimension_; - return res; - } - - void init_next_dimension() const{ - for(auto trie : cofaces_) - to_see_.push_back(trie); - } - -private: - mutable std::deque<STrie*> to_see_; - mutable unsigned current_dimension_=0; - - - std::vector<STrie*> cofaces_; - +struct Tries { + typedef typename SimplexHandle::Vertex_handle Vertex_handle; + typedef SimplexHandle Simplex; + + typedef Trie<Simplex> STrie; + + template<typename SimpleHandleOutputIterator> + Tries(unsigned num_vertices, SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) : + cofaces_(num_vertices, 0) { + for (auto i = 0u; i < num_vertices; ++i) + cofaces_[i] = new STrie(Vertex_handle(i)); + for (auto s_it = simplex_begin; s_it != simplex_end; ++s_it) { + if (s_it->dimension() >= 1) + cofaces_[s_it->first_vertex()]->add_simplex(*s_it); + } + } + + ~Tries() { + for (STrie* t : cofaces_) + delete t; + } + + // return a simplex that consists in all u such uv is an edge and u>v + + 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& s) const { + auto first_v = s.first_vertex(); + return cofaces_[first_v]->contains(s); + } + + friend std::ostream& operator<<(std::ostream& stream, const Tries& tries) { + for (auto trie : tries.cofaces_) + stream << *trie << std::endl; + return stream; + } + + // init_next_dimension must be called first + + std::vector<Simplex> next_dimension_simplices() const { + std::vector<Simplex> 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) + to_see_.push_back(child.get()); + to_see_.pop_front(); + } + ++current_dimension_; + return res; + } + + void init_next_dimension() const { + for (auto trie : cofaces_) + to_see_.push_back(trie); + } + + private: + mutable std::deque<STrie*> to_see_; + mutable unsigned current_dimension_ = 0; + std::vector<STrie*> cofaces_; }; +} // namespace skbl +} // namespace Gudhi -} - -} - -#endif /* TRIE_H_ */ +#endif // SKELETON_BLOCKER_INTERNAL_TRIE_H_ 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 f6f2c955..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 @@ -1,134 +1,131 @@ - /* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): David Salinas - * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ -#ifndef GUDHI_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ -#define GUDHI_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ - -#include "boost/iterator/iterator_facade.hpp" - -namespace Gudhi{ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ +#define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ + +#include <boost/iterator/iterator_facade.hpp> + +namespace Gudhi { 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<typename MapIteratorType, typename ReturnType> class Blocker_iterator_internal : public boost::iterator_facade< - Blocker_iterator_internal<MapIteratorType,ReturnType>, - ReturnType, - boost::forward_traversal_tag, - ReturnType - >{ -private: - MapIteratorType current_position; - MapIteratorType end_of_map; -public: - - Blocker_iterator_internal():current_position(){} - - Blocker_iterator_internal(MapIteratorType position,MapIteratorType end_of_map_ ): - current_position(position), end_of_map(end_of_map_) - { } - - bool equal(const Blocker_iterator_internal& other) const{ - return current_position == other.current_position; - } - - void increment(){ - goto_next_blocker(); - } - - ReturnType dereference() const { - return(current_position->second); - } - -private: - /** - * Let the current pair be (v,sigma) where v is a vertex and sigma is a blocker. - * If v is not the first vertex of sigma then we already have seen sigma as a blocker - * and we look for the next one. - */ - void goto_next_blocker(){ - do { - ++current_position; - } while (!(current_position == end_of_map) && !first_time_blocker_is_seen()); - } - - bool first_time_blocker_is_seen() const{ - return current_position->first == current_position->second->first_vertex(); - } +Blocker_iterator_internal<MapIteratorType, ReturnType>, +ReturnType, +boost::forward_traversal_tag, +ReturnType +> { + private: + MapIteratorType current_position; + MapIteratorType end_of_map; + + public: + Blocker_iterator_internal() : current_position() { } + + Blocker_iterator_internal(MapIteratorType position, MapIteratorType end_of_map_) : + current_position(position), end_of_map(end_of_map_) { } + + bool equal(const Blocker_iterator_internal& other) const { + return current_position == other.current_position; + } + + void increment() { + goto_next_blocker(); + } + + ReturnType dereference() const { + return (current_position->second); + } + + private: + /** + * Let the current pair be (v,sigma) where v is a vertex and sigma is a blocker. + * If v is not the first vertex of sigma then we already have seen sigma as a blocker + * and we look for the next one. + */ + void goto_next_blocker() { + do { + ++current_position; + } while (!(current_position == end_of_map) && !first_time_blocker_is_seen()); + } + + bool first_time_blocker_is_seen() const { + return current_position->first == current_position->second->first_vertex(); + } }; - - /** * @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<typename MapIteratorType, typename ReturnType> class Blocker_iterator_around_vertex_internal : public boost::iterator_facade< - Blocker_iterator_around_vertex_internal<MapIteratorType,ReturnType>, - ReturnType, - boost::forward_traversal_tag, - ReturnType ->{ -private: - MapIteratorType current_position_; -public: - - Blocker_iterator_around_vertex_internal():current_position_(){} - - Blocker_iterator_around_vertex_internal(MapIteratorType position): - current_position_(position) - {} - - Blocker_iterator_around_vertex_internal& operator=(Blocker_iterator_around_vertex_internal other){ - this->current_position_ = other.current_position_; - return *this; - } - - bool equal(const Blocker_iterator_around_vertex_internal& other) const{ - return current_position_ == other.current_position_; - } - - void increment(){ - current_position_++; - } - - ReturnType dereference() const{ - return(current_position_->second); - } - - - MapIteratorType current_position(){ - return this->current_position_; - } +Blocker_iterator_around_vertex_internal<MapIteratorType, ReturnType>, +ReturnType, +boost::forward_traversal_tag, +ReturnType +> { + private: + MapIteratorType current_position_; + + public: + Blocker_iterator_around_vertex_internal() : current_position_() { } + + Blocker_iterator_around_vertex_internal(MapIteratorType position) : + current_position_(position) { } + + Blocker_iterator_around_vertex_internal& operator=(Blocker_iterator_around_vertex_internal other) { + this->current_position_ = other.current_position_; + return *this; + } + + bool equal(const Blocker_iterator_around_vertex_internal& other) const { + return current_position_ == other.current_position_; + } + + void increment() { + current_position_++; + } + + ReturnType dereference() const { + return (current_position_->second); + } + + MapIteratorType current_position() { + return this->current_position_; + } }; -} +} // namespace skbl -} // namespace GUDHI +} // namespace Gudhi -#endif /* GUDHI_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ */ +#endif // SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_BLOCKERS_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h index 0be6c74d..ef4c7970 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h @@ -1,167 +1,144 @@ - /* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): David Salinas - * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ -#ifndef GUDHI_SKELETON_BLOCKERS_ITERATORS_EDGES_H_ -#define GUDHI_SKELETON_BLOCKERS_ITERATORS_EDGES_H_ - -#include "boost/iterator/iterator_facade.hpp" - - -namespace Gudhi{ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_EDGES_ITERATORS_H_ +#define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_EDGES_ITERATORS_H_ + +#include <boost/iterator/iterator_facade.hpp> +#include <boost/graph/adjacency_list.hpp> + +#include <utility> // for pair<> + +namespace Gudhi { namespace skbl { template<typename SkeletonBlockerComplex> -class Edge_around_vertex_iterator : - public boost::iterator_facade < Edge_around_vertex_iterator<SkeletonBlockerComplex> - , typename SkeletonBlockerComplex::Edge_handle const - , boost::forward_traversal_tag - , typename SkeletonBlockerComplex::Edge_handle const - > -{ - friend class boost::iterator_core_access; - - typedef SkeletonBlockerComplex Complex; - typedef typename Complex::boost_adjacency_iterator boost_adjacency_iterator; - typedef typename Complex::Vertex_handle Vertex_handle; - typedef typename Complex::Edge_handle Edge_handle; - -private: - - const Complex* complex; - Vertex_handle v; - - boost_adjacency_iterator current_; - boost_adjacency_iterator end_; - -public: - - Edge_around_vertex_iterator():complex(NULL){ - } - - Edge_around_vertex_iterator(const Complex* complex_,Vertex_handle v_): - complex(complex_), - v(v_) - { - tie(current_,end_) = adjacent_vertices(v.vertex, complex->skeleton); - } - - /** - * returns an iterator to the end - */ - Edge_around_vertex_iterator(const Complex* complex_,Vertex_handle v_,int end): - complex(complex_), - v(v_) - { - tie(current_,end_) = adjacent_vertices(v.vertex, complex->skeleton); - set_end(); - } - - bool equal(const Edge_around_vertex_iterator& other) const{ - return (complex== other.complex) && (v == other.v) && (current_ == other.current_) && (end_ == other.end_); - } - - void increment(){ - if(current_ != end_) - ++current_; - } - - Edge_handle dereference() const{ - return *(*complex)[std::make_pair(v,static_cast<Vertex_handle>(*current_))]; - } - -private: - //remove this ugly hack - void set_end(){ - current_ = end_; - } +class Edge_around_vertex_iterator : public boost::iterator_facade <Edge_around_vertex_iterator<SkeletonBlockerComplex> +, typename SkeletonBlockerComplex::Edge_handle const, boost::forward_traversal_tag +, typename SkeletonBlockerComplex::Edge_handle const> { + friend class boost::iterator_core_access; + + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::boost_adjacency_iterator boost_adjacency_iterator; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Edge_handle Edge_handle; + + private: + const Complex* complex; + Vertex_handle v; + + boost_adjacency_iterator current_; + boost_adjacency_iterator end_; + + public: + Edge_around_vertex_iterator() : complex(NULL) { } + + Edge_around_vertex_iterator(const Complex* complex_, Vertex_handle v_) : + complex(complex_), + v(v_) { + tie(current_, end_) = adjacent_vertices(v.vertex, complex->skeleton); + } + + /** + * returns an iterator to the end + */ + Edge_around_vertex_iterator(const Complex* complex_, Vertex_handle v_, int end) : + complex(complex_), + v(v_) { + tie(current_, end_) = adjacent_vertices(v.vertex, complex->skeleton); + set_end(); + } + + bool equal(const Edge_around_vertex_iterator& other) const { + return (complex == other.complex) && (v == other.v) && (current_ == other.current_) && (end_ == other.end_); + } + + void increment() { + if (current_ != end_) + ++current_; + } + + Edge_handle dereference() const { + return *(*complex)[std::make_pair(v, static_cast<Vertex_handle> (*current_))]; + } + + private: + // remove this ugly hack + void set_end() { + current_ = end_; + } }; - - /** *@brief Iterator on the edges of a simplicial complex. * */ template<typename SkeletonBlockerComplex> -class Edge_iterator : -public boost::iterator_facade < Edge_iterator<SkeletonBlockerComplex> +class Edge_iterator : public boost::iterator_facade <Edge_iterator<SkeletonBlockerComplex> , typename SkeletonBlockerComplex::Edge_handle const , boost::forward_traversal_tag -, typename SkeletonBlockerComplex::Edge_handle const -> - -{ - friend class boost::iterator_core_access; -public: - typedef SkeletonBlockerComplex Complex; - typedef typename Complex::boost_edge_iterator boost_edge_iterator; - typedef typename Complex::Edge_handle Edge_handle; - - - const Complex* complex; - std::pair<boost_edge_iterator,boost_edge_iterator> edge_iterator ; - - Edge_iterator():complex(NULL){ - } - - Edge_iterator(const SkeletonBlockerComplex* complex_): - complex(complex_), - edge_iterator(boost::edges(complex_->skeleton)) - { - } - - /** - * return an iterator to the end - */ - Edge_iterator(const SkeletonBlockerComplex* complex_,int end): - complex(complex_), - edge_iterator(boost::edges(complex_->skeleton)) - { - edge_iterator.first = edge_iterator.second; - } - - - bool equal(const Edge_iterator& other) const{ - return (complex == other.complex) && (edge_iterator == other.edge_iterator); - } - - void increment(){ - if(edge_iterator.first != edge_iterator.second){ - ++(edge_iterator.first); - } - } - - Edge_handle dereference() const{ - return(*(edge_iterator.first)); - } +, typename SkeletonBlockerComplex::Edge_handle const> { + friend class boost::iterator_core_access; + + public: + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::boost_edge_iterator boost_edge_iterator; + typedef typename Complex::Edge_handle Edge_handle; + + const Complex* complex; + std::pair<boost_edge_iterator, boost_edge_iterator> edge_iterator; + + Edge_iterator() : complex(NULL) { } + + Edge_iterator(const SkeletonBlockerComplex* complex_) : + complex(complex_), + edge_iterator(boost::edges(complex_->skeleton)) { } + + /** + * return an iterator to the end + */ + Edge_iterator(const SkeletonBlockerComplex* complex_, int end) : + complex(complex_), + edge_iterator(boost::edges(complex_->skeleton)) { + edge_iterator.first = edge_iterator.second; + } + + bool equal(const Edge_iterator& other) const { + return (complex == other.complex) && (edge_iterator == other.edge_iterator); + } + + void increment() { + if (edge_iterator.first != edge_iterator.second) { + ++(edge_iterator.first); + } + } + + Edge_handle dereference() const { + return (*(edge_iterator.first)); + } }; +} // namespace skbl +} // namespace Gudhi -} - -} // namespace GUDHI - - -#endif /* GUDHI_SKELETON_BLOCKERS_ITERATORS_EDGES_H_ */ - - +#endif // SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_EDGES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h index 20a94734..cc3ed276 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h @@ -19,17 +19,14 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef GUDHI_SKELETON_BLOCKERS_ITERATORS_H_ -#define GUDHI_SKELETON_BLOCKERS_ITERATORS_H_ +#ifndef SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_ITERATORS_H_ +#define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_ITERATORS_H_ -#include "Skeleton_blockers_vertices_iterators.h" -#include "Skeleton_blockers_edges_iterators.h" -#include "Skeleton_blockers_blockers_iterators.h" -#include "Skeleton_blockers_triangles_iterators.h" -#include "Skeleton_blockers_simplices_iterators.h" +#include <gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h> +#include <gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h> +#include <gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h> +#include <gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h> +#include <gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h> - - - -#endif /* GUDHI_SKELETON_BLOCKERS_ITERATORS_H_ */ +#endif // SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_ITERATORS_H_ 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 666ce430..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 @@ -1,46 +1,42 @@ - /* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): David Salinas - * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ -#ifndef GUDHI_KELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ -#define GUDHI_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ +#define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ + +#include <gudhi/Skeleton_blocker_link_complex.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h> +#include <gudhi/Skeleton_blocker/internal/Trie.h> +#include <gudhi/Utils.h> + +#include <boost/iterator/iterator_facade.hpp> #include <memory> #include <list> #include <iostream> -#include "gudhi/Utils.h" -#include "boost/iterator/iterator_facade.hpp" - - -#include "gudhi/Skeleton_blocker_link_complex.h" -#include "gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h" - -#include "gudhi/Skeleton_blocker/internal/Trie.h" - namespace Gudhi { - namespace skbl { - /** * Link may be Skeleton_blocker_link_complex<SkeletonBlockerComplex> to iterate over all * simplices around a vertex OR @@ -49,299 +45,354 @@ namespace skbl { * The iteration is done by computing a trie with the link and doing a breadth-first traversal * of the trie. */ -template<typename SkeletonBlockerComplex,typename Link> +template<typename SkeletonBlockerComplex, typename Link> class Simplex_around_vertex_iterator : - public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerComplex,Link> -, typename SkeletonBlockerComplex::Simplex_handle +public boost::iterator_facade < Simplex_around_vertex_iterator<SkeletonBlockerComplex, Link> +, typename SkeletonBlockerComplex::Simplex , boost::forward_traversal_tag -, typename SkeletonBlockerComplex::Simplex_handle -> -{ - 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 Link::Vertex_handle Link_vertex_handle; - // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion - - typedef typename Gudhi::skbl::Trie<Simplex_handle> Trie; - - -private: - const Complex* complex; - Vertex_handle v; - std::shared_ptr<Link> link_v; - std::shared_ptr<Trie> trie; - std::list<Trie*> nodes_to_be_seen; // todo deque - -public: - Simplex_around_vertex_iterator():complex(0){ - } - - Simplex_around_vertex_iterator(const Complex* complex_,Vertex_handle v_): - complex(complex_), - v(v_), - link_v(new Link(*complex_,v_)), - trie(new Trie(v_)){ - compute_trie_and_nodes_to_be_seen(); - } - - // todo avoid useless copy - // todo currently just work if copy begin iterator - Simplex_around_vertex_iterator(const Simplex_around_vertex_iterator& other): - complex(other.complex), - v(other.v), - link_v(other.link_v), - trie(other.trie), - nodes_to_be_seen(other.nodes_to_be_seen){ - if(!other.is_end()){ - } - } - - /** - * returns an iterator to the end - */ - Simplex_around_vertex_iterator(const Complex* complex_,Vertex_handle v_,bool end): - complex(complex_), - v(v_){ - set_end(); - } - -private: - - - void compute_trie_and_nodes_to_be_seen(){ - // once we go through every simplices passing through v0 - // we remove v0. That way, it prevents from passing a lot of times - // though edges leaving v0. - // another solution would have been to provides an adjacency iterator - // to superior vertices that avoids lower ones. - while(!link_v->empty()){ - auto v0 = *(link_v->vertex_range().begin()); - trie->add_child(build_trie(v0,trie.get())); - link_v->remove_vertex(v0); - } - nodes_to_be_seen.push_back(trie.get()); - } - - Trie* build_trie(Link_vertex_handle link_vh,Trie* parent){ - Trie* res = new Trie(parent_vertex(link_vh),parent); - for(Link_vertex_handle nv : link_v->vertex_range(link_vh)) { - if(link_vh < nv){ - Simplex_handle 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)); - } - } - } - return res; - } - - bool is_node_in_complex(Trie* trie){ - return true; - } - - Vertex_handle parent_vertex(Link_vertex_handle link_vh) const{ - return complex->convert_handle_from_another_complex(*link_v,link_vh); - } - - - -public: - - friend std::ostream& operator<<(std::ostream& stream, const Simplex_around_vertex_iterator& savi){ - stream<< savi.trie<< std::endl; ; - stream << "("<<savi.nodes_to_be_seen.size()<<") nodes to see\n"; - return stream; - } - - bool equal(const Simplex_around_vertex_iterator& other) const{ - bool same_complex = (complex == other.complex); - if(!same_complex) - return false; - - if(!(v == other.v)) - return false; - - bool both_empty = nodes_to_be_seen.empty() && other.nodes_to_be_seen.empty(); - if(both_empty) - return true; - - bool both_non_empty = !nodes_to_be_seen.empty() && !other.nodes_to_be_seen.empty(); - - if(!both_non_empty) return false; //one is empty the other is not - - bool same_node = (**(nodes_to_be_seen.begin()) == **(other.nodes_to_be_seen.begin())); - return same_node; - } - - void increment(){ - assert(!is_end()); - Trie* first_node = nodes_to_be_seen.front(); - - nodes_to_be_seen.pop_front(); - - for(auto childs : first_node->childs){ - nodes_to_be_seen.push_back(childs.get()); - } - - } - - Simplex_handle dereference() const{ - assert(!nodes_to_be_seen.empty()); - Trie* first_node = nodes_to_be_seen.front(); - return first_node->simplex(); - } - -//private: - Simplex_handle get_trie_address() const{ - assert(!nodes_to_be_seen.empty()); - return nodes_to_be_seen.front(); - } - -private: - void set_end(){ - nodes_to_be_seen.clear(); - } - - bool is_end() const{ - return nodes_to_be_seen.empty(); - } +, 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; + + // 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<Simplex> Trie; + + private: + const Complex* complex; + Vertex_handle v; + std::shared_ptr<Link> link_v; + std::shared_ptr<Trie> trie; + std::list<Trie*> nodes_to_be_seen; // todo deque + + public: + Simplex_around_vertex_iterator() : complex(0) {} + + Simplex_around_vertex_iterator(const Complex* complex_, Vertex_handle v_) : + complex(complex_), + v(v_), + link_v(new Link(*complex_, v_)), + trie(new Trie(v_)) { + compute_trie_and_nodes_to_be_seen(); + } + + // todo avoid useless copy + // todo currently just work if copy begin iterator + Simplex_around_vertex_iterator(const Simplex_around_vertex_iterator& other) : + complex(other.complex), + v(other.v), + link_v(other.link_v), + trie(other.trie), + nodes_to_be_seen(other.nodes_to_be_seen) { + if (!other.is_end()) {} + } + + /** + * returns an iterator to the end + */ + Simplex_around_vertex_iterator(const Complex* complex_, Vertex_handle v_, bool end) : + complex(complex_), + v(v_) { + set_end(); + } + + private: + void compute_trie_and_nodes_to_be_seen() { + // once we go through every simplices passing through v0 + // we remove v0. That way, it prevents from passing a lot of times + // though edges leaving v0. + // another solution would have been to provides an adjacency iterator + // to superior vertices that avoids lower ones. + while (!link_v->empty()) { + auto v0 = *(link_v->vertex_range().begin()); + trie->add_child(build_trie(v0, trie.get())); + link_v->remove_vertex(v0); + } + nodes_to_be_seen.push_back(trie.get()); + } + + Trie* build_trie(Link_vertex_handle link_vh, Trie* parent) { + Trie* res = new Trie(parent_vertex(link_vh), parent); + for (Link_vertex_handle nv : link_v->vertex_range(link_vh)) { + if (link_vh < nv) { + 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)); + } + } + } + return res; + } + + bool is_node_in_complex(Trie* trie) { + return true; + } + + Vertex_handle parent_vertex(Link_vertex_handle link_vh) const { + return complex->convert_handle_from_another_complex(*link_v, link_vh); + } + + public: + friend std::ostream& operator<<(std::ostream& stream, const Simplex_around_vertex_iterator& savi) { + stream << savi.trie << std::endl; + stream << "(" << savi.nodes_to_be_seen.size() << ") nodes to see\n"; + return stream; + } + + bool equal(const Simplex_around_vertex_iterator& other) const { + bool same_complex = (complex == other.complex); + if (!same_complex) + return false; + + if (!(v == other.v)) + return false; + + bool both_empty = nodes_to_be_seen.empty() && other.nodes_to_be_seen.empty(); + if (both_empty) + return true; + + bool both_non_empty = !nodes_to_be_seen.empty() && !other.nodes_to_be_seen.empty(); + + if (!both_non_empty) return false; // one is empty the other is not + + bool same_node = (**(nodes_to_be_seen.begin()) == **(other.nodes_to_be_seen.begin())); + return same_node; + } + + void increment() { + assert(!is_end()); + Trie* first_node = nodes_to_be_seen.front(); + + nodes_to_be_seen.pop_front(); + + for (auto childs : first_node->childs) { + nodes_to_be_seen.push_back(childs.get()); + } + } + + Simplex dereference() const { + assert(!nodes_to_be_seen.empty()); + Trie* first_node = nodes_to_be_seen.front(); + return first_node->simplex(); + } + + Simplex get_trie_address() const { + assert(!nodes_to_be_seen.empty()); + return nodes_to_be_seen.front(); + } + + private: + void set_end() { + nodes_to_be_seen.clear(); + } + + bool is_end() const { + return nodes_to_be_seen.empty(); + } }; - - template<typename SkeletonBlockerComplex> class Simplex_iterator : - public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> -, typename SkeletonBlockerComplex::Simplex_handle +public boost::iterator_facade < Simplex_iterator<SkeletonBlockerComplex> +, typename SkeletonBlockerComplex::Simplex , boost::forward_traversal_tag -, typename SkeletonBlockerComplex::Simplex_handle -> -{ - typedef Skeleton_blocker_link_superior<SkeletonBlockerComplex> Link; - - friend class boost::iterator_core_access; - - template<class SkBlDS> friend class Skeleton_blocker_complex; - - - 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::Complex_vertex_iterator Complex_vertex_iterator; - - - typedef typename Link::Vertex_handle Link_vertex_handle; - -private: - - const Complex* complex_; - Complex_vertex_iterator current_vertex_; - - typedef Simplex_around_vertex_iterator<SkeletonBlockerComplex,Link> SAVI; - SAVI current_simplex_around_current_vertex_; - SAVI simplices_around_current_vertex_end_; - - -public: - Simplex_iterator():complex_(0){} - - // should not be called if the complex is empty - Simplex_iterator(const Complex* complex): - complex_(complex), - current_vertex_(complex->vertex_range().begin()), - current_simplex_around_current_vertex_(complex,*current_vertex_), - simplices_around_current_vertex_end_(complex,*current_vertex_,true) - { - assert(!complex->empty()); - } +, typename SkeletonBlockerComplex::Simplex +> { + typedef Skeleton_blocker_link_superior<SkeletonBlockerComplex> Link; + + friend class boost::iterator_core_access; + + template<class SkBlDS> friend class Skeleton_blocker_complex; + + 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; + typedef typename Link::Vertex_handle Link_vertex_handle; + + private: + const Complex* complex_; + Complex_vertex_iterator current_vertex_; + + typedef Simplex_around_vertex_iterator<SkeletonBlockerComplex, Link> SAVI; + SAVI current_simplex_around_current_vertex_; + SAVI simplices_around_current_vertex_end_; + + public: + Simplex_iterator() : complex_(0) { } + + Simplex_iterator(const Complex* complex) : + complex_(complex), + current_vertex_(complex->vertex_range().begin()), + current_simplex_around_current_vertex_(complex, *current_vertex_), + simplices_around_current_vertex_end_(complex, *current_vertex_, true) { + // should not be called if the complex is empty + assert(!complex->empty()); + } + + private: + // todo return to private + Simplex_iterator(const Complex* complex, bool end) : + complex_(complex) { + set_end(); + } + + public: + Simplex_iterator(const Simplex_iterator& other) + : + complex_(other.complex_), + current_vertex_(other.current_vertex_), + current_simplex_around_current_vertex_(other.current_simplex_around_current_vertex_), + simplices_around_current_vertex_end_(other.simplices_around_current_vertex_end_) { } + + friend Simplex_iterator make_begin_iterator(const Complex* complex) { + if (complex->empty()) + return make_end_simplex_iterator(complex); + else + return Simplex_iterator(complex); + } + + friend Simplex_iterator make_end_simplex_iterator(const Complex* complex) { + return Simplex_iterator(complex, true); + } + + bool equal(const Simplex_iterator& other) const { + if (complex_ != other.complex_) return false; + if (current_vertex_ != other.current_vertex_) return false; + if (is_end() && other.is_end()) return true; + if (current_simplex_around_current_vertex_ != other.current_simplex_around_current_vertex_) + return false; + return true; + } + + void increment() { + if (current_simplex_around_current_vertex_ != simplices_around_current_vertex_end_) { + current_simplex_around_current_vertex_.increment(); + if (current_simplex_around_current_vertex_ == simplices_around_current_vertex_end_) + goto_next_vertex(); + } else { + goto_next_vertex(); + } + } + + void goto_next_vertex() { + current_vertex_.increment(); + if (!is_end()) { + current_simplex_around_current_vertex_ = SAVI(complex_, *current_vertex_); + simplices_around_current_vertex_end_ = SAVI(complex_, *current_vertex_, true); + } + } + + Simplex dereference() const { + return current_simplex_around_current_vertex_.dereference(); + } + + private: + void set_end() { + current_vertex_ = complex_->vertex_range().end(); + } + + bool is_end() const { + return (current_vertex_ == complex_->vertex_range().end()); + } +}; -private: - // todo return to private - Simplex_iterator(const Complex* complex,bool end): - complex_(complex) - { - set_end(); - } +/** + * Iterator through the maximal faces of the coboundary of a simplex. + */ +template<typename SkeletonBlockerComplex, typename Link> +class Simplex_coboundary_iterator : +public boost::iterator_facade < Simplex_coboundary_iterator<SkeletonBlockerComplex, Link> +, 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> 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: - - Simplex_iterator(const Simplex_iterator& other) - : - complex_(other.complex_), - current_vertex_(other.current_vertex_), - current_simplex_around_current_vertex_(other.current_simplex_around_current_vertex_), - simplices_around_current_vertex_end_(other.simplices_around_current_vertex_end_) - { - } - - friend Simplex_iterator make_begin_iterator(const Complex* complex){ - if(complex->empty()) - return make_end_simplex_iterator(complex); - else - return Simplex_iterator(complex); - } - - friend Simplex_iterator make_end_simplex_iterator(const Complex* complex){ - return Simplex_iterator(complex,true); - } - - bool equal(const Simplex_iterator& other) const{ - if(complex_!=other.complex_) return false; - if(current_vertex_!=other.current_vertex_) return false; - if(is_end() && other.is_end()) return true; - if(current_simplex_around_current_vertex_ != other.current_simplex_around_current_vertex_) - return false; - return true; - } - - void increment(){ - if(current_simplex_around_current_vertex_!= simplices_around_current_vertex_end_){ - current_simplex_around_current_vertex_.increment(); - if( current_simplex_around_current_vertex_== simplices_around_current_vertex_end_) - goto_next_vertex(); - } - else{ - goto_next_vertex(); - } - } - - void goto_next_vertex(){ - current_vertex_.increment(); - if(!is_end()){ - current_simplex_around_current_vertex_= SAVI(complex_,*current_vertex_); - simplices_around_current_vertex_end_ = SAVI(complex_,*current_vertex_,true); - } - } - - Simplex_handle dereference() const{ - return current_simplex_around_current_vertex_.dereference(); - } + 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: - void set_end(){ - current_vertex_ = complex_->vertex_range().end(); - } - - bool is_end() const{ - return (current_vertex_ == complex_->vertex_range().end()); - } + bool is_end() const { + return !link || current_vertex == link_vertex_end; + } }; -} - -} // namespace GUDHI - - - +} // namespace skbl +} // namespace Gudhi -#endif /* SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ */ +#endif // SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_SIMPLICES_ITERATORS_H_ 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 e137d1ea..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 @@ -1,117 +1,108 @@ - /* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): David Salinas - * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ -#ifndef GUDHI_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ -#define GUDHI_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ - -#include "boost/iterator/iterator_facade.hpp" +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ +#define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ + +#include <boost/iterator/iterator_facade.hpp> #include <memory> -namespace Gudhi{ +namespace Gudhi { namespace skbl { -////////////////////////////////////////////////////////////////////// /** * \brief Iterator over the triangles that are * adjacent to a vertex of the simplicial complex. * \remark Will be removed soon -> dont look */ -template<typename Complex,typename LinkType> +template<typename Complex, typename LinkType> class Triangle_around_vertex_iterator : public boost::iterator_facade -< Triangle_around_vertex_iterator <Complex,LinkType> -, typename Complex::Simplex_handle const +< Triangle_around_vertex_iterator <Complex, LinkType> +, typename Complex::Simplex const , boost::forward_traversal_tag -, typename Complex::Simplex_handle const -> -{ - friend class boost::iterator_core_access; - template<typename T> 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 Complex::Complex_edge_iterator Complex_edge_iterator_; - - const Complex* complex_; - Vertex_handle v_; - std::shared_ptr<LinkType> link_; - Complex_edge_iterator_ current_edge_; - bool is_end_; -public: - Triangle_around_vertex_iterator(const Complex* complex,Vertex_handle v): - complex_(complex),v_(v),link_(new LinkType(*complex,v_)), - current_edge_(link_->edge_range().begin()), - is_end_(current_edge_ == link_->edge_range().end()){ - } - - /** - * @brief ugly hack to get an iterator to the end - */ - Triangle_around_vertex_iterator(const Complex* complex,Vertex_handle v,bool is_end): - complex_(complex),v_(v),link_(0),is_end_(true){ - } - - /** - * @brief ugly hack to get an iterator to the end - */ - Triangle_around_vertex_iterator(): - complex_(0),v_(-1),link_(0),is_end_(true){ - } - - - Triangle_around_vertex_iterator(const Triangle_around_vertex_iterator& other){ - v_ = other.v_; - complex_ = other.complex_; - is_end_ = other.is_end_; - - if(!is_end_){ - link_ = other.link_; - current_edge_= other.current_edge_; - } - } - - bool equal(const Triangle_around_vertex_iterator& other) const{ - return (complex_==other.complex_) && ((finished() &&other.finished()) || current_edge_ == other.current_edge_); - } - - Simplex_handle 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))); - } - - void increment(){ - ++current_edge_; - } - -private: - bool finished() const{ - return is_end_ || (current_edge_ == link_->edge_range().end()); - } - +, typename Complex::Simplex const> { + friend class boost::iterator_core_access; + template<typename T> 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 Simplex; + typedef typename Complex::Complex_edge_iterator Complex_edge_iterator_; + + const Complex* complex_; + Vertex_handle v_; + std::shared_ptr<LinkType> link_; + Complex_edge_iterator_ current_edge_; + bool is_end_; + + public: + Triangle_around_vertex_iterator(const Complex* complex, Vertex_handle v) : + complex_(complex), v_(v), link_(new LinkType(*complex, v_)), + current_edge_(link_->edge_range().begin()), + is_end_(current_edge_ == link_->edge_range().end()) { } + + /** + * @brief ugly hack to get an iterator to the end + */ + Triangle_around_vertex_iterator(const Complex* complex, Vertex_handle v, bool is_end) : + complex_(complex), v_(v), link_(0), is_end_(true) { } + + /** + * @brief ugly hack to get an iterator to the end + */ + Triangle_around_vertex_iterator() : + complex_(0), v_(-1), link_(0), is_end_(true) { } + + Triangle_around_vertex_iterator(const Triangle_around_vertex_iterator& other) { + v_ = other.v_; + complex_ = other.complex_; + is_end_ = other.is_end_; + + if (!is_end_) { + link_ = other.link_; + current_edge_ = other.current_edge_; + } + } + + bool equal(const Triangle_around_vertex_iterator& other) const { + return (complex_ == other.complex_) && ((finished() && other.finished()) || current_edge_ == other.current_edge_); + } + + Simplex dereference() const { + Root_vertex_handle v1 = (*link_)[*current_edge_].first(); + Root_vertex_handle v2 = (*link_)[*current_edge_].second(); + return Simplex(v_, *(complex_->get_address(v1)), *(complex_->get_address(v2))); + } + + void increment() { + ++current_edge_; + } + + private: + bool finished() const { + return is_end_ || (current_edge_ == link_->edge_range().end()); + } }; - - /** * \brief Iterator over the triangles of the * simplicial complex. @@ -119,121 +110,111 @@ private: * */ template<typename SkeletonBlockerComplex> -class Triangle_iterator : - public boost::iterator_facade< - Triangle_iterator <SkeletonBlockerComplex>, - typename SkeletonBlockerComplex::Simplex_handle const - , boost::forward_traversal_tag - , typename SkeletonBlockerComplex::Simplex_handle 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::Superior_triangle_around_vertex_iterator STAVI; - typedef typename SkeletonBlockerComplex::Complex_vertex_iterator Complex_vertex_iterator; - - const SkeletonBlockerComplex* complex_; - Complex_vertex_iterator current_vertex_; - STAVI current_triangle_; - bool is_end_; -public: - - /* - * @remark assume that the complex is non-empty - */ - Triangle_iterator(const SkeletonBlockerComplex* complex): - complex_(complex), - current_vertex_(complex->vertex_range().begin()), - current_triangle_(complex,*current_vertex_), // xxx this line is problematic is the complex is empty - is_end_(false){ - - assert(!complex->empty()); - gotoFirstTriangle(); - } - -private: - //goto to the first triangle or to the end if none - void gotoFirstTriangle(){ - if(!is_finished() && current_triangle_.finished()){ - goto_next_vertex(); - } - } -public: - - /** - * @brief ugly hack to get an iterator to the end - * @remark assume that the complex is non-empty - */ - Triangle_iterator(const SkeletonBlockerComplex* complex,bool is_end): - complex_(complex), - current_vertex_(complex->vertex_range().end()), - current_triangle_(), // xxx this line is problematic is the complex is empty - is_end_(true){ - } - - - Triangle_iterator& operator=(const Triangle_iterator & other){ - complex_ = other.complex_; - Complex_vertex_iterator current_vertex_; - STAVI current_triangle_; - return *this; - } - - - bool equal(const Triangle_iterator& other) const{ - bool both_are_finished = is_finished() && other.is_finished(); - bool both_arent_finished = !is_finished() && !other.is_finished(); - // if the two iterators are not finished, they must have the same state - return (complex_==other.complex_) && - (both_are_finished || - ( (both_arent_finished) && current_vertex_ == other.current_vertex_ && current_triangle_ == other.current_triangle_)); - - } - - Simplex_handle dereference() const{ - return *current_triangle_; - } - -private: - - // goto the next vertex that has a triangle pending or the - // end vertex iterator if none exists - void goto_next_vertex(){ - assert(current_triangle_.finished()); //we mush have consume all triangles passing through the vertex - assert(!is_finished()); // we must not be done - - ++current_vertex_; - - if(!is_finished()){ - current_triangle_ = STAVI(complex_, *current_vertex_); - if(current_triangle_.finished()) - goto_next_vertex(); - } - } -public: - void increment(){ - if(!current_triangle_.finished()){ - ++current_triangle_; // problem here - if(current_triangle_.finished()) - goto_next_vertex(); - } - else{ - assert(!is_finished()); - goto_next_vertex(); - } - } - -private: - bool is_finished() const{ - return is_end_ || current_vertex_ == complex_->vertex_range().end(); - } +class Triangle_iterator : public boost::iterator_facade< +Triangle_iterator <SkeletonBlockerComplex>, +typename SkeletonBlockerComplex::Simplex const +, boost::forward_traversal_tag +, 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 Simplex; + typedef typename SkeletonBlockerComplex::Superior_triangle_around_vertex_iterator STAVI; + typedef typename SkeletonBlockerComplex::Complex_vertex_iterator Complex_vertex_iterator; + + const SkeletonBlockerComplex* complex_; + Complex_vertex_iterator current_vertex_; + STAVI current_triangle_; + bool is_end_; + + public: + /* + * @remark assume that the complex is non-empty + */ + Triangle_iterator(const SkeletonBlockerComplex* complex) : + complex_(complex), + current_vertex_(complex->vertex_range().begin()), + current_triangle_(complex, *current_vertex_), // xxx this line is problematic is the complex is empty + is_end_(false) { + assert(!complex->empty()); + gotoFirstTriangle(); + } + + private: + // goto to the first triangle or to the end if none + void gotoFirstTriangle() { + if (!is_finished() && current_triangle_.finished()) { + goto_next_vertex(); + } + } + + public: + /** + * @brief ugly hack to get an iterator to the end + * @remark assume that the complex is non-empty + */ + Triangle_iterator(const SkeletonBlockerComplex* complex, bool is_end) : + complex_(complex), + current_vertex_(complex->vertex_range().end()), + current_triangle_(), // xxx this line is problematic is the complex is empty + is_end_(true) { } + + Triangle_iterator& operator=(const Triangle_iterator & other) { + complex_ = other.complex_; + Complex_vertex_iterator current_vertex_; + STAVI current_triangle_; + return *this; + } + + bool equal(const Triangle_iterator& other) const { + bool both_are_finished = is_finished() && other.is_finished(); + bool both_arent_finished = !is_finished() && !other.is_finished(); + // if the two iterators are not finished, they must have the same state + return (complex_ == other.complex_) && (both_are_finished || ((both_arent_finished) && + current_vertex_ == other.current_vertex_ && current_triangle_ == other.current_triangle_)); + } + + Simplex dereference() const { + return *current_triangle_; + } + + private: + // goto the next vertex that has a triangle pending or the + // end vertex iterator if none exists + void goto_next_vertex() { + assert(current_triangle_.finished()); // we mush have consume all triangles passing through the vertex + assert(!is_finished()); // we must not be done + + ++current_vertex_; + + if (!is_finished()) { + current_triangle_ = STAVI(complex_, *current_vertex_); + if (current_triangle_.finished()) + goto_next_vertex(); + } + } + + public: + void increment() { + if (!current_triangle_.finished()) { + ++current_triangle_; // problem here + if (current_triangle_.finished()) + goto_next_vertex(); + } else { + assert(!is_finished()); + goto_next_vertex(); + } + } + + private: + bool is_finished() const { + return is_end_ || current_vertex_ == complex_->vertex_range().end(); + } }; -} +} // namespace skbl -} // namespace GUDHI +} // namespace Gudhi -#endif /* GUDHI_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ */ +#endif // SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_TRIANGLES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h index a9d4e373..14ae136a 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h @@ -1,31 +1,32 @@ - /* This file is part of the Gudhi Library. The Gudhi library - * (Geometric Understanding in Higher Dimensions) is a generic C++ - * library for computational topology. - * - * Author(s): David Salinas - * - * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 3 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see <http://www.gnu.org/licenses/>. - */ -#ifndef GUDHI_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ -#define GUDHI_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ - -#include "boost/iterator/iterator_facade.hpp" - - -namespace Gudhi{ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author(s): David Salinas + * + * Copyright (C) 2014 INRIA Sophia Antipolis-Mediterranee (France) + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ +#ifndef SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ +#define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ + +#include <boost/iterator/iterator_facade.hpp> + +#include <utility> // for pair<> + +namespace Gudhi { namespace skbl { @@ -35,148 +36,137 @@ namespace skbl { *@remark Incrementation increases Vertex_handle. */ template<typename SkeletonBlockerComplex> -class Vertex_iterator : public boost::iterator_facade -< Vertex_iterator <SkeletonBlockerComplex> - , typename SkeletonBlockerComplex::Vertex_handle const - , boost::forward_traversal_tag - , typename SkeletonBlockerComplex::Vertex_handle const - > -{ - friend class boost::iterator_core_access; - - typedef typename SkeletonBlockerComplex::boost_vertex_iterator boost_vertex_iterator; - typedef typename SkeletonBlockerComplex::Vertex_handle Vertex_handle; -private: - const SkeletonBlockerComplex* complex; - std::pair<boost_vertex_iterator,boost_vertex_iterator> vertexIterator; - - -public: - Vertex_iterator():complex(NULL){ - } - - Vertex_iterator(const SkeletonBlockerComplex* complex_): - complex(complex_), - vertexIterator(vertices(complex_->skeleton)){ - if(!finished() && !is_active()) { - goto_next_valid(); - } - } - - /** - * return an iterator to the end. - */ - Vertex_iterator(const SkeletonBlockerComplex* complex_,int end): - complex(complex_),vertexIterator(vertices(complex_->skeleton)){ - vertexIterator.first = vertexIterator.second ; - } - -public: - void increment () {goto_next_valid();} - Vertex_handle dereference() const { - return(Vertex_handle(*(vertexIterator.first))); - } - - bool equal(const Vertex_iterator& other) const{ - return vertexIterator == other.vertexIterator && complex == other.complex; - } - - bool operator<(const Vertex_iterator& other) const{ - return dereference()<other.dereference(); - } - -private: - bool finished() const{ - return vertexIterator.first == vertexIterator.second; - } - - void goto_next_valid(){ - ++vertexIterator.first; - if(!finished() && !is_active()){ - goto_next_valid(); - } - } - - bool is_active() const{ - return ((*complex)[Vertex_handle(*vertexIterator.first)]).is_active(); - } - +class Vertex_iterator : public boost::iterator_facade< Vertex_iterator <SkeletonBlockerComplex> +, typename SkeletonBlockerComplex::Vertex_handle const +, boost::forward_traversal_tag +, typename SkeletonBlockerComplex::Vertex_handle const> { + friend class boost::iterator_core_access; + + typedef typename SkeletonBlockerComplex::boost_vertex_iterator boost_vertex_iterator; + typedef typename SkeletonBlockerComplex::Vertex_handle Vertex_handle; + private: + const SkeletonBlockerComplex* complex; + std::pair<boost_vertex_iterator, boost_vertex_iterator> vertexIterator; + + + public: + Vertex_iterator() : complex(NULL) { } + + Vertex_iterator(const SkeletonBlockerComplex* complex_) : + complex(complex_), + vertexIterator(vertices(complex_->skeleton)) { + if (!finished() && !is_active()) { + goto_next_valid(); + } + } + + /** + * return an iterator to the end. + */ + Vertex_iterator(const SkeletonBlockerComplex* complex_, int end) : + complex(complex_), vertexIterator(vertices(complex_->skeleton)) { + vertexIterator.first = vertexIterator.second; + } + + public: + void increment() { + goto_next_valid(); + } + + Vertex_handle dereference() const { + return (Vertex_handle(*(vertexIterator.first))); + } + + bool equal(const Vertex_iterator& other) const { + return vertexIterator == other.vertexIterator && complex == other.complex; + } + + bool operator<(const Vertex_iterator& other) const { + return dereference() < other.dereference(); + } + + private: + bool finished() const { + return vertexIterator.first == vertexIterator.second; + } + + void goto_next_valid() { + ++vertexIterator.first; + if (!finished() && !is_active()) { + goto_next_valid(); + } + } + + bool is_active() const { + return ((*complex)[Vertex_handle(*vertexIterator.first)]).is_active(); + } }; - - - template<typename SkeletonBlockerComplex> -class Neighbors_vertices_iterator -: public boost::iterator_facade < Neighbors_vertices_iterator<SkeletonBlockerComplex> - , typename SkeletonBlockerComplex::Vertex_handle const - , boost::forward_traversal_tag - , typename SkeletonBlockerComplex::Vertex_handle const - > -{ - friend class boost::iterator_core_access; - - typedef SkeletonBlockerComplex Complex; - typedef typename Complex::boost_adjacency_iterator boost_adjacency_iterator; - typedef typename Complex::Vertex_handle Vertex_handle; - typedef typename Complex::Edge_handle Edge_handle; - -private: - - const Complex* complex; - Vertex_handle v; - - boost_adjacency_iterator current_; - boost_adjacency_iterator end_; - -public: - // boost_adjacency_iterator ai, ai_end; - // for (tie(ai, ai_end) = adjacent_vertices(v.vertex, skeleton); ai != ai_end; ++ai){ - - Neighbors_vertices_iterator():complex(NULL){ - } - - Neighbors_vertices_iterator(const Complex* complex_,Vertex_handle v_): - complex(complex_), - v(v_){ - tie(current_,end_) = adjacent_vertices(v.vertex, complex->skeleton); - } - - /** - * returns an iterator to the end - */ - Neighbors_vertices_iterator(const Complex* complex_,Vertex_handle v_,int end): - complex(complex_), - v(v_){ - tie(current_,end_) = adjacent_vertices(v.vertex, complex->skeleton); - set_end(); - } - - - void increment () { - if(current_ != end_) - ++current_; - } - - Vertex_handle dereference() const { - return(Vertex_handle(*current_)); - } - - bool equal(const Neighbors_vertices_iterator& other) const{ - return (complex== other.complex) && (v == other.v) && (current_ == other.current_) && (end_ == other.end_); - } - -private: - //todo remove this ugly hack - void set_end(){ - current_ = end_; - } +class Neighbors_vertices_iterator: public boost::iterator_facade < Neighbors_vertices_iterator<SkeletonBlockerComplex> +, typename SkeletonBlockerComplex::Vertex_handle const +, boost::forward_traversal_tag +, typename SkeletonBlockerComplex::Vertex_handle const> { + friend class boost::iterator_core_access; + + typedef SkeletonBlockerComplex Complex; + typedef typename Complex::boost_adjacency_iterator boost_adjacency_iterator; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Edge_handle Edge_handle; + + private: + const Complex* complex; + Vertex_handle v; + + boost_adjacency_iterator current_; + boost_adjacency_iterator end_; + + public: + // boost_adjacency_iterator ai, ai_end; + // for (tie(ai, ai_end) = adjacent_vertices(v.vertex, skeleton); ai != ai_end; ++ai) { + + Neighbors_vertices_iterator() : complex(NULL) { } + + Neighbors_vertices_iterator(const Complex* complex_, Vertex_handle v_) : + complex(complex_), + v(v_) { + tie(current_, end_) = adjacent_vertices(v.vertex, complex->skeleton); + } + + /** + * returns an iterator to the end + */ + Neighbors_vertices_iterator(const Complex* complex_, Vertex_handle v_, int end) : + complex(complex_), + v(v_) { + tie(current_, end_) = adjacent_vertices(v.vertex, complex->skeleton); + set_end(); + } + + void increment() { + if (current_ != end_) + ++current_; + } + + Vertex_handle dereference() const { + return (Vertex_handle(*current_)); + } + + bool equal(const Neighbors_vertices_iterator& other) const { + return (complex == other.complex) && (v == other.v) && (current_ == other.current_) && (end_ == other.end_); + } + + private: + // todo remove this ugly hack + void set_end() { + current_ = end_; + } }; -} +} // namespace skbl -} // namespace GUDHI +} // namespace Gudhi -#endif /* GUDHI_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ */ +#endif // SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h index 700830f2..5b774f25 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h @@ -20,8 +20,18 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_COMPLEX_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_COMPLEX_H_ +#ifndef SKELETON_BLOCKER_COMPLEX_H_ +#define SKELETON_BLOCKER_COMPLEX_H_ + +#include <gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h> +#include <gudhi/Skeleton_blocker_link_complex.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h> +#include <gudhi/Skeleton_blocker/internal/Top_faces.h> +#include <gudhi/Skeleton_blocker/internal/Trie.h> +#include <gudhi/Utils.h> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/connected_components.hpp> @@ -40,18 +50,6 @@ #include <algorithm> #include <utility> -#include "gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h" -#include "gudhi/Skeleton_blocker_link_complex.h" -#include "gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h" -#include "gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h" -#include "gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h" - -#include "gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h" -#include "gudhi/Skeleton_blocker/internal/Top_faces.h" -#include "gudhi/Skeleton_blocker/internal/Trie.h" - -#include "gudhi/Utils.h" - namespace Gudhi { namespace skbl { @@ -94,16 +92,16 @@ class Skeleton_blocker_complex { /** * @brief A ordered set of integers that represents a simplex. */ - typedef Skeleton_blocker_simplex<Vertex_handle> Simplex_handle; + typedef Skeleton_blocker_simplex<Vertex_handle> Simplex; typedef Skeleton_blocker_simplex<Root_vertex_handle> 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<boost::setS, // edges @@ -128,14 +126,14 @@ class Skeleton_blocker_complex { typedef typename boost::graph_traits<Graph>::edge_descriptor Edge_handle; protected: - typedef std::multimap<Vertex_handle, Simplex_handle *> BlockerMap; - typedef typename std::multimap<Vertex_handle, Simplex_handle *>::value_type BlockerPair; - typedef typename std::multimap<Vertex_handle, Simplex_handle *>::iterator BlockerMapIterator; - typedef typename std::multimap<Vertex_handle, Simplex_handle *>::const_iterator BlockerMapConstIterator; + typedef std::multimap<Vertex_handle, Simplex *> BlockerMap; + typedef typename std::multimap<Vertex_handle, Simplex *>::value_type BlockerPair; + typedef typename std::multimap<Vertex_handle, Simplex *>::iterator BlockerMapIterator; + typedef typename std::multimap<Vertex_handle, Simplex *>::const_iterator BlockerMapConstIterator; protected: - int num_vertices_; - int num_blockers_; + size_t num_vertices_; + size_t num_blockers_; typedef Skeleton_blocker_complex_visitor<Vertex_handle> Visitor; // typedef Visitor* Visitor_ptr; @@ -164,17 +162,17 @@ class Skeleton_blocker_complex { /** *@brief constructs a simplicial complex with a given number of vertices and a visitor. */ - explicit Skeleton_blocker_complex(int num_vertices_ = 0, Visitor* visitor_ = NULL) + explicit Skeleton_blocker_complex(size_t num_vertices_ = 0, Visitor* visitor_ = NULL) : visitor(visitor_) { clear(); - for (int i = 0; i < num_vertices_; ++i) { + for (size_t i = 0; i < num_vertices_; ++i) { add_vertex(); } } private: // typedef Trie<Skeleton_blocker_complex<SkeletonBlockerDS>> STrie; - typedef Trie<Simplex_handle> STrie; + typedef Trie<Simplex> STrie; public: /** @@ -182,37 +180,41 @@ class Skeleton_blocker_complex { * @details is_flag_complex indicates if the complex is a flag complex or not (to know if blockers have to be computed or not). */ template<typename SimpleHandleOutputIterator> - Skeleton_blocker_complex(SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end, + Skeleton_blocker_complex(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end, bool is_flag_complex = false, Visitor* visitor_ = NULL) : num_vertices_(0), num_blockers_(0), visitor(visitor_) { - add_vertex_and_edges(simplex_begin, simplex_end); + add_vertices_and_edges(simplices_begin, simplices_end); if (!is_flag_complex) // need to compute blockers - add_blockers(simplex_begin, simplex_end); + add_blockers(simplices_begin, simplices_end); } private: + /** + * Add vertices and edges of a simplex in one pass + */ template<typename SimpleHandleOutputIterator> - void add_vertex_and_edges(SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) { + void add_vertices_and_edges(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end) { std::vector<std::pair<Vertex_handle, Vertex_handle>> edges; // first pass to add vertices and edges int num_vertex = -1; - for (auto s_it = simplex_begin; s_it != simplex_end; ++s_it) { + for (auto s_it = simplices_begin; s_it != simplices_end; ++s_it) { if (s_it->dimension() == 0) num_vertex = (std::max)(num_vertex, s_it->first_vertex().vertex); if (s_it->dimension() == 1) edges.emplace_back(s_it->first_vertex(), s_it->last_vertex()); } 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<typename SimpleHandleOutputIterator> - void add_blockers(SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) { - Tries<Simplex_handle> tries(num_vertices(), simplex_begin, simplex_end); + void add_blockers(SimpleHandleOutputIterator simplices_begin, SimpleHandleOutputIterator simplices_end) { + Tries<Simplex> tries(num_vertices(), simplices_begin, simplices_end); tries.init_next_dimension(); auto simplices(tries.next_dimension_simplices()); @@ -221,7 +223,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)); @@ -378,6 +380,7 @@ class Skeleton_blocker_complex { /** * @brief Adds a vertex to the simplicial complex and returns its Vertex_handle. + * @remark Vertex representation is contiguous. */ Vertex_handle add_vertex() { Vertex_handle address(boost::add_vertex(skeleton)); @@ -427,7 +430,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 +538,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) { + // 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<Edge_handle,bool> 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 +657,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 +679,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 +768,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 +806,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 +824,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 +839,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 +862,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 +877,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 +889,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 +903,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 +916,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 +928,11 @@ class Skeleton_blocker_complex { */ // xxx rename get_address et place un using dans sub_complex - boost::optional<Simplex_handle> get_simplex_address( + boost::optional<Simplex> get_simplex_address( const Root_simplex_handle& s) const { - boost::optional<Simplex_handle> res; + boost::optional<Simplex> res; - Simplex_handle s_address; + Simplex s_address; // Root_simplex_const_iterator i; for (auto i = s.begin(); i != s.end(); ++i) { boost::optional<Vertex_handle> address = get_address(*i); @@ -920,7 +949,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 +961,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) { @@ -972,10 +1001,31 @@ class Skeleton_blocker_complex { return std::distance(triangles.begin(), triangles.end()); } + + /* + * @brief returns the number of simplices of a given dimension in the complex. + */ + size_t num_simplices() const { + auto simplices = complex_simplex_range(); + return std::distance(simplices.begin(), simplices.end()); + } + + /* + * @brief returns the number of simplices of a given dimension in the complex. + */ + size_t num_simplices(unsigned dimension) const { + // TODO(DS): iterator on k-simplices + size_t res = 0; + for (const auto& s : complex_simplex_range()) + if (s.dimension() == dimension) + ++res; + return res; + } + /* * @brief returns the number of blockers in the complex. */ - int num_blockers() const { + size_t num_blockers() const { return num_blockers_; } @@ -1018,7 +1068,7 @@ class Skeleton_blocker_complex { } //@} - /** @Simplification operations + /** @name Simplification operations */ //@{ @@ -1061,7 +1111,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 +1128,33 @@ 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 and all its faces. + * @details the simplex must have dimension greater than one (otherwise use add_vertex or add_edge_without_blockers). */ - void add_simplex(const Simplex_handle& sigma); + void add_simplex(const Simplex& sigma); 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() @@ -1131,7 +1183,7 @@ class Skeleton_blocker_complex { } //@} - /** @Edge contraction operations + /** @name Edge contraction operations */ //@{ @@ -1174,7 +1226,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<Simplex_handle> & buffer) const; + void tip_blockers(Vertex_handle a, Vertex_handle b, std::vector<Simplex> & buffer) const; private: /** @@ -1217,7 +1269,7 @@ class Skeleton_blocker_complex { private: void get_blockers_to_be_added_after_contraction(Vertex_handle a, Vertex_handle b, - std::set<Simplex_handle>& blockers_to_add); + std::set<Simplex>& blockers_to_add); /** * delete all blockers that passes through a or b */ @@ -1358,12 +1410,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<Skeleton_blocker_complex, Link> 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<Skeleton_blocker_complex,Superior_link> Complex_simplex_iterator; typedef Simplex_iterator<Skeleton_blocker_complex> Complex_simplex_iterator; @@ -1373,7 +1441,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 +1461,7 @@ class Skeleton_blocker_complex { * @brief Iterator over the blockers adjacent to a vertex */ typedef Blocker_iterator_around_vertex_internal< - typename std::multimap<Vertex_handle, Simplex_handle *>::iterator, + typename std::multimap<Vertex_handle, Simplex *>::iterator, Blocker_handle> Complex_blocker_around_vertex_iterator; @@ -1401,12 +1469,13 @@ class Skeleton_blocker_complex { * @brief Iterator over (constant) blockers adjacent to a vertex */ typedef Blocker_iterator_around_vertex_internal< - typename std::multimap<Vertex_handle, Simplex_handle *>::const_iterator, + typename std::multimap<Vertex_handle, Simplex *>::const_iterator, const Blocker_handle> Const_complex_blocker_around_vertex_iterator; typedef boost::iterator_range <Complex_blocker_around_vertex_iterator> Complex_blocker_around_vertex_range; - typedef boost::iterator_range <Const_complex_blocker_around_vertex_iterator> Const_complex_blocker_around_vertex_range; + typedef boost::iterator_range <Const_complex_blocker_around_vertex_iterator> + Const_complex_blocker_around_vertex_range; public: /** @@ -1432,7 +1501,7 @@ class Skeleton_blocker_complex { * @brief Iterator over the blockers. */ typedef Blocker_iterator_internal< - typename std::multimap<Vertex_handle, Simplex_handle *>::iterator, + typename std::multimap<Vertex_handle, Simplex *>::iterator, Blocker_handle> Complex_blocker_iterator; @@ -1440,7 +1509,7 @@ class Skeleton_blocker_complex { * @brief Iterator over the (constant) blockers. */ typedef Blocker_iterator_internal< - typename std::multimap<Vertex_handle, Simplex_handle *>::const_iterator, + typename std::multimap<Vertex_handle, Simplex *>::const_iterator, const Blocker_handle> Const_complex_blocker_iterator; @@ -1514,11 +1583,12 @@ class Skeleton_blocker_complex { * return the total number of simplices */ template<typename Complex, typename SimplexHandleIterator> -Complex make_complex_from_top_faces(SimplexHandleIterator simplex_begin, SimplexHandleIterator simplex_end, +Complex make_complex_from_top_faces(SimplexHandleIterator simplices_begin, SimplexHandleIterator simplices_end, bool is_flag_complex = false) { - typedef typename Complex::Simplex_handle Simplex_handle; - std::vector<Simplex_handle> simplices; - for (auto top_face = simplex_begin; top_face != simplex_end; ++top_face) { + // TODO(DS): use add_simplex instead! should be more efficient and more elegant :) + typedef typename Complex::Simplex Simplex; + std::vector<Simplex> simplices; + for (auto top_face = simplices_begin; top_face != simplices_end; ++top_face) { auto subfaces_topface = subfaces(*top_face); simplices.insert(simplices.end(), subfaces_topface.begin(), subfaces_topface.end()); } @@ -1531,6 +1601,4 @@ Complex make_complex_from_top_faces(SimplexHandleIterator simplex_begin, Simplex #include "Skeleton_blocker_simplifiable_complex.h" - -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_COMPLEX_H_ - +#endif // SKELETON_BLOCKER_COMPLEX_H_ 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 437482cb..5c898152 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_geometric_complex.h @@ -19,12 +19,12 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ +#ifndef SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ +#define SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ -#include "gudhi/Utils.h" -#include "gudhi/Skeleton_blocker_complex.h" -#include "gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h" +#include <gudhi/Utils.h> +#include <gudhi/Skeleton_blocker_complex.h> +#include <gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h> namespace Gudhi { @@ -46,7 +46,7 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { 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; @@ -79,23 +79,6 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { (*this)[Vertex_handle(current++)].point() = Point(point->begin(), point->end()); } - template<typename SimpleHandleOutputIterator, typename PointIterator> - friend Skeleton_blocker_geometric_complex make_complex_from_top_faces( - SimpleHandleOutputIterator simplex_begin, - SimpleHandleOutputIterator simplex_end, - PointIterator points_begin, - PointIterator points_end, - bool is_flag_complex = false) { - Skeleton_blocker_geometric_complex complex; - unsigned current = 0; - complex = - make_complex_from_top_faces<Skeleton_blocker_geometric_complex>(simplex_begin, simplex_end, is_flag_complex); - for (auto point = points_begin; point != points_end; ++point) - // complex.point(Vertex_handle(current++)) = Point(point->begin(),point->end()); - complex.point(Vertex_handle(current++)) = Point(*point); - return complex; - } - /** * @brief Constructor with a list of simplices. * Points of every vertex are the point constructed with default constructor. @@ -157,7 +140,7 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { * 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; @@ -166,7 +149,7 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { /** * 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); @@ -189,13 +172,13 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { * 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); } @@ -215,8 +198,27 @@ public Skeleton_blocker_complex<SkeletonBlockerGeometricDS> { } }; + +template<typename SkeletonBlockerGeometricComplex, typename SimpleHandleOutputIterator, typename PointIterator> +SkeletonBlockerGeometricComplex make_complex_from_top_faces( + SimpleHandleOutputIterator simplex_begin, + SimpleHandleOutputIterator simplex_end, + PointIterator points_begin, + PointIterator points_end, + bool is_flag_complex = false) { + typedef SkeletonBlockerGeometricComplex SBGC; + SkeletonBlockerGeometricComplex complex; + unsigned current = 0; + complex = + make_complex_from_top_faces<SBGC>(simplex_begin, simplex_end, is_flag_complex); + for (auto point = points_begin; point != points_end; ++point) + // complex.point(Vertex_handle(current++)) = Point(point->begin(),point->end()); + complex.point(typename SBGC::Vertex_handle(current++)) = typename SBGC::Point(*point); + return complex; +} + } // namespace skbl } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ +#endif // SKELETON_BLOCKER_GEOMETRIC_COMPLEX_H_ 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 725ecce5..85a6b0b5 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_link_complex.h @@ -19,11 +19,11 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_LINK_COMPLEX_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_LINK_COMPLEX_H_ +#ifndef SKELETON_BLOCKER_LINK_COMPLEX_H_ +#define SKELETON_BLOCKER_LINK_COMPLEX_H_ -#include "gudhi/Utils.h" -#include "gudhi/Skeleton_blocker_complex.h" +#include <gudhi/Utils.h> +#include <gudhi/Skeleton_blocker_complex.h> namespace Gudhi { @@ -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)); @@ -297,4 +294,4 @@ class Skeleton_blocker_link_complex : public Skeleton_blocker_sub_complex< } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_LINK_COMPLEX_H_ +#endif // SKELETON_BLOCKER_LINK_COMPLEX_H_ 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 dd8d898e..94a125c1 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h @@ -19,15 +19,15 @@ * You should have received a copy of the GNU General Public License * along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_ -#define SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_ +#ifndef SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_ +#define SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_ + +#include <gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h> #include <list> #include <vector> #include <set> -#include "gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h" - namespace Gudhi { namespace skbl { @@ -45,9 +45,7 @@ bool Skeleton_blocker_complex<SkeletonBlockerDS>::is_popable_blocker(Blocker_han assert(this->contains_blocker(*sigma)); Skeleton_blocker_link_complex<Skeleton_blocker_complex> link_blocker_sigma; build_link_of_blocker(*this, *sigma, link_blocker_sigma); - - bool res = link_blocker_sigma.is_contractible() == CONTRACTIBLE; - return res; + return link_blocker_sigma.is_contractible() == CONTRACTIBLE; } /** @@ -133,7 +131,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_all_popable_blockers(Ve template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::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 +146,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Vertex_handle v) { */ template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::update_blockers_after_remove_star_of_vertex_or_edge( - const Simplex_handle& simplex_to_be_removed) { + const Simplex& simplex_to_be_removed) { std::list <Blocker_handle> blockers_to_update; if (simplex_to_be_removed.empty()) return; @@ -159,7 +157,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::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 +176,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::update_blockers_after_remove_s */ template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::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 +193,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Edge_handle e) { * Remove the star of the simplex 'sigma' which needs to belong to the complex */ template<typename SkeletonBlockerDS> -void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(const Simplex_handle& sigma) { +void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(const Simplex& sigma) { assert(this->contains(sigma)); if (sigma.dimension() == 0) { remove_star(sigma.first_vertex()); @@ -207,33 +205,41 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(const Simplex_hand } } -/** - * @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). - */ template<typename SkeletonBlockerDS> -void Skeleton_blocker_complex<SkeletonBlockerDS>::add_simplex(const Simplex_handle& sigma) { +void Skeleton_blocker_complex<SkeletonBlockerDS>::add_simplex(const Simplex& 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); + if (!contains_vertices(sigma)) { + std::cerr << "add_simplex: Some vertices were not present in the complex, adding them" << std::endl; + size_t num_vertices_to_add = sigma.last_vertex() - this->num_vertices() + 1; + for (size_t i = 0; i < num_vertices_to_add; ++i) + this->add_vertex(); + } + assert(contains_vertices(sigma)); + if (!contains_edges(sigma)) + add_edge(sigma); + remove_blocker_include_in_simplex(sigma); + add_blockers_after_simplex_insertion(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); - } - remove_blocker_include_in_simplex(sigma); + +template<typename SkeletonBlockerDS> +void Skeleton_blocker_complex<SkeletonBlockerDS>::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<typename SkeletonBlockerDS> -void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_containing_simplex(const Simplex_handle& sigma) { +void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_containing_simplex(const Simplex& sigma) { std::vector <Blocker_handle> blockers_to_remove; for (auto blocker : this->blocker_range(sigma.first_vertex())) { if (blocker->contains(sigma)) @@ -247,14 +253,26 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_containing_simp * remove all blockers that contains sigma */ template<typename SkeletonBlockerDS> -void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_include_in_simplex(const Simplex_handle& sigma) { - std::vector <Blocker_handle> 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<SkeletonBlockerDS>::remove_blocker_include_in_simplex(const Simplex& sigma) { + // TODO(DS): write efficiently by using only superior blockers + // eg for all s, check blockers whose vertices are all greater than s + std::set <Blocker_handle> 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); + } } /** @@ -264,21 +282,21 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_blocker_include_in_simp */ template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::tip_blockers(Vertex_handle a, Vertex_handle b, - std::vector<Simplex_handle> & buffer) const { + std::vector<Simplex> & 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); } @@ -295,7 +313,7 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::tip_blockers(Vertex_handle a, template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::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); } @@ -338,13 +356,15 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::contract_edge(Vertex_handle a, Vertex_handle b) { assert(this->contains_vertex(a)); assert(this->contains_vertex(b)); - assert(this->contains_edge(a, b)); - // if some blockers passes through 'ab', we remove them. + if (this->contains_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<Simplex_handle> blockers_to_add; + std::set<Simplex> blockers_to_add; get_blockers_to_be_added_after_contraction(a, b, blockers_to_add); @@ -364,9 +384,8 @@ Skeleton_blocker_complex<SkeletonBlockerDS>::contract_edge(Vertex_handle a, Vert } template<typename SkeletonBlockerDS> -void -Skeleton_blocker_complex<SkeletonBlockerDS>::get_blockers_to_be_added_after_contraction(Vertex_handle a, Vertex_handle b, - std::set<Simplex_handle>& blockers_to_add) { +void Skeleton_blocker_complex<SkeletonBlockerDS>::get_blockers_to_be_added_after_contraction(Vertex_handle a, + Vertex_handle b, std::set<Simplex>& blockers_to_add) { blockers_to_add.clear(); typedef Skeleton_blocker_link_complex<Skeleton_blocker_complex<SkeletonBlockerDS> > LinkComplexType; @@ -374,19 +393,19 @@ Skeleton_blocker_complex<SkeletonBlockerDS>::get_blockers_to_be_added_after_cont LinkComplexType link_a(*this, a); LinkComplexType link_b(*this, b); - std::vector<Simplex_handle> vector_alpha, vector_beta; + std::vector<Simplex> 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<Skeleton_blocker_complex < SkeletonBlockerDS >> (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); } @@ -444,4 +463,4 @@ Skeleton_blocker_complex<SkeletonBlockerDS>::notify_changed_edges(Vertex_handle } // namespace Gudhi -#endif // SRC_SKELETON_BLOCKER_INCLUDE_GUDHI_SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_ +#endif // SKELETON_BLOCKER_SIMPLIFIABLE_COMPLEX_H_ |