Merge branch 'master' into insert

5 files changed, 168 insertions, 28 deletions

diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index 7d2b12ba..ef9f8428 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -43,6 +43,10 @@
 
 namespace Gudhi {
 
+/** \addtogroup simplex_tree 
+ *  @{
+ */
+
 /**
  * \class Extended_simplex_type Simplex_tree.h gudhi/Simplex_tree.h
  * \brief Extended simplex type data structure for representing the type of simplices in an extended filtration.
@@ -98,8 +102,7 @@ class Simplex_tree {
   // Simplex_key next to each other).
   typedef typename boost::container::flat_map<Vertex_handle, Node> Dictionary;
 
-  /* \brief Set of nodes sharing a same parent in the simplex tree. */
-  /* \brief Set of nodes sharing a same parent in the simplex tree. */
+  /** \brief Set of nodes sharing a same parent in the simplex tree. */
   typedef Simplex_tree_siblings<Simplex_tree, Dictionary> Siblings;
 
 
@@ -188,6 +191,12 @@ class Simplex_tree {
   typedef Simplex_tree_boundary_simplex_iterator<Simplex_tree> Boundary_simplex_iterator;
   /** \brief Range over the simplices of the boundary of a simplex. */
   typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range;
+  /** \brief Iterator over the simplices of the boundary of a simplex and their opposite vertices.
+   *
+   * 'value_type' is std::pair<Simplex_handle, Vertex_handle>. */
+  typedef Simplex_tree_boundary_opposite_vertex_simplex_iterator<Simplex_tree> Boundary_opposite_vertex_simplex_iterator;
+  /** \brief Range over the simplices of the boundary of a simplex and their opposite vertices. */
+  typedef boost::iterator_range<Boundary_opposite_vertex_simplex_iterator> Boundary_opposite_vertex_simplex_range;
   /** \brief Iterator over the simplices of the simplicial complex.
    *
    * 'value_type' is Simplex_handle. */
@@ -297,6 +306,23 @@ class Simplex_tree {
                                   Boundary_simplex_iterator(this));
   }
 
+  /** \brief Given a simplex, returns a range over the simplices of its boundary and their opposite vertices.
+   *
+   * The boundary of a simplex is the set of codimension \f$1\f$ subsimplices of the simplex.
+   * If the simplex is \f$[v_0, \cdots ,v_d]\f$, with canonical orientation induced by \f$ v_0 < \cdots < v_d \f$, the
+   * iterator enumerates the simplices of the boundary in the order:
+   * \f$[v_0,\cdots,\widehat{v_i},\cdots,v_d]\f$ for \f$i\f$ from \f$d\f$ to \f$0\f$, where \f$\widehat{v_i}\f$ means
+   * that the vertex \f$v_i\f$, known as the opposite vertex, is omitted from boundary, but returned as the second
+   * element of a pair.
+   *
+   * @param[in] sh Simplex for which the boundary is computed.
+   */
+  template<class SimplexHandle>
+  Boundary_opposite_vertex_simplex_range boundary_opposite_vertex_simplex_range(SimplexHandle sh) {
+    return Boundary_opposite_vertex_simplex_range(Boundary_opposite_vertex_simplex_iterator(this, sh),
+                                                  Boundary_opposite_vertex_simplex_iterator(this));
+  }
+
   /** @} */  // end range and iterator methods
   /** \name Constructor/Destructor
    * @{ */
@@ -945,7 +971,7 @@ class Simplex_tree {
         // If we reached the end of the vertices, and the simplex has more vertices than the given simplex
         // => we found a coface
 
-        // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with nbVertices
+        // Add a coface if we want the star or if the number of vertices of the current simplex matches with nbVertices
         bool addCoface = (star || curr_nbVertices == nbVertices);
         if (addCoface)
           cofaces.push_back(simplex);
@@ -1063,8 +1089,8 @@ class Simplex_tree {
    *
    * Inserts all vertices and edges given by a OneSkeletonGraph.
    * OneSkeletonGraph must be a model of
-   * <a href="http://www.boost.org/doc/libs/1_76_0/libs/graph/doc/VertexAndEdgeListGraph.html">boost::VertexAndEdgeListGraph</a>
-   * and <a href="http://www.boost.org/doc/libs/1_76_0/libs/graph/doc/PropertyGraph.html">boost::PropertyGraph</a>.
+   * <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/VertexAndEdgeListGraph.html">boost::VertexAndEdgeListGraph</a>
+   * and <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/PropertyGraph.html">boost::PropertyGraph</a>.
    *
    * The vertex filtration value is accessible through the property tag
    * vertex_filtration_t.
@@ -1318,7 +1344,7 @@ class Simplex_tree {
     }
   }
 
-  /* \private Returns the Simplex_handle composed of the vertex list (from the Simplex_handle), plus the given
+  /** \private Returns the Simplex_handle composed of the vertex list (from the Simplex_handle), plus the given
    * Vertex_handle if the Vertex_handle is found in the Simplex_handle children list.
    * Returns null_simplex() if it does not exist
   */
@@ -1471,7 +1497,7 @@ class Simplex_tree {
 
       int sh_dimension = dimension(sh);
       if (sh_dimension >= dimension_)
-        // Stop browsing as soon as the dimension is reached, no need to go furter
+        // Stop browsing as soon as the dimension is reached, no need to go further
         return false;
       new_dimension = (std::max)(new_dimension, sh_dimension);
     }
@@ -1781,7 +1807,7 @@ struct Simplex_tree_options_fast_persistence {
   static const bool contiguous_vertices = true;
 };
 
-/** @} */  // end defgroup simplex_tree
+/** @}*/  // end addtogroup simplex_tree
 
 }  // namespace Gudhi
 
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 e5522cc7..b63a5595 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
@@ -5,6 +5,7 @@
  *    Copyright (C) 2014 Inria
  *
  *    Modification(s):
+ *      - 2022/04 Vincent Rouvreau: Add Simplex_tree_boundary_opposite_vertex_simplex_iterator for alpha and cech purpose
  *      - YYYY/MM Author: Description of the modification
  */
 
@@ -17,15 +18,16 @@
 #include <boost/container/static_vector.hpp>
 
 #include <vector>
+#include <utility>  // for std::pair
 
 namespace Gudhi {
 
-/* \addtogroup simplex_tree
+/** \addtogroup simplex_tree 
  * Iterators and range types for the Simplex_tree.
- * @{
+ *  @{
  */
 
-/* \brief Iterator over the vertices of a simplex
+/** \brief Iterator over the vertices of a simplex
  * in a SimplexTree.
  *
  * Forward iterator, 'value_type' is SimplexTree::Vertex_handle.*/
@@ -71,7 +73,7 @@ class Simplex_tree_simplex_vertex_iterator : public boost::iterator_facade<
 };
 
 /*---------------------------------------------------------------------------*/
-/* \brief Iterator over the simplices of the boundary of a
+/** \brief Iterator over the simplices of the boundary of a
  *  simplex.
  *
  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
@@ -123,7 +125,7 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
 
  private:
   friend class boost::iterator_core_access;
-// valid when iterating along the SAME boundary.
+  // valid when iterating along the SAME boundary.
   bool equal(Simplex_tree_boundary_simplex_iterator const& other) const {
     return sh_ == other.sh_;
   }
@@ -178,8 +180,118 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade<
   Simplex_handle sh_;  // current Simplex_handle in the boundary
   SimplexTree * st_;  // simplex containing the simplicial complex
 };
+
+/** \brief Iterator over the simplices of the boundary of a simplex and their opposite vertices.
+ *
+ * Forward iterator, value_type is std::pair<SimplexTree::Simplex_handle, SimplexTree::Vertex_handle>.*/
+template<class SimplexTree>
+class Simplex_tree_boundary_opposite_vertex_simplex_iterator : public boost::iterator_facade<
+    Simplex_tree_boundary_opposite_vertex_simplex_iterator<SimplexTree>,
+    std::pair<typename SimplexTree::Simplex_handle, typename SimplexTree::Vertex_handle> const, boost::forward_traversal_tag> {
+ public:
+  using Simplex_handle = typename SimplexTree::Simplex_handle;
+  using Vertex_handle = typename SimplexTree::Vertex_handle;
+  using Siblings = typename SimplexTree::Siblings;
+
+  // For cython purpose only. The object it initializes should be overwritten ASAP and never used before it is
+  // overwritten.
+  Simplex_tree_boundary_opposite_vertex_simplex_iterator()
+      : sib_(nullptr),
+        st_(nullptr)  {
+  }
+
+  // any end() iterator
+  explicit Simplex_tree_boundary_opposite_vertex_simplex_iterator(SimplexTree * st)
+      : last_(st->null_vertex()),
+        next_(st->null_vertex()),
+        sib_(nullptr),
+        baov_(st->null_simplex(), st->null_vertex()),
+        st_(st)  {
+  }
+
+  template<class SimplexHandle>
+  Simplex_tree_boundary_opposite_vertex_simplex_iterator(SimplexTree * st, SimplexHandle sh)
+      : last_(sh->first),
+        next_(st->null_vertex()),
+        sib_(nullptr),
+        baov_(st->null_simplex(), sh->first),
+        st_(st) {
+    // Only check once at the beginning instead of for every increment, as this is expensive.
+    if (SimplexTree::Options::contiguous_vertices)
+      GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes");
+    Siblings * sib = st->self_siblings(sh);
+    next_ = sib->parent();
+    sib_ = sib->oncles();
+    if (sib_ != nullptr) {
+      if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr)
+        // Only relevant for edges
+        baov_.first = sib_->members_.begin()+next_;
+      else
+        baov_.first = sib_->find(next_);
+    }
+  }
+
+ private:
+  friend class boost::iterator_core_access;
+
+  // valid when iterating along the SAME boundary.
+  bool equal(Simplex_tree_boundary_opposite_vertex_simplex_iterator const& other) const {
+    return (baov_.first == other.baov_.first);
+  }
+
+  std::pair<Simplex_handle, Vertex_handle> const& dereference() const {
+   return baov_;
+  }
+
+  void increment() {
+    if (sib_ == nullptr) {
+      baov_.first = st_->null_simplex();
+      return;  // ------>>
+    }
+    Siblings * for_sib = sib_;
+    Siblings * new_sib = sib_->oncles();
+    auto rit = suffix_.rbegin();
+    if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) {
+      // We reached the root, use a short-cut to find a vertex.
+      if (rit == suffix_.rend()) {
+        baov_.second = baov_.first->first;
+        // Segment, this vertex is the last boundary simplex
+        baov_.first = for_sib->members_.begin()+last_;
+        sib_ = nullptr;
+        return;
+      } else {
+        // Dim >= 2, initial step of the descent
+        baov_.first = for_sib->members_.begin()+*rit;
+        for_sib = baov_.first->second.children();
+        ++rit;
+      }
+    }
+    for (; rit != suffix_.rend(); ++rit) {
+      baov_.first = for_sib->find(*rit);
+      for_sib = baov_.first->second.children();
+    }
+    baov_.first = for_sib->find(last_);  // baov_.first points to the right simplex now
+    suffix_.push_back(next_);
+    next_ = sib_->parent();
+    sib_ = new_sib;
+    baov_.second = suffix_.back();
+  }
+
+  // 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_
+  // 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<Vertex_handle, 40> suffix_;
+  // static_vector still has some overhead compared to a trivial hand-made
+  // version using std::aligned_storage, or compared to making suffix_ static.
+  Siblings * sib_;  // where the next search will start from
+  std::pair<Simplex_handle, Vertex_handle> baov_;  // a pair containing the current Simplex_handle in the boundary and its opposite vertex
+  SimplexTree * st_;  // simplex containing the simplicial complex
+};
+
 /*---------------------------------------------------------------------------*/
