From 73194242e1c8012c1320a7581a382a3b2b59eb09 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Tue, 3 Mar 2020 16:30:22 +0100 Subject: Fix #172 and add a proper comment on the modification --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'src/Simplex_tree/include/gudhi') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 76608008..5110819f 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1347,7 +1347,9 @@ class Simplex_tree { }); Filtration_value max_filt_border_value = filtration(*max_border); - if (simplex.second.filtration() < max_filt_border_value) { + // Replacing if(f=max)) would mean that if f is NaN, we replace it with the max of the children. + // That seems more useful than keeping NaN. + if (!(simplex.second.filtration() >= max_filt_border_value)) { // Store the filtration modification information modified = true; simplex.second.assign_filtration(max_filt_border_value); -- cgit v1.2.3 From 5b5e9fce6a80151f29f98dde67f5e4150edb9a5b Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 5 Mar 2020 10:03:26 +0100 Subject: Add some tests and documentation for NaN management in make_filtration_non_decreasing Simplex tree method --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 + src/Simplex_tree/test/CMakeLists.txt | 6 + ...ee_make_filtration_non_decreasing_unit_test.cpp | 148 +++++++++++++++++++++ src/Simplex_tree/test/simplex_tree_unit_test.cpp | 84 ------------ 4 files changed, 156 insertions(+), 84 deletions(-) create mode 100644 src/Simplex_tree/test/simplex_tree_make_filtration_non_decreasing_unit_test.cpp (limited to 'src/Simplex_tree/include/gudhi') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 5110819f..7b39a500 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1317,6 +1317,8 @@ class Simplex_tree { * \post Some simplex tree functions require the filtration to be valid. `make_filtration_non_decreasing()` * function is not launching `initialize_filtration()` but returns the filtration modification information. If the * complex has changed , please call `initialize_filtration()` to recompute it. + * + * If a simplex has a `NaN` filtration value, it is considered lower than any other defined filtration value. */ bool make_filtration_non_decreasing() { bool modified = false; diff --git a/src/Simplex_tree/test/CMakeLists.txt b/src/Simplex_tree/test/CMakeLists.txt index 8b9163f5..cf2b0153 100644 --- a/src/Simplex_tree/test/CMakeLists.txt +++ b/src/Simplex_tree/test/CMakeLists.txt @@ -28,3 +28,9 @@ if (TBB_FOUND) target_link_libraries(Simplex_tree_ctor_and_move_test_unit ${TBB_LIBRARIES}) endif() gudhi_add_boost_test(Simplex_tree_ctor_and_move_test_unit) + +add_executable ( Simplex_tree_make_filtration_non_decreasing_test_unit simplex_tree_make_filtration_non_decreasing_unit_test.cpp ) +if (TBB_FOUND) + target_link_libraries(Simplex_tree_make_filtration_non_decreasing_test_unit ${TBB_LIBRARIES}) +endif() +gudhi_add_boost_test(Simplex_tree_make_filtration_non_decreasing_test_unit) diff --git a/src/Simplex_tree/test/simplex_tree_make_filtration_non_decreasing_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_make_filtration_non_decreasing_unit_test.cpp new file mode 100644 index 00000000..a8130e25 --- /dev/null +++ b/src/Simplex_tree/test/simplex_tree_make_filtration_non_decreasing_unit_test.cpp @@ -0,0 +1,148 @@ +/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT. + * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. + * Author(s): Vincent Rouvreau + * + * Copyright (C) 2020 Inria + * + * Modification(s): + * - YYYY/MM Author: Description of the modification + */ + +#include +#include // for NaN +#include // for isNaN + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "simplex_tree_make_filtration_non_decreasing" +#include +#include + +// ^ +// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. +#include "gudhi/Simplex_tree.h" + +using namespace Gudhi; + +typedef boost::mpl::list, Simplex_tree> list_of_tested_variants; + +BOOST_AUTO_TEST_CASE_TEMPLATE(make_filtration_non_decreasing, typeST, list_of_tested_variants) { + typeST st; + + st.insert_simplex_and_subfaces({2, 1, 0}, 2.0); + st.insert_simplex_and_subfaces({3, 0}, 2.0); + st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + + /* Inserted simplex: */ + /* 1 */ + /* o */ + /* /X\ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + + std::cout << "Check default insertion ensures the filtration values are non decreasing" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); + + // Because of non decreasing property of simplex tree, { 0 } , { 1 } and { 0, 1 } are going to be set from value 2.0 + // to 1.0 + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + + // Inserted simplex: + // 1 6 + // o---o + // /X\7/ + // o---o---o---o + // 2 0 3\X/4 + // o + // 5 + + std::cout << "Check default second insertion ensures the filtration values are non decreasing" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); + + // Copy original simplex tree + typeST st_copy = st; + + // Modify specific values for st to become like st_copy thanks to make_filtration_non_decreasing + st.assign_filtration(st.find({0,1,6,7}), 0.8); + st.assign_filtration(st.find({0,1,6}), 0.9); + st.assign_filtration(st.find({0,6}), 0.6); + st.assign_filtration(st.find({3,4,5}), 1.2); + st.assign_filtration(st.find({3,4}), 1.1); + st.assign_filtration(st.find({4,5}), 1.99); + + std::cout << "Check the simplex_tree is rolled back in case of decreasing filtration values" << std::endl; + BOOST_CHECK(st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_copy); + + // Other simplex tree + typeST st_other; + st_other.insert_simplex_and_subfaces({2, 1, 0}, 3.0); // This one is different from st + st_other.insert_simplex_and_subfaces({3, 0}, 2.0); + st_other.insert_simplex_and_subfaces({3, 4, 5}, 2.0); + st_other.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); + + // Modify specific values for st to become like st_other thanks to make_filtration_non_decreasing + st.assign_filtration(st.find({2}), 3.0); + // By modifying just the simplex {2} + // {0,1,2}, {1,2} and {0,2} will be modified + + std::cout << "Check the simplex_tree is repaired in case of decreasing filtration values" << std::endl; + BOOST_CHECK(st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_other); + + // Modify specific values for st still to be non-decreasing + st.assign_filtration(st.find({0,1,2}), 10.0); + st.assign_filtration(st.find({0,2}), 9.0); + st.assign_filtration(st.find({0,1,6,7}), 50.0); + st.assign_filtration(st.find({0,1,6}), 49.0); + st.assign_filtration(st.find({0,1,7}), 48.0); + // Other copy simplex tree + typeST st_other_copy = st; + + std::cout << "Check the simplex_tree is not modified in case of non-decreasing filtration values" << std::endl; + BOOST_CHECK(!st.make_filtration_non_decreasing()); + BOOST_CHECK(st == st_other_copy); + +} + +BOOST_AUTO_TEST_CASE_TEMPLATE(make_filtration_non_decreasing_on_nan_values, typeST, list_of_tested_variants) { + typeST st; + + st.insert_simplex_and_subfaces({2, 1, 0}, std::numeric_limits::quiet_NaN()); + st.insert_simplex_and_subfaces({3, 0}, std::numeric_limits::quiet_NaN()); + st.insert_simplex_and_subfaces({3, 4, 5}, std::numeric_limits::quiet_NaN()); + + /* Inserted simplex: */ + /* 1 */ + /* o */ + /* /X\ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + + std::cout << "SPECIFIC CASE:" << std::endl; + std::cout << "Insertion with NaN values does not ensure the filtration values are non decreasing" << std::endl; + st.make_filtration_non_decreasing(); + + std::cout << "Check all filtration values are NaN" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + BOOST_CHECK(std::isnan(st.filtration(f_simplex))); + } + + st.assign_filtration(st.find({0}), 0.); + st.assign_filtration(st.find({1}), 0.); + st.assign_filtration(st.find({2}), 0.); + st.assign_filtration(st.find({3}), 0.); + st.assign_filtration(st.find({4}), 0.); + st.assign_filtration(st.find({5}), 0.); + + std::cout << "Check make_filtration_non_decreasing is modifying the simplicial complex" << std::endl; + BOOST_CHECK(st.make_filtration_non_decreasing()); + + std::cout << "Check all filtration values are now defined" << std::endl; + for (auto f_simplex : st.filtration_simplex_range()) { + BOOST_CHECK(!std::isnan(st.filtration(f_simplex))); + } +} \ No newline at end of file diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 58bfa8db..e739ad0a 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -791,90 +791,6 @@ BOOST_AUTO_TEST_CASE(non_contiguous) { 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}, 2.0); - st.insert_simplex_and_subfaces({3, 0}, 2.0); - st.insert_simplex_and_subfaces({3, 4, 5}, 2.0); - - /* Inserted simplex: */ - /* 1 */ - /* o */ - /* /X\ */ - /* o---o---o---o */ - /* 2 0 3\X/4 */ - /* o */ - /* 5 */ - - std::cout << "Check default insertion ensures the filtration values are non decreasing" << std::endl; - BOOST_CHECK(!st.make_filtration_non_decreasing()); - - // Because of non decreasing property of simplex tree, { 0 } , { 1 } and { 0, 1 } are going to be set from value 2.0 - // to 1.0 - st.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); - - // Inserted simplex: - // 1 6 - // o---o - // /X\7/ - // o---o---o---o - // 2 0 3\X/4 - // o - // 5 - - std::cout << "Check default second insertion ensures the filtration values are non decreasing" << std::endl; - BOOST_CHECK(!st.make_filtration_non_decreasing()); - - // Copy original simplex tree - typeST st_copy = st; - - // Modify specific values for st to become like st_copy thanks to make_filtration_non_decreasing - st.assign_filtration(st.find({0,1,6,7}), 0.8); - st.assign_filtration(st.find({0,1,6}), 0.9); - st.assign_filtration(st.find({0,6}), 0.6); - st.assign_filtration(st.find({3,4,5}), 1.2); - st.assign_filtration(st.find({3,4}), 1.1); - st.assign_filtration(st.find({4,5}), 1.99); - - std::cout << "Check the simplex_tree is rolled back in case of decreasing filtration values" << std::endl; - BOOST_CHECK(st.make_filtration_non_decreasing()); - BOOST_CHECK(st == st_copy); - - // Other simplex tree - typeST st_other; - st_other.insert_simplex_and_subfaces({2, 1, 0}, 3.0); // This one is different from st - st_other.insert_simplex_and_subfaces({3, 0}, 2.0); - st_other.insert_simplex_and_subfaces({3, 4, 5}, 2.0); - st_other.insert_simplex_and_subfaces({0, 1, 6, 7}, 1.0); - - // Modify specific values for st to become like st_other thanks to make_filtration_non_decreasing - st.assign_filtration(st.find({2}), 3.0); - // By modifying just the simplex {2} - // {0,1,2}, {1,2} and {0,2} will be modified - - std::cout << "Check the simplex_tree is repaired in case of decreasing filtration values" << std::endl; - BOOST_CHECK(st.make_filtration_non_decreasing()); - BOOST_CHECK(st == st_other); - - // Modify specific values for st still to be non-decreasing - st.assign_filtration(st.find({0,1,2}), 10.0); - st.assign_filtration(st.find({0,2}), 9.0); - st.assign_filtration(st.find({0,1,6,7}), 50.0); - st.assign_filtration(st.find({0,1,6}), 49.0); - st.assign_filtration(st.find({0,1,7}), 48.0); - // Other copy simplex tree - typeST st_other_copy = st; - - std::cout << "Check the simplex_tree is not modified in case of non-decreasing filtration values" << std::endl; - BOOST_CHECK(!st.make_filtration_non_decreasing()); - BOOST_CHECK(st == st_other_copy); - -} - typedef boost::mpl::list, -- cgit v1.2.3 From 78ccc10eb0034a4648df303f2913b6b4680b085e Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Fri, 6 Mar 2020 17:35:38 +0100 Subject: Generators for simplex tree --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 86 +++++++++++++++++++++- .../gudhi/Simplex_tree/Simplex_tree_iterators.h | 12 +-- src/Simplex_tree/test/simplex_tree_unit_test.cpp | 36 +++++++++ 3 files changed, 122 insertions(+), 12 deletions(-) (limited to 'src/Simplex_tree/include/gudhi') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 76608008..7315bf45 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -24,6 +24,7 @@ #include #include #include +#include #ifdef GUDHI_USE_TBB #include @@ -246,8 +247,8 @@ class Simplex_tree { * which is consequenlty * equal to \f$(-1)^{\text{dim} \sigma}\f$ the canonical orientation on the simplex. */ - Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) { - assert(sh != null_simplex()); // Empty simplex + Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) const { + GUDHI_CHECK(sh != null_simplex(), "empty simplex"); return Simplex_vertex_range(Simplex_vertex_iterator(this, sh), Simplex_vertex_iterator(this)); } @@ -450,6 +451,15 @@ class Simplex_tree { return true; } + /** \brief Returns the filtration value of a simplex. + * + * Same as `filtration()`, but does not handle `null_simplex()`. + */ + static Filtration_value filtration_(Simplex_handle sh) { + GUDHI_CHECK (sh != null_simplex(), "null simplex"); + return sh->second.filtration(); + } + public: /** \brief Returns the key associated to a simplex. * @@ -827,7 +837,7 @@ class Simplex_tree { /** Returns the Siblings containing a simplex.*/ template - Siblings* self_siblings(SimplexHandle sh) { + static Siblings* self_siblings(SimplexHandle sh) { if (sh->second.children()->parent() == sh->first) return sh->second.children()->oncles(); else @@ -1465,6 +1475,76 @@ class Simplex_tree { } } + /** \brief Returns a vertex of `sh` that has the same filtration value as `sh` if it exists, and `null_vertex()` otherwise. + * + * For a lower-star filtration built with `make_filtration_non_decreasing()`, this is a way to invert the process and find out which vertex had its filtration value propagated to `sh`. + * If several vertices have the same filtration value, the one it returns is arbitrary. */ + Vertex_handle vertex_with_same_filtration(Simplex_handle sh) { + auto filt = filtration_(sh); + for(auto v : simplex_vertex_range(sh)) + if(filtration_(find_vertex(v)) == filt) + return v; + return null_vertex(); + } + + /** \brief Returns an edge of `sh` that has the same filtration value as `sh` if it exists, and `null_simplex()` otherwise. + * + * For a flag-complex built with `expansion()`, this is a way to invert the process and find out which edge had its filtration value propagated to `sh`. + * If several edges have the same filtration value, the one it returns is arbitrary. + * + * \pre `sh` must have dimension at least 1. */ + Simplex_handle edge_with_same_filtration(Simplex_handle sh) { +#if 0 + // FIXME: Only do this if dim >= 2, since we don't want to return a vertex... + // Test if we are lucky and the parent has the same filtration value. + Siblings* sib = self_siblings(sh); + Vertex_handle v_par = sib->parent(); + sib = sib->oncles(); + Simplex_handle par = sib->find(v_par); + if(filtration_(par) == filt) return edge_with_same_filtration(par); +#endif + auto&& vertices = simplex_vertex_range(sh); + auto end = std::end(vertices); + auto vi = std::begin(vertices); + GUDHI_CHECK(vi != end, "empty simplex"); + auto v0 = *vi; + ++vi; + GUDHI_CHECK(vi != end, "simplex of dimension 0"); + if(std::next(vi) == end) return sh; // shortcut for dimension 1 + boost::container::static_vector suffix; + suffix.push_back(v0); + auto filt = filtration_(sh); + do + { + Vertex_handle v = *vi; + auto&& children1 = find_vertex(v)->second.children()->members_; + for(auto w : suffix){ + // Can we take advantage of the fact that suffix is ordered? + Simplex_handle s = children1.find(w); + if(filtration_(s) == filt) + return s; + } + suffix.push_back(v); + } + while(++vi != end); + return null_simplex(); + } + + /** \brief Returns an edge of `sh` that has the same filtration value as `sh` if it exists, and `null_simplex()` otherwise. + * + * For a flag-complex built with `expansion()`, this is a way to invert the process and find out which edge had its filtration value propagated to `sh`. + * If several edges have the same filtration value, the one it returns is arbitrary. */ + Simplex_handle minimal_simplex_with_same_filtration(Simplex_handle sh) { + if(dimension(sh) == 0) // vertices are minimal + return sh; + auto filt = filtration_(sh); + // Naive implementation, it can be sped up. + for(auto b : boundary_simplex_range(sh)) + if(filtration_(b) == filt) + return minimal_simplex_with_same_filtration(b); + return sh; // None of its faces has the same filtration. + } + private: Vertex_handle null_vertex_; /** \brief Total number of simplices in the complex, without the empty simplex.*/ 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 efccf2f2..9007b6bd 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 @@ -15,9 +15,7 @@ #include #include -#if BOOST_VERSION >= 105600 -# include -#endif +#include #include @@ -42,13 +40,13 @@ class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade< typedef typename SimplexTree::Siblings Siblings; typedef typename SimplexTree::Vertex_handle Vertex_handle; - explicit Simplex_tree_simplex_vertex_iterator(SimplexTree * st) + explicit Simplex_tree_simplex_vertex_iterator(SimplexTree const* st) : // any end() iterator sib_(nullptr), v_(st->null_vertex()) { } - Simplex_tree_simplex_vertex_iterator(SimplexTree * st, Simplex_handle sh) + Simplex_tree_simplex_vertex_iterator(SimplexTree const* st, Simplex_handle sh) : sib_(st->self_siblings(sh)), v_(sh->first) { } @@ -166,15 +164,11 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< // Most of the storage should be moved to the range, iterators should be light. Vertex_handle last_; // last vertex of the simplex Vertex_handle next_; // next vertex to push in suffix_ -#if BOOST_VERSION >= 105600 // 40 seems a conservative bound on the dimension of a Simplex_tree for now, // as it would not fit on the biggest hard-drive. boost::container::static_vector suffix_; // static_vector still has some overhead compared to a trivial hand-made // version using std::aligned_storage, or compared to making suffix_ static. -#else - std::vector suffix_; -#endif Siblings * sib_; // where the next search will start from Simplex_handle sh_; // current Simplex_handle in the boundary SimplexTree * st_; // simplex containing the simplicial complex diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index 58bfa8db..2a2e2b25 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -986,5 +986,41 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(insert_duplicated_vertices, typeST, list_of_tested << " - num_simplices = " << st.num_simplices() << std::endl; BOOST_CHECK(st.dimension() == 1); BOOST_CHECK(st.num_simplices() == st.num_vertices() + 1); +} +BOOST_AUTO_TEST_CASE_TEMPLATE(generators, typeST, list_of_tested_variants) { + std::cout << "********************************************************************" << std::endl; + std::cout << "TEST FIND GENERATORS" << std::endl; + { + typeST st; + st.insert_simplex_and_subfaces({0,1,2,3,4,5,6},0); + st.assign_filtration(st.find({0,2,4}), 10); + st.assign_filtration(st.find({1,5}), 20); + st.assign_filtration(st.find({1,2,4}), 30); + st.assign_filtration(st.find({3}), 5); + st.make_filtration_non_decreasing(); + BOOST_CHECK(st.filtration(st.find({1,2}))==0); + BOOST_CHECK(st.filtration(st.find({0,1,2,3,4}))==30); + BOOST_CHECK(st.minimal_simplex_with_same_filtration(st.find({0,1,2,3,4,5}))==st.find({1,2,4})); + BOOST_CHECK(st.minimal_simplex_with_same_filtration(st.find({0,2,3}))==st.find({3})); + auto s=st.minimal_simplex_with_same_filtration(st.find({0,2,6})); + BOOST_CHECK(s==st.find({0})||s==st.find({2})||s==st.find({6})); + BOOST_CHECK(st.vertex_with_same_filtration(st.find({2}))==2); + BOOST_CHECK(st.vertex_with_same_filtration(st.find({1,5}))==st.null_vertex()); + BOOST_CHECK(st.vertex_with_same_filtration(st.find({5,6}))>=5); + } + { + typeST st; + st.insert_simplex_and_subfaces({0,1}, 8); + st.insert_simplex_and_subfaces({0,2}, 10); + st.insert_simplex_and_subfaces({3,4}, 6); + st.insert_simplex_and_subfaces({1,2}, 5); + st.insert_simplex_and_subfaces({1,5}, 4); + st.insert_simplex_and_subfaces({0,5}, 3); + st.insert_simplex_and_subfaces({2,5}, 2); + st.insert_simplex_and_subfaces({1,3}, 9); + st.expansion(50); + BOOST_CHECK(st.edge_with_same_filtration(st.find({0,1,2,5}))==st.find({0,2})); + BOOST_CHECK(st.edge_with_same_filtration(st.find({1,5}))==st.find({1,5})); + } } -- cgit v1.2.3 From 5748647e9e89bb91e361b06c7c6cb053081618bf Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Fri, 6 Mar 2020 18:10:05 +0100 Subject: Fix doc of minimal_simplex_with_same_filtration --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'src/Simplex_tree/include/gudhi') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 7315bf45..b6973756 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1530,13 +1530,11 @@ class Simplex_tree { return null_simplex(); } - /** \brief Returns an edge of `sh` that has the same filtration value as `sh` if it exists, and `null_simplex()` otherwise. + /** \brief Returns a minimal face of `sh` that has the same filtration value as `sh`. * - * For a flag-complex built with `expansion()`, this is a way to invert the process and find out which edge had its filtration value propagated to `sh`. - * If several edges have the same filtration value, the one it returns is arbitrary. */ + * For a complex built with `make_filtration_non_decreasing()`, this is a way to invert the process and find out which simplex had its filtration value propagated to `sh`. + * If several minimal (for inclusion) simplices have the same filtration value, the one it returns is arbitrary, and it is not guaranteed to be the one with smallest dimension. */ Simplex_handle minimal_simplex_with_same_filtration(Simplex_handle sh) { - if(dimension(sh) == 0) // vertices are minimal - return sh; auto filt = filtration_(sh); // Naive implementation, it can be sped up. for(auto b : boundary_simplex_range(sh)) -- cgit v1.2.3 From 8bd39f74f69e8fcb662873e0e045c953b814f28f Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Fri, 6 Mar 2020 18:21:40 +0100 Subject: Tweak doc. --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/Simplex_tree/include/gudhi') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index b6973756..ad592a92 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1532,7 +1532,7 @@ class Simplex_tree { /** \brief Returns a minimal face of `sh` that has the same filtration value as `sh`. * - * For a complex built with `make_filtration_non_decreasing()`, this is a way to invert the process and find out which simplex had its filtration value propagated to `sh`. + * For a filtration built with `make_filtration_non_decreasing()`, this is a way to invert the process and find out which simplex had its filtration value propagated to `sh`. * If several minimal (for inclusion) simplices have the same filtration value, the one it returns is arbitrary, and it is not guaranteed to be the one with smallest dimension. */ Simplex_handle minimal_simplex_with_same_filtration(Simplex_handle sh) { auto filt = filtration_(sh); -- cgit v1.2.3 From 47e72c7250bff568735df829a40bcbea0a48f7c2 Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Tue, 17 Mar 2020 13:28:35 +0100 Subject: Remove code that was commented out. --- src/Simplex_tree/include/gudhi/Simplex_tree.h | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-) (limited to 'src/Simplex_tree/include/gudhi') diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index ad592a92..af711075 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1494,16 +1494,8 @@ class Simplex_tree { * * \pre `sh` must have dimension at least 1. */ Simplex_handle edge_with_same_filtration(Simplex_handle sh) { -#if 0 - // FIXME: Only do this if dim >= 2, since we don't want to return a vertex... - // Test if we are lucky and the parent has the same filtration value. - Siblings* sib = self_siblings(sh); - Vertex_handle v_par = sib->parent(); - sib = sib->oncles(); - Simplex_handle par = sib->find(v_par); - if(filtration_(par) == filt) return edge_with_same_filtration(par); -#endif - auto&& vertices = simplex_vertex_range(sh); + // See issue #251 for potential speed improvements. + auto&& vertices = simplex_vertex_range(sh); // vertices in decreasing order auto end = std::end(vertices); auto vi = std::begin(vertices); GUDHI_CHECK(vi != end, "empty simplex"); -- cgit v1.2.3 From b262406b0a75e39276c11f70ef1174981aa31b51 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Tue, 17 Mar 2020 17:57:17 +0100 Subject: Remove thread_local workaround --- src/Alpha_complex/include/gudhi/Alpha_complex_3d.h | 5 +-- src/Nerve_GIC/include/gudhi/GIC.h | 14 +------- .../include/gudhi/Persistent_cohomology.h | 5 +-- src/Simplex_tree/include/gudhi/Simplex_tree.h | 12 ++----- src/cmake/modules/GUDHI_compilation_flags.cmake | 37 ---------------------- src/python/CMakeLists.txt | 10 ------ 6 files changed, 5 insertions(+), 78 deletions(-) (limited to 'src/Simplex_tree/include/gudhi') diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex_3d.h b/src/Alpha_complex/include/gudhi/Alpha_complex_3d.h index 7f96c94c..1486cefd 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex_3d.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex_3d.h @@ -61,10 +61,7 @@ namespace Gudhi { namespace alpha_complex { -#ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL -thread_local -#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL - double RELATIVE_PRECISION_OF_TO_DOUBLE = 0.00001; +thread_local double RELATIVE_PRECISION_OF_TO_DOUBLE = 0.00001; // Value_from_iterator returns the filtration value from an iterator on alpha shapes values // diff --git a/src/Nerve_GIC/include/gudhi/GIC.h b/src/Nerve_GIC/include/gudhi/GIC.h index 2a6d4788..9a4c813d 100644 --- a/src/Nerve_GIC/include/gudhi/GIC.h +++ b/src/Nerve_GIC/include/gudhi/GIC.h @@ -139,19 +139,9 @@ class Cover_complex { for (boost::tie(ei, ei_end) = boost::edges(G); ei != ei_end; ++ei) boost::remove_edge(*ei, G); } - // Thread local is not available on XCode version < V.8 - // If not available, random engine is a class member. -#ifndef GUDHI_CAN_USE_CXX11_THREAD_LOCAL - std::default_random_engine re; -#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL - // Find random number in [0,1]. double GetUniform() { - // Thread local is not available on XCode version < V.8 - // If available, random engine is defined for each thread. -#ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL thread_local std::default_random_engine re; -#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL std::uniform_real_distribution Dist(0, 1); return Dist(re); } @@ -456,9 +446,7 @@ class Cover_complex { if (distances.size() == 0) compute_pairwise_distances(distance); - // This cannot be parallelized if thread_local is not defined - // thread_local is not defined for XCode < v.8 - #if defined(GUDHI_USE_TBB) && defined(GUDHI_CAN_USE_CXX11_THREAD_LOCAL) + #ifdef GUDHI_USE_TBB std::mutex deltamutex; tbb::parallel_for(0, N, [&](int i){ std::vector samples(m); diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index b1ded5ae..ca4bc10d 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -288,10 +288,7 @@ class Persistent_cohomology { // with multiplicity. We used to sum the coefficients directly in // annotations_in_boundary by using a map, we now do it later. typedef std::pair annotation_t; -#ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL - thread_local -#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL - std::vector annotations_in_boundary; + thread_local std::vector annotations_in_boundary; annotations_in_boundary.clear(); int sign = 1 - 2 * (dim_sigma % 2); // \in {-1,1} provides the sign in the // alternate sum in the boundary. diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index b7fb9002..2adc8354 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -765,12 +765,7 @@ class Simplex_tree { if (first == last) return { null_simplex(), true }; // FIXME: false would make more sense to me. - // Copy before sorting - // Thread local is not available on XCode version < V.8 - It will slow down computation -#ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL - thread_local -#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL - std::vector copy; + thread_local std::vector copy; copy.clear(); copy.insert(copy.end(), first, last); std::sort(copy.begin(), copy.end()); @@ -1133,10 +1128,7 @@ class Simplex_tree { Dictionary_it next = siblings->members().begin(); ++next; -#ifdef GUDHI_CAN_USE_CXX11_THREAD_LOCAL - thread_local -#endif // GUDHI_CAN_USE_CXX11_THREAD_LOCAL - std::vector > inter; + thread_local std::vector > inter; for (Dictionary_it s_h = siblings->members().begin(); s_h != siblings->members().end(); ++s_h, ++next) { Simplex_handle root_sh = find_vertex(s_h->first); diff --git a/src/cmake/modules/GUDHI_compilation_flags.cmake b/src/cmake/modules/GUDHI_compilation_flags.cmake index 34c2e065..567fbc40 100644 --- a/src/cmake/modules/GUDHI_compilation_flags.cmake +++ b/src/cmake/modules/GUDHI_compilation_flags.cmake @@ -1,7 +1,6 @@ # This files manage compilation flags required by GUDHI include(TestCXXAcceptsFlag) -include(CheckCXXSourceCompiles) # add a compiler flag only if it is accepted macro(add_cxx_compiler_flag _flag) @@ -12,32 +11,6 @@ macro(add_cxx_compiler_flag _flag) endif() endmacro() -function(can_cgal_use_cxx11_thread_local) - # This is because of https://github.com/CGAL/cgal/blob/master/Installation/include/CGAL/tss.h - # CGAL is using boost thread if thread_local is not ready (requires XCode 8 for Mac). - # The test in https://github.com/CGAL/cgal/blob/master/Installation/include/CGAL/config.h - # #if __has_feature(cxx_thread_local) || \ - # ( (__GNUC__ * 100 + __GNUC_MINOR__) >= 408 && __cplusplus >= 201103L ) || \ - # ( _MSC_VER >= 1900 ) - # #define CGAL_CAN_USE_CXX11_THREAD_LOCAL - # #endif - set(CGAL_CAN_USE_CXX11_THREAD_LOCAL " - int main() { - #ifndef __has_feature - #define __has_feature(x) 0 // Compatibility with non-clang compilers. - #endif - #if __has_feature(cxx_thread_local) || \ - ( (__GNUC__ * 100 + __GNUC_MINOR__) >= 408 && __cplusplus >= 201103L ) || \ - ( _MSC_VER >= 1900 ) - bool has_feature_thread_local = true; - #else - // Explicit error of compilation for CMake test purpose - has_feature_thread_local is not defined - #endif - bool result = has_feature_thread_local; - } ") - check_cxx_source_compiles("${CGAL_CAN_USE_CXX11_THREAD_LOCAL}" CGAL_CAN_USE_CXX11_THREAD_LOCAL_RESULT) -endfunction() - set (CMAKE_CXX_STANDARD 14) enable_testing() @@ -58,16 +31,6 @@ if (DEBUG_TRACES) add_definitions(-DDEBUG_TRACES) endif() -set(GUDHI_CAN_USE_CXX11_THREAD_LOCAL " - int main() { - thread_local int result = 0; - return result; - } ") -check_cxx_source_compiles("${GUDHI_CAN_USE_CXX11_THREAD_LOCAL}" GUDHI_CAN_USE_CXX11_THREAD_LOCAL_RESULT) -if (GUDHI_CAN_USE_CXX11_THREAD_LOCAL_RESULT) - add_definitions(-DGUDHI_CAN_USE_CXX11_THREAD_LOCAL) -endif() - if(CMAKE_BUILD_TYPE MATCHES Debug) message("++ Debug compilation flags are: ${CMAKE_CXX_FLAGS} ${CMAKE_CXX_FLAGS_DEBUG}") else() diff --git a/src/python/CMakeLists.txt b/src/python/CMakeLists.txt index 22af3ec9..f00966a5 100644 --- a/src/python/CMakeLists.txt +++ b/src/python/CMakeLists.txt @@ -128,16 +128,6 @@ if(PYTHONINTERP_FOUND) endif () if(CGAL_FOUND) - can_cgal_use_cxx11_thread_local() - if (NOT CGAL_CAN_USE_CXX11_THREAD_LOCAL_RESULT) - if(CMAKE_BUILD_TYPE MATCHES Debug) - add_GUDHI_PYTHON_lib("${Boost_THREAD_LIBRARY_DEBUG}") - else() - add_GUDHI_PYTHON_lib("${Boost_THREAD_LIBRARY_RELEASE}") - endif() - message("** Add Boost ${Boost_LIBRARY_DIRS}") - set(GUDHI_PYTHON_LIBRARY_DIRS "${GUDHI_PYTHON_LIBRARY_DIRS}'${Boost_LIBRARY_DIRS}', ") - endif() # Add CGAL compilation args if(CGAL_HEADER_ONLY) add_gudhi_debug_info("CGAL header only version ${CGAL_VERSION}") -- cgit v1.2.3