Merge remote-tracking branch 'origin/master' into insert

4 files changed, 81 insertions, 0 deletions

diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd
index 175f970e..284daa96 100644
--- a/src/python/gudhi/simplex_tree.pxd
+++ b/src/python/gudhi/simplex_tree.pxd
@@ -77,6 +77,9 @@ 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
         pair[Simplex_tree_boundary_iterator, Simplex_tree_boundary_iterator] get_boundary_iterators(vector[int] simplex) nogil except +
+        # Expansion with blockers
+        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<Gudhi::Simplex_tree<Gudhi::Simplex_tree_options_full_featured>>":
diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx
index 83d7b092..43461e02 100644
--- a/src/python/gudhi/simplex_tree.pyx
+++ b/src/python/gudhi/simplex_tree.pyx
@@ -25,6 +25,9 @@ ctypedef fused some_float:
     float
     double
 
+cdef bool callback(vector[int] simplex, void *blocker_func):
+    return (<object>blocker_func)(simplex)
+
 # SimplexTree python interface
 cdef class SimplexTree:
     """The simplex tree is an efficient and flexible data structure for
@@ -558,6 +561,27 @@ 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 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 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.
+
+        .. 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.
+        :type blocker_func: Callable[[List[int]], bool]
+        """
+        self.get_ptr().expansion_with_blockers_callback(max_dim, callback, <void*>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 95c0c037..b93ccfff 100644
--- a/src/python/include/Simplex_tree_interface.h
+++ b/src/python/include/Simplex_tree_interface.h
@@ -44,6 +44,7 @@ class Simplex_tree_interface : public Simplex_tree<SimplexTreeOptions> {
   using Boundary_simplex_iterator = typename Base::Boundary_simplex_iterator;
   using Siblings = typename Base::Siblings;
   using Node = typename Base::Node;
+  typedef bool (*blocker_func_t)(Simplex simplex, void *user_data);
 
  public:
 
@@ -221,6 +222,13 @@ class Simplex_tree_interface : public Simplex_tree<SimplexTreeOptions> {
 #endif
   }
 
+  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(Base::simplex_vertex_range(sh).begin(), Base::simplex_vertex_range(sh).end());
+      return user_func(simplex, user_data);
+    });
+  }
+
   // 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 a5b8ffe0..15279c28 100755
--- a/src/python/test/test_simplex_tree.py
+++ b/src/python/test/test_simplex_tree.py
@@ -600,3 +600,49 @@ def test_insert_batch():
         ([5, 6], 4.0),
         ([2, 5, 6], 4.0),
     ]
+
+
+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)
+
+    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")
+            st.assign_filtration(simplex, st.filtration(simplex) + 1.0)
+            return False
+
+    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]) == 4.0
+    assert st.filtration([0, 1, 3]) == 5.0
+    assert st.filtration([0, 2, 3]) == 6.0
+    assert st.filtration([1, 2, 3]) == 6.0
+
+    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]) == 4.0
+    assert st.filtration([0, 1, 3]) == 5.0
+    assert st.filtration([0, 2, 3]) == 6.0
+    assert st.filtration([1, 2, 3]) == 6.0
+    assert st.filtration([0, 1, 2, 3]) == 7.0