summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorROUVREAU Vincent <vincent.rouvreau@inria.fr>2020-09-01 14:51:25 +0200
committerROUVREAU Vincent <vincent.rouvreau@inria.fr>2020-09-01 14:51:25 +0200
commitc2eb0484191f89fcbe40bc4ab04943eb808f12a9 (patch)
tree272289c27b583d4444e5e273ced5846561b5a9d1 /src
parentcea821f9ca34c270a5ccc047342c2c21ae79a6c0 (diff)
expansion with blocker and how to modify filtration value
Diffstat (limited to 'src')
-rw-r--r--src/python/gudhi/simplex_tree.pxd2
-rw-r--r--src/python/gudhi/simplex_tree.pyx23
-rwxr-xr-xsrc/python/test/test_simplex_tree.py46
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.