From cea821f9ca34c270a5ccc047342c2c21ae79a6c0 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Fri, 28 Aug 2020 17:42:12 +0200 Subject: A prototype to fix #364 --- src/python/gudhi/simplex_tree.pxd | 3 ++ src/python/gudhi/simplex_tree.pyx | 21 ++++++++++++++ src/python/include/Simplex_tree_interface.h | 12 ++++++++ src/python/test/test_simplex_tree.py | 44 +++++++++++++++++++++++++++++ 4 files changed, 80 insertions(+) (limited to 'src/python') diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd index 75e94e0b..44533d7f 100644 --- a/src/python/gudhi/simplex_tree.pxd +++ b/src/python/gudhi/simplex_tree.pxd @@ -66,6 +66,9 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": vector[Simplex_tree_simplex_handle].const_iterator get_filtration_iterator_end() nogil Simplex_tree_skeleton_iterator get_skeleton_iterator_begin(int dimension) nogil Simplex_tree_skeleton_iterator get_skeleton_iterator_end(int dimension) nogil + # + ctypedef bool (*blocker_func)(vector[int], void *user_data) + void expansion_with_blockers_callback(int dimension, blocker_func user_func, void *user_data) cdef extern from "Persistent_cohomology_interface.h" namespace "Gudhi": cdef cppclass Simplex_tree_persistence_interface "Gudhi::Persistent_cohomology_interface>": diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index dfb1d985..e297cfbd 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -17,6 +17,9 @@ __author__ = "Vincent Rouvreau" __copyright__ = "Copyright (C) 2016 Inria" __license__ = "MIT" +cdef bool callback(vector[int] simplex, void *blocker_func): + return (blocker_func)(simplex) + # SimplexTree python interface cdef class SimplexTree: """The simplex tree is an efficient and flexible data structure for @@ -409,6 +412,24 @@ cdef class SimplexTree: persistence_result = self.pcohptr.get_persistence() return self.get_ptr().compute_extended_persistence_subdiagrams(persistence_result, min_persistence) + def expansion_with_blocker(self, max_dim, blocker_func): + """Expands the Simplex_tree containing only its one skeleton + until dimension max_dim. + + The expanded simplicial complex until dimension :math:`d` + attached to a graph :math:`G` is the maximal simplicial complex of + dimension at most :math:`d` admitting the graph :math:`G` as + :math:`1`-skeleton. + The filtration value assigned to a simplex is the maximal filtration + value of one of its edges. + + The Simplex_tree must contain no simplex of dimension bigger than + 1 when calling the method. + + :param max_dim: The maximal dimension. + :type max_dim: int + """ + self.get_ptr().expansion_with_blockers_callback(max_dim, callback, blocker_func) def persistence(self, homology_coeff_field=11, min_persistence=0, persistence_dim_max = False): """This function computes and returns the persistence of the simplicial complex. diff --git a/src/python/include/Simplex_tree_interface.h b/src/python/include/Simplex_tree_interface.h index e288a8cf..9f92b349 100644 --- a/src/python/include/Simplex_tree_interface.h +++ b/src/python/include/Simplex_tree_interface.h @@ -39,6 +39,7 @@ class Simplex_tree_interface : public Simplex_tree { using Skeleton_simplex_iterator = typename Base::Skeleton_simplex_iterator; using Complex_simplex_iterator = typename Base::Complex_simplex_iterator; using Extended_filtration_data = typename Base::Extended_filtration_data; + typedef bool (*blocker_func)(Simplex simplex, void *user_data); public: @@ -188,6 +189,17 @@ class Simplex_tree_interface : public Simplex_tree { return collapsed_stree_ptr; } + void expansion_with_blockers_callback(int dimension, blocker_func user_func, void *user_data) { + Base::expansion_with_blockers(dimension, [&](Simplex_handle sh){ + Simplex simplex; + for (auto vertex : Base::simplex_vertex_range(sh)) { + simplex.insert(simplex.begin(), vertex); + } + return user_func(simplex, user_data); + }); + Base::clear_filtration(); + } + // Iterator over the simplex tree Complex_simplex_iterator get_simplices_iterator_begin() { // this specific case works because the range is just a pair of iterators - won't work if range was a vector diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index 83be0602..7aad8259 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -358,3 +358,47 @@ def test_collapse_edges(): assert st.find([1, 3]) == False for simplex in st.get_skeleton(0): assert simplex[1] == 1. + +def blocker(simplex): + try: + # Block all simplices that countains vertex 6 + simplex.index(6) + print(simplex, ' is blocked') + return True + except ValueError: + print(simplex, ' is accepted') + return False + +def test_expansion_with_blocker(): + st=SimplexTree() + st.insert([0,1],0) + st.insert([0,2],1) + st.insert([0,3],2) + st.insert([1,2],3) + st.insert([1,3],4) + st.insert([2,3],5) + st.insert([2,4],6) + st.insert([3,6],7) + st.insert([4,5],8) + st.insert([4,6],9) + st.insert([5,6],10) + st.insert([6],10) + + st.expansion_with_blocker(2, blocker) + assert st.num_simplices() == 22 + assert st.dimension() == 2 + assert st.find([4,5,6]) == False + assert st.filtration([0,1,2]) == 3. + assert st.filtration([0,1,3]) == 4. + assert st.filtration([0,2,3]) == 5. + assert st.filtration([1,2,3]) == 5. + + st.expansion_with_blocker(3, blocker) + assert st.num_simplices() == 23 + assert st.dimension() == 3 + assert st.find([4,5,6]) == False + assert st.filtration([0,1,2]) == 3. + assert st.filtration([0,1,3]) == 4. + assert st.filtration([0,2,3]) == 5. + assert st.filtration([1,2,3]) == 5. + assert st.filtration([0,1,2,3]) == 5. -- cgit v1.2.3 From c2eb0484191f89fcbe40bc4ab04943eb808f12a9 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Tue, 1 Sep 2020 14:51:25 +0200 Subject: expansion with blocker and how to modify filtration value --- src/python/gudhi/simplex_tree.pxd | 2 +- src/python/gudhi/simplex_tree.pyx | 23 +++++++++--------- src/python/test/test_simplex_tree.py | 46 +++++++++++++++++++++--------------- 3 files changed, 40 insertions(+), 31 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd index 44533d7f..80c6ffca 100644 --- a/src/python/gudhi/simplex_tree.pxd +++ b/src/python/gudhi/simplex_tree.pxd @@ -66,7 +66,7 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": vector[Simplex_tree_simplex_handle].const_iterator get_filtration_iterator_end() nogil Simplex_tree_skeleton_iterator get_skeleton_iterator_begin(int dimension) nogil Simplex_tree_skeleton_iterator get_skeleton_iterator_end(int dimension) nogil - # + # Expansion with blockers ctypedef bool (*blocker_func)(vector[int], void *user_data) void expansion_with_blockers_callback(int dimension, blocker_func user_func, void *user_data) diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index e297cfbd..debe92c0 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -413,21 +413,22 @@ cdef class SimplexTree: return self.get_ptr().compute_extended_persistence_subdiagrams(persistence_result, min_persistence) def expansion_with_blocker(self, max_dim, blocker_func): - """Expands the Simplex_tree containing only its one skeleton - until dimension max_dim. + """Expands the Simplex_tree containing only a graph. Simplices corresponding to cliques in the graph are added + incrementally, faces before cofaces, unless the simplex has dimension larger than `max_dim` or `blocker_func` + returns `True` for this simplex. - The expanded simplicial complex until dimension :math:`d` - attached to a graph :math:`G` is the maximal simplicial complex of - dimension at most :math:`d` admitting the graph :math:`G` as - :math:`1`-skeleton. - The filtration value assigned to a simplex is the maximal filtration - value of one of its edges. + The function identifies a candidate simplex whose faces are all already in the complex, inserts it with a + filtration value corresponding to the maximum of the filtration values of the faces, then calls `blocker_func` + with this new simplex (represented as a list of int). If `blocker_func` returns `True`, the simplex is removed, + otherwise it is kept. The algorithm then proceeds with the next candidate. - The Simplex_tree must contain no simplex of dimension bigger than - 1 when calling the method. + Note that you cannot update the filtration value of the simplex during the evaluation of `blocker_func`, as it + would segfault. - :param max_dim: The maximal dimension. + :param max_dim: Expansion maximal dimension value. :type max_dim: int + :param blocker_func: Blocker oracle. + :type blocker_func: Its concept is `Boolean blocker_func(list of int)` """ self.get_ptr().expansion_with_blockers_callback(max_dim, callback, blocker_func) diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index 7aad8259..33b0ac99 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -359,16 +359,6 @@ def test_collapse_edges(): for simplex in st.get_skeleton(0): assert simplex[1] == 1. -def blocker(simplex): - try: - # Block all simplices that countains vertex 6 - simplex.index(6) - print(simplex, ' is blocked') - return True - except ValueError: - print(simplex, ' is accepted') - return False - def test_expansion_with_blocker(): st=SimplexTree() st.insert([0,1],0) @@ -384,21 +374,39 @@ def test_expansion_with_blocker(): st.insert([5,6],10) st.insert([6],10) + # One cannot modify filtration inside blocker - segfault - Let's record accepted simplices + accepted_simp = [] + def blocker(simplex): + try: + # Block all simplices that countains vertex 6 + simplex.index(6) + print(simplex, ' is blocked') + return True + except ValueError: + print(simplex, ' is accepted') + accepted_simp.append(simplex) + return False + st.expansion_with_blocker(2, blocker) + for simplex in accepted_simp: + st.assign_filtration(simplex, st.filtration(simplex) + 1.) assert st.num_simplices() == 22 assert st.dimension() == 2 assert st.find([4,5,6]) == False - assert st.filtration([0,1,2]) == 3. - assert st.filtration([0,1,3]) == 4. - assert st.filtration([0,2,3]) == 5. - assert st.filtration([1,2,3]) == 5. + assert st.filtration([0,1,2]) == 4. + assert st.filtration([0,1,3]) == 5. + assert st.filtration([0,2,3]) == 6. + assert st.filtration([1,2,3]) == 6. + accepted_simp = [] st.expansion_with_blocker(3, blocker) + for simplex in accepted_simp: + st.assign_filtration(simplex, st.filtration(simplex) + 1.) assert st.num_simplices() == 23 assert st.dimension() == 3 assert st.find([4,5,6]) == False - assert st.filtration([0,1,2]) == 3. - assert st.filtration([0,1,3]) == 4. - assert st.filtration([0,2,3]) == 5. - assert st.filtration([1,2,3]) == 5. - assert st.filtration([0,1,2,3]) == 5. + assert st.filtration([0,1,2]) == 4. + assert st.filtration([0,1,3]) == 5. + assert st.filtration([0,2,3]) == 6. + assert st.filtration([1,2,3]) == 6. + assert st.filtration([0,1,2,3]) == 6. -- cgit v1.2.3 From f4f5992e9025d055e35c86589923f1b0299f552e Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 22 Apr 2021 08:39:03 +0200 Subject: code review: rename block_func when it is a type. Type is a 'callable' --- src/python/gudhi/simplex_tree.pxd | 4 ++-- src/python/gudhi/simplex_tree.pyx | 2 +- src/python/include/Simplex_tree_interface.h | 4 ++-- 3 files changed, 5 insertions(+), 5 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd index 80c6ffca..ff750af9 100644 --- a/src/python/gudhi/simplex_tree.pxd +++ b/src/python/gudhi/simplex_tree.pxd @@ -67,8 +67,8 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": Simplex_tree_skeleton_iterator get_skeleton_iterator_begin(int dimension) nogil Simplex_tree_skeleton_iterator get_skeleton_iterator_end(int dimension) nogil # Expansion with blockers - ctypedef bool (*blocker_func)(vector[int], void *user_data) - void expansion_with_blockers_callback(int dimension, blocker_func user_func, void *user_data) + ctypedef bool (*blocker_func_t)(vector[int], void *user_data) + void expansion_with_blockers_callback(int dimension, blocker_func_t user_func, void *user_data) cdef extern from "Persistent_cohomology_interface.h" namespace "Gudhi": cdef cppclass Simplex_tree_persistence_interface "Gudhi::Persistent_cohomology_interface>": diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index debe92c0..383d1949 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -428,7 +428,7 @@ cdef class SimplexTree: :param max_dim: Expansion maximal dimension value. :type max_dim: int :param blocker_func: Blocker oracle. - :type blocker_func: Its concept is `Boolean blocker_func(list of int)` + :type blocker_func: Callable[[List[int]], bool] """ self.get_ptr().expansion_with_blockers_callback(max_dim, callback, blocker_func) diff --git a/src/python/include/Simplex_tree_interface.h b/src/python/include/Simplex_tree_interface.h index 9f92b349..a859bec0 100644 --- a/src/python/include/Simplex_tree_interface.h +++ b/src/python/include/Simplex_tree_interface.h @@ -39,7 +39,7 @@ class Simplex_tree_interface : public Simplex_tree { using Skeleton_simplex_iterator = typename Base::Skeleton_simplex_iterator; using Complex_simplex_iterator = typename Base::Complex_simplex_iterator; using Extended_filtration_data = typename Base::Extended_filtration_data; - typedef bool (*blocker_func)(Simplex simplex, void *user_data); + typedef bool (*blocker_func_t)(Simplex simplex, void *user_data); public: @@ -189,7 +189,7 @@ class Simplex_tree_interface : public Simplex_tree { return collapsed_stree_ptr; } - void expansion_with_blockers_callback(int dimension, blocker_func user_func, void *user_data) { + void expansion_with_blockers_callback(int dimension, blocker_func_t user_func, void *user_data) { Base::expansion_with_blockers(dimension, [&](Simplex_handle sh){ Simplex simplex; for (auto vertex : Base::simplex_vertex_range(sh)) { -- cgit v1.2.3 From 69168e8ed24165ab89ea1c57bc21dd994c93dd8e Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Tue, 27 Apr 2021 09:03:47 +0200 Subject: vector initialization improvement --- src/python/include/Simplex_tree_interface.h | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-) (limited to 'src/python') diff --git a/src/python/include/Simplex_tree_interface.h b/src/python/include/Simplex_tree_interface.h index a859bec0..dd8d715c 100644 --- a/src/python/include/Simplex_tree_interface.h +++ b/src/python/include/Simplex_tree_interface.h @@ -191,13 +191,9 @@ class Simplex_tree_interface : public Simplex_tree { void expansion_with_blockers_callback(int dimension, blocker_func_t user_func, void *user_data) { Base::expansion_with_blockers(dimension, [&](Simplex_handle sh){ - Simplex simplex; - for (auto vertex : Base::simplex_vertex_range(sh)) { - simplex.insert(simplex.begin(), vertex); - } + Simplex simplex(Base::simplex_vertex_range(sh).begin(), Base::simplex_vertex_range(sh).end()); return user_func(simplex, user_data); }); - Base::clear_filtration(); } // Iterator over the simplex tree -- cgit v1.2.3 From 8667b75601cc0420f3b196d5b44ec93fd6058057 Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau Date: Mon, 21 Mar 2022 17:14:30 +0100 Subject: Add some c++ tests and use unitary_tests_utils. Fix python test --- .../simplex_tree_graph_expansion_unit_test.cpp | 192 ++++++++++++++++----- src/python/test/test_simplex_tree.py | 11 +- 2 files changed, 151 insertions(+), 52 deletions(-) (limited to 'src/python') diff --git a/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp index 881a06ae..6d63d8ae 100644 --- a/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp @@ -9,33 +9,62 @@ */ #include -#include -#include -#include -#include // std::pair, std::make_pair -#include // float comparison -#include -#include // greater +#include #define BOOST_TEST_DYN_LINK -#define BOOST_TEST_MODULE "simplex_tree" +#define BOOST_TEST_MODULE "simplex_tree_graph_expansion" #include #include -// ^ -// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined. #include "gudhi/Simplex_tree.h" +#include using namespace Gudhi; typedef boost::mpl::list, Simplex_tree> list_of_tested_variants; +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_all_is_blocked, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_all_is_blocked\n"; + std::clog << "********************************************************************\n"; + using Simplex_handle = typename typeST::Simplex_handle; + // Construct the Simplex Tree with a 1-skeleton graph example + typeST simplex_tree; + + simplex_tree.insert_simplex({0, 1}, 0.); + simplex_tree.insert_simplex({0, 2}, 1.); + simplex_tree.insert_simplex({0, 3}, 2.); + simplex_tree.insert_simplex({1, 2}, 3.); + simplex_tree.insert_simplex({1, 3}, 4.); + simplex_tree.insert_simplex({2, 3}, 5.); + simplex_tree.insert_simplex({2, 4}, 6.); + simplex_tree.insert_simplex({3, 6}, 7.); + simplex_tree.insert_simplex({4, 5}, 8.); + simplex_tree.insert_simplex({4, 6}, 9.); + simplex_tree.insert_simplex({5, 6}, 10.); + simplex_tree.insert_simplex({6}, 10.); -bool AreAlmostTheSame(float a, float b) { - return std::fabs(a - b) < std::numeric_limits::epsilon(); + typeST stree_copy = simplex_tree; + + simplex_tree.expansion_with_blockers(3, [&](Simplex_handle sh){ return true; }); + + std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; + std::clog << " - dimension " << simplex_tree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) + std::clog << "(" << vertex << ")"; + std::clog << std::endl; + } + + BOOST_CHECK(stree_copy == simplex_tree); } BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_with_blockers_3\n"; + std::clog << "********************************************************************\n"; using Simplex_handle = typename typeST::Simplex_handle; // Construct the Simplex Tree with a 1-skeleton graph example typeST simplex_tree; @@ -72,9 +101,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, li return result; }); - std::clog << "********************************************************************\n"; - std::clog << "simplex_tree_expansion_with_blockers_3\n"; - std::clog << "********************************************************************\n"; std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; std::clog << " - dimension " << simplex_tree.dimension() << "\n"; std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; @@ -89,15 +115,23 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, li BOOST_CHECK(simplex_tree.dimension() == 3); // {4, 5, 6} shall be blocked BOOST_CHECK(simplex_tree.find({4, 5, 6}) == simplex_tree.null_simplex()); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 4.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 6.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 6.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), 7.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2})), + static_cast(4.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,3})), + static_cast(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,2,3})), + static_cast(6.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({1,2,3})), + static_cast(6.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), + static_cast(7.)); } BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_with_blockers_2\n"; + std::clog << "********************************************************************\n"; using Simplex_handle = typename typeST::Simplex_handle; // Construct the Simplex Tree with a 1-skeleton graph example typeST simplex_tree; @@ -134,9 +168,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, li return result; }); - std::clog << "********************************************************************\n"; - std::clog << "simplex_tree_expansion_with_blockers_2\n"; - std::clog << "********************************************************************\n"; std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; std::clog << " - dimension " << simplex_tree.dimension() << "\n"; std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; @@ -151,14 +182,22 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, li BOOST_CHECK(simplex_tree.dimension() == 2); // {4, 5, 6} shall be blocked BOOST_CHECK(simplex_tree.find({4, 5, 6}) == simplex_tree.null_simplex()); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 4.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 6.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 6.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2})), + static_cast(4.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,3})), + static_cast(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,2,3})), + static_cast(6.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({1,2,3})), + static_cast(6.)); BOOST_CHECK(simplex_tree.find({0,1,2,3}) == simplex_tree.null_simplex()); } -BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion, typeST, list_of_tested_variants) { +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_find_simplex_blockers, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_with_find_simplex_blockers\n"; + std::clog << "********************************************************************\n"; + using Simplex_handle = typename typeST::Simplex_handle; // Construct the Simplex Tree with a 1-skeleton graph example typeST simplex_tree; @@ -175,10 +214,66 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion, typeST, list_of_tested_var simplex_tree.insert_simplex({5, 6}, 10.); simplex_tree.insert_simplex({6}, 10.); - simplex_tree.expansion(3); + simplex_tree.expansion_with_blockers(3, [&](Simplex_handle sh){ + bool result = false; + std::clog << "Blocker on ["; + std::vector simplex; + // User can loop on the vertices from the given simplex_handle i.e. + for (auto vertex : simplex_tree.simplex_vertex_range(sh)) { + // We block the expansion, if the vertex '1' is in the given list of vertices + if (vertex == 1) + result = true; + std::clog << vertex << ", "; + simplex.push_back(vertex); + } + std::clog << "] => " << result << std::endl; + // Not efficient but test it works - required by the python interface + BOOST_CHECK(simplex_tree.find(simplex) == sh); + return result; + }); + + std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; + std::clog << " - dimension " << simplex_tree.dimension() << "\n"; + std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + for (auto f_simplex : simplex_tree.filtration_simplex_range()) { + std::clog << " " << "[" << simplex_tree.filtration(f_simplex) << "] "; + for (auto vertex : simplex_tree.simplex_vertex_range(f_simplex)) + std::clog << "(" << vertex << ")"; + std::clog << std::endl; + } + + BOOST_CHECK(simplex_tree.num_simplices() == 20); + BOOST_CHECK(simplex_tree.dimension() == 2); + + // {1, 2, 3}, {0, 1, 2} and {0, 1, 3} shall be blocked as it contains vertex 1 + BOOST_CHECK(simplex_tree.find({4, 5, 6}) != simplex_tree.null_simplex()); + BOOST_CHECK(simplex_tree.find({1, 2, 3}) == simplex_tree.null_simplex()); + BOOST_CHECK(simplex_tree.find({0, 2, 3}) != simplex_tree.null_simplex()); + BOOST_CHECK(simplex_tree.find({0, 1, 2}) == simplex_tree.null_simplex()); + BOOST_CHECK(simplex_tree.find({0, 1, 3}) == simplex_tree.null_simplex()); +} + +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_3, typeST, list_of_tested_variants) { std::clog << "********************************************************************\n"; std::clog << "simplex_tree_expansion_3\n"; std::clog << "********************************************************************\n"; + // Construct the Simplex Tree with a 1-skeleton graph example + typeST simplex_tree; + + simplex_tree.insert_simplex({0, 1}, 0.); + simplex_tree.insert_simplex({0, 2}, 1.); + simplex_tree.insert_simplex({0, 3}, 2.); + simplex_tree.insert_simplex({1, 2}, 3.); + simplex_tree.insert_simplex({1, 3}, 4.); + simplex_tree.insert_simplex({2, 3}, 5.); + simplex_tree.insert_simplex({2, 4}, 6.); + simplex_tree.insert_simplex({3, 6}, 7.); + simplex_tree.insert_simplex({4, 5}, 8.); + simplex_tree.insert_simplex({4, 6}, 9.); + simplex_tree.insert_simplex({5, 6}, 10.); + simplex_tree.insert_simplex({6}, 10.); + + simplex_tree.expansion(3); std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; std::clog << " - dimension " << simplex_tree.dimension() << "\n"; std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; @@ -192,16 +287,25 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion, typeST, list_of_tested_var BOOST_CHECK(simplex_tree.num_simplices() == 24); BOOST_CHECK(simplex_tree.dimension() == 3); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({4,5,6})), 10.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 3.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 4.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), 5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({4,5,6})), + static_cast(10.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2})), + static_cast(3.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,3})), + static_cast(4.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,2,3})), + static_cast(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({1,2,3})), + static_cast(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2,3})), + static_cast(5.)); } BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_2, typeST, list_of_tested_variants) { + std::clog << "********************************************************************\n"; + std::clog << "simplex_tree_expansion_2\n"; + std::clog << "********************************************************************\n"; // Construct the Simplex Tree with a 1-skeleton graph example typeST simplex_tree; @@ -220,9 +324,6 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_2, typeST, list_of_tested_v simplex_tree.expansion(2); - std::clog << "********************************************************************\n"; - std::clog << "simplex_tree_expansion_2\n"; - std::clog << "********************************************************************\n"; std::clog << "* The complex contains " << simplex_tree.num_simplices() << " simplices"; std::clog << " - dimension " << simplex_tree.dimension() << "\n"; std::clog << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; @@ -236,10 +337,15 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_2, typeST, list_of_tested_v BOOST_CHECK(simplex_tree.num_simplices() == 23); BOOST_CHECK(simplex_tree.dimension() == 2); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({4,5,6})), 10.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,2})), 3.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,1,3})), 4.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({0,2,3})), 5.)); - BOOST_CHECK(AreAlmostTheSame(simplex_tree.filtration(simplex_tree.find({1,2,3})), 5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({4,5,6})), + static_cast(10.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,2})), + static_cast(3.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,1,3})), + static_cast(4.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({0,2,3})), + static_cast(5.)); + GUDHI_TEST_FLOAT_EQUALITY_CHECK(simplex_tree.filtration(simplex_tree.find({1,2,3})), + static_cast(5.)); BOOST_CHECK(simplex_tree.find({0,1,2,3}) == simplex_tree.null_simplex()); } diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index d8173b52..eb481a49 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -531,8 +531,6 @@ def test_expansion_with_blocker(): st.insert([5,6],10) st.insert([6],10) - # One cannot modify filtration inside blocker - segfault - Let's record accepted simplices - accepted_simp = [] def blocker(simplex): try: # Block all simplices that countains vertex 6 @@ -541,12 +539,10 @@ def test_expansion_with_blocker(): return True except ValueError: print(simplex, ' is accepted') - accepted_simp.append(simplex) + st.assign_filtration(simplex, st.filtration(simplex) + 1.) return False st.expansion_with_blocker(2, blocker) - for simplex in accepted_simp: - st.assign_filtration(simplex, st.filtration(simplex) + 1.) assert st.num_simplices() == 22 assert st.dimension() == 2 assert st.find([4,5,6]) == False @@ -555,10 +551,7 @@ def test_expansion_with_blocker(): assert st.filtration([0,2,3]) == 6. assert st.filtration([1,2,3]) == 6. - accepted_simp = [] st.expansion_with_blocker(3, blocker) - for simplex in accepted_simp: - st.assign_filtration(simplex, st.filtration(simplex) + 1.) assert st.num_simplices() == 23 assert st.dimension() == 3 assert st.find([4,5,6]) == False @@ -566,4 +559,4 @@ def test_expansion_with_blocker(): assert st.filtration([0,1,3]) == 5. assert st.filtration([0,2,3]) == 6. assert st.filtration([1,2,3]) == 6. - assert st.filtration([0,1,2,3]) == 6. + assert st.filtration([0,1,2,3]) == 7. -- cgit v1.2.3 From 924302f092d6d08c59500c5f6e75bcad9416581a Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau Date: Mon, 28 Mar 2022 08:39:21 +0200 Subject: doc review: remove segfault note as it is no more the case --- src/python/gudhi/simplex_tree.pyx | 3 --- 1 file changed, 3 deletions(-) (limited to 'src/python') diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index 644110c1..fc704358 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -487,9 +487,6 @@ cdef class SimplexTree: with this new simplex (represented as a list of int). If `blocker_func` returns `True`, the simplex is removed, otherwise it is kept. The algorithm then proceeds with the next candidate. - Note that you cannot update the filtration value of the simplex during the evaluation of `blocker_func`, as it - would segfault. - :param max_dim: Expansion maximal dimension value. :type max_dim: int :param blocker_func: Blocker oracle. -- cgit v1.2.3 From f6a45247e9a9f126c214d1b1003ae19fb2cc84a3 Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau Date: Mon, 28 Mar 2022 09:00:23 +0200 Subject: doc review: add a warning about phantom simplices for blocker_func --- src/python/gudhi/simplex_tree.pyx | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'src/python') diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index fc704358..a4914184 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -487,6 +487,11 @@ cdef class SimplexTree: with this new simplex (represented as a list of int). If `blocker_func` returns `True`, the simplex is removed, otherwise it is kept. The algorithm then proceeds with the next candidate. + .. warning:: + Several candidates of the same dimension may be inserted simultaneously before calling `block_simplex`, so + if you examine the complex in `block_simplex`, you may hit a few simplices of the same dimension that have + not been vetted by `block_simplex` yet, or have already been rejected but not yet removed. + :param max_dim: Expansion maximal dimension value. :type max_dim: int :param blocker_func: Blocker oracle. -- cgit v1.2.3