Merge branch 'master' of https://github.com/GUDHI/gudhi-devel into diff

9 files changed, 187 insertions, 84 deletions

diff --git a/src/Contraction/include/gudhi/Edge_contraction.h b/src/Contraction/include/gudhi/Edge_contraction.h
index 6c0f4c78..58d627c2 100644
--- a/src/Contraction/include/gudhi/Edge_contraction.h
+++ b/src/Contraction/include/gudhi/Edge_contraction.h
@@ -26,6 +26,7 @@ namespace contraction {
 
 
 /** \defgroup contr Edge contraction
+@{
 
 \author David Salinas
 
@@ -195,7 +196,6 @@ int main (int argc, char *argv[])
 
 	return EXIT_SUCCESS;
 }
-}
   \endcode
 
 \verbatim
diff --git a/src/Doxyfile.in b/src/Doxyfile.in
index ae8db1a3..f76ba2bd 100644
--- a/src/Doxyfile.in
+++ b/src/Doxyfile.in
@@ -231,12 +231,6 @@ TAB_SIZE               = 2
 
 ALIASES                =
 
-# This tag can be used to specify a number of word-keyword mappings (TCL only).
-# A mapping has the form "name=value". For example adding "class=itcl::class"
-# will allow you to use the command class in the itcl::class meaning.
-
-TCL_SUBST              =
-
 # Set the OPTIMIZE_OUTPUT_FOR_C tag to YES if your project consists of C sources
 # only. Doxygen will then generate output that is more tailored for C. For
 # instance, some of the names that are used will be different. The list of all
@@ -874,7 +868,7 @@ EXCLUDE_SYMBOLS        =
 # that contain example code fragments that are included (see the \include
 # command).
 
-EXAMPLE_PATH           = @CMAKE_SOURCE_DIR@/biblio/ \
+EXAMPLE_PATH           = @CMAKE_SOURCE_DIR@ \
                          @CMAKE_SOURCE_DIR@/data/ \
                          @GUDHI_DOXYGEN_EXAMPLE_PATH@
 
@@ -1040,25 +1034,6 @@ USE_HTAGS              = NO
 
 VERBATIM_HEADERS       = YES
 
-# If the CLANG_ASSISTED_PARSING tag is set to YES then doxygen will use the
-# clang parser (see: http://clang.llvm.org/) for more accurate parsing at the
-# cost of reduced performance. This can be particularly helpful with template
-# rich C++ code for which doxygen's built-in parser lacks the necessary type
-# information.
-# Note: The availability of this option depends on whether or not doxygen was
-# generated with the -Duse-libclang=ON option for CMake.
-# The default value is: NO.
-
-CLANG_ASSISTED_PARSING = NO
-
-# If clang assisted parsing is enabled you can provide the compiler with command
-# line options that you would normally use when invoking the compiler. Note that
-# the include paths will already be set by doxygen for the files and directories
-# specified with INPUT and INCLUDE_PATH.
-# This tag requires that the tag CLANG_ASSISTED_PARSING is set to YES.
-
-CLANG_OPTIONS          =
-
 #---------------------------------------------------------------------------
 # Configuration options related to the alphabetical class index
 #---------------------------------------------------------------------------
@@ -1070,13 +1045,6 @@ CLANG_OPTIONS          =
 
 ALPHABETICAL_INDEX     = YES
 
-# The COLS_IN_ALPHA_INDEX tag can be used to specify the number of columns in
-# which the alphabetical index list will be split.
-# Minimum value: 1, maximum value: 20, default value: 5.
-# This tag requires that the tag ALPHABETICAL_INDEX is set to YES.
-
-COLS_IN_ALPHA_INDEX    = 5
-
 # In case all classes in a project start with a common prefix, all classes will
 # be put under the same header in the alphabetical index. The IGNORE_PREFIX tag
 # can be used to specify a prefix (or a list of prefixes) that should be ignored
@@ -1775,16 +1743,6 @@ LATEX_BATCHMODE        = NO
 
 LATEX_HIDE_INDICES     = NO
 
-# If the LATEX_SOURCE_CODE tag is set to YES then doxygen will include source
-# code with syntax highlighting in the LaTeX output.
-#
-# Note that which sources are shown also depends on other settings such as
-# SOURCE_BROWSER.
-# The default value is: NO.
-# This tag requires that the tag GENERATE_LATEX is set to YES.
-
-LATEX_SOURCE_CODE      = NO
-
 # The LATEX_BIB_STYLE tag can be used to specify the style to use for the
 # bibliography, e.g. plainnat, or ieeetr. See
 # http://en.wikipedia.org/wiki/BibTeX and \cite for more info.
@@ -1857,16 +1815,6 @@ RTF_STYLESHEET_FILE    =
 
 RTF_EXTENSIONS_FILE    =
 
-# If the RTF_SOURCE_CODE tag is set to YES then doxygen will include source code
-# with syntax highlighting in the RTF output.
-#
-# Note that which sources are shown also depends on other settings such as
-# SOURCE_BROWSER.
-# The default value is: NO.
-# This tag requires that the tag GENERATE_RTF is set to YES.
-
-RTF_SOURCE_CODE        = NO
-
 #---------------------------------------------------------------------------
 # Configuration options related to the man page output
 #---------------------------------------------------------------------------
@@ -1956,15 +1904,6 @@ GENERATE_DOCBOOK       = NO
 
 DOCBOOK_OUTPUT         = docbook
 
-# If the DOCBOOK_PROGRAMLISTING tag is set to YES, doxygen will include the
-# program listings (including syntax highlighting and cross-referencing
-# information) to the DOCBOOK output. Note that enabling this will significantly
-# increase the size of the DOCBOOK output.
-# The default value is: NO.
-# This tag requires that the tag GENERATE_DOCBOOK is set to YES.
-
-DOCBOOK_PROGRAMLISTING = NO
-
 #---------------------------------------------------------------------------
 # Configuration options for the AutoGen Definitions output
 #---------------------------------------------------------------------------
@@ -2139,12 +2078,6 @@ EXTERNAL_GROUPS        = YES
 
 EXTERNAL_PAGES         = YES
 
-# The PERL_PATH should be the absolute path and name of the perl script
-# interpreter (i.e. the result of 'which perl').
-# The default file (with absolute path) is: /usr/bin/perl.
-
-PERL_PATH              = /usr/bin/perl
-
 #---------------------------------------------------------------------------
 # Configuration options related to the dot tool
 #---------------------------------------------------------------------------
@@ -2158,15 +2091,6 @@ PERL_PATH              = /usr/bin/perl
 
 CLASS_DIAGRAMS         = NO
 
-# You can define message sequence charts within doxygen comments using the \msc
-# command. Doxygen will then run the mscgen tool (see:
-# http://www.mcternan.me.uk/mscgen/)) to produce the chart and insert it in the
-# documentation. The MSCGEN_PATH tag allows you to specify the directory where
-# the mscgen tool resides. If left empty the tool is assumed to be found in the
-# default search path.
-
-MSCGEN_PATH            =
-
 # You can include diagrams made with dia in doxygen documentation. Doxygen will
 # then run dia to produce the diagram and insert it in the documentation. The
 # DIA_PATH tag allows you to specify the directory where the dia binary resides.
diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h
index d48f6616..34bc5ace 100644
--- a/src/Simplex_tree/include/gudhi/Simplex_tree.h
+++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h
@@ -187,6 +187,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. */
@@ -296,6 +302,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
    * @{ */
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..394c6ee1 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,6 +18,7 @@
 #include <boost/container/static_vector.hpp>
 
 #include <vector>
+#include <utility>  // for std::pair
 
 namespace Gudhi {
 
@@ -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,6 +180,116 @@ 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.
  *
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..ae25d290 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
@@ -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;
diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
index bdd41d34..b18e2ec4 100644
--- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp
+++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp
@@ -17,6 +17,8 @@
 #include <limits>
 #include <functional>  // greater
 #include <tuple>  // std::tie
+#include <iterator>  // for std::distance
+#include <cstddef>  // for std::size_t
 
 #define BOOST_TEST_DYN_LINK
 #define BOOST_TEST_MODULE "simplex_tree"
@@ -991,3 +993,48 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_reset_filtration, typeST, list_of_tes
 
 }
 
+BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_boundaries_and_opposite_vertex_iterator, typeST, list_of_tested_variants) {
+  std::clog << "********************************************************************" << std::endl;
+  std::clog << "TEST OF BOUNDARIES AND OPPOSITE VERTEX ITERATORS" << std::endl;
+  typeST st;
+
+  st.insert_simplex_and_subfaces({2, 1, 0}, 3.);
+  st.insert_simplex_and_subfaces({3, 0}, 2.);
+  st.insert_simplex_and_subfaces({3, 4, 5}, 3.);
+  st.insert_simplex_and_subfaces({0, 1, 6, 7}, 4.);
+
+  /* Inserted simplex:        */
+  /*    1   6                 */
+  /*    o---o                 */
+  /*   /X\7/                  */
+  /*  o---o---o---o           */
+  /*  2   0   3\X/4           */
+  /*            o             */
+  /*            5             */
+  using Simplex = std::vector<typename typeST::Vertex_handle>;
+  // simplices must be kept sorted by vertex number for std::vector to use operator== - cf. last BOOST_CHECK
+  std::vector<Simplex> simplices = {{0, 1, 2}, {0, 3}, {0, 1, 6, 7}, {3, 4, 5}, {3, 5}, {2}};
+  for (auto simplex : simplices) {
+    Simplex opposite_vertices;
+    for(auto boundary_and_opposite_vertex : st.boundary_opposite_vertex_simplex_range(st.find(simplex))) {
+      Simplex output;
+      for (auto vertex : st.simplex_vertex_range(boundary_and_opposite_vertex.first)) {
+        std::clog << vertex << " ";
+        output.emplace_back(vertex);
+      }
+      std::clog << " - opposite vertex = " << boundary_and_opposite_vertex.second << std::endl;
+      // Check that boundary simplex + opposite vertex = simplex given as input
+      output.emplace_back(boundary_and_opposite_vertex.second);
+      std::sort(output.begin(), output.end());
+      BOOST_CHECK(simplex == output);
+      opposite_vertices.emplace_back(boundary_and_opposite_vertex.second);
+    }
+    // Check that the list of all opposite vertices = simplex given as input
+    // no opposite vertices if simplex given as input is of dimension 1
+    std::sort(opposite_vertices.begin(), opposite_vertices.end());
+    if (simplex.size() > 1)
+      BOOST_CHECK(simplex == opposite_vertices);
+    else
+      BOOST_CHECK(opposite_vertices.size() == 0);
+  }
+}
diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h
index 125c6387..031bcb9c 100644
--- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h
+++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h
@@ -1071,7 +1071,6 @@ class Skeleton_blocker_complex {
 
   /**
    * Removes all the popable blockers of the complex and delete them.
-   * @returns the number of popable blockers deleted
    */
   void remove_popable_blockers();
 
@@ -1103,7 +1102,6 @@ class Skeleton_blocker_complex {
  public:
   /**
    * Remove the star of the edge connecting vertices a and b.
-   * @returns the number of blocker that have been removed
    */
   void remove_star(Vertex_handle a, Vertex_handle b);
 
diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h
index 404f04f9..5db9c2fd 100644..100755
--- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h
+++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h
@@ -39,7 +39,6 @@ bool Skeleton_blocker_complex<SkeletonBlockerDS>::is_popable_blocker(Blocker_han
 
 /**
  * Removes all the popable blockers of the complex and delete them.
- * @returns the number of popable blockers deleted
  */
 template<typename SkeletonBlockerDS>
 void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_popable_blockers() {
@@ -160,7 +159,6 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::update_blockers_after_remove_s
 
 /**
  * Remove the star of the edge connecting vertices a and b.
- * @returns the number of blocker that have been removed
  */
 template<typename SkeletonBlockerDS>
 void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Vertex_handle a, Vertex_handle b) {
diff --git a/src/common/doc/examples.h b/src/common/doc/examples.h
index 879fb96a..556a24f1 100644
--- a/src/common/doc/examples.h
+++ b/src/common/doc/examples.h
@@ -1,6 +1,6 @@
 // List of GUDHI examples and utils - Doxygen needs at least a file tag to analyse comments
 // Generated from scripts/cpp_examples_for_doxygen.py
-/*! @file Examples
+/*! @file
  * \section Witness_complex_example_section Witness_complex
  * @example strong_witness_persistence.cpp
  * @example weak_witness_persistence.cpp