From 8400ce874e0d17c6d6c80bbd4b34dff40a768fe0 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Tue, 14 Apr 2020 10:19:38 +0200 Subject: Some documentation and examples --- src/CMakeLists.txt | 1 + src/Collapse/doc/intro_edge_collapse.h | 77 +++++++++++----------- src/Collapse/example/CMakeLists.txt | 10 +++ .../example/edge_collapse_basic_example.cpp | 45 +++++++++++++ .../example/edge_collapse_example_basic.txt | 5 ++ .../include/gudhi/Flag_complex_sparse_matrix.h | 20 +++--- src/common/doc/main_page.md | 30 +++++++++ 7 files changed, 140 insertions(+), 48 deletions(-) create mode 100644 src/Collapse/example/CMakeLists.txt create mode 100644 src/Collapse/example/edge_collapse_basic_example.cpp create mode 100644 src/Collapse/example/edge_collapse_example_basic.txt (limited to 'src') 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 dominated edge 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 elementary egde collapse 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$, - * if and only if all the maximal simplices of \f$K\f$ that contain $e$ also contain \f$v^{\prime}\f$ + * if and only if 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$, if and only - * if 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 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 $) 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 + +#include +#include + +int main() { + // Type definitions + using Filtration_value = float; + using Vertex_handle = short; + using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; + using Filtered_edge = Flag_complex_sparse_matrix::Filtered_edge; + using Filtered_edge_list = std::vector; + 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 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 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; + 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; public: - // A Filtered_edge is a std::pair, Filtration_value> + /** \brief A Filtered_edge is a std::pair, `Filtration_value`>. */ using Filtered_edge = std::pair; - // 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; 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 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 @@ +#### Strong collapse + + + + + + + + + + +
+ \image html "edge_collapse_representation.png" + + 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. + + Author: Siddharth Pritam
+ Introduced in: GUDHI 2.4.0
+ Copyright: MIT
+ Requires: \ref eigen +
+ User manual: \ref edge_collapse +
+ ### Cover Complexes -- cgit v1.2.3