-/* \brief Iterator over the simplices of a simplicial complex.
+/** \brief Iterator over the simplices of a simplicial complex.
  *
  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
 template<class SimplexTree>
@@ -252,7 +364,7 @@ class Simplex_tree_complex_simplex_iterator : public boost::iterator_facade<
   SimplexTree * st_;
 };
 
-/* \brief Iterator over the simplices of the skeleton of a given
+/** \brief Iterator over the simplices of the skeleton of a given
  * dimension of the simplicial complex.
  *
  * Forward iterator, value_type is SimplexTree::Simplex_handle.*/
@@ -335,7 +447,8 @@ class Simplex_tree_skeleton_simplex_iterator : public boost::iterator_facade<
   int curr_dim_;
 };
 
-/* @} */  // end addtogroup simplex_tree
+/** @}*/  // end addtogroup simplex_tree
+
 }  // namespace Gudhi
 
 #endif  // SIMPLEX_TREE_SIMPLEX_TREE_ITERATORS_H_
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h
index ae140859..63023daa 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h
@@ -15,16 +15,15 @@
 
 namespace Gudhi {
 
-/* \addtogroup simplex_tree
+/** \addtogroup simplex_tree
  * Represents a node of a Simplex_tree.
  * @{
  */
 
-/*
- * \brief Node of a simplex tree with filtration value
+/** \brief Node of a simplex tree with filtration value
  * and simplex key.
  *
- * It stores explicitely its own filtration value and its own Simplex_key.
+ * It stores explicitly its own filtration value and its own Simplex_key.
  */
 template<class SimplexTree>
 struct Simplex_tree_node_explicit_storage : SimplexTree::Filtration_simplex_base, SimplexTree::Key_simplex_base {
@@ -54,7 +53,8 @@ struct Simplex_tree_node_explicit_storage : SimplexTree::Filtration_simplex_base
   Siblings * children_;
 };
 
-/* @} */  // end addtogroup simplex_tree
+/** @}*/  // end addtogroup simplex_tree
+
 }  // namespace Gudhi
 
 #endif  // SIMPLEX_TREE_SIMPLEX_TREE_NODE_EXPLICIT_STORAGE_H_
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h
index b53bad29..d849eeba 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h
@@ -20,12 +20,12 @@
 
 namespace Gudhi {
 
-/* \addtogroup simplex_tree
+/** \addtogroup simplex_tree
  * Represents a set of node of a Simplex_tree that share the same parent.
  * @{
  */
 
-/* \brief Data structure to store a set of nodes in a SimplexTree sharing
+/** \brief Data structure to store a set of nodes in a SimplexTree sharing
  * the same parent node.*/
 template<class SimplexTree, class MapContainer>
 class Simplex_tree_siblings {
@@ -36,6 +36,7 @@ class Simplex_tree_siblings {
   template<class T> friend class Simplex_tree_boundary_simplex_iterator;
   template<class T> friend class Simplex_tree_complex_simplex_iterator;
   template<class T> friend class Simplex_tree_skeleton_simplex_iterator;
+  template<class T> friend class Simplex_tree_boundary_opposite_vertex_simplex_iterator;
 
   typedef typename SimplexTree::Vertex_handle Vertex_handle;
   typedef typename SimplexTree::Filtration_value Filtration_value;
@@ -57,7 +58,7 @@ class Simplex_tree_siblings {
         members_() {
   }
 
-  /* \brief Constructor with initialized set of members.
+  /** \brief Constructor with initialized set of members.
    *
    * 'members' must be sorted and unique.*/
   template<typename RandomAccessVertexRange>
@@ -71,8 +72,7 @@ class Simplex_tree_siblings {
     }
   }
 
-  /*
-   * \brief Inserts a Node in the set of siblings nodes.
+  /** \brief Inserts a Node in the set of siblings nodes.
    *
    * If already present, assigns the minimal filtration value 
    * between input filtration_value and the value already 
@@ -113,7 +113,8 @@ class Simplex_tree_siblings {
   Dictionary members_;
 };
 
-/* @} */  // end addtogroup simplex_tree
+/** @}*/  // end addtogroup simplex_tree
+
 }  // namespace Gudhi
 
 #endif  // SIMPLEX_TREE_SIMPLEX_TREE_SIBLINGS_H_
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h b/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h
index 3e395ae2..29c76e50 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree/indexing_tag.h
@@ -20,7 +20,7 @@ namespace Gudhi {
 struct linear_indexing_tag {
 };
 
-/* \brief Tag for a zigzag ordering of simplices. */
+/** \brief Tag for a zigzag ordering of simplices. */
 //  struct zigzag_indexing_tag {};
 }  // namespace Gudhi