diff options
Diffstat (limited to 'include/gudhi/Skeleton_blocker')
15 files changed, 0 insertions, 2813 deletions
diff --git a/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h b/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h deleted file mode 100644 index 6c6a8638..00000000 --- a/include/gudhi/Skeleton_blocker/Skeleton_blocker_complex_visitor.h +++ /dev/null @@ -1,144 +0,0 @@ -/* 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 - * - * 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_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/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h b/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h deleted file mode 100644 index feab7b3f..00000000 --- a/include/gudhi/Skeleton_blocker/Skeleton_blocker_link_superior.h +++ /dev/null @@ -1,77 +0,0 @@ -/* 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 - * - * 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_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/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h b/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h deleted file mode 100644 index 56009daf..00000000 --- a/include/gudhi/Skeleton_blocker/Skeleton_blocker_off_io.h +++ /dev/null @@ -1,203 +0,0 @@ -/* 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 - * - * 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_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/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h b/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h deleted file mode 100644 index 22c1668e..00000000 --- a/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_geometric_traits.h +++ /dev/null @@ -1,99 +0,0 @@ -/* 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 - * - * 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_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/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h b/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h deleted file mode 100644 index 144f1fd0..00000000 --- a/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h +++ /dev/null @@ -1,190 +0,0 @@ -/* 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 - * - * 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_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/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h b/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h deleted file mode 100644 index d7193157..00000000 --- a/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h +++ /dev/null @@ -1,374 +0,0 @@ -/* 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 - * - * 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_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/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h b/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h deleted file mode 100644 index dbfb4042..00000000 --- a/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h +++ /dev/null @@ -1,273 +0,0 @@ -/* 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 - * - * 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_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/include/gudhi/Skeleton_blocker/internal/Top_faces.h b/include/gudhi/Skeleton_blocker/internal/Top_faces.h deleted file mode 100644 index f80ca4fe..00000000 --- a/include/gudhi/Skeleton_blocker/internal/Top_faces.h +++ /dev/null @@ -1,73 +0,0 @@ -/* 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 - * - * 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 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/include/gudhi/Skeleton_blocker/internal/Trie.h b/include/gudhi/Skeleton_blocker/internal/Trie.h deleted file mode 100644 index 7a5d38eb..00000000 --- a/include/gudhi/Skeleton_blocker/internal/Trie.h +++ /dev/null @@ -1,269 +0,0 @@ -/* 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 - * - * 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_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/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h b/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h deleted file mode 100644 index 95c5f7ef..00000000 --- a/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_blockers_iterators.h +++ /dev/null @@ -1,134 +0,0 @@ -/* 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 - * - * 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 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/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h b/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h deleted file mode 100644 index 5c725aae..00000000 --- a/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_edges_iterators.h +++ /dev/null @@ -1,147 +0,0 @@ -/* 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 - * - * 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 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/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h b/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h deleted file mode 100644 index 8054e64f..00000000 --- a/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_iterators.h +++ /dev/null @@ -1,32 +0,0 @@ - /* 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 - * - * 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_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/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h b/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h deleted file mode 100644 index e2024652..00000000 --- a/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_simplices_iterators.h +++ /dev/null @@ -1,402 +0,0 @@ -/* 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 - * - * 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/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/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h b/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h deleted file mode 100644 index a834fe1d..00000000 --- a/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h +++ /dev/null @@ -1,226 +0,0 @@ -/* 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 - * - * 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 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/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h b/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h deleted file mode 100644 index 3a638ae6..00000000 --- a/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_vertices_iterators.h +++ /dev/null @@ -1,170 +0,0 @@ -/* 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 - * - * 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 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_ |