diff options
Diffstat (limited to 'src/Skeleton_blocker/include/gudhi/Skeleton_blocker')
15 files changed, 2632 insertions, 0 deletions
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 new file mode 100644 index 00000000..9f145013 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h @@ -0,0 +1,132 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_COMPLEX_VISITOR_H_ + +#include <gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h> + +namespace Gudhi { + +namespace skeleton_blocker { +// TODO(DS): to be constified + +/** + *@class Skeleton_blocker_complex_visitor + *@brief Interface for a visitor of a simplicial complex. + */ +template<typename Vertex_handle> +class Skeleton_blocker_complex_visitor { + public: + virtual ~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_without_blockers(Vertex_handle a, Vertex_handle b) = 0; + virtual void on_remove_edge(Vertex_handle a, Vertex_handle b) = 0; + + /** + * @brief Called when an edge changes, during the contraction of + * an edge + */ + virtual void on_changed_edge(Vertex_handle a, Vertex_handle b) = 0; + + /** + * @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_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; + virtual void on_add_blocker( + const Skeleton_blocker_simplex<Vertex_handle>&) = 0; + virtual void on_delete_blocker( + const Skeleton_blocker_simplex<Vertex_handle>*) = 0; +}; + +/** + *@class Dummy_complex_visitor + *@brief A dummy visitor of a simplicial complex that does nothing + * + */ +template<typename Vertex_handle> +class Dummy_complex_visitor : public Skeleton_blocker_complex_visitor< +Vertex_handle> { + public: + void on_add_vertex(Vertex_handle) { } + + void on_remove_vertex(Vertex_handle) { } + + void on_add_edge_without_blockers(Vertex_handle a, Vertex_handle b) { } + + void on_remove_edge(Vertex_handle a, Vertex_handle b) { } + + void on_changed_edge(Vertex_handle a, Vertex_handle b) { } + + void on_swaped_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) { } + + void on_add_blocker(const Skeleton_blocker_simplex<Vertex_handle>&) { } + + void on_delete_blocker(const Skeleton_blocker_simplex<Vertex_handle>*) { } +}; + +/** + *@class Print_complex_visitor + *@brief A visitor that prints the visit information. + * + */ +template<typename Vertex_handle> +class Print_complex_visitor : public Skeleton_blocker_complex_visitor< +Vertex_handle> { + public: + void on_add_vertex(Vertex_handle v) { + std::cerr << "on_add_vertex:" << v << std::endl; + } + + void on_remove_vertex(Vertex_handle v) { + std::cerr << "on_remove_vertex:" << v << 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; + } + + void on_changed_edge(Vertex_handle a, Vertex_handle b) { + std::cerr << "on_changed_edge:" << a << "," << b << std::endl; + } + + void on_swaped_edge(Vertex_handle a, Vertex_handle b, Vertex_handle x) { + std::cerr << "on_swaped_edge:" << a << "," << b << "," << x << std::endl; + } + + void on_add_blocker(const Skeleton_blocker_simplex<Vertex_handle>& b) { + std::cerr << "on_add_blocker:" << b << std::endl; + } + + void on_delete_blocker(const Skeleton_blocker_simplex<Vertex_handle>* b) { + std::cerr << "on_delete_blocker:" << b << std::endl; + } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..d348b696 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h @@ -0,0 +1,65 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_LINK_SUPERIOR_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_LINK_SUPERIOR_H_ + +#include <gudhi/Skeleton_blocker_link_complex.h> + +namespace Gudhi { + +namespace skeleton_blocker { + +template<class ComplexType> class Skeleton_blocker_sub_complex; + +/** + * \brief Class representing the link of a simplicial complex encoded by a skeleton/blockers pair. + * It computes only vertices greater than the simplex used to build the link. + */ +template<typename ComplexType> +class Skeleton_blocker_link_superior : public Skeleton_blocker_link_complex< +ComplexType> { + typedef typename ComplexType::Edge_handle Edge_handle; + + typedef typename ComplexType::boost_vertex_handle boost_vertex_handle; + + public: + typedef typename ComplexType::Vertex_handle Vertex_handle; + typedef typename ComplexType::Root_vertex_handle Root_vertex_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::Simplex_vertex_const_iterator AddressSimplexConstIterator; + typedef typename ComplexType::Root_simplex_handle::Simplex_vertex_const_iterator IdSimplexConstIterator; + + Skeleton_blocker_link_superior() + : Skeleton_blocker_link_complex<ComplexType>(true) { } + + Skeleton_blocker_link_superior(const ComplexType & parent_complex, + Simplex& alpha_parent_adress) + : Skeleton_blocker_link_complex<ComplexType>(parent_complex, + alpha_parent_adress, true) { } + + Skeleton_blocker_link_superior(const ComplexType & parent_complex, + Vertex_handle a_parent_adress) + : Skeleton_blocker_link_complex<ComplexType>(parent_complex, + a_parent_adress, true) { } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..52300493 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h @@ -0,0 +1,191 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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> + +namespace Gudhi { + +namespace skeleton_blocker { + +/** + *@brief Off reader visitor that can be passed to Off_reader to read a Skeleton_blocker_complex. + */ +template<typename Complex> +class Skeleton_blocker_off_flag_visitor_reader { + Complex& complex_; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Point Point; + + const bool load_only_points_; + + public: + explicit Skeleton_blocker_off_flag_visitor_reader(Complex& complex, bool load_only_points = false) : + complex_(complex), + load_only_points_(load_only_points) { } + + void init(int dim, int num_vertices, int num_faces, int num_edges) { + // TODO(DS): do an assert to check that this number are correctly read + // TODO(DS): reserve size for vector points + } + + void point(const std::vector<double>& point) { + complex_.add_vertex(Point(point.begin(), point.end())); + } + + void maximal_face(const std::vector<int>& face) { + 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_without_blockers(Vertex_handle(face[i]), Vertex_handle(face[j])); + } + } + } + + void done() { } +}; + +/** + *@brief Off reader visitor that can be passed to Off_reader to read a Skeleton_blocker_complex. + */ +template<typename Complex> +class Skeleton_blocker_off_visitor_reader { + Complex& complex_; + typedef typename Complex::Vertex_handle Vertex_handle; + typedef typename Complex::Simplex Simplex; + typedef typename Complex::Point Point; + + const bool load_only_points_; + std::vector<Point> points_; + std::vector<Simplex> maximal_faces_; + + public: + explicit Skeleton_blocker_off_visitor_reader(Complex& complex, bool load_only_points = false) : + complex_(complex), + load_only_points_(load_only_points) { } + + void init(int dim, int num_vertices, int num_faces, int num_edges) { + maximal_faces_.reserve(num_faces); + points_.reserve(num_vertices); + } + + void point(const std::vector<double>& point) { + points_.emplace_back(point.begin(), point.end()); + } + + void maximal_face(const std::vector<int>& face) { + if (!load_only_points_) { + Simplex s; + for (auto x : face) + s.add_vertex(Vertex_handle(x)); + maximal_faces_.emplace_back(s); + } + } + + void done() { + complex_ = make_complex_from_top_faces<Complex>(maximal_faces_.begin(), maximal_faces_.end(), + points_.begin(), points_.end()); + } +}; + +/** + *@brief Class that allows to load a Skeleton_blocker_complex from an off file. + */ +template<typename Complex> +class Skeleton_blocker_off_reader { + public: + /** + * name_file : file to read + * read_complex : complex that will receive the file content + * read_only_points : specify true if only the points must be read + */ + Skeleton_blocker_off_reader(const std::string & name_file, Complex& read_complex, + bool read_only_points = false, bool is_flag = false) : valid_(false) { + std::ifstream stream(name_file); + if (stream.is_open()) { + if (is_flag || read_only_points) { + Skeleton_blocker_off_flag_visitor_reader<Complex> off_visitor(read_complex, read_only_points); + Off_reader off_reader(stream); + valid_ = off_reader.read(off_visitor); + } else { + Skeleton_blocker_off_visitor_reader<Complex> off_visitor(read_complex, read_only_points); + Off_reader off_reader(stream); + valid_ = off_reader.read(off_visitor); + } + } + } + + /** + * return true if reading did not meet problems. + */ + bool is_valid() const { + return valid_; + } + + private: + bool valid_; +}; + +template<typename Complex> +class Skeleton_blocker_off_writer { + public: + /** + * name_file : file where the off will be written + * save_complex : complex that be outputted in the file + * for now only save triangles. + */ + Skeleton_blocker_off_writer(const std::string & name_file, const Complex& save_complex) { + typedef typename Complex::Vertex_handle Vertex_handle; + + std::ofstream stream(name_file); + if (stream.is_open()) { + stream << "OFF\n"; + size_t num_triangles = std::distance(save_complex.triangle_range().begin(), save_complex.triangle_range().end()); + stream << save_complex.num_vertices() << " " << num_triangles << " 0 \n"; + + // in case the complex has deactivated some vertices, eg only has vertices 0 2 5 7 for instance + // we compute a map from 0 2 5 7 to 0 1 2 3 + std::map<Vertex_handle, size_t> vertex_num; + size_t current_vertex = 0; + + for (auto v : save_complex.vertex_range()) { + vertex_num[v] = current_vertex++; + const auto& pt(save_complex.point(v)); + for (auto x : pt) + stream << x << " "; + stream << std::endl; + } + + for (const auto & t : save_complex.triangle_range()) { + stream << "3 "; + for (auto x : t) + stream << vertex_num[x] << " "; + stream << std::endl; + } + stream.close(); + } else { + std::cerr << "could not open file " << name_file << std::endl; + } + } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..772e33aa --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h @@ -0,0 +1,87 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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> + +namespace Gudhi { + +namespace skeleton_blocker { + +/** + * @extends SkeletonBlockerGeometricDS + * @ingroup skbl + * @brief Simple traits that is a model of SkeletonBlockerGeometricDS and + * can be passed as a template argument to Skeleton_blocker_geometric_complex + */ +template<typename GeometryTrait> +struct Skeleton_blocker_simple_geometric_traits : +public Skeleton_blocker_simple_traits { + public: + typedef GeometryTrait GT; + typedef typename GT::Point Point; + typedef typename Skeleton_blocker_simple_traits::Root_vertex_handle Root_vertex_handle; + typedef typename Skeleton_blocker_simple_traits::Graph_vertex Simple_vertex; + + /** + * @brief Vertex with a point attached. + */ + class Simple_geometric_vertex : public Simple_vertex { + template<class ComplexGeometricTraits> friend class Skeleton_blocker_geometric_complex; + private: + Point point_; + + Point& point() { + return point_; + } + + const Point& point() const { + return point_; + } + }; + + class Simple_geometric_edge : + public Skeleton_blocker_simple_traits::Graph_edge { + int index_; + public: + Simple_geometric_edge() + : Skeleton_blocker_simple_traits::Graph_edge(), + index_(-1) { } + + /** + * @brief Allows to modify the index of the edge. + * The indices of the edge are used to store heap information + * in the edge contraction algorithm. + */ + int& index() { + return index_; + } + + int index() const { + return index_; + } + }; + + typedef Simple_geometric_vertex Graph_vertex; + typedef Skeleton_blocker_simple_traits::Graph_edge Graph_edge; +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..0c0cc624 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h @@ -0,0 +1,178 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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> + +namespace Gudhi { + +namespace skeleton_blocker { + +/** + * @extends SkeletonBlockerDS + * @ingroup skbl + * @brief Simple traits that is a model of SkeletonBlockerDS and + * can be passed as a template argument to Skeleton_blocker_complex + */ +struct Skeleton_blocker_simple_traits { + /** + * @brief Global and local handle similar to <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a>. + * Vertices are stored in a vector. + * For the root simplicial complex, the local and global descriptors are the same. + * For a subcomplex L and one of its vertices 'v', the local descriptor of 'v' is its position in + * the vertex vector of the subcomplex L whereas its global descriptor is the position of 'v' + * in the vertex vector of the root simplicial complex. + */ + struct Root_vertex_handle { + typedef int boost_vertex_handle; + + explicit Root_vertex_handle(boost_vertex_handle val = -1) + : vertex(val) { } + boost_vertex_handle vertex; + + bool operator!=(const Root_vertex_handle& other) const { + return !(this->vertex == other.vertex); + } + + bool operator==(const Root_vertex_handle& other) const { + return this->vertex == other.vertex; + } + + bool operator<(const Root_vertex_handle& other) const { + return this->vertex < other.vertex; + } + + friend std::ostream& operator<<(std::ostream& o, + const Root_vertex_handle & v) { + o << v.vertex; + return o; + } + }; + + struct Vertex_handle { + typedef int boost_vertex_handle; + + explicit Vertex_handle(boost_vertex_handle val = -1) + : vertex(val) { } + + operator int() const { + return static_cast<int> (vertex); + } + + boost_vertex_handle vertex; + + bool operator==(const Vertex_handle& other) const { + return this->vertex == other.vertex; + } + + bool operator!=(const Vertex_handle& other) const { + return this->vertex != other.vertex; + } + + bool operator<(const Vertex_handle& other) const { + return this->vertex < other.vertex; + } + + friend std::ostream& operator<<(std::ostream& o, const Vertex_handle & v) { + o << v.vertex; + return o; + } + }; + + class Graph_vertex { + bool is_active_; + Root_vertex_handle id_; + + public: + virtual ~Graph_vertex() { } + + void activate() { + is_active_ = true; + } + + void deactivate() { + is_active_ = false; + } + + bool is_active() const { + return is_active_; + } + + void set_id(Root_vertex_handle i) { + id_ = i; + } + + Root_vertex_handle get_id() const { + return id_; + } + + virtual std::string to_string() const { + std::ostringstream res; + res << id_; + return res.str(); + } + + friend std::ostream& operator<<(std::ostream& o, const Graph_vertex & v) { + o << v.to_string(); + return o; + } + }; + + class Graph_edge { + Root_vertex_handle a_; + Root_vertex_handle b_; + int index_; + + public: + Graph_edge() + : a_(-1), + b_(-1), + index_(-1) { } + + int& index() { + return index_; + } + + int index() const { + return index_; + } + + void setId(Root_vertex_handle a, Root_vertex_handle b) { + a_ = a; + b_ = b; + } + + Root_vertex_handle first() const { + return a_; + } + + Root_vertex_handle second() const { + return b_; + } + + friend std::ostream& operator<<(std::ostream& o, const Graph_edge & v) { + o << "(" << v.a_ << "," << v.b_ << " - id = " << v.index(); + return o; + } + }; +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..12fe6469 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h @@ -0,0 +1,362 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_ +#define SKELETON_BLOCKER_SKELETON_BLOCKER_SIMPLEX_H_ + +#include <cassert> +#include <iostream> +#include <set> +#include <vector> +#include <initializer_list> +#include <string> +#include <algorithm> + +namespace Gudhi { + +namespace skeleton_blocker { + +/** + *@brief Abstract simplex used in Skeleton blockers data-structure. + * + * An abstract simplex is represented as an ordered set of T elements, + * each element representing a vertex. + * + * The element representing a vertex can be SkeletonBlockerDS::Vertex_handle or SkeletonBlockerDS::Root_vertex_handle. + * + * + */ +template<typename T> + +class Skeleton_blocker_simplex { + private: + std::set<T> simplex_set; + + public: + typedef typename T::boost_vertex_handle boost_vertex_handle; + + typedef T Vertex_handle; + + typedef typename std::set<T>::const_iterator Simplex_vertex_const_iterator; + typedef typename std::set<T>::iterator Simplex_vertex_iterator; + + /** @name Constructors / Destructors / Initialization + */ + //@{ + + void clear() { + simplex_set.clear(); + } + + Skeleton_blocker_simplex(std::initializer_list<T>& list) { + std::for_each(list.begin(), list.end(), [&] (T const& elt) { + add_vertex(elt); + }); + } + + template<typename ... Args> + explicit Skeleton_blocker_simplex(Args ... args) { + add_vertices(args...); + } + + template<typename ... Args> + void add_vertices(T v, Args ... args) { + add_vertex(v); + add_vertices(args...); + } + + void add_vertices(T v) { + add_vertex(v); + } + + void add_vertices() { } + + /** + * Initialize a simplex with a string such as {0,1,2} + */ + explicit Skeleton_blocker_simplex(std::string token) { + clear(); + if ((token[0] == '{') && (token[token.size() - 1] == '}')) { + token.erase(0, 1); + token.erase(token.size() - 1, 1); + while (token.size() != 0) { + int coma_position = token.find_first_of(','); + // cout << "coma_position:"<<coma_position<<endl; + std::string n = token.substr(0, coma_position); + // cout << "token:"<<token<<endl; + token.erase(0, n.size() + 1); + add_vertex((T) (atoi(n.c_str()))); + } + } + } + + //@} + + /** @name Simplex manipulation + */ + //@{ + /** + * Add the vertex v to the simplex: + * Note that adding two times the same vertex is + * the same that adding it once. + */ + void add_vertex(T v) { + simplex_set.insert(v); + } + + /** + * Remove the vertex v from the simplex: + */ + void remove_vertex(T v) { + simplex_set.erase(v); + } + + /** + * Intersects the simplex with the simplex a. + */ + void intersection(const Skeleton_blocker_simplex & a) { + std::vector<T> v; + v.reserve((std::min)(simplex_set.size(), a.simplex_set.size())); + + set_intersection(simplex_set.begin(), simplex_set.end(), + a.simplex_set.begin(), a.simplex_set.end(), + std::back_inserter(v)); + clear(); + for (auto i : v) + simplex_set.insert(i); + } + + /** + * Substracts a from the simplex. + */ + void difference(const Skeleton_blocker_simplex & a) { + std::vector<T> v; + v.reserve(simplex_set.size()); + + set_difference(simplex_set.begin(), simplex_set.end(), + a.simplex_set.begin(), a.simplex_set.end(), + std::back_inserter(v)); + + clear(); + for (auto i : v) + simplex_set.insert(i); + } + + /** + * Add vertices of a to the simplex. + */ + void union_vertices(const Skeleton_blocker_simplex & a) { + std::vector<T> v; + v.reserve(simplex_set.size() + a.simplex_set.size()); + + set_union(simplex_set.begin(), simplex_set.end(), a.simplex_set.begin(), + a.simplex_set.end(), std::back_inserter(v)); + clear(); + simplex_set.insert(v.begin(), v.end()); + } + + typename std::set<T>::const_iterator begin() const { + return simplex_set.cbegin(); + } + + typename std::set<T>::const_iterator end() const { + return simplex_set.cend(); + } + + typename std::set<T>::const_reverse_iterator rbegin() const { + return simplex_set.crbegin(); + } + + typename std::set<T>::const_reverse_iterator rend() const { + return simplex_set.crend(); + } + + typename std::set<T>::iterator begin() { + return simplex_set.begin(); + } + + typename std::set<T>::iterator end() { + return simplex_set.end(); + } + + //@} + + /** @name Queries + */ + //@{ + /** + * Returns the dimension of the simplex. + */ + int dimension() const { + return (simplex_set.size() - 1); + } + + bool empty() const { + return simplex_set.empty(); + } + + /** + * Returns the first and smallest vertex of the simplex. + * + * Be careful : assumes the simplex is non-empty. + */ + T first_vertex() const { + assert(!empty()); + return *(begin()); + } + + /** + * Returns the last and greatest vertex of the simplex. + * + * Be careful : assumes the simplex is non-empty. + */ + T last_vertex() const { + assert(!empty()); + return *(simplex_set.rbegin()); + } + + /** + * @return true iff the simplex contains the simplex a. + */ + bool contains(const Skeleton_blocker_simplex & a) const { + return includes(simplex_set.cbegin(), simplex_set.cend(), + a.simplex_set.cbegin(), a.simplex_set.cend()); + } + + /** + * @return true iff the simplex contains the difference \f$ a \setminus b \f$. + */ + bool contains_difference(const Skeleton_blocker_simplex& a, + const Skeleton_blocker_simplex& b) const { + auto first1 = begin(); + auto last1 = end(); + + auto first2 = a.begin(); + auto last2 = a.end(); + + while (first2 != last2) { + // we ignore vertices of b + if (b.contains(*first2)) { + ++first2; + } else { + if ((first1 == last1) || (*first2 < *first1)) + return false; + if (!(*first1 < *first2)) + ++first2; + ++first1; + } + } + return true; + } + + /** + * @return true iff the simplex contains the difference \f$ a \setminus \{ x \} \f$. + */ + bool contains_difference(const Skeleton_blocker_simplex& a, T x) const { + auto first1 = begin(); + auto last1 = end(); + + auto first2 = a.begin(); + auto last2 = a.end(); + + while (first2 != last2) { + // we ignore vertices x + if (x == *first2) { + ++first2; + } else { + if ((first1 == last1) || (*first2 < *first1)) + return false; + if (!(*first1 < *first2)) + ++first2; + ++first1; + } + } + return true; + } + + /** + * @return true iff the simplex contains the difference \f$ a \setminus \{ x,y \} \f$. + */ + bool contains_difference(const Skeleton_blocker_simplex& a, T x, T y) const { + auto first1 = begin(); + auto last1 = end(); + + auto first2 = a.begin(); + auto last2 = a.end(); + + while (first2 != last2) { + // we ignore vertices of x,y + if (x == *first2 || y == *first2) { + ++first2; + } else { + if ((first1 == last1) || (*first2 < *first1)) + return false; + if (!(*first1 < *first2)) + ++first2; + ++first1; + } + } + return true; + } + + bool contains(T v) const { + return (simplex_set.find(v) != simplex_set.end()); + } + + bool disjoint(const Skeleton_blocker_simplex& a) const { + std::vector<T> v; + v.reserve(std::min(simplex_set.size(), a.simplex_set.size())); + + set_intersection(simplex_set.cbegin(), simplex_set.cend(), + a.simplex_set.cbegin(), a.simplex_set.cend(), + std::back_inserter(v)); + + return (v.size() == 0); + } + + bool operator==(const Skeleton_blocker_simplex& other) const { + return (this->simplex_set == other.simplex_set); + } + + bool operator!=(const Skeleton_blocker_simplex& other) const { + return (this->simplex_set != other.simplex_set); + } + + bool operator<(const Skeleton_blocker_simplex& other) const { + return (std::lexicographical_compare(this->simplex_set.begin(), + this->simplex_set.end(), other.begin(), + other.end())); + } + + //@} + + friend std::ostream& operator<<(std::ostream& o, + const Skeleton_blocker_simplex & sigma) { + bool first = true; + o << "{"; + for (auto i : sigma) { + if (first) + first = false; + else + o << ","; + o << i; + } + o << "}"; + return o; + } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..4c48ff31 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h @@ -0,0 +1,261 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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/Debug_utils.h> + +#include <map> +#include <vector> + +namespace Gudhi { + +namespace skeleton_blocker { + +/** + * @brief Simplicial subcomplex of a complex represented by a skeleton/blockers pair. + * @extends Skeleton_blocker_complex + * @details Stores a subcomplex of a simplicial complex. + * To simplify explanations below, we will suppose that : + * - K is the root simplicial complex + * - L is a subcomplex of K. + * + * One vertex of K may exists in L but with a different address. + * To be able to locate the vertices in K from vertices of L, the class + * stores a map 'adresses' between vertices of K and vertices of L. + * + * Note that the type for handle of vertices of L is 'Vertex_handle' and + * the type for handle of vertices of K is 'Root_vertex_handle'. + * + * The template ComplexType is type of the root complex. It allows to know + * if the subcomplex is geometric or not. + * It has to be either 'Skeleton_blockers_complex' or 'Skeleton_blockers_geometric_complex'. + * + */ +template<typename ComplexType> +class Skeleton_blocker_sub_complex : public ComplexType { + protected: + template<class T> friend class Skeleton_blocker_link_complex; + + typedef typename ComplexType::Graph Graph; + typedef typename ComplexType::Edge_handle Edge_handle; + + typedef typename ComplexType::boost_vertex_handle boost_vertex_handle; + + public: + using ComplexType::add_vertex; + 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 Simplex; + typedef typename ComplexType::Root_simplex_handle Root_simplex_handle; + + protected: + /** + * @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 + */ + typedef std::map<Root_vertex_handle, Vertex_handle> IdAddressMap; + typedef typename IdAddressMap::value_type AddressPair; + typedef typename IdAddressMap::iterator IdAddressMapIterator; + typedef typename IdAddressMap::const_iterator IdAddressMapConstIterator; + std::map<Root_vertex_handle, Vertex_handle> adresses; + + public: + /** + * Add a vertex 'global' of K to L. When added to L, this vertex will receive + * another number, addresses(global), its local adress. + * return the adress where the vertex lay on L. + * The vertex corresponding to 'global' must not be already present + * in the complex. + */ + Vertex_handle add_vertex(Root_vertex_handle global) { + assert(!this->contains_vertex(global)); + Vertex_handle address(boost::add_vertex(this->skeleton)); + this->num_vertices_++; + (*this)[address].activate(); + (*this)[address].set_id(global); + adresses.insert(AddressPair(global, address)); + this->degree_.push_back(0); + return address; + } + + /** + * Add an edge (v1_root,v2_root) to the sub-complex. + * It assumes that both vertices corresponding to v1_root and v2_root are present + * in the sub-complex. + */ + 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_without_blockers(*v1_sub, *v2_sub); + } + + /** + * Add a blocker to the sub-complex. + * It assumes that all vertices of blocker_root are present + * in the sub-complex. + */ + 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(*blocker_sub)); + } + + public: + /** + * Constructs the restricted complex of 'parent_complex' to + * vertices of 'simplex'. + */ + void make_restricted_complex(const ComplexType & parent_complex, + const Simplex& simplex) { + this->clear(); + // add vertices to the sub complex + for (auto x : simplex) { + assert(parent_complex.contains_vertex(x)); + auto x_local = this->add_vertex(parent_complex[x].get_id()); + (*this)[x_local] = parent_complex[x]; + } + + // add edges to the sub complex + for (auto x : simplex) { + // x_neigh is the neighbor of x intersected with vertices_simplex + Simplex x_neigh; + parent_complex.add_neighbours(x, x_neigh, true); + x_neigh.intersection(simplex); + for (auto y : x_neigh) { + this->add_edge_without_blockers(parent_complex[x].get_id(), parent_complex[y].get_id()); + } + } + + // add blockers to the sub complex + for (auto blocker : parent_complex.const_blocker_range()) { + // 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 blocker_restr( + *(this->get_simplex_address(blocker_root))); + this->add_blocker(new Simplex(blocker_restr)); + } + } + } + + void clear() { + adresses.clear(); + ComplexType::clear(); + } + + /** + * Compute the local vertex in L corresponding to the vertex global in K. + * runs in O(log n) if n = num_vertices() + */ + boost::optional<Vertex_handle> get_address(Root_vertex_handle global) const { + boost::optional < Vertex_handle > res; + IdAddressMapConstIterator it = adresses.find(global); + if (it == adresses.end()) + res.reset(); + else + res = (*it).second; + return res; + } + + // /** + // * Allocates a simplex in L corresponding to the simplex s in K + // * with its local adresses and returns an AddressSimplex. + // */ + // boost::optional<Simplex> get_address(const Root_simplex_handle & s) const; + + // private: + /** + * same as get_address except that it will return a simplex in any case. + * The vertices that were not found are not added. + */ + // @remark should be private but problem with VS + + std::vector<boost::optional<Vertex_handle> > get_addresses( + const Root_simplex_handle & s) const { + std::vector < boost::optional<Vertex_handle> > res; + for (auto i : s) { + res.push_back(get_address(i)); + } + return res; + } +}; + +/** + * @remark remarque perte de temps a creer un nouveau simplexe a chaque fois + * alors qu'on pourrait utiliser a la place de 'addresses_sigma_in_link' + * un simplex avec des valeurs sp�ciales ComplexDS::null_vertex par exemple + * pour indiquer qu'un vertex n'appartient pas au complex + */ +template<typename ComplexType> +bool proper_face_in_union( + Skeleton_blocker_sub_complex<ComplexType> & link, + std::vector<boost::optional<typename ComplexType::Vertex_handle> > & addresses_sigma_in_link, + std::size_t vertex_to_be_ignored) { + // 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 sigma_in_link; + for (std::size_t i = 0; i < addresses_sigma_in_link.size(); ++i) { + if (i != vertex_to_be_ignored) { + if (!addresses_sigma_in_link[i]) { + vertices_sigma_are_in_link = false; + break; + } else { + sigma_in_link.add_vertex(*addresses_sigma_in_link[i]); + } + } + } + // If one of vertices of the simplex is not in the complex then it returns false + // Otherwise, it tests if the simplex is in the complex + return vertices_sigma_are_in_link && link.contains(sigma_in_link); +} + +// Remark: this function should be friend in order to leave get_adresses private +// however doing so seemes currently not possible due to a visual studio bug c2668 +// "the compiler does not support partial ordering of template functions as specified in the C++ Standard" +// http://www.serkey.com/error-c2668-ambiguous-call-to-overloaded-function-bb45ft.html + +template<typename ComplexType> +bool proper_faces_in_union( + Skeleton_blocker_simplex<typename ComplexType::Root_vertex_handle> & sigma, + Skeleton_blocker_sub_complex<ComplexType> & link1, + Skeleton_blocker_sub_complex<ComplexType> & link2) { + typedef typename ComplexType::Vertex_handle Vertex_handle; + std::vector < boost::optional<Vertex_handle> > addresses_sigma_in_link1 = + link1.get_addresses(sigma); + std::vector < boost::optional<Vertex_handle> > addresses_sigma_in_link2 = + link2.get_addresses(sigma); + + for (std::size_t current_index = 0; current_index < addresses_sigma_in_link1.size(); + ++current_index) { + if (!proper_face_in_union(link1, addresses_sigma_in_link1, current_index) + && !proper_face_in_union(link2, addresses_sigma_in_link2, + current_index)) { + return false; + } + } + return true; +} + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..91e79b42 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Top_faces.h @@ -0,0 +1,61 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef SKELETON_BLOCKER_INTERNAL_TOP_FACES_H_ +#define SKELETON_BLOCKER_INTERNAL_TOP_FACES_H_ + +#include <list> +#include <vector> +#include <set> + +namespace Gudhi { + +namespace skeleton_blocker { + +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; + } +} + +/** + * 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); + } +} + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..a43fa034 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h @@ -0,0 +1,256 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef SKELETON_BLOCKER_INTERNAL_TRIE_H_ +#define SKELETON_BLOCKER_INTERNAL_TRIE_H_ + +#include <memory> +#include <vector> +#include <deque> +#include <set> + +namespace Gudhi { + +namespace skeleton_blocker { + +template<typename SimplexHandle> +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; + + 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 int current_dimension_ = 0; + std::vector<STrie*> cofaces_; +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..4f51f572 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h @@ -0,0 +1,122 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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 skeleton_blocker { + +/** + * @brief Iterator through the blockers of a vertex. + */ +// 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(); + } +}; + +/** + * @brief Iterator through the blockers of a vertex + */ +// 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_; + } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..154388a1 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h @@ -0,0 +1,135 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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 skeleton_blocker { + +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_; + } +}; + +/** + *@brief Iterator on the edges of a simplicial complex. + * + */ +template<typename 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)); + } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..7b43e05f --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h @@ -0,0 +1,20 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#ifndef SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_ITERATORS_H_ +#define SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_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 // 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 new file mode 100644 index 00000000..920f8cb6 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h @@ -0,0 +1,390 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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/Debug_utils.h> + +#include <boost/iterator/iterator_facade.hpp> + +#include <memory> +#include <list> +#include <iostream> + +namespace Gudhi { + +namespace skeleton_blocker { + +/** + * Link may be Skeleton_blocker_link_complex<SkeletonBlockerComplex> to iterate over all + * simplices around a vertex OR + * Skeleton_blocker_superior_link_complex<SkeletonBlockerComplex> to iterate over all + * superior vertices around a vertex. + * 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> +class Simplex_around_vertex_iterator : +public boost::iterator_facade < Simplex_around_vertex_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; + + // Link_vertex_handle == Complex_Vertex_handle but this renaming helps avoiding confusion + typedef typename Link::Vertex_handle Link_vertex_handle; + + typedef typename Gudhi::skeleton_blocker::Trie<Simplex> Trie; + + private: + const Complex* complex; + Vertex_handle v; + std::shared_ptr<Link> link_v; + std::shared_ptr<Trie> trie; + // TODO(DS): use a deque instead + std::list<Trie*> nodes_to_be_seen; + + 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(DS): avoid useless copy + // TODO(DS): 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(); + + // one is empty the other is not + if (!both_non_empty) return false; + + 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 +, boost::forward_traversal_tag +, 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: + 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()); + } +}; + +/** + * 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: + friend std::ostream& operator<<(std::ostream& stream, const Simplex_coboundary_iterator& sci) { + return stream; + } + + // assume that iterator points to the same complex and comes from the same simplex + bool equal(const Simplex_coboundary_iterator& other) const { + assert(complex == other.complex && sigma == other.sigma); + if (is_end()) return other.is_end(); + if (other.is_end()) return is_end(); + return *current_vertex == *(other.current_vertex); + } + + void increment() { + ++current_vertex; + } + + Simplex dereference() const { + Simplex res(sigma); + res.add_vertex(parent_vertex(*current_vertex)); + return res; + } + + private: + bool is_end() const { + return !link || current_vertex == link_vertex_end; + } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..37c0b4d3 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h @@ -0,0 +1,214 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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 skeleton_blocker { + +/** + * \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> +class Triangle_around_vertex_iterator : public boost::iterator_facade +< Triangle_around_vertex_iterator <Complex, LinkType> +, typename Complex::Simplex const +, boost::forward_traversal_tag +, 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. + * \remark Will be removed soon -> dont look + * + */ +template<typename SkeletonBlockerComplex> +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_), // 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() { + // we must have consume all triangles passing through the vertex + assert(current_triangle_.finished()); + // we must not be done + assert(!is_finished()); + + ++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 skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#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 new file mode 100644 index 00000000..49e94256 --- /dev/null +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h @@ -0,0 +1,158 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): David Salinas + * + * Copyright (C) 2014 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#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 skeleton_blocker { + +/** + *@brief Iterator on the vertices of a simplicial complex + *@remark The increment operator go to the next active vertex. + *@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(); + } +}; + +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: + 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(DS): remove this ugly hack + void set_end() { + current_ = end_; + } +}; + +} // namespace skeleton_blocker + +namespace skbl = skeleton_blocker; + +} // namespace Gudhi + +#endif // SKELETON_BLOCKER_ITERATORS_SKELETON_BLOCKERS_VERTICES_ITERATORS_H_ |