diff options
author | ROUVREAU Vincent <vincent.rouvreau@inria.fr> | 2020-09-01 14:51:25 +0200 |
---|---|---|
committer | ROUVREAU Vincent <vincent.rouvreau@inria.fr> | 2020-09-01 14:51:25 +0200 |
commit | c2eb0484191f89fcbe40bc4ab04943eb808f12a9 (patch) | |
tree | 272289c27b583d4444e5e273ced5846561b5a9d1 /src | |
parent | cea821f9ca34c270a5ccc047342c2c21ae79a6c0 (diff) |
expansion with blocker and how to modify filtration value
Diffstat (limited to 'src')
-rw-r--r-- | src/python/gudhi/simplex_tree.pxd | 2 | ||||
-rw-r--r-- | src/python/gudhi/simplex_tree.pyx | 23 | ||||
-rwxr-xr-x | src/python/test/test_simplex_tree.py | 46 |
3 files changed, 40 insertions, 31 deletions
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, <void*>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. |