From ca63b38beafa9f5bb0b674682764e26097380134 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Mon, 16 Mar 2020 23:06:09 +0100 Subject: Collapse first version from Siddharth --- src/Collapse/example/CMakeLists.txt | 9 +++++++++ 1 file changed, 9 insertions(+) create mode 100644 src/Collapse/example/CMakeLists.txt (limited to 'src/Collapse/example/CMakeLists.txt') diff --git a/src/Collapse/example/CMakeLists.txt b/src/Collapse/example/CMakeLists.txt new file mode 100644 index 00000000..c9cba3fa --- /dev/null +++ b/src/Collapse/example/CMakeLists.txt @@ -0,0 +1,9 @@ +project(Collapse_examples) + +add_executable ( Collapse_example_rips_persistence_with_collapse rips_persistence_with_sc.cpp ) +target_link_libraries(Collapse_example_rips_persistence_with_collapse Boost::program_options) + +if (TBB_FOUND) + target_link_libraries(Collapse_example_rips_persistence_with_collapse ${TBB_LIBRARIES}) +endif() +add_test(NAME Collapse_example_rips_persistence_with_collapse COMMAND $) -- cgit v1.2.3 From d9bbfcaf73da6071ee52d05a04b152667027e976 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 19 Mar 2020 10:20:16 +0100 Subject: Remove examples --- src/Collapse/example/CMakeLists.txt | 9 -- src/Collapse/example/rips_persistence_with_sc.cpp | 179 ---------------------- 2 files changed, 188 deletions(-) delete mode 100644 src/Collapse/example/CMakeLists.txt delete mode 100644 src/Collapse/example/rips_persistence_with_sc.cpp (limited to 'src/Collapse/example/CMakeLists.txt') diff --git a/src/Collapse/example/CMakeLists.txt b/src/Collapse/example/CMakeLists.txt deleted file mode 100644 index c9cba3fa..00000000 --- a/src/Collapse/example/CMakeLists.txt +++ /dev/null @@ -1,9 +0,0 @@ -project(Collapse_examples) - -add_executable ( Collapse_example_rips_persistence_with_collapse rips_persistence_with_sc.cpp ) -target_link_libraries(Collapse_example_rips_persistence_with_collapse Boost::program_options) - -if (TBB_FOUND) - target_link_libraries(Collapse_example_rips_persistence_with_collapse ${TBB_LIBRARIES}) -endif() -add_test(NAME Collapse_example_rips_persistence_with_collapse COMMAND $) diff --git a/src/Collapse/example/rips_persistence_with_sc.cpp b/src/Collapse/example/rips_persistence_with_sc.cpp deleted file mode 100644 index 46ec8eca..00000000 --- a/src/Collapse/example/rips_persistence_with_sc.cpp +++ /dev/null @@ -1,179 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include -#include - -// Types definition -using Vector_of_points = std::vector; - -using Simplex_tree = Gudhi::Simplex_tree; -using Filtration_value = double; -using Rips_complex = Gudhi::rips_complex::Rips_complex; -using Rips_edge_list = Gudhi::rips_edge_list::Rips_edge_list; -using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; -using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; -using Distance_matrix = std::vector>; - - -class filt_edge_to_dist_matrix -{ -public: - template - filt_edge_to_dist_matrix(Distance_matrix & distance_mat, Filtered_sorted_edge_list & edge_filt, std::size_t number_of_points) - { - double inf = std::numeric_limits::max(); - doubleVector distances ; - std::pair e; - for(std::size_t indx = 0; indx < number_of_points; indx++) { - for (std::size_t j = 0; j <= indx; j++) { - if( j == indx) - distances.push_back(0); - - else - distances.push_back(inf); - } - distance_mat.push_back(distances); - distances.clear(); - } - - for(auto edIt = edge_filt.begin(); edIt != edge_filt.end(); edIt++) { - e=std::minmax(std::get<1>(*edIt),std::get<2>(*edIt)); - distance_mat.at(std::get<1>(e)).at(std::get<0>(e)) = std::get<0>(*edIt); - } - } -}; - - -int main(int argc, char * const argv[]) { - - auto the_begin = std::chrono::high_resolution_clock::now(); - PointSetGen point_generator; - std::string out_file_name = "default"; - std::string in_file_name = "default"; - std::size_t number_of_points; - - typedef size_t Vertex_handle; - typedef std::vector< std::tuple > Filtered_sorted_edge_list; - - int dimension; - double end_threshold; - double steps; - char manifold; - - Vector_of_points * point_vector; - - int dim_max = 2; - - point_generator.program_options(argc, argv, steps, end_threshold, manifold, dimension, dim_max, in_file_name, out_file_name); - - std::cout << "The current input values to run the program is: "<< std::endl; - std::cout << "steps, end_threshold, manifold, dimension, max_complex_dimension, in_file_name, out_file_name" << std::endl; - std::cout << steps << ", " << end_threshold << ", " << manifold << ", " << dimension << ", " << dim_max << ", " << in_file_name << ", " << out_file_name << std::endl; - - Map map_empty; - - std::string filediag_aft ("./PersistenceOutput/collapsed_persistence_diags") ; - - filediag_aft = filediag_aft+"_"+ out_file_name+ ".txt"; - - Distance_matrix distances; - Distance_matrix *sparse_distances = new Distance_matrix(); - - - if(manifold == 'f') { - Gudhi::Points_off_reader off_reader(in_file_name); - if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << in_file_name << "\n"; - exit(-1); // ----- >> - } - - point_vector = new Vector_of_points(off_reader.get_point_cloud().begin(), off_reader.get_point_cloud().end()); - dimension = point_vector->at(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"; - } - else if (manifold == 'm'){ - std::string csv_file_name(in_file_name); - distances = Gudhi::read_lower_triangular_matrix_from_csv_file(csv_file_name); - number_of_points = distances.size(); - std::cout << "Read the distance matrix succesfully, of size: " << number_of_points << std::endl; - } - else { - std::cerr << "Wrong parameters for input manifold..." <size() << std::endl; - } - - //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 = new FlagComplexSpMatrix(number_of_points,*edge_t); - std::cout<< "Matrix instansiated" << std::endl; - if(edge_t->size() >0){ - delete edge_t; - edge_t = new Filtered_sorted_edge_list(); - *edge_t = mat_filt_edge_coll->filtered_edge_collapse(); - filt_edge_to_dist_matrix(*sparse_distances, *edge_t, number_of_points); - std::cout << "Total number of vertices after collapse in the sparse matrix are: " << mat_filt_edge_coll->num_vertices() << std::endl; - } - else - { - std::cerr << "Total number of egdes are zero." <(the_end- the_begin).count() - << " ms\n" << std::endl; - return 0; - -} - -- cgit v1.2.3 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 --- biblio/bibliography.bib | 13 ++++ biblio/how_to_cite_gudhi.bib.in | 10 +++ 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 +++++++++ 9 files changed, 163 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/Collapse/example/CMakeLists.txt') 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 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 From e41edaed6e4e77438a2ab9da69862dc311602758 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Wed, 3 Jun 2020 14:56:43 +0200 Subject: Add an example that tests the persistence is conserved when using edge collapse, versus a classical rips --- src/Collapse/example/CMakeLists.txt | 13 ++ .../example/edge_collapse_conserve_persistence.cpp | 157 +++++++++++++++++++++ .../point_cloud_edge_collapse_rips_persistence.cpp | 3 - 3 files changed, 170 insertions(+), 3 deletions(-) create mode 100644 src/Collapse/example/edge_collapse_conserve_persistence.cpp (limited to 'src/Collapse/example/CMakeLists.txt') diff --git a/src/Collapse/example/CMakeLists.txt b/src/Collapse/example/CMakeLists.txt index 6cf3bf07..96354489 100644 --- a/src/Collapse/example/CMakeLists.txt +++ b/src/Collapse/example/CMakeLists.txt @@ -8,3 +8,16 @@ if (TBB_FOUND) endif() add_test(NAME Edge_collapse_example_basic COMMAND $) + +# Point cloud +add_executable ( Edge_collapse_conserve_persistence edge_collapse_conserve_persistence.cpp ) + +if (TBB_FOUND) + target_link_libraries(Edge_collapse_conserve_persistence ${TBB_LIBRARIES}) +endif() + +add_test(NAME Edge_collapse_conserve_persistence_1 COMMAND $ + "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" "1.") + + add_test(NAME Edge_collapse_conserve_persistence_2 COMMAND $ + "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" "2.") diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp new file mode 100644 index 00000000..47accb0c --- /dev/null +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -0,0 +1,157 @@ +/* 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 +#include +#include +#include +#include +#include + +#include // for std::pair +#include +#include + +// Types definition + +using Simplex_tree = Gudhi::Simplex_tree<>; +using Filtration_value = Simplex_tree::Filtration_value; +using Vertex_handle = Simplex_tree::Vertex_handle; +using Point = std::vector; +using Vector_of_points = std::vector; + +using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; +using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; + +using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; +using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; + +using Persistence_pair = std::tuple; +/* + * Compare two intervals by dimension, then by length. + */ +struct cmp_intervals_by_dim_then_length { + explicit cmp_intervals_by_dim_then_length(Simplex_tree * sc) + : sc_(sc) { } + + template + bool operator()(const Persistent_interval & p1, const Persistent_interval & p2) { + if (sc_->dimension(get < 0 > (p1)) == sc_->dimension(get < 0 > (p2))) + return (sc_->filtration(get < 1 > (p1)) - sc_->filtration(get < 0 > (p1)) + > sc_->filtration(get < 1 > (p2)) - sc_->filtration(get < 0 > (p2))); + else + return (sc_->dimension(get < 0 > (p1)) > sc_->dimension(get < 0 > (p2))); + } + Simplex_tree* sc_; +}; + +std::vector get_persistence_pairs(Simplex_tree& st, int ambient_dim) { + std::vector ppairs; + st.expansion(ambient_dim); + + // Sort the simplices in the order of the filtration + st.initialize_filtration(); + // Compute the persistence diagram of the complex + Persistent_cohomology pcoh(st); + // initializes the coefficient field for homology - must be a prime number + int p = 11; + pcoh.init_coefficients(p); + + // Default min_interval_length = 0. + pcoh.compute_persistent_cohomology(); + // Custom sort and output persistence + cmp_intervals_by_dim_then_length cmp(&st); + auto persistent_pairs = pcoh.get_persistent_pairs(); + std::sort(std::begin(persistent_pairs), std::end(persistent_pairs), cmp); + for (auto pair : persistent_pairs) { + ppairs.push_back({st.dimension(get<0>(pair)), + st.filtration(get<0>(pair)), + st.filtration(get<1>(pair)) }); + } + return ppairs; +} + +int main(int argc, char* argv[]) { + if (argc != 3) { + std::cerr << "This program requires an OFF file and minimal threshold value as parameter\n"; + std::cerr << "For instance: ./Edge_collapse_conserve_persistence ../../data/points/tore3D_300.off 1.\n"; + exit(-1); // ----- >> + } + + std::string off_file_points {argv[1]}; + double threshold {atof(argv[2])}; + + Gudhi::Points_off_reader off_reader(off_file_points); + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << off_file_points << "\n"; + exit(-1); // ----- >> + } + + Vector_of_points point_vector = off_reader.get_point_cloud(); + if (point_vector.size() <= 0) { + std::cerr << "Empty point cloud." << std::endl; + exit(-1); // ----- >> + } + + Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(off_reader.get_point_cloud(), + threshold, + Gudhi::Euclidean_distance()); + + if (num_edges(proximity_graph) <= 0) { + std::cerr << "Total number of egdes are zero." << std::endl; + exit(-1); + } + + // ***** Simplex tree from a flag complex built after collapse ***** + Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); + + Simplex_tree stree_from_collapse; + mat_filt_edge_coll.filtered_edge_collapse( + [&stree_from_collapse](const std::vector& edge, Filtration_value filtration) { + // insert the 2 vertices with a 0. filtration value just like a Rips + stree_from_collapse.insert_simplex({edge[0]}, 0.); + stree_from_collapse.insert_simplex({edge[1]}, 0.); + // insert the edge + stree_from_collapse.insert_simplex(edge, filtration); + }); + + // ***** Simplex tree from the complete flag complex ***** + Simplex_tree stree_wo_collapse; + stree_wo_collapse.insert_graph(proximity_graph); + + int ambient_dim = point_vector[0].size(); + + std::vector ppairs_from_collapse = get_persistence_pairs(stree_from_collapse, ambient_dim); + std::vector ppairs_wo_collapse = get_persistence_pairs(stree_wo_collapse, ambient_dim); + + if (ppairs_wo_collapse.size() != ppairs_from_collapse.size()) { + std::cerr << "Number of persistence pairs with collapse is " << ppairs_from_collapse.size() << std::endl; + std::cerr << "Number of persistence pairs without collapse is " << ppairs_wo_collapse.size() << std::endl; + exit(-1); + } + + int return_value = 0; + auto ppwoc_ptr = ppairs_wo_collapse.begin(); + for (auto ppfc: ppairs_from_collapse) { + if (ppfc != *ppwoc_ptr) { + return_value++; + std::cerr << "Without collapse: " + << std::get<0>(*ppwoc_ptr) << " " << std::get<1>(*ppwoc_ptr) << " " << std::get<2>(*ppwoc_ptr) + << " - With collapse: " + << std::get<0>(ppfc) << " " << std::get<1>(ppfc) << " " << std::get<2>(ppfc) << std::endl; + } + std::clog << " ** Without collapse: " + << std::get<0>(*ppwoc_ptr) << " " << std::get<1>(*ppwoc_ptr) << " " << std::get<2>(*ppwoc_ptr) + << " - With collapse: " + << std::get<0>(ppfc) << " " << std::get<1>(ppfc) << " " << std::get<2>(ppfc) << std::endl; + ppwoc_ptr++; + } + return return_value; +} diff --git a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp index b9130d4c..067b29e3 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -33,7 +33,6 @@ using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; -using Distance_matrix = std::vector>; void program_options(int argc, char* argv[], std::string& off_file_points, std::string& filediag, Filtration_value& threshold, int& dim_max, int& p, Filtration_value& min_persistence); @@ -54,8 +53,6 @@ int main(int argc, char* argv[]) { std::cout << min_persistence << ", " << threshold << ", " << dim_max << ", " << off_file_points << ", " << filediag << std::endl; - Distance_matrix sparse_distances; - Gudhi::Points_off_reader off_reader(off_file_points); if (!off_reader.is_valid()) { std::cerr << "Unable to read file " << off_file_points << "\n"; -- cgit v1.2.3 From 8e3e8efcb0c9a3e5650545ee0d9756129b10a95c Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 4 Jun 2020 09:55:58 +0200 Subject: Try to add inf values --- src/Collapse/example/CMakeLists.txt | 7 + ...edge_collapse_conserve_persistence_with_inf.cpp | 164 +++++++++++++++++++++ 2 files changed, 171 insertions(+) create mode 100644 src/Collapse/example/edge_collapse_conserve_persistence_with_inf.cpp (limited to 'src/Collapse/example/CMakeLists.txt') diff --git a/src/Collapse/example/CMakeLists.txt b/src/Collapse/example/CMakeLists.txt index 96354489..95e1696f 100644 --- a/src/Collapse/example/CMakeLists.txt +++ b/src/Collapse/example/CMakeLists.txt @@ -21,3 +21,10 @@ add_test(NAME Edge_collapse_conserve_persistence_1 COMMAND $ "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" "2.") + +# Tests +add_executable ( inf edge_collapse_conserve_persistence_with_inf.cpp ) + +if (TBB_FOUND) + target_link_libraries(inf ${TBB_LIBRARIES}) +endif() diff --git a/src/Collapse/example/edge_collapse_conserve_persistence_with_inf.cpp b/src/Collapse/example/edge_collapse_conserve_persistence_with_inf.cpp new file mode 100644 index 00000000..0555725f --- /dev/null +++ b/src/Collapse/example/edge_collapse_conserve_persistence_with_inf.cpp @@ -0,0 +1,164 @@ +/* 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 +#include +#include +#include +#include +#include + +#include // for std::pair +#include +#include +#include // for numeric_limits<> + +// Types definition + +using Simplex_tree = Gudhi::Simplex_tree<>; +using Filtration_value = Simplex_tree::Filtration_value; +using Vertex_handle = Simplex_tree::Vertex_handle; +using Point = std::vector; +using Vector_of_points = std::vector; + +using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; +using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; + +using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; +using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; + +using Persistence_pair = std::tuple; +/* + * Compare two intervals by dimension, then by length. + */ +struct cmp_intervals_by_dim_then_length { + explicit cmp_intervals_by_dim_then_length(Simplex_tree * sc) + : sc_(sc) { } + + template + bool operator()(const Persistent_interval & p1, const Persistent_interval & p2) { + if (sc_->dimension(get < 0 > (p1)) == sc_->dimension(get < 0 > (p2))) + return (sc_->filtration(get < 1 > (p1)) - sc_->filtration(get < 0 > (p1)) + > sc_->filtration(get < 1 > (p2)) - sc_->filtration(get < 0 > (p2))); + else + return (sc_->dimension(get < 0 > (p1)) > sc_->dimension(get < 0 > (p2))); + } + Simplex_tree* sc_; +}; + +std::vector get_persistence_pairs(Simplex_tree& st, int ambient_dim) { + std::vector ppairs; + std::cout << "expansion" << std::endl; + st.expansion(ambient_dim); + + // Sort the simplices in the order of the filtration + std::cout << "initialize_filtration" << std::endl; + st.initialize_filtration(); + std::cout << "Persistent_cohomology" << std::endl; + // Compute the persistence diagram of the complex + Persistent_cohomology pcoh(st); + // initializes the coefficient field for homology - must be a prime number + int p = 11; + std::cout << "init_coefficients" << std::endl; + pcoh.init_coefficients(p); + + // Default min_interval_length = 0. + std::cout << "compute_persistent_cohomology" << std::endl; + pcoh.compute_persistent_cohomology(); + // Custom sort and output persistence + cmp_intervals_by_dim_then_length cmp(&st); + auto persistent_pairs = pcoh.get_persistent_pairs(); + std::sort(std::begin(persistent_pairs), std::end(persistent_pairs), cmp); + for (auto pair : persistent_pairs) { + ppairs.push_back({st.dimension(get<0>(pair)), + st.filtration(get<0>(pair)), + st.filtration(get<1>(pair)) }); + } + return ppairs; +} + +int main(int argc, char* argv[]) { + if (argc != 3) { + std::cerr << "This program requires an OFF file and minimal threshold value as parameter\n"; + std::cerr << "For instance: ./Edge_collapse_conserve_persistence ../../data/points/tore3D_300.off 1.\n"; + exit(-1); // ----- >> + } + + std::string off_file_points {argv[1]}; + double threshold {atof(argv[2])}; + + Gudhi::Points_off_reader off_reader(off_file_points); + if (!off_reader.is_valid()) { + std::cerr << "Unable to read file " << off_file_points << "\n"; + exit(-1); // ----- >> + } + + Vector_of_points point_vector = off_reader.get_point_cloud(); + if (point_vector.size() <= 0) { + std::cerr << "Empty point cloud." << std::endl; + exit(-1); // ----- >> + } + + Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(off_reader.get_point_cloud(), + threshold, + Gudhi::Euclidean_distance()); + + if (num_edges(proximity_graph) <= 0) { + std::cerr << "Total number of egdes are zero." << std::endl; + exit(-1); + } + + int ambient_dim = point_vector[0].size(); + + // ***** Simplex tree from a flag complex built after collapse ***** + Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); + + Simplex_tree stree_from_collapse; + for (Vertex_handle i = 0; i < point_vector.size(); i++) { + // insert the 2 vertices with a 0. filtration value just like a Rips + stree_from_collapse.insert_simplex({i}, 0.); + for (Vertex_handle j = 0; j < i; j++) { + stree_from_collapse.insert_simplex({i, j}, std::numeric_limits::infinity()); + } + } + mat_filt_edge_coll.filtered_edge_collapse( + [&stree_from_collapse](const std::vector& edge, Filtration_value filtration) { + // insert the edge + stree_from_collapse.assign_filtration(stree_from_collapse.find(edge), filtration); + }); + + std::vector ppairs_from_collapse = get_persistence_pairs(stree_from_collapse, ambient_dim); + + // ***** Simplex tree from the complete flag complex ***** + Simplex_tree stree_wo_collapse; + stree_wo_collapse.insert_graph(proximity_graph); + + std::vector ppairs_wo_collapse = get_persistence_pairs(stree_wo_collapse, ambient_dim); + + if (ppairs_wo_collapse.size() != ppairs_from_collapse.size()) { + std::cerr << "Number of persistence pairs with collapse is " << ppairs_from_collapse.size() << std::endl; + std::cerr << "Number of persistence pairs without collapse is " << ppairs_wo_collapse.size() << std::endl; + exit(-1); + } + + int return_value = 0; + auto ppwoc_ptr = ppairs_wo_collapse.begin(); + for (auto ppfc: ppairs_from_collapse) { + if (ppfc != *ppwoc_ptr) { + return_value++; + std::cerr << "Without collapse: " + << std::get<0>(*ppwoc_ptr) << " " << std::get<1>(*ppwoc_ptr) << " " << std::get<2>(*ppwoc_ptr) + << " - With collapse: " + << std::get<0>(ppfc) << " " << std::get<1>(ppfc) << " " << std::get<2>(ppfc) << std::endl; + } + ppwoc_ptr++; + } + return return_value; +} -- cgit v1.2.3 From 52fe5b2c6841dc15000896c60e0d6a12591bdc29 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 4 Jun 2020 15:14:50 +0200 Subject: Revert "Try to add inf values" This reverts commit 8e3e8efcb0c9a3e5650545ee0d9756129b10a95c. --- src/Collapse/example/CMakeLists.txt | 7 - ...edge_collapse_conserve_persistence_with_inf.cpp | 164 --------------------- 2 files changed, 171 deletions(-) delete mode 100644 src/Collapse/example/edge_collapse_conserve_persistence_with_inf.cpp (limited to 'src/Collapse/example/CMakeLists.txt') diff --git a/src/Collapse/example/CMakeLists.txt b/src/Collapse/example/CMakeLists.txt index 95e1696f..96354489 100644 --- a/src/Collapse/example/CMakeLists.txt +++ b/src/Collapse/example/CMakeLists.txt @@ -21,10 +21,3 @@ add_test(NAME Edge_collapse_conserve_persistence_1 COMMAND $ "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" "2.") - -# Tests -add_executable ( inf edge_collapse_conserve_persistence_with_inf.cpp ) - -if (TBB_FOUND) - target_link_libraries(inf ${TBB_LIBRARIES}) -endif() diff --git a/src/Collapse/example/edge_collapse_conserve_persistence_with_inf.cpp b/src/Collapse/example/edge_collapse_conserve_persistence_with_inf.cpp deleted file mode 100644 index 0555725f..00000000 --- a/src/Collapse/example/edge_collapse_conserve_persistence_with_inf.cpp +++ /dev/null @@ -1,164 +0,0 @@ -/* 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 -#include -#include -#include -#include -#include - -#include // for std::pair -#include -#include -#include // for numeric_limits<> - -// Types definition - -using Simplex_tree = Gudhi::Simplex_tree<>; -using Filtration_value = Simplex_tree::Filtration_value; -using Vertex_handle = Simplex_tree::Vertex_handle; -using Point = std::vector; -using Vector_of_points = std::vector; - -using Flag_complex_sparse_matrix = Gudhi::collapse::Flag_complex_sparse_matrix; -using Proximity_graph = Flag_complex_sparse_matrix::Proximity_graph; - -using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; -using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; - -using Persistence_pair = std::tuple; -/* - * Compare two intervals by dimension, then by length. - */ -struct cmp_intervals_by_dim_then_length { - explicit cmp_intervals_by_dim_then_length(Simplex_tree * sc) - : sc_(sc) { } - - template - bool operator()(const Persistent_interval & p1, const Persistent_interval & p2) { - if (sc_->dimension(get < 0 > (p1)) == sc_->dimension(get < 0 > (p2))) - return (sc_->filtration(get < 1 > (p1)) - sc_->filtration(get < 0 > (p1)) - > sc_->filtration(get < 1 > (p2)) - sc_->filtration(get < 0 > (p2))); - else - return (sc_->dimension(get < 0 > (p1)) > sc_->dimension(get < 0 > (p2))); - } - Simplex_tree* sc_; -}; - -std::vector get_persistence_pairs(Simplex_tree& st, int ambient_dim) { - std::vector ppairs; - std::cout << "expansion" << std::endl; - st.expansion(ambient_dim); - - // Sort the simplices in the order of the filtration - std::cout << "initialize_filtration" << std::endl; - st.initialize_filtration(); - std::cout << "Persistent_cohomology" << std::endl; - // Compute the persistence diagram of the complex - Persistent_cohomology pcoh(st); - // initializes the coefficient field for homology - must be a prime number - int p = 11; - std::cout << "init_coefficients" << std::endl; - pcoh.init_coefficients(p); - - // Default min_interval_length = 0. - std::cout << "compute_persistent_cohomology" << std::endl; - pcoh.compute_persistent_cohomology(); - // Custom sort and output persistence - cmp_intervals_by_dim_then_length cmp(&st); - auto persistent_pairs = pcoh.get_persistent_pairs(); - std::sort(std::begin(persistent_pairs), std::end(persistent_pairs), cmp); - for (auto pair : persistent_pairs) { - ppairs.push_back({st.dimension(get<0>(pair)), - st.filtration(get<0>(pair)), - st.filtration(get<1>(pair)) }); - } - return ppairs; -} - -int main(int argc, char* argv[]) { - if (argc != 3) { - std::cerr << "This program requires an OFF file and minimal threshold value as parameter\n"; - std::cerr << "For instance: ./Edge_collapse_conserve_persistence ../../data/points/tore3D_300.off 1.\n"; - exit(-1); // ----- >> - } - - std::string off_file_points {argv[1]}; - double threshold {atof(argv[2])}; - - Gudhi::Points_off_reader off_reader(off_file_points); - if (!off_reader.is_valid()) { - std::cerr << "Unable to read file " << off_file_points << "\n"; - exit(-1); // ----- >> - } - - Vector_of_points point_vector = off_reader.get_point_cloud(); - if (point_vector.size() <= 0) { - std::cerr << "Empty point cloud." << std::endl; - exit(-1); // ----- >> - } - - Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(off_reader.get_point_cloud(), - threshold, - Gudhi::Euclidean_distance()); - - if (num_edges(proximity_graph) <= 0) { - std::cerr << "Total number of egdes are zero." << std::endl; - exit(-1); - } - - int ambient_dim = point_vector[0].size(); - - // ***** Simplex tree from a flag complex built after collapse ***** - Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); - - Simplex_tree stree_from_collapse; - for (Vertex_handle i = 0; i < point_vector.size(); i++) { - // insert the 2 vertices with a 0. filtration value just like a Rips - stree_from_collapse.insert_simplex({i}, 0.); - for (Vertex_handle j = 0; j < i; j++) { - stree_from_collapse.insert_simplex({i, j}, std::numeric_limits::infinity()); - } - } - mat_filt_edge_coll.filtered_edge_collapse( - [&stree_from_collapse](const std::vector& edge, Filtration_value filtration) { - // insert the edge - stree_from_collapse.assign_filtration(stree_from_collapse.find(edge), filtration); - }); - - std::vector ppairs_from_collapse = get_persistence_pairs(stree_from_collapse, ambient_dim); - - // ***** Simplex tree from the complete flag complex ***** - Simplex_tree stree_wo_collapse; - stree_wo_collapse.insert_graph(proximity_graph); - - std::vector ppairs_wo_collapse = get_persistence_pairs(stree_wo_collapse, ambient_dim); - - if (ppairs_wo_collapse.size() != ppairs_from_collapse.size()) { - std::cerr << "Number of persistence pairs with collapse is " << ppairs_from_collapse.size() << std::endl; - std::cerr << "Number of persistence pairs without collapse is " << ppairs_wo_collapse.size() << std::endl; - exit(-1); - } - - int return_value = 0; - auto ppwoc_ptr = ppairs_wo_collapse.begin(); - for (auto ppfc: ppairs_from_collapse) { - if (ppfc != *ppwoc_ptr) { - return_value++; - std::cerr << "Without collapse: " - << std::get<0>(*ppwoc_ptr) << " " << std::get<1>(*ppwoc_ptr) << " " << std::get<2>(*ppwoc_ptr) - << " - With collapse: " - << std::get<0>(ppfc) << " " << std::get<1>(ppfc) << " " << std::get<2>(ppfc) << std::endl; - } - ppwoc_ptr++; - } - return return_value; -} -- cgit v1.2.3 From a106902b9f52115ec481029df194dffc4685e2ca Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 4 Jun 2020 16:39:24 +0200 Subject: Fix tests and utils --- src/Collapse/example/CMakeLists.txt | 6 +++--- .../example/edge_collapse_conserve_persistence.cpp | 15 +++++++++------ .../distance_matrix_edge_collapse_rips_persistence.cpp | 4 ++++ .../point_cloud_edge_collapse_rips_persistence.cpp | 6 +++++- 4 files changed, 21 insertions(+), 10 deletions(-) (limited to 'src/Collapse/example/CMakeLists.txt') diff --git a/src/Collapse/example/CMakeLists.txt b/src/Collapse/example/CMakeLists.txt index 96354489..ba0e75e3 100644 --- a/src/Collapse/example/CMakeLists.txt +++ b/src/Collapse/example/CMakeLists.txt @@ -17,7 +17,7 @@ if (TBB_FOUND) endif() add_test(NAME Edge_collapse_conserve_persistence_1 COMMAND $ - "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" "1.") + "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" "0.2") - add_test(NAME Edge_collapse_conserve_persistence_2 COMMAND $ - "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" "2.") +add_test(NAME Edge_collapse_conserve_persistence_2 COMMAND $ + "${CMAKE_SOURCE_DIR}/data/points/tore3D_300.off" "1.8") diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp index 0beef061..93982081 100644 --- a/src/Collapse/example/edge_collapse_conserve_persistence.cpp +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -109,28 +109,31 @@ int main(int argc, char* argv[]) { exit(-1); } + int ambient_dim = point_vector[0].size(); + // ***** Simplex tree from a flag complex built after collapse ***** Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); Simplex_tree stree_from_collapse; + for (Vertex_handle vertex = 0; vertex < point_vector.size(); vertex++) { + // insert the vertex with a 0. filtration value just like a Rips + stree_from_collapse.insert_simplex({vertex}, 0.); + } mat_filt_edge_coll.filtered_edge_collapse( [&stree_from_collapse](const std::vector& edge, Filtration_value filtration) { - // insert the 2 vertices with a 0. filtration value just like a Rips - stree_from_collapse.insert_simplex({edge[0]}, 0.); - stree_from_collapse.insert_simplex({edge[1]}, 0.); // insert the edge stree_from_collapse.insert_simplex(edge, filtration); }); + std::vector ppairs_from_collapse = get_persistence_pairs(stree_from_collapse, ambient_dim); + // ***** Simplex tree from the complete flag complex ***** Simplex_tree stree_wo_collapse; stree_wo_collapse.insert_graph(proximity_graph); - int ambient_dim = point_vector[0].size(); - - std::vector ppairs_from_collapse = get_persistence_pairs(stree_from_collapse, ambient_dim); std::vector ppairs_wo_collapse = get_persistence_pairs(stree_wo_collapse, ambient_dim); + // ***** Comparison ***** if (ppairs_wo_collapse.size() != ppairs_from_collapse.size()) { std::cerr << "Number of persistence pairs with collapse is " << ppairs_from_collapse.size() << std::endl; std::cerr << "Number of persistence pairs without collapse is " << ppairs_wo_collapse.size() << std::endl; diff --git a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp index f39e9764..1ac017c2 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -93,6 +93,10 @@ int main(int argc, char* argv[]) { Flag_complex_sparse_matrix flag_complex(proximity_graph); Simplex_tree stree; + for (Vertex_handle vertex = 0; vertex < distances.size(); vertex++) { + // insert the vertex with a 0. filtration value just like a Rips + stree.insert_simplex({vertex}, 0.); + } flag_complex.filtered_edge_collapse( [&stree](std::vector edge, Filtration_value filtration) { // insert the 2 vertices with a 0. filtration value just like a Rips diff --git a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp index 067b29e3..9624d516 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -68,7 +68,7 @@ int main(int argc, char* argv[]) { std::cout << "Successfully read " << point_vector.size() << " point_vector.\n"; std::cout << "Ambient dimension is " << point_vector[0].size() << ".\n"; - Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(off_reader.get_point_cloud(), + Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(point_vector, threshold, Gudhi::Euclidean_distance()); @@ -80,6 +80,10 @@ int main(int argc, char* argv[]) { Flag_complex_sparse_matrix mat_filt_edge_coll(proximity_graph); Simplex_tree stree; + for (Vertex_handle vertex = 0; vertex < point_vector.size(); vertex++) { + // insert the vertex with a 0. filtration value just like a Rips + stree.insert_simplex({vertex}, 0.); + } mat_filt_edge_coll.filtered_edge_collapse( [&stree](const std::vector& edge, Filtration_value filtration) { // insert the 2 vertices with a 0. filtration value just like a Rips -- cgit v1.2.3