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/common/doc/main_page.md | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) (limited to 'src/common/doc/main_page.md') 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 4fdc721bbd19bc6389d611d252ff08f8fbbeee23 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Tue, 28 Apr 2020 08:33:51 +0200 Subject: Code and doc review fix --- src/Collapse/doc/intro_edge_collapse.h | 2 +- src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h | 10 +++++----- .../distance_matrix_edge_collapse_rips_persistence.cpp | 4 +--- src/common/doc/main_page.md | 2 +- src/common/include/gudhi/graph_simplicial_complex.h | 8 ++++++++ 5 files changed, 16 insertions(+), 10 deletions(-) (limited to 'src/common/doc/main_page.md') diff --git a/src/Collapse/doc/intro_edge_collapse.h b/src/Collapse/doc/intro_edge_collapse.h index 0691ccf6..5c126d29 100644 --- a/src/Collapse/doc/intro_edge_collapse.h +++ b/src/Collapse/doc/intro_edge_collapse.h @@ -2,7 +2,7 @@ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Siddharth Pritam * - * Copyright (C) 2019 Inria + * Copyright (C) 2020 Inria * * Modification(s): * - YYYY/MM Author: Description of the modification diff --git a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h index 49c28f63..6fa4438c 100644 --- a/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h +++ b/src/Collapse/include/gudhi/Flag_complex_sparse_matrix.h @@ -2,7 +2,7 @@ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details. * Author(s): Siddharth Pritam * - * Copyright (C) 2018 Inria + * Copyright (C) 2020 Inria * * Modification(s): * - 2020/03 Vincent Rouvreau: integration to the gudhi library @@ -44,8 +44,8 @@ namespace collapse { * \ingroup collapse * * \details - * A class to store the vertices v/s MaxSimplices Sparse Matrix and to perform collapse operations using the N^2() - * Algorithm. + * This class stores a Flag complex + * in an Eigen sparse matrix. * * \tparam Vertex type must be a signed integer type. It admits a total order <. * \tparam Filtration type for the value of the filtration function. Must be comparable with <. @@ -73,7 +73,7 @@ class Flag_complex_sparse_matrix { using Row_indices_vector = std::vector; public: - /** \brief A Filtered_edge is a std::pair, `Filtration_value`>. */ + /** \brief Filtered_edge is a type to store an edge with its filtration value. */ using Filtered_edge = std::pair; /** \brief Proximity_graph is a type that can be used to construct easily a Flag_complex_sparse_matrix. */ using Proximity_graph = Gudhi::Proximity_graph; @@ -358,7 +358,7 @@ class Flag_complex_sparse_matrix { } } - /** \brief Performs edge collapse in a decreasing sequence of the filtration value. + /** \brief Performs edge collapse in a increasing sequence of the filtration value. * * \tparam FilteredEdgeInsertion is an output iterator that furnishes * `({Vertex_handle u, Vertex_handle v}, Filtration_value f)` that will fill the user defined data structure. 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 f4a460ab..f39e9764 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -79,9 +79,7 @@ int main(int argc, char* argv[]) { program_options(argc, argv, csv_matrix_file, filediag, threshold, dim_max, p, min_persistence); - Distance_matrix distances; - - distances = Gudhi::read_lower_triangular_matrix_from_csv_file(csv_matrix_file); + Distance_matrix distances = Gudhi::read_lower_triangular_matrix_from_csv_file(csv_matrix_file); std::cout << "Read the distance matrix succesfully, of size: " << distances.size() << std::endl; Proximity_graph proximity_graph = Gudhi::compute_proximity_graph(boost::irange((size_t)0, diff --git a/src/common/doc/main_page.md b/src/common/doc/main_page.md index cdea3d94..85b39be9 100644 --- a/src/common/doc/main_page.md +++ b/src/common/doc/main_page.md @@ -242,7 +242,7 @@
-#### Strong collapse +#### Edge collapse diff --git a/src/common/include/gudhi/graph_simplicial_complex.h b/src/common/include/gudhi/graph_simplicial_complex.h index b8508697..3e7720d7 100644 --- a/src/common/include/gudhi/graph_simplicial_complex.h +++ b/src/common/include/gudhi/graph_simplicial_complex.h @@ -19,6 +19,9 @@ #include // for std::tie namespace Gudhi { +/** @file + * @brief Graph simplicial complex methods + */ /* Edge tag for Boost PropertyGraph. */ struct edge_filtration_t { @@ -42,10 +45,15 @@ using Proximity_graph = typename boost::adjacency_list < boost::vecS, boost::vec , boost::property < edge_filtration_t, typename SimplicialComplexForProximityGraph::Filtration_value >>; /** \brief Computes the proximity graph of the points. + * + * \fn Gudhi::Proximity_graph compute_proximity_graph(const ForwardPointRange& + * points, typename SimplicialComplexForProximityGraph::Filtration_value threshold, Distance distance) * * If points contains n elements, the proximity graph is the graph with n vertices, and an edge [u,v] iff the * distance function between points u and v is smaller than threshold. * + * \tparam SimplicialComplexForProximityGraph furnishes `Filtration_value` and `Vertex_handle` type definitions. + * * \tparam ForwardPointRange furnishes `.begin()` and `.end()` methods. * * \tparam Distance furnishes `operator()(const Point& p1, const Point& p2)`, where -- cgit v1.2.3 From 796ebfdc2e6b6e3cdac18760f905ddf8dfc7367e Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Tue, 2 Jun 2020 22:31:59 +0200 Subject: Move Edge collapse section --- src/common/doc/main_page.md | 46 ++++++++++++++++++++++----------------------- 1 file changed, 23 insertions(+), 23 deletions(-) (limited to 'src/common/doc/main_page.md') diff --git a/src/common/doc/main_page.md b/src/common/doc/main_page.md index 462d857e..b12145a3 100644 --- a/src/common/doc/main_page.md +++ b/src/common/doc/main_page.md @@ -217,57 +217,57 @@
-### Witness complex +### Edge collapse
- \image html "Witness_complex_representation.png" + \image html "edge_collapse_representation.png" - Witness complex \f$ Wit(W,L) \f$ is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$. - The data structure is described in \cite boissonnatmariasimplextreealgorithmica . + 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: Siargey Kachanovich
- Introduced in: GUDHI 1.3.0
- Copyright: MIT ([GPL v3](../../licensing/) for Euclidean version)
- Euclidean version requires: \ref eigen ≥ 3.1.0 and \ref cgal ≥ 4.11.0 + Author: Siddharth Pritam
+ Introduced in: GUDHI 2.4.0
+ Copyright: MIT
+ Requires: \ref eigen
- User manual: \ref witness_complex + User manual: \ref edge_collapse
-#### Edge collapse +### Witness complex
- \image html "edge_collapse_representation.png" + \image html "Witness_complex_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. + Witness complex \f$ Wit(W,L) \f$ is a simplicial complex defined on two sets of points in \f$\mathbb{R}^D\f$. + The data structure is described in \cite boissonnatmariasimplextreealgorithmica . - Author: Siddharth Pritam
- Introduced in: GUDHI 2.4.0
- Copyright: MIT
- Requires: \ref eigen + Author: Siargey Kachanovich
+ Introduced in: GUDHI 1.3.0
+ Copyright: MIT ([GPL v3](../../licensing/) for Euclidean version)
+ Euclidean version requires: \ref eigen ≥ 3.1.0 and \ref cgal ≥ 4.11.0
- User manual: \ref edge_collapse + User manual: \ref witness_complex
-- cgit v1.2.3 From 0a26e55af17a19b3e33b852b722f6d089abc6f9c Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Mon, 15 Jun 2020 08:45:36 +0200 Subject: Add image for edge collapse --- src/Collapse/doc/dominated_edge.png | Bin 0 -> 349766 bytes src/common/doc/main_page.md | 2 +- 2 files changed, 1 insertion(+), 1 deletion(-) create mode 100644 src/Collapse/doc/dominated_edge.png (limited to 'src/common/doc/main_page.md') diff --git a/src/Collapse/doc/dominated_edge.png b/src/Collapse/doc/dominated_edge.png new file mode 100644 index 00000000..5900a55a Binary files /dev/null and b/src/Collapse/doc/dominated_edge.png differ diff --git a/src/common/doc/main_page.md b/src/common/doc/main_page.md index b12145a3..740a3e52 100644 --- a/src/common/doc/main_page.md +++ b/src/common/doc/main_page.md @@ -222,7 +222,7 @@ -- cgit v1.2.3
- \image html "edge_collapse_representation.png" + \image html "dominated_edge.png" Edge collapse is able to reduce any flag filtration to a smaller flag filtration with the same persistence, using -- cgit v1.2.3 From f7876ea08e810c57f90e0233fffbd91d57f6d037 Mon Sep 17 00:00:00 2001 From: ROUVREAU Vincent Date: Wed, 1 Jul 2020 22:09:58 +0200 Subject: doc review: fix some errors --- biblio/bibliography.bib | 28 +++++++++++++--------- .../include/gudhi/Flag_complex_edge_collapser.h | 6 ++--- src/common/doc/main_page.md | 2 +- 3 files changed, 20 insertions(+), 16 deletions(-) (limited to 'src/common/doc/main_page.md') diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 4e716986..ad8ce50a 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -1279,15 +1279,21 @@ year = "2011" bibsource = {dblp computer science bibliography, https://dblp.org} } -@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 ; Computational Topology}, - pdf = {https://hal.inria.fr/hal-02395227/file/socg2020_paper_152.pdf}, - hal_id = {hal-02395227}, - hal_version = {v1}, +@InProceedings{edgecollapsesocg2020, + author = {Jean-Daniel Boissonnat and Siddharth Pritam}, + title = {{Edge Collapse and Persistence of Flag Complexes}}, + booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, + pages = {19:1--19:15}, + series = {Leibniz International Proceedings in Informatics (LIPIcs)}, + ISBN = {978-3-95977-143-6}, + ISSN = {1868-8969}, + year = {2020}, + volume = {164}, + editor = {Sergio Cabello and Danny Z. Chen}, + publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik}, + address = {Dagstuhl, Germany}, + URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12177}, + URN = {urn:nbn:de:0030-drops-121777}, + doi = {10.4230/LIPIcs.SoCG.2020.19}, + annote = {Keywords: Computational Topology, Topological Data Analysis, Edge Collapse, Simple Collapse, Persistent homology} } diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 01be8f03..d1a47b75 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -342,16 +342,14 @@ class Flag_complex_edge_collapser { /** \brief Implicitly constructs a flag complex from edges as an input, collapses edges while preserving the persistent * homology and returns the remaining edges as a range. * - * \fn auto Gudhi::collapse::flag_complex_collapse_edges(FilteredEdgeRange const& edges) - * * \param[in] edges Range of Filtered edges.There is no need the range to be sorted, as it will be performed. * * \tparam FilteredEdgeRange furnishes `std::begin` and `std::end` methods and returns an iterator on a * FilteredEdge of type `std::tuple` where `Vertex_handle` is the type * of a vertex index and `Filtration_value` is the type of an edge filtration value. * - * \return Remaining edges after collapse of type - * `std::vector>`. + * \return Remaining edges after collapse as a range of + * ``. * * \ingroup edge_collapse * diff --git a/src/common/doc/main_page.md b/src/common/doc/main_page.md index 740a3e52..e19af537 100644 --- a/src/common/doc/main_page.md +++ b/src/common/doc/main_page.md @@ -235,7 +235,7 @@ Author: Siddharth Pritam
- Introduced in: GUDHI 2.4.0
+ Introduced in: GUDHI 3.3.0
Copyright: MIT
Requires: \ref eigen