diff options
Diffstat (limited to 'src/Simplex_tree')
6 files changed, 223 insertions, 98 deletions
diff --git a/src/Simplex_tree/concept/SimplexTreeOptions.h b/src/Simplex_tree/concept/SimplexTreeOptions.h index add3ebdd..d072cf34 100644 --- a/src/Simplex_tree/concept/SimplexTreeOptions.h +++ b/src/Simplex_tree/concept/SimplexTreeOptions.h @@ -37,5 +37,7 @@ struct SimplexTreeOptions { static const bool store_key; /// If true, each simplex has extra storage for one `Filtration_value`, and this value is propagated by operations like `Gudhi::Simplex_tree::expansion`. Without it, `Persistent_cohomology` degenerates to computing usual (non-persistent) cohomology. static const bool store_filtration; + /// If true, the list of vertices present in the complex must always be 0, ..., num_vertices-1, without any hole. + static constexpr bool contiguous_vertices; }; diff --git a/src/Simplex_tree/example/simplex_tree_from_alpha_shapes_3.cpp b/src/Simplex_tree/example/simplex_tree_from_alpha_shapes_3.cpp index 45efe3ed..49d358ab 100644 --- a/src/Simplex_tree/example/simplex_tree_from_alpha_shapes_3.cpp +++ b/src/Simplex_tree/example/simplex_tree_from_alpha_shapes_3.cpp @@ -62,7 +62,8 @@ typedef Alpha_shape_3::Edge Edge; typedef std::list<Alpha_shape_3::Vertex_handle> Vertex_list; // gudhi type definition -typedef Gudhi::Simplex_tree<>::Vertex_handle Simplex_tree_vertex; +typedef Gudhi::Simplex_tree<> Simplex_tree; +typedef Simplex_tree::Vertex_handle Simplex_tree_vertex; typedef std::map<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex > Alpha_shape_simplex_tree_map; typedef std::pair<Alpha_shape_3::Vertex_handle, Simplex_tree_vertex> Alpha_shape_simplex_tree_pair; typedef std::vector< Simplex_tree_vertex > Simplex_tree_vector_vertex; @@ -161,7 +162,7 @@ int main(int argc, char * const argv[]) { // Loop on objects vector Vertex_list vertex_list; - Gudhi::Simplex_tree<> simplex_tree; + Simplex_tree simplex_tree; Alpha_shape_simplex_tree_map map_cgal_simplex_tree; std::vector<Alpha_value_type>::iterator the_alpha_value_iterator = the_alpha_values.begin(); for (auto object_iterator : the_objects) { diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index d4f9aeae..3ba838a7 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -36,6 +36,10 @@ #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> @@ -80,15 +84,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. @@ -543,7 +539,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=std::initializer_list<Vertex_handle>> + template<class InputVertexRange = std::initializer_list<Vertex_handle>> Simplex_handle find(const InputVertexRange & s) { auto first = std::begin(s); auto last = std::end(s); @@ -579,9 +575,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. @@ -637,7 +646,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=std::initializer_list<Vertex_handle>> + 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); @@ -799,8 +808,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: @@ -1263,6 +1276,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 diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h index 372ef329..936b7a1f 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h @@ -54,7 +54,7 @@ class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade< explicit Simplex_tree_simplex_vertex_iterator(SimplexTree * st) : // any end() iterator - sib_(NULL), + sib_(nullptr), v_(st->null_vertex()) { } @@ -99,21 +99,22 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< // any end() iterator explicit Simplex_tree_boundary_simplex_iterator(SimplexTree * st) - : last_(st->null_vertex()), - sib_(NULL) { + : sib_(nullptr), + sh_(st->null_simplex()), + st_(st) { } Simplex_tree_boundary_simplex_iterator(SimplexTree * st, Simplex_handle sh) - : suffix_(), + : last_(sh->first), + sib_(nullptr), st_(st) { - last_ = sh->first; Siblings * sib = st->self_siblings(sh); next_ = sib->parent(); - sib_ = sib->oncles(); /* \todo check if NULL*/ - if (sib_ != NULL) { + sib_ = sib->oncles(); + if (sib_ != nullptr) { sh_ = sib_->find(next_); } else { - last_ = st->null_vertex(); + sh_ = st->null_simplex(); } // vertex: == end() } @@ -121,28 +122,40 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< friend class boost::iterator_core_access; // valid when iterating along the SAME boundary. bool equal(Simplex_tree_boundary_simplex_iterator const& other) const { - return (sib_ == other.sib_ && last_ == other.last_); + return sh_ == other.sh_; } Simplex_handle const& dereference() const { + assert(sh_ != st_->null_simplex()); return sh_; } void increment() { - if (sib_ == NULL) { - last_ = st_->null_vertex(); + if (sib_ == nullptr) { + sh_ = st_->null_simplex(); return; } Siblings * for_sib = sib_; - for (auto rit = suffix_.rbegin(); rit != suffix_.rend(); ++rit) { + Siblings * new_sib = sib_->oncles(); + auto rit = suffix_.rbegin(); + if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr && rit != suffix_.rend()) { + // We reached the root, use a short-cut to find a vertex. We could also + // optimize finding the second vertex of a segment, but people are + // expected to call endpoints(). + assert(st_->contiguous_vertices()); + sh_ = for_sib->members_.begin()+*rit; + for_sib = sh_->second.children(); + ++rit; + } + for (; rit != suffix_.rend(); ++rit) { sh_ = for_sib->find(*rit); for_sib = sh_->second.children(); } sh_ = for_sib->find(last_); // sh_ points to the right simplex now suffix_.push_back(next_); next_ = sib_->parent(); - sib_ = sib_->oncles(); + sib_ = new_sib; } // Most of the storage should be moved to the range, iterators should be light. @@ -176,13 +189,15 @@ class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade< // any end() iterator Simplex_tree_complex_simplex_iterator() - : st_(NULL) { + : sib_(nullptr), + st_(nullptr) { } explicit Simplex_tree_complex_simplex_iterator(SimplexTree * st) - : st_(st) { - if (st == NULL || st->root() == NULL || st->root()->members().empty()) { - st_ = NULL; + : sib_(nullptr), + st_(st) { + if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) { + st_ = nullptr; } else { sh_ = st->root()->members().begin(); sib_ = st->root(); @@ -197,10 +212,10 @@ class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade< // valid when iterating along the SAME boundary. bool equal(Simplex_tree_complex_simplex_iterator const& other) const { - if (other.st_ == NULL) { - return (st_ == NULL); + if (other.st_ == nullptr) { + return (st_ == nullptr); } - if (st_ == NULL) { + if (st_ == nullptr) { return false; } return (&(sh_->second) == &(other.sh_->second)); @@ -214,8 +229,8 @@ class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade< void increment() { ++sh_; if (sh_ == sib_->members().end()) { - if (sib_->oncles() == NULL) { - st_ = NULL; + if (sib_->oncles() == nullptr) { + st_ = nullptr; return; } // reach the end sh_ = sib_->oncles()->members().find(sib_->parent()); @@ -248,15 +263,19 @@ class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade< // any end() iterator Simplex_tree_skeleton_simplex_iterator() - : st_(NULL) { + : sib_(nullptr), + st_(nullptr), + dim_skel_(0), + curr_dim_(0) { } Simplex_tree_skeleton_simplex_iterator(SimplexTree * st, int dim_skel) - : st_(st), + : sib_(nullptr), + st_(st), dim_skel_(dim_skel), curr_dim_(0) { - if (st == NULL || st->root() == NULL || st->root()->members().empty()) { - st_ = NULL; + if (st == nullptr || st->root() == nullptr || st->root()->members().empty()) { + st_ = nullptr; } else { sh_ = st->root()->members().begin(); sib_ = st->root(); @@ -272,10 +291,10 @@ class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade< // valid when iterating along the SAME boundary. bool equal(Simplex_tree_skeleton_simplex_iterator const& other) const { - if (other.st_ == NULL) { - return (st_ == NULL); + if (other.st_ == nullptr) { + return (st_ == nullptr); } - if (st_ == NULL) { + if (st_ == nullptr) { return false; } return (&(sh_->second) == &(other.sh_->second)); @@ -289,8 +308,8 @@ class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade< void increment() { ++sh_; if (sh_ == sib_->members().end()) { - if (sib_->oncles() == NULL) { - st_ = NULL; + if (sib_->oncles() == nullptr) { + st_ = nullptr; return; } // reach the end sh_ = sib_->oncles()->members().find(sib_->parent()); diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h index c1ff8bf2..8942d92c 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h @@ -57,7 +57,7 @@ class Simplex_tree_siblings { /* Default constructor.*/ Simplex_tree_siblings() - : oncles_(NULL), + : oncles_(nullptr), parent_(-1), members_() { } diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 0d73d347..1a050a25 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -4,10 +4,12 @@ #include <utility> // std::pair, std::make_pair #include <cmath> // float comparison #include <limits> +#include <functional> // greater #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MODULE "simplex_tree" #include <boost/test/unit_test.hpp> +#include <boost/mpl/list.hpp> // ^ // /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. @@ -15,26 +17,25 @@ using namespace Gudhi; -typedef Simplex_tree<> typeST; -typedef std::pair<typeST::Simplex_handle, bool> typePairSimplexBool; -typedef std::vector<Vertex_handle> typeVectorVertex; -typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex; +typedef boost::mpl::list<Simplex_tree<>, Simplex_tree<Simplex_tree_options_fast_persistence>> list_of_tested_variants; const Vertex_handle DEFAULT_VERTEX_HANDLE = (const Vertex_handle) - 1; const Filtration_value DEFAULT_FILTRATION_VALUE = (const Filtration_value) 0.0; +template<class typeST> void test_empty_simplex_tree(typeST& tst) { BOOST_CHECK(tst.null_vertex() == DEFAULT_VERTEX_HANDLE); BOOST_CHECK(tst.filtration() == DEFAULT_FILTRATION_VALUE); BOOST_CHECK(tst.num_vertices() == (size_t) 0); BOOST_CHECK(tst.num_simplices() == (size_t) 0); - typeST::Siblings* STRoot = tst.root(); - BOOST_CHECK(STRoot != NULL); - BOOST_CHECK(STRoot->oncles() == NULL); + typename typeST::Siblings* STRoot = tst.root(); + BOOST_CHECK(STRoot != nullptr); + BOOST_CHECK(STRoot->oncles() == nullptr); BOOST_CHECK(STRoot->parent() == DEFAULT_VERTEX_HANDLE); BOOST_CHECK(tst.dimension() == -1); } +template<class typeST> void test_iterators_on_empty_simplex_tree(typeST& tst) { std::cout << "Iterator on vertices: " << std::endl; for (auto vertex : tst.complex_vertex_range()) { @@ -56,8 +57,9 @@ void test_iterators_on_empty_simplex_tree(typeST& tst) { } } -BOOST_AUTO_TEST_CASE(simplex_tree_when_empty) { - const Filtration_value DEFAULT_FILTRATION_VALUE = 0; +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_when_empty, typeST, list_of_tested_variants) { + typedef std::pair<typename typeST::Simplex_handle, bool> typePairSimplexBool; + typedef std::vector<Vertex_handle> typeVectorVertex; std::cout << "********************************************************************" << std::endl; std::cout << "TEST OF DEFAULT CONSTRUCTOR" << std::endl; @@ -72,7 +74,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_when_empty) { BOOST_CHECK(simplexVectorEmpty.empty() == true); typePairSimplexBool returnEmptyValue = st.insert_simplex(simplexVectorEmpty, DEFAULT_FILTRATION_VALUE); - BOOST_CHECK(returnEmptyValue.first == typeST::Simplex_handle(NULL)); + BOOST_CHECK(returnEmptyValue.first == typename typeST::Simplex_handle(nullptr)); BOOST_CHECK(returnEmptyValue.second == true); test_empty_simplex_tree(st); @@ -84,7 +86,7 @@ bool AreAlmostTheSame(float a, float b) { return std::fabs(a - b) < std::numeric_limits<float>::epsilon(); } -BOOST_AUTO_TEST_CASE(simplex_tree_from_file) { +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_from_file, typeST, list_of_tested_variants) { // TEST OF INSERTION std::cout << "********************************************************************" << std::endl; std::cout << "TEST OF SIMPLEX TREE FROM A FILE" << std::endl; @@ -101,7 +103,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_from_file) { // Check BOOST_CHECK(st.num_simplices() == 143353); BOOST_CHECK(st.dimension() == 3); - BOOST_CHECK(st.filtration() == 0.4); + BOOST_CHECK(AreAlmostTheSame(st.filtration(), 0.4)); int previous_size = 0; for (auto f_simplex : st.filtration_simplex_range()) { @@ -119,6 +121,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_from_file) { simplex_tree_stream.close(); } +template<class typeST, class typeSimplex> void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int pos) { auto f_simplex = simplexTree.filtration_simplex_range().begin() + pos; @@ -135,16 +138,18 @@ void test_simplex_tree_contains(typeST& simplexTree, typeSimplex& simplex, int p } } +template<class typeST, class typePairSimplexBool> void test_simplex_tree_insert_returns_true(const typePairSimplexBool& returnValue) { BOOST_CHECK(returnValue.second == true); - typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator - BOOST_CHECK(shReturned != typeST::Simplex_handle(NULL)); + typename typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator + BOOST_CHECK(shReturned != typename typeST::Simplex_handle(nullptr)); } // Global variables Filtration_value max_fil = DEFAULT_FILTRATION_VALUE; int dim_max = -1; +template<class typeST, class Filtration_value> void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, const Filtration_value& fil) { if (vectorSize > dim_max + 1) { dim_max = vectorSize - 1; @@ -173,11 +178,17 @@ void set_and_test_simplex_tree_dim_fil(typeST& simplexTree, int vectorSize, cons BOOST_CHECK(simplexTree.num_simplices() == num_simp); } -BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_variants) { + typedef std::pair<typename typeST::Simplex_handle, bool> typePairSimplexBool; + typedef std::vector<Vertex_handle> typeVectorVertex; + typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex; const Filtration_value FIRST_FILTRATION_VALUE = 0.1; const Filtration_value SECOND_FILTRATION_VALUE = 0.2; const Filtration_value THIRD_FILTRATION_VALUE = 0.3; const Filtration_value FOURTH_FILTRATION_VALUE = 0.4; + // reset since we run the test several times + dim_max = -1; + max_fil = DEFAULT_FILTRATION_VALUE; // TEST OF INSERTION std::cout << "********************************************************************" << std::endl; @@ -191,7 +202,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { typeSimplex firstSimplex = std::make_pair(firstSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); typePairSimplexBool returnValue = st.insert_simplex(firstSimplex.first, firstSimplex.second); - test_simplex_tree_insert_returns_true(returnValue); + test_simplex_tree_insert_returns_true<typeST>(returnValue); set_and_test_simplex_tree_dim_fil(st, firstSimplexVector.size(), firstSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 1); @@ -202,7 +213,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { typeSimplex secondSimplex = std::make_pair(secondSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = st.insert_simplex(secondSimplex.first, secondSimplex.second); - test_simplex_tree_insert_returns_true(returnValue); + test_simplex_tree_insert_returns_true<typeST>(returnValue); set_and_test_simplex_tree_dim_fil(st, secondSimplexVector.size(), secondSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 2); @@ -213,7 +224,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { typeSimplex thirdSimplex = std::make_pair(thirdSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = st.insert_simplex(thirdSimplex.first, thirdSimplex.second); - test_simplex_tree_insert_returns_true(returnValue); + test_simplex_tree_insert_returns_true<typeST>(returnValue); set_and_test_simplex_tree_dim_fil(st, thirdSimplexVector.size(), thirdSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 2); // Not incremented !! @@ -224,7 +235,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { typeSimplex fourthSimplex = std::make_pair(fourthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = st.insert_simplex(fourthSimplex.first, fourthSimplex.second); - test_simplex_tree_insert_returns_true(returnValue); + test_simplex_tree_insert_returns_true<typeST>(returnValue); set_and_test_simplex_tree_dim_fil(st, fourthSimplexVector.size(), fourthSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 3); @@ -235,7 +246,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { typeSimplex fifthSimplex = std::make_pair(fifthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = st.insert_simplex(fifthSimplex.first, fifthSimplex.second); - test_simplex_tree_insert_returns_true(returnValue); + test_simplex_tree_insert_returns_true<typeST>(returnValue); set_and_test_simplex_tree_dim_fil(st, fifthSimplexVector.size(), fifthSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! @@ -246,7 +257,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { typeSimplex sixthSimplex = std::make_pair(sixthSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = st.insert_simplex(sixthSimplex.first, sixthSimplex.second); - test_simplex_tree_insert_returns_true(returnValue); + test_simplex_tree_insert_returns_true<typeST>(returnValue); set_and_test_simplex_tree_dim_fil(st, sixthSimplexVector.size(), sixthSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! @@ -257,7 +268,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { typeSimplex seventhSimplex = std::make_pair(seventhSimplexVector, Filtration_value(THIRD_FILTRATION_VALUE)); returnValue = st.insert_simplex(seventhSimplex.first, seventhSimplex.second); - test_simplex_tree_insert_returns_true(returnValue); + test_simplex_tree_insert_returns_true<typeST>(returnValue); set_and_test_simplex_tree_dim_fil(st, seventhSimplexVector.size(), seventhSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 3); // Not incremented !! @@ -268,7 +279,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { typeSimplex eighthSimplex = std::make_pair(eighthSimplexVector, Filtration_value(FIRST_FILTRATION_VALUE)); returnValue = st.insert_simplex(eighthSimplex.first, eighthSimplex.second); - test_simplex_tree_insert_returns_true(returnValue); + test_simplex_tree_insert_returns_true<typeST>(returnValue); set_and_test_simplex_tree_dim_fil(st, eighthSimplexVector.size(), eighthSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 4); @@ -279,7 +290,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { typeSimplex ninethSimplex = std::make_pair(ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); returnValue = st.insert_simplex(ninethSimplex.first, ninethSimplex.second); - test_simplex_tree_insert_returns_true(returnValue); + test_simplex_tree_insert_returns_true<typeST>(returnValue); set_and_test_simplex_tree_dim_fil(st, ninethSimplexVector.size(), ninethSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! @@ -292,8 +303,8 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { returnValue = st.insert_simplex(tenthSimplex.first, tenthSimplex.second); BOOST_CHECK(returnValue.second == false); - typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator - BOOST_CHECK(shReturned == typeST::Simplex_handle(NULL)); + typename typeST::Simplex_handle shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator + BOOST_CHECK(shReturned == typename typeST::Simplex_handle(nullptr)); BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! BOOST_CHECK(st.dimension() == dim_max); BOOST_CHECK(AreAlmostTheSame(st.filtration(), max_fil)); @@ -307,7 +318,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { BOOST_CHECK(returnValue.second == false); shReturned = returnValue.first; // Simplex_handle = boost::container::flat_map< Vertex_handle, Node >::iterator - BOOST_CHECK(shReturned == typeST::Simplex_handle(NULL)); + BOOST_CHECK(shReturned == typename typeST::Simplex_handle(nullptr)); BOOST_CHECK(st.num_vertices() == (size_t) 4); // Not incremented !! BOOST_CHECK(st.dimension() == dim_max); BOOST_CHECK(AreAlmostTheSame(st.filtration(), max_fil)); @@ -351,7 +362,7 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { // Display the Simplex_tree - Can not be done in the middle of 2 inserts std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; - std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; for (auto f_simplex : st.filtration_simplex_range()) { std::cout << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { @@ -362,11 +373,10 @@ BOOST_AUTO_TEST_CASE(simplex_tree_insertion) { } -bool sort_in_decr_order(Vertex_handle i, Vertex_handle j) { - return (i > j); -} - -BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { +BOOST_AUTO_TEST_CASE_TEMPLATE(NSimplexAndSubfaces_tree_insertion, typeST, list_of_tested_variants) { + typedef std::pair<typename typeST::Simplex_handle, bool> typePairSimplexBool; + typedef std::vector<Vertex_handle> typeVectorVertex; + typedef std::pair<typeVectorVertex, Filtration_value> typeSimplex; std::cout << "********************************************************************" << std::endl; std::cout << "TEST OF RECURSIVE INSERTION" << std::endl; typeST st; @@ -384,7 +394,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Check it is well inserted BOOST_CHECK(true == returnValue.second); position = 0; - std::sort(SimplexVector1.begin(), SimplexVector1.end(), sort_in_decr_order); + std::sort(SimplexVector1.begin(), SimplexVector1.end(), std::greater<Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector1[position] << std::endl; @@ -403,7 +413,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Check it is well inserted BOOST_CHECK(true == returnValue.second); position = 0; - std::sort(SimplexVector2.begin(), SimplexVector2.end(), sort_in_decr_order); + std::sort(SimplexVector2.begin(), SimplexVector2.end(), std::greater<Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector2[position] << std::endl; @@ -422,7 +432,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Check it is well inserted BOOST_CHECK(true == returnValue.second); position = 0; - std::sort(SimplexVector3.begin(), SimplexVector3.end(), sort_in_decr_order); + std::sort(SimplexVector3.begin(), SimplexVector3.end(), std::greater<Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector3[position] << std::endl; @@ -452,7 +462,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Check it is well inserted BOOST_CHECK(true == returnValue.second); position = 0; - std::sort(SimplexVector5.begin(), SimplexVector5.end(), sort_in_decr_order); + std::sort(SimplexVector5.begin(), SimplexVector5.end(), std::greater<Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector5[position] << std::endl; @@ -471,14 +481,14 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Check it is well inserted BOOST_CHECK(true == returnValue.second); position = 0; - std::sort(SimplexVector6.begin(), SimplexVector6.end(), sort_in_decr_order); + std::sort(SimplexVector6.begin(), SimplexVector6.end(), std::greater<Vertex_handle>()); for (auto vertex : st.simplex_vertex_range(returnValue.first)) { // Check returned Simplex_handle std::cout << "vertex = " << vertex << " | vector[" << position << "] = " << SimplexVector6[position] << std::endl; BOOST_CHECK(vertex == SimplexVector6[position]); position++; } - + /* Inserted simplex: */ /* 1 6 */ /* o---o */ @@ -494,11 +504,24 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { /* A facet [3,4,5] */ /* A cell [0,1,6,7] */ + typeSimplex simplexPair1 = std::make_pair(SimplexVector1, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair2 = std::make_pair(SimplexVector2, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair3 = std::make_pair(SimplexVector3, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair4 = std::make_pair(SimplexVector4, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair5 = std::make_pair(SimplexVector5, DEFAULT_FILTRATION_VALUE); + typeSimplex simplexPair6 = std::make_pair(SimplexVector6, DEFAULT_FILTRATION_VALUE); + test_simplex_tree_contains(st, simplexPair1, 6); // (2,1,0) is in position 6 + test_simplex_tree_contains(st, simplexPair2, 7); // (3) is in position 7 + test_simplex_tree_contains(st, simplexPair3, 8); // (3,0) is in position 8 + test_simplex_tree_contains(st, simplexPair4, 2); // (1,0) is in position 2 + test_simplex_tree_contains(st, simplexPair5, 14); // (3,4,5) is in position 14 + test_simplex_tree_contains(st, simplexPair6, 26); // (7,6,1,0) is in position 26 + // ------------------------------------------------------------------------------------------------------------------ // Find in the simplex_tree // ------------------------------------------------------------------------------------------------------------------ typeVectorVertex simpleSimplexVector{1}; - Simplex_tree<>::Simplex_handle simplexFound = st.find(simpleSimplexVector); + typename typeST::Simplex_handle simplexFound = st.find(simpleSimplexVector); std::cout << "**************IS THE SIMPLEX {1} IN THE SIMPLEX TREE ?\n"; if (simplexFound != st.null_simplex()) std::cout << "***+ YES IT IS!\n"; @@ -549,7 +572,7 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { // Display the Simplex_tree - Can not be done in the middle of 2 inserts std::cout << "The complex contains " << st.num_simplices() << " simplices" << std::endl; std::cout << " - dimension " << st.dimension() << " - filtration " << st.filtration() << std::endl; - std::cout << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; + std::cout << std::endl << std::endl << "Iterator on Simplices in the filtration, with [filtration value]:" << std::endl; for (auto f_simplex : st.filtration_simplex_range()) { std::cout << " " << "[" << st.filtration(f_simplex) << "] "; for (auto vertex : st.simplex_vertex_range(f_simplex)) { @@ -559,14 +582,15 @@ BOOST_AUTO_TEST_CASE(NSimplexAndSubfaces_tree_insertion) { } } -void test_cofaces(typeST& st, std::vector<Vertex_handle> expected, int dim, std::vector<typeST::Simplex_handle> res) { - typeST::Cofaces_simplex_range cofaces; +template<class typeST, class Vertex_handle> +void test_cofaces(typeST& st, const std::vector<Vertex_handle>& expected, int dim, const std::vector<typename typeST::Simplex_handle>& res) { + typename typeST::Cofaces_simplex_range cofaces; if (dim == 0) cofaces = st.star_simplex_range(st.find(expected)); else cofaces = st.cofaces_simplex_range(st.find(expected), dim); for (auto simplex = cofaces.begin(); simplex != cofaces.end(); ++simplex) { - typeST::Simplex_vertex_range rg = st.simplex_vertex_range(*simplex); + typename typeST::Simplex_vertex_range rg = st.simplex_vertex_range(*simplex); for (auto vertex = rg.begin(); vertex != rg.end(); ++vertex) { std::cout << "(" << *vertex << ")"; } @@ -575,7 +599,8 @@ void test_cofaces(typeST& st, std::vector<Vertex_handle> expected, int dim, std: } } -BOOST_AUTO_TEST_CASE(coface_on_simplex_tree) { +BOOST_AUTO_TEST_CASE_TEMPLATE(coface_on_simplex_tree, typeST, list_of_tested_variants) { + typedef std::vector<Vertex_handle> typeVectorVertex; std::cout << "********************************************************************" << std::endl; std::cout << "TEST COFACE ALGORITHM" << std::endl; typeST st; @@ -605,7 +630,7 @@ BOOST_AUTO_TEST_CASE(coface_on_simplex_tree) { st.set_dimension(3); std::vector<Vertex_handle> simplex_result; - std::vector<typeST::Simplex_handle> result; + std::vector<typename typeST::Simplex_handle> result; std::cout << "First test - Star of (3):" << std::endl; simplex_result = {3}; @@ -673,7 +698,8 @@ BOOST_AUTO_TEST_CASE(coface_on_simplex_tree) { } -BOOST_AUTO_TEST_CASE(copy_move_on_simplex_tree) { +BOOST_AUTO_TEST_CASE_TEMPLATE(copy_move_on_simplex_tree, typeST, list_of_tested_variants) { + typedef std::vector<Vertex_handle> typeVectorVertex; std::cout << "********************************************************************" << std::endl; std::cout << "TEST COPY MOVE CONSTRUCTORS" << std::endl; typeST st; @@ -722,21 +748,58 @@ BOOST_AUTO_TEST_CASE(copy_move_on_simplex_tree) { // Check there is a new simplex tree reference BOOST_CHECK(&st_move != &st_copy); BOOST_CHECK(&st_move != &st); - + typeST st_empty; // Check st has been emptied by the move BOOST_CHECK(st == st_empty); BOOST_CHECK(st.filtration() == 0); BOOST_CHECK(st.dimension() == -1); BOOST_CHECK(st.num_simplices() == 0); - BOOST_CHECK(st.num_vertices() == (size_t) 0); - + BOOST_CHECK(st.num_vertices() == (size_t)0); + std::cout << "Printing st once again- address = " << &st << std::endl; } +template<class typeST> +void test_simplex_is_vertex(typeST& st, typename typeST::Simplex_handle sh, typename typeST::Vertex_handle v) { + BOOST_CHECK(st.dimension(sh) == 0); + auto&& r = st.simplex_vertex_range(sh); + auto i = std::begin(r); + BOOST_CHECK(*i == v); + BOOST_CHECK(++i == std::end(r)); +} + +BOOST_AUTO_TEST_CASE(non_contiguous) { + typedef Simplex_tree<> typeST; + typedef typeST::Vertex_handle Vertex_handle; + typedef typeST::Simplex_handle Simplex_handle; + std::cout << "********************************************************************" << std::endl; + std::cout << "TEST NON-CONTIGUOUS VERTICES" << std::endl; + typeST st; + Vertex_handle e[] = {3,-7}; + std::cout << "Insert" << std::endl; + st.insert_simplex_and_subfaces(e); + BOOST_CHECK(st.num_vertices() == 2); + BOOST_CHECK(st.num_simplices() == 3); + std::cout << "Find" << std::endl; + Simplex_handle sh = st.find(e); + BOOST_CHECK(sh != st.null_simplex()); + std::cout << "Endpoints" << std::endl; + auto p = st.endpoints(sh); + test_simplex_is_vertex(st, p.first, 3); + test_simplex_is_vertex(st, p.second, -7); + std::cout << "Boundary" << std::endl; + auto&& b = st.boundary_simplex_range(sh); + auto i = std::begin(b); + test_simplex_is_vertex(st, *i, -7); + test_simplex_is_vertex(st, *++i, 3); + BOOST_CHECK(++i == std::end(b)); +} + BOOST_AUTO_TEST_CASE(make_filtration_non_decreasing) { std::cout << "********************************************************************" << std::endl; std::cout << "MAKE FILTRATION NON DECREASING" << std::endl; + typedef Simplex_tree<> typeST; typeST st; st.insert_simplex_and_subfaces({2, 1, 0}, 4.0); @@ -803,12 +866,13 @@ struct MyOptions : Simplex_tree_options_full_featured { // I have few vertices typedef short Vertex_handle; }; -typedef Simplex_tree<MyOptions> miniST; BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { std::cout << "********************************************************************" << std::endl; std::cout << "REMOVE MAXIMAL SIMPLEX" << std::endl; + + typedef Simplex_tree<MyOptions> miniST; miniST st; // FIXME @@ -892,6 +956,7 @@ BOOST_AUTO_TEST_CASE(remove_maximal_simplex) { BOOST_AUTO_TEST_CASE(prune_above_filtration) { std::cout << "********************************************************************" << std::endl; std::cout << "PRUNE ABOVE FILTRATION" << std::endl; + typedef Simplex_tree<> typeST; typeST st; // FIXME |