From 23ea38b9c879088c58e02ea4cf5aa5799e8d00b0 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Sat, 11 Apr 2020 10:02:27 +0200 Subject: Proper copyrights and doc for utils --- src/Collapse/utilities/collapse.md | 63 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 63 insertions(+) create mode 100644 src/Collapse/utilities/collapse.md (limited to 'src/Collapse/utilities/collapse.md') diff --git a/src/Collapse/utilities/collapse.md b/src/Collapse/utilities/collapse.md new file mode 100644 index 00000000..9ca5077a --- /dev/null +++ b/src/Collapse/utilities/collapse.md @@ -0,0 +1,63 @@ +--- +layout: page +title: "Collapse" +meta_title: "Edge collapse" +teaser: "" +permalink: /collapse/ +--- +{::comment} +Leave the lines above as it is required by the web site generator 'Jekyll' +{:/comment} + + +## point_cloud_edge_collapse_rips_persistence ## +This program computes the one-skeleton graph defined on a set of input points, using Euclidean distance, and collapse edges. +This program finally computes persistent homology with coefficient field *Z/pZ* of the Rips complex built on top of these collapse edges. +The output diagram contains one bar per line, written with the convention: + +`p dim birth death` + +where `dim` is the dimension of the homological feature, `birth` and `death` are respectively the birth and death of the feature, and `p` is the characteristic of the field *Z/pZ* used for homology coefficients (`p` must be a prime number). + +**Usage** + +`point_cloud_edge_collapse_rips_persistence [options] ` + +**Allowed options** + +* `-h [ --help ]` Produce help message +* `-o [ --output-file ]` Name of file in which the persistence diagram is written. Default print in standard output. +* `-r [ --max-edge-length ]` (default = inf) Maximal length of an edge for the Rips complex construction. +* `-d [ --cpx-dimension ]` (default = 1) Maximal dimension of the Rips complex we want to compute. +* `-p [ --field-charac ]` (default = 11) Characteristic p of the coefficient field Z/pZ for computing homology. +* `-m [ --min-persistence ]` (default = 0) Minimal lifetime of homology feature to be recorded. Enter a negative value to see zero length intervals. + +Beware: this program may use a lot of RAM and take a lot of time if `max-edge-length` is set to a large value. + +**Example 1 with Z/2Z coefficients** + +`point_cloud_edge_collapse_rips_persistence ../../data/points/tore3D_1307.off -r 0.25 -m 0.5 -d 3 -p 2` + +**Example 2 with Z/3Z coefficients** + +`point_cloud_edge_collapse_rips_persistence ../../data/points/tore3D_1307.off -r 0.25 -m 0.5 -d 3 -p 3` + + +## distance_matrix_edge_collapse_rips_persistence ## + +Same as `point_cloud_edge_collapse_rips_persistence` but taking a distance matrix as input. + +**Usage** + +`distance_matrix_edge_collapse_rips_persistence [options] ` + +where +`` is the path to the file containing a distance matrix. Can be square or lower triangular matrix. Separator is ';'. +The code do not check if it is dealing with a distance matrix. It is the user responsibility to provide a valid input. +Please refer to data/distance_matrix/lower_triangular_distance_matrix.csv for an example of a file. + +**Example** + +`distance_matrix_edge_collapse_rips_persistence data/distance_matrix/full_square_distance_matrix.csv -r 15 -d 3 -p 3 -m 0` + + -- cgit v1.2.3 From 0dc7269875e9101902adf414c62f95730fddcbcd Mon Sep 17 00:00:00 2001 From: Vincent Rouvreau <10407034+VincentRouvreau@users.noreply.github.com> Date: Fri, 17 Apr 2020 17:19:18 +0200 Subject: Update src/Collapse/utilities/collapse.md Co-Authored-By: Marc Glisse --- src/Collapse/utilities/collapse.md | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/Collapse/utilities/collapse.md') diff --git a/src/Collapse/utilities/collapse.md b/src/Collapse/utilities/collapse.md index 9ca5077a..a0220edb 100644 --- a/src/Collapse/utilities/collapse.md +++ b/src/Collapse/utilities/collapse.md @@ -11,7 +11,7 @@ Leave the lines above as it is required by the web site generator 'Jekyll' ## point_cloud_edge_collapse_rips_persistence ## -This program computes the one-skeleton graph defined on a set of input points, using Euclidean distance, and collapse edges. +This program computes the Rips graph defined on a set of input points, using Euclidean distance, and collapses edges. This program finally computes persistent homology with coefficient field *Z/pZ* of the Rips complex built on top of these collapse edges. The output diagram contains one bar per line, written with the convention: @@ -60,4 +60,3 @@ Please refer to data/distance_matrix/lower_triangular_distance_matrix.csv for an `distance_matrix_edge_collapse_rips_persistence data/distance_matrix/full_square_distance_matrix.csv -r 15 -d 3 -p 3 -m 0` - -- cgit v1.2.3 From 2945af0dd22fd95e61b5757d9bb9c3de5dae0abc Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Thu, 25 Jun 2020 18:06:41 +0200 Subject: Iterate on edge collapse for utils --- src/Collapse/utilities/collapse.md | 1 + .../point_cloud_edge_collapse_rips_persistence.cpp | 49 +++++++++++++++------- 2 files changed, 35 insertions(+), 15 deletions(-) (limited to 'src/Collapse/utilities/collapse.md') diff --git a/src/Collapse/utilities/collapse.md b/src/Collapse/utilities/collapse.md index a0220edb..1f41bb1f 100644 --- a/src/Collapse/utilities/collapse.md +++ b/src/Collapse/utilities/collapse.md @@ -31,6 +31,7 @@ where `dim` is the dimension of the homological feature, `birth` and `death` are * `-d [ --cpx-dimension ]` (default = 1) Maximal dimension of the Rips complex we want to compute. * `-p [ --field-charac ]` (default = 11) Characteristic p of the coefficient field Z/pZ for computing homology. * `-m [ --min-persistence ]` (default = 0) Minimal lifetime of homology feature to be recorded. Enter a negative value to see zero length intervals. +* `-i [ --edge-collapse-iterations ]` (default = 1) Number of iterations edge collapse is performed. Beware: this program may use a lot of RAM and take a lot of time if `max-edge-length` is set to a large 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 4e14d7a8..8522c259 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -30,13 +30,15 @@ using Point = std::vector; using Vector_of_points = std::vector; using Flag_complex_edge_collapser = Gudhi::collapse::Flag_complex_edge_collapser; +using Filtered_edge = Flag_complex_edge_collapser::Filtered_edge; using Proximity_graph = Gudhi::Proximity_graph; using Field_Zp = Gudhi::persistent_cohomology::Field_Zp; using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomology; 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); + Filtration_value& threshold, int& dim_max, int& p, int& edge_collapse_iter_nb, + Filtration_value& min_persistence); int main(int argc, char* argv[]) { std::string off_file_points; @@ -44,9 +46,10 @@ int main(int argc, char* argv[]) { double threshold; int dim_max; int p; + int edge_collapse_iter_nb; double min_persistence; - program_options(argc, argv, off_file_points, filediag, threshold, dim_max, p, min_persistence); + program_options(argc, argv, off_file_points, filediag, threshold, dim_max, p, edge_collapse_iter_nb, min_persistence); std::cout << "The current input values to run the program is: " << std::endl; std::cout << "min_persistence, threshold, max_complex_dimension, off_file_points, filediag" @@ -78,24 +81,37 @@ int main(int argc, char* argv[]) { exit(-1); } - Flag_complex_edge_collapser edge_collapser( - boost::adaptors::transform(edges(proximity_graph), [&](auto&&edge){ - return std::make_tuple(source(edge, proximity_graph), - target(edge, proximity_graph), - get(Gudhi::edge_filtration_t(), proximity_graph, edge)); - }) - ); + auto edges_from_graph = boost::adaptors::transform(edges(proximity_graph), [&](auto&&edge){ + return std::make_tuple(source(edge, proximity_graph), + target(edge, proximity_graph), + get(Gudhi::edge_filtration_t(), proximity_graph, edge)); + }); + std::vector edges_list(edges_from_graph.begin(), edges_from_graph.end()); + + std::vector remaining_edges; + for (int iter = 0; iter < edge_collapse_iter_nb; iter++) { + Flag_complex_edge_collapser edge_collapser(edges_list); + edge_collapser.process_edges( + [&remaining_edges](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { + // insert the edge + remaining_edges.emplace_back(u, v, filtration); + }); + if ((iter + 1) < edge_collapse_iter_nb) { + edges_list.clear(); + std::copy(remaining_edges.begin(), remaining_edges.end(), std::back_inserter(edges_list)); + remaining_edges.clear(); + } + } Simplex_tree stree; for (Vertex_handle vertex = 0; static_cast(vertex) < point_vector.size(); vertex++) { // insert the vertex with a 0. filtration value just like a Rips stree.insert_simplex({vertex}, 0.); } - edge_collapser.process_edges( - [&stree](Vertex_handle u, Vertex_handle v, Filtration_value filtration) { - // insert the edge - stree.insert_simplex({u, v}, filtration); - }); + + for (auto filtered_edge : remaining_edges) { + stree.insert_simplex({std::get<0>(filtered_edge), std::get<1>(filtered_edge)}, std::get<2>(filtered_edge)); + } stree.expansion(dim_max); @@ -122,7 +138,8 @@ int main(int argc, char* argv[]) { } 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) { + Filtration_value& threshold, int& dim_max, int& p, int& edge_collapse_iter_nb, + Filtration_value& min_persistence) { namespace po = boost::program_options; po::options_description hidden("Hidden options"); hidden.add_options()("input-file", po::value(&off_file_points), @@ -139,6 +156,8 @@ void program_options(int argc, char* argv[], std::string& off_file_points, std:: "Maximal dimension of the Rips complex we want to compute.")( "field-charac,p", po::value(&p)->default_value(11), "Characteristic p of the coefficient field Z/pZ for computing homology.")( + "edge-collapse-iterations,i", po::value(&edge_collapse_iter_nb)->default_value(1), + "Number of iterations edge collapse is performed.")( "min-persistence,m", po::value(&min_persistence), "Minimal lifetime of homology feature to be recorded. Default is 0. Enter a negative value to see zero length " "intervals"); -- cgit v1.2.3