diff options
Diffstat (limited to 'src/Simplex_tree/include/gudhi/Simplex_tree.h')
-rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 72 |
1 files changed, 55 insertions, 17 deletions
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 4c6a95e8..096270ee 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -35,10 +35,15 @@ #include <boost/iterator/transform_iterator.hpp> #include <boost/graph/adjacency_list.hpp> +#ifdef GUDHI_USE_TBB +#include <tbb/parallel_sort.h> +#endif + #include <algorithm> #include <utility> #include <vector> #include <functional> // for greater<> +#include <initializer_list> namespace Gudhi { @@ -77,15 +82,7 @@ namespace Gudhi { * @{ */ -/// Model of SimplexTreeOptions. -struct Simplex_tree_options_full_featured { - typedef linear_indexing_tag Indexing_tag; - typedef int Vertex_handle; - typedef double Filtration_value; - typedef int Simplex_key; - static const bool store_key = true; - static const bool store_filtration = true; -}; +struct Simplex_tree_options_full_featured; /** * \brief Simplex Tree data structure for representing simplicial complexes. @@ -328,11 +325,10 @@ class Simplex_tree { Simplex_tree(const Simplex_tree& simplex_source) : null_vertex_(simplex_source.null_vertex_), threshold_(simplex_source.threshold_), + root_(nullptr, null_vertex_ , simplex_source.root_.members_), filtration_vect_(), dimension_(simplex_source.dimension_) { auto root_source = simplex_source.root_; - auto memb_source = root_source.members(); - root_ = Siblings(nullptr, null_vertex_, memb_source); rec_copy(&root_, &root_source); } @@ -344,7 +340,7 @@ class Simplex_tree { Siblings * newsib = new Siblings(sib, sh_source->first); newsib->members_.reserve(sh_source->second.children()->members().size()); for (auto & child : sh_source->second.children()->members()) - newsib->members_.emplace_hint(newsib->members_.end(), child.first, Node(sib, child.second.filtration())); + newsib->members_.emplace_hint(newsib->members_.end(), child.first, Node(newsib, child.second.filtration())); rec_copy(newsib, sh_source->second.children()); sh->second.assign_children(newsib); } @@ -531,7 +527,7 @@ class Simplex_tree { * The type InputVertexRange must be a range of <CODE>Vertex_handle</CODE> * on which we can call std::begin() function */ - template<class InputVertexRange> + template<class InputVertexRange = std::initializer_list<Vertex_handle>> Simplex_handle find(const InputVertexRange & s) { auto first = std::begin(s); auto last = std::end(s); @@ -567,9 +563,22 @@ class Simplex_tree { /** \brief Returns the Simplex_handle corresponding to the 0-simplex * representing the vertex with Vertex_handle v. */ Simplex_handle find_vertex(Vertex_handle v) { - return root_.members_.begin() + v; + if (Options::contiguous_vertices) { + assert(contiguous_vertices()); + return root_.members_.begin() + v; + } else { + return root_.members_.find(v); + } + } + + public: + /** \private \brief Test if the vertices have contiguous numbering: 0, 1, etc. */ + bool contiguous_vertices() const { + if (root_.members_.empty()) return true; + if (root_.members_.begin()->first != 0) return false; + if (std::prev(root_.members_.end())->first != root_.members_.size()-1) return false; + return true; } - //{ return root_.members_.find(v); } private: /** \brief Inserts a simplex represented by a vector of vertex. @@ -625,7 +634,7 @@ class Simplex_tree { * * The type InputVertexRange must be a range for which .begin() and * .end() return input iterators, with 'value_type' Vertex_handle. */ - template<class InputVertexRange> + template<class InputVertexRange = std::initializer_list<Vertex_handle>> std::pair<Simplex_handle, bool> insert_simplex(const InputVertexRange & simplex, Filtration_value filtration = 0) { auto first = std::begin(simplex); @@ -654,7 +663,7 @@ class Simplex_tree { * output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to * null_simplex. */ - template<class InputVertexRange> + template<class InputVertexRange=std::initializer_list<Vertex_handle>> std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, Filtration_value filtration = 0) { auto first = std::begin(Nsimplex); @@ -788,8 +797,12 @@ class Simplex_tree { * heuristic consists in inserting the cofaces of a simplex as soon as * possible. */ +#ifdef GUDHI_USE_TBB + tbb::parallel_sort(filtration_vect_, is_before_in_filtration(this)); +#else std::stable_sort(filtration_vect_.begin(), filtration_vect_.end(), is_before_in_filtration(this)); +#endif } private: @@ -1145,6 +1158,31 @@ std::istream& operator>>(std::istream & is, Simplex_tree<T...> & st) { return is; } + +/// Model of SimplexTreeOptions. +struct Simplex_tree_options_full_featured { + typedef linear_indexing_tag Indexing_tag; + typedef int Vertex_handle; + typedef double Filtration_value; + typedef int Simplex_key; + static const bool store_key = true; + static const bool store_filtration = true; + static const bool contiguous_vertices = false; +}; + +/** Model of SimplexTreeOptions, faster than + `Simplex_tree_options_full_featured` but note the unsafe + `contiguous_vertices` option. */ +struct Simplex_tree_options_fast_persistence { + typedef linear_indexing_tag Indexing_tag; + typedef int Vertex_handle; + typedef float Filtration_value; + typedef int Simplex_key; + static const bool store_key = true; + static const bool store_filtration = true; + static const bool contiguous_vertices = true; +}; + /** @} */ // end defgroup simplex_tree } // namespace Gudhi |