Add doc and start tests

3 files changed, 201 insertions, 0 deletions

diff --git a/src/Collapse/doc/intro_edge_collapse.h b/src/Collapse/doc/intro_edge_collapse.h
new file mode 100644
index 00000000..b42b5e65
--- /dev/null
+++ b/src/Collapse/doc/intro_edge_collapse.h
@@ -0,0 +1,98 @@
+/*    This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ *    See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ *    Author(s):       Siddharth Pritam
+ *
+ *    Copyright (C) 2019 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef DOC_EDGE_COLLAPSE_INTRO_EDGE_COLLAPSE_H_
+#define DOC_EDGE_COLLAPSE_INTRO_EDGE_COLLAPSE_H_
+
+namespace Gudhi {
+
+namespace edge_collapse {
+
+/**  \defgroup edge_collapse Edge collapse
+ * 
+ * \author    Siddharth Pritam
+ * 
+ * @{
+ * 
+ * \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$. 
+ * 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
+ * has all simplices of \f$K\f$ except \f$e\f$ and the ones containing \f$e\f$.
+ * There is an <b>edge collapse</b> from a simplicial complex \f$K\f$ to its subcomplex \f$L\f$, 
+ * 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$.
+ * 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$
+ * 
+ * -- 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$.
+
+ *  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. 
+
+ * 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 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. 
+ * 
+
+ * 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
+ * 
+ * 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.
+ * 
+ * Then, it is asked to display the distance matrix after the collapse operation.
+ * 
+ * \include Strong_collapse/strong_collapse_from_points.cpp
+ * 
+ * \code $> ./strong_collapse_from_points
+ * \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 .
+ * 
+ */
+/** @} */  // end defgroup strong_collapse
+
+}  // namespace edge_collapse
+
+}  // namespace Gudhi
+
+#endif  // DOC_EDGE_COLLAPSE_INTRO_EDGE_COLLAPSE_H_
diff --git a/src/Collapse/test/CMakeLists.txt b/src/Collapse/test/CMakeLists.txt
new file mode 100644
index 00000000..c7eafb46
--- /dev/null
+++ b/src/Collapse/test/CMakeLists.txt
@@ -0,0 +1,9 @@
+project(Collapse_tests)
+
+include(GUDHI_boost_test)
+
+add_executable ( Collapse_test_unit collapse_unit_test.cpp )
+if (TBB_FOUND)
+  target_link_libraries(Collapse_test_unit ${TBB_LIBRARIES})
+endif()
+gudhi_add_boost_test(Collapse_test_unit)
diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp
new file mode 100644
index 00000000..c2f08e57
--- /dev/null
+++ b/src/Collapse/test/collapse_unit_test.cpp
@@ -0,0 +1,94 @@
+/*    This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ *    See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ *    Author(s):       Vincent Rouvreau
+ *
+ *    Copyright (C) 2020 Inria
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#include <iostream>
+#include <fstream>
+#include <string>
+#include <algorithm>
+#include <utility>  // std::pair, std::make_pair
+#include <cmath>  // float comparison
+#include <limits>
+#include <functional>  // greater
+#include <tuple>  // std::tie
+
+#define BOOST_TEST_DYN_LINK
+#define BOOST_TEST_MODULE "collapse"
+#include <boost/test/unit_test.hpp>
+#include <boost/mpl/list.hpp>
+
+//  ^
+// /!\ Nothing else from Simplex_tree shall be included to test includes are well defined.
+#include "gudhi/FlagComplexSpMatrix.h"
+#include "gudhi/Rips_edge_list.h"
+
+using namespace Gudhi;
+
+// Types definition
+using Vector_of_points = std::vector<std::vector<double>>;
+
+using Simplex_tree = Gudhi::Simplex_tree<Gudhi::Simplex_tree_options_fast_persistence>;
+using Filtration_value = double;
+using Rips_complex = Gudhi::rips_complex::Rips_complex<Filtration_value>;
+using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list<Filtration_value>;
+using Field_Zp = Gudhi::persistent_cohomology::Field_Zp;
+using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology<Simplex_tree, Field_Zp>;
+using Distance_matrix = std::vector<std::vector<Filtration_value>>;
+
+
+BOOST_AUTO_TEST_CASE(collapse) {
+  typedef size_t Vertex_handle;
+  typedef std::vector<std::tuple<Filtration_value, Vertex_handle, Vertex_handle>> Filtered_sorted_edge_list;
+
+  std::size_t number_of_points;
+  std::string off_file_points;
+  std::string filediag;
+  int dim_max;
+  int p;
+  double min_persistence;
+
+  Map map_empty;
+
+  Distance_matrix sparse_distances;
+
+
+  Vector_of_points point_vector {{0., 0.},{0., 1.},{1., 0.},{1., 1.}};
+
+  int dimension = point_vector[0].dimension();
+  number_of_points = point_vector.size();
+  std::cout << "Successfully read " << number_of_points << " point_vector.\n";
+  std::cout << "Ambient dimension is " << dimension << ".\n";
+
+  std::cout << "Point Set Generated." << std::endl;
+
+  double threshold = 1.;
+  Filtered_sorted_edge_list edge_t;
+  std::cout << "Computing the one-skeleton for threshold: " << threshold << std::endl;
+
+  Rips_edge_list Rips_edge_list_from_file(point_vector, threshold, Gudhi::Euclidean_distance());
+  Rips_edge_list_from_file.create_edges(edge_t);
+
+  std::cout << "Sorted edge list computed" << std::endl;
+  std::cout << "Total number of edges before collapse are: " << edge_t.size() << std::endl;
+
+  if (edge_t.size() <= 0) {
+    std::cerr << "Total number of egdes are zero." << std::endl;
+    exit(-1);
+  }
+
+  // Now we will perform filtered edge collapse to sparsify the edge list edge_t.
+  std::cout << "Filtered edge collapse begins" << std::endl;
+  FlagComplexSpMatrix mat_filt_edge_coll(number_of_points, edge_t);
+  std::cout << "Matrix instansiated" << std::endl;
+  Filtered_sorted_edge_list collapse_edges;
+  collapse_edges = mat_filt_edge_coll.filtered_edge_collapse();
+ 
+}
+
+