Some documentation and examples

9 files changed, 163 insertions, 48 deletions

diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib
index b017a07e..24f85b48 100644
--- a/biblio/bibliography.bib
+++ b/biblio/bibliography.bib
@@ -1208,3 +1208,16 @@ numpages = {11},
 location = {Montr\'{e}al, Canada},
 series = {NIPS’18}
 }
+
+@unpublished{edgecollapsesocg2020,
+  title = {{Edge Collapse and Persistence of Flag Complexes}},
+  author = {Boissonnat, Jean-Daniel and Pritam, Siddharth},
+  url = {https://hal.inria.fr/hal-02395227},
+  note = {working paper or preprint},
+  year = {2019},
+  month = Dec,
+  keywords = {Persistent homology ; Strong Collapse ; Computational geometry ; Topological Data Analysis ; 2012 ACM Subject Classification Mathematics of computing ; Computational Topology},
+  pdf = {https://hal.inria.fr/hal-02395227/file/socg2020_paper_152.pdf},
+  hal_id = {hal-02395227},
+  hal_version = {v1},
+}
\ No newline at end of file
diff --git a/biblio/how_to_cite_gudhi.bib.in b/biblio/how_to_cite_gudhi.bib.in
index 05d3cc98..54d10857 100644
--- a/biblio/how_to_cite_gudhi.bib.in
+++ b/biblio/how_to_cite_gudhi.bib.in
@@ -156,3 +156,13 @@
 , url = "https://gudhi.inria.fr/doc/@GUDHI_VERSION@/group___persistence__representations.html"
 , year =        @GUDHI_VERSION_YEAR@
 }
+
+@incollection{gudhi:Collapse
+, author =  "Siddharth Pritam"
+, title =   "Edge collapse"
+, publisher =  "{GUDHI Editorial Board}"
+, edition =     "{@GUDHI_VERSION@}"
+, booktitle =   "{GUDHI} User and Reference Manual"
+, url = "https://gudhi.inria.fr/doc/@GUDHI_VERSION@/group__edge__collapse.html"
+, year =        @GUDHI_VERSION_YEAR@
+}
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 561aa049..9e4d78ac 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -26,6 +26,7 @@ add_gudhi_module(Bitmap_cubical_complex)
 add_gudhi_module(Bottleneck_distance)
 add_gudhi_module(Cech_complex)
 add_gudhi_module(Contraction)
+add_gudhi_module(Collapse)
 add_gudhi_module(Hasse_complex)
 add_gudhi_module(Persistence_representations)
 add_gudhi_module(Persistent_cohomology)
diff --git a/src/Collapse/doc/intro_edge_collapse.h b/src/Collapse/doc/intro_edge_collapse.h
index 70c816f4..0691ccf6 100644
--- a/src/Collapse/doc/intro_edge_collapse.h
+++ b/src/Collapse/doc/intro_edge_collapse.h
@@ -24,9 +24,9 @@ namespace collapse {
  * \section edge_collapse_definition Edge collapse definition
  * 
  * An edge \f$e\f$ in a simplicial complex \f$K\f$ is called a <b>dominated edge</b> if the link of \f$e\f$ in
- * \f$K\f$, \f$lk_K(e)\f$ is a simplicial cone, that is, there exists a vertex \f$v^{\prime} \notin e\f$ and a subcomplex
- * \f$L\f$ in \f$K\f$, such that \f$lk_K(e) = v^{\prime}L\f$. We say that the vertex  \f$v^{\prime}\f$ is {dominating}
- * \f$e\f$ and \f$e\f$ is {dominated} by \f$v^{\prime}\f$. 
+ * \f$K\f$, \f$lk_K(e)\f$ is a simplicial cone, that is, there exists a vertex \f$v^{\prime} \notin e\f$ and a
+ * subcomplex \f$L\f$ in \f$K\f$, such that \f$lk_K(e) = v^{\prime}L\f$. We say that the vertex  \f$v^{\prime}\f$ is
+ * {dominating} \f$e\f$ and \f$e\f$ is {dominated} by \f$v^{\prime}\f$. 
  * An <b> elementary egde collapse </b> is the removal of a dominated edge \f$e\f$ from \f$K\f$, 
  * which we denote with \f$K\f$ \f${\searrow\searrow}^1 \f$ \f$K\setminus e\f$. 
  * The symbol \f$\mathbf{K\setminus e}\f$ (deletion of \f$e\f$ from \f$K\f$) refers to the subcomplex of \f$K\f$ which
@@ -35,59 +35,62 @@ namespace collapse {
  * if there exists a series of elementary edge collapses from \f$K\f$ to \f$L\f$, denoted as \f$K\f$
  * \f${\searrow\searrow}\f$ \f$L\f$.
  * 
- * An edge collapse is a homotopy preserving operation, and it can be further expressed as sequence of the classical elementary simple collapse. 
- * A complex without any dominated edge is called a $1$- minimal complex and the core \f$K^1\f$ of simplicial comlex is a
- * minimal complex such that \f$K\f$ \f${\searrow\searrow}\f$ \f$K^1\f$.
+ * An edge collapse is a homotopy preserving operation, and it can be further expressed as sequence of the classical
+ * elementary simple collapse. 
+ * A complex without any dominated edge is called a \f$1\f$- minimal complex and the core \f$K^1\f$ of simplicial
+ * complex is a minimal complex such that \f$K\f$ \f${\searrow\searrow}\f$ \f$K^1\f$.
  * Computation of a core (not unique) involves computation of dominated edges and the dominated edges can be easily
  * characterized as follows:
  * 
  * -- For general simplicial complex: An edge \f$e \in K\f$ is dominated by another vertex \f$v^{\prime} \in K\f$,
- * <i>if and only if</i> all the maximal simplices of \f$K\f$ that contain $e$ also contain \f$v^{\prime}\f$
+ * <i>if and only if</i> all the maximal simplices of \f$K\f$ that contain \f$e\f$ also contain \f$v^{\prime}\f$
  * 
  * -- For a flag complex: An edge \f$e \in K\f$ is dominated by another vertex \f$v^{\prime} \in K\f$, <i>if and only
- * if</i> all the vertices in \f$K\f$ that has an edge with both vertices of \f$e\f$  also has an edge with \f$v^{\prime}\f$.
+ * if</i> all the vertices in \f$K\f$ that has an edge with both vertices of \f$e\f$  also has an edge with
+ * \f$v^{\prime}\f$.
 
- *  This module implements edge collapse of a filtered flag complex, in particular  it reduces a filtration of Vietoris-Rips (VR) complex from its graph 
- *  to another smaller flag filtration with same persistence. Where a filtration is a sequence of simplicial
- *  (here Rips) complexes connected with inclusions. The algorithm to compute the smaller induced filtration is described in Section 5 \cite edgecollapsesocg2020.
- *  Edge collapse can be successfully employed to reduce any given filtration of flag complexes to a smaller induced
- *  filtration which preserves the persistent homology of the original filtration and is a flag complex as well. 
+ * This module implements edge collapse of a filtered flag complex, in particular  it reduces a filtration of
+ * Vietoris-Rips complex from its graph 
+ * to another smaller flag filtration with same persistence. Where a filtration is a sequence of simplicial
+ * (here Rips) complexes connected with inclusions. The algorithm to compute the smaller induced filtration is
+ * described in Section 5 \cite edgecollapsesocg2020.
+ * Edge collapse can be successfully employed to reduce any given filtration of flag complexes to a smaller induced
+ * filtration which preserves the persistent homology of the original filtration and is a flag complex as well. 
 
- * The general idea is that we consider edges in the filtered graph and sort them according to their filtration value giving them a total order.
- * Each edge gets a unique index denoted as \f$i\f$ in this order.  To reduce the filtration, we move forward with increasing filtration value 
- * in the graph and check if the current edge \f$e_i\f$ is dominated in the current graph  \f$G_i := \{e_1, .. e_i\} \f$ or not. 
- * If the edge \f$e_i\f$ is dominated we remove it from the filtration and move forward to the next edge \f$e_{i+1}\f$. 
- * If f$e_i\f$ is non-dominated then we keep it in the reduced filtration and then go backward in the current graph \f$G_i\f$ to look for new non-dominated edges 
- * that was dominated before but might become non-dominated at this point.  
- * If an edge \f$e_j, j < i \f$ during the backward search is found to be non-dominated, we include \f$\e_j\f$ in to the reduced filtration and we set its new filtration value to be $i$ that is the index of \f$e_i\f$.
+ * The general idea is that we consider edges in the filtered graph and sort them according to their filtration value
+ * giving them a total order.
+ * Each edge gets a unique index denoted as \f$i\f$ in this order.  To reduce the filtration, we move forward with
+ * increasing filtration value 
+ * in the graph and check if the current edge \f$e_i\f$ is dominated in the current graph \f$G_i := \{e_1, .. e_i\} \f$
+ * or not. 
+ * If the edge \f$e_i\f$ is dominated we remove it from the filtration and move forward to the next edge \f$e_{i+1}\f$.
+ * If \f$e_i\f$ is non-dominated then we keep it in the reduced filtration and then go backward in the current graph
+ * \f$G_i\f$ to look for new non-dominated edges that was dominated before but might become non-dominated at this
+ * point. 
+ * If an edge \f$e_j, j < i \f$ during the backward search is found to be non-dominated, we include \f$e_j\f$ in to the
+ * reduced filtration and we set its new filtration value to be \f$i\f$ that is the index of \f$e_i\f$.
  * The precise mechanism for this reduction has been described in Section 5 \cite edgecollapsesocg2020. 
  * Here we implement this mechanism for a filtration of Rips complex, 
- * After perfoming the reduction the filtration reduces to a flag-filtration with the same persistence as the original filtration. 
+ * After perfoming the reduction the filtration reduces to a flag-filtration with the same persistence as the original
+ * filtration. 
  * 
-
- * Comment: I think it would be good if you (Vincent) check the later part according to the examples you build.
- * \subsection edge_collapse_from_points_example Example from a point cloud and a distance function
+ * \subsection edgecollapseexample Basic edge collapse
  * 
- * This example builds the edge graph from the given points, threshold value, and distance function.
- * Then it creates a `Flag_complex_edge_collapse` (exact version) with it.
+ * This example builds the `Flag_complex_sparse_matrix` from a proximity graph represented as a list of
+ * `Flag_complex_sparse_matrix::Filtered_edge`.
+ * Then it collapses edges and displays a new list of `Flag_complex_sparse_matrix::Filtered_edge` (with less edges)
+ * that will preserve the persistence homology computation.
  * 
- * Then, it is asked to display the distance matrix after the collapse operation.
+ * \include Collapse/edge_collapse_basic_example.cpp
  * 
- * \include Strong_collapse/strong_collapse_from_points.cpp
+ * When launching the example:
  * 
- * \code $> ./strong_collapse_from_points
+ * \code $> ./Edge_collapse_example_basic
  * \endcode
  *
  * the program output is:
  * 
- * \include Strong_collapse/strong_collapse_from_points_for_doc.txt
- * 
- * A `Gudhi::rips_complex::Rips_complex` can be built from the distance matrix if you want to compute persistence on
- * top of it.
-
- * For more information about our approach of computing edge collapses and persitent homology via edge collapses,
- * we refer the users to \cite edgecollapsesocg2020 .
- * 
+ * \include Collapse/edge_collapse_example_basic.txt
  */
 /** @} */  // end defgroup strong_collapse
 
diff --git a/src/Collapse/example/CMakeLists.txt b/src/Collapse/example/CMakeLists.txt
new file mode 100644
index 00000000..6cf3bf07
--- /dev/null
+++ b/src/Collapse/example/CMakeLists.txt
@@ -0,0 +1,10 @@
+project(Edge_collapse_examples)
+
+# Point cloud
+add_executable ( Edge_collapse_example_basic edge_collapse_basic_example.cpp )
+
+if (TBB_FOUND)
+  target_link_libraries(Edge_collapse_example_basic ${TBB_LIBRARIES})
+endif()
+
+add_test(NAME Edge_collapse_example_basic COMMAND $<TARGET_FILE:Edge_collapse_example_basic>)
diff --git a/src/Collapse/example/edge_collapse_basic_example.cpp b/src/Collapse/example/edge_collapse_basic_example.cpp
new file mode 100644
index 00000000..a154c6bb
--- /dev/null
+++ b/src/Collapse/example/edge_collapse_basic_example.cpp
@@ -0,0 +1,45 @@
+#include <gudhi/Flag_complex_sparse_matrix.h>
+
+#include <iostream>
+#include <vector>
+
+int main() {
+  // Type definitions
+  using Filtration_value = float;
+  using Vertex_handle = short;
+  using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix<Vertex_handle, Filtration_value>;
+  using Filtered_edge = Flag_complex_sparse_matrix::Filtered_edge;
+  using Filtered_edge_list = std::vector<Filtered_edge>;
+  using Edge = Flag_complex_sparse_matrix::Edge;
+
+  //  1   2
+  //  o---o
+  //  |\ /|
+  //  | x |
+  //  |/ \|
+  //  o---o
+  //  0   3
+  Filtered_edge_list graph = {{{0, 1}, 1.},
+                              {{1, 2}, 1.},
+                              {{2, 3}, 1.},
+                              {{3, 0}, 1.},
+                              {{0, 2}, 2.},
+                              {{1, 3}, 2.}};
+
+  Flag_complex_sparse_matrix flag_complex_sparse_matrix(graph);
+
+  Filtered_edge_list collapse_edges;
+  // Retrieve collapse edges from the output iterator
+  flag_complex_sparse_matrix.filtered_edge_collapse(
+    [&collapse_edges](std::pair<Vertex_handle, Vertex_handle> edge, Filtration_value filtration) {
+        collapse_edges.push_back({edge, filtration});
+      });
+
+  for (Filtered_edge filtered_edge_from_collapse : collapse_edges) {
+    Edge edge_from_collapse = std::get<0>(filtered_edge_from_collapse);
+    std::cout << "fn[" << std::get<0>(edge_from_collapse) << ", " << std::get<1>(edge_from_collapse) << "] = "
+              << std::get<1>(filtered_edge_from_collapse) << std::endl;
+  }
+
+  return 0;
+}
diff --git a/src/Collapse/example/edge_collapse_example_basic.txt b/src/Collapse/example/edge_collapse_example_basic.txt
new file mode 100644
index 00000000..acecacaf
--- /dev/null
+++ b/src/Collapse/example/edge_collapse_example_basic.txt
@@ -0,0 +1,5 @@
+fn[0, 1] = 1
+fn[1, 2] = 1
+fn[2, 3] = 1
+fn[3, 0] = 1
+fn[0, 2] = 2
diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h
index c92dd60b..a2f3a2a9 100644
--- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h
+++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h
@@ -53,16 +53,16 @@ namespace collapse {
 template<typename Vertex, typename Filtration>
 class Flag_complex_sparse_matrix {
  public:
-  // Re-define Vertex as Vertex_handle type to ease the interface with compute_proximity_graph
+  /** \brief Re-define Vertex as Vertex_handle type to ease the interface with compute_proximity_graph. */
   using Vertex_handle = Vertex;
-  // Re-define Filtration as Filtration_value type to ease the interface with compute_proximity_graph
+  /** \brief Re-define Filtration as Filtration_value type to ease the interface with compute_proximity_graph. */
   using Filtration_value = Filtration;
- private:
-  // This is an ordered pair, An edge is stored with convention of the first
-  // element being the smaller i.e {2,3} not {3,2}. However this is at the level
-  // of row indices on actual vertex lables
+  /** \brief This is an ordered pair, An edge is stored with convention of the first element being the smaller i.e
+   * {2,3} not {3,2}. However this is at the level of row indices on actual vertex lables.
+   */
   using Edge = std::pair<Vertex_handle, Vertex_handle>;
 
+ private:
   // Row_index type in the sparse matrix
   using Row_index = std::size_t;
 
@@ -73,9 +73,9 @@ class Flag_complex_sparse_matrix {
   using Row_indices_vector = std::vector<Row_index>;
 
  public:
-  // A Filtered_edge is a std::pair<std::pair<Vertex_handle, Vertex_handle>, Filtration_value>
+  /** \brief A Filtered_edge is a std::pair<std::pair<`Vertex_handle`, `Vertex_handle`>, `Filtration_value`>. */
   using Filtered_edge = std::pair<Edge, Filtration_value>;
-  // Proximity_graph is a type that can be used to construct easily a Flag_complex_sparse_matrix
+  /** \brief Proximity_graph is a type that can be used to construct easily a Flag_complex_sparse_matrix. */
   using Proximity_graph = Gudhi::Proximity_graph<Flag_complex_sparse_matrix>;
 
  private:
@@ -319,10 +319,8 @@ class Flag_complex_sparse_matrix {
    * @param[in] filtered_edge_range Range of filtered edges. Filtered edges must be in
    * `Flag_complex_sparse_matrix::Filtered_edge`.
    *
-   * @pre Available if Alpha_complex_3d is not Periodic.
-   *
    * There is no need the range to be sorted, as it will be performed in
-   * `Flag_complex_sparse_matrix::filtered_edge_collapse.
+   * `Flag_complex_sparse_matrix::filtered_edge_collapse`.
    */
   template<typename Filtered_edge_range>
   Flag_complex_sparse_matrix(const Filtered_edge_range& filtered_edge_range)
diff --git a/src/common/doc/main_page.md b/src/common/doc/main_page.md
index 6ea10b88..cdea3d94 100644
--- a/src/common/doc/main_page.md
+++ b/src/common/doc/main_page.md
@@ -242,6 +242,36 @@
  </tr>
 </table>
 
+#### Strong collapse
+
+<table>
+  <tr>
+    <td width="35%" rowspan=2>
+      \image html "edge_collapse_representation.png"
+    </td>
+    <td width="50%">
+    Edge collapse is able to reduce any flag filtration to a smaller flag filtration with the same persistence, using
+    only the 1-skeletons of a simplicial complex.
+    The reduction is exact and the persistence homology of the reduced sequence is identical to the persistence
+    homology of the input sequence. The resulting method is simple and extremely efficient.
+
+    Computation of edge collapse and persistent homology of a filtered flag complex via edge collapse as described in
+    \cite edgecollapsesocg2020.
+    </td>
+    <td width="15%">
+      <b>Author:</b> Siddharth Pritam<br>
+      <b>Introduced in:</b> GUDHI 2.4.0<br>
+      <b>Copyright:</b> MIT<br>
+      <b>Requires:</b> \ref eigen
+    </td>
+ </tr>
+ <tr>
+    <td colspan=2 height="25">
+    <b>User manual:</b> \ref edge_collapse
+    </td>
+ </tr>
+</table>
+
 ### Cover Complexes
 <table>
   <tr>