diff options
| author | Hind-M <hind.montassif@gmail.com> | 2022-06-07 14:40:04 +0200 |
|---|---|---|
| committer | Hind-M <hind.montassif@gmail.com> | 2022-06-07 14:40:04 +0200 |
| commit | ca724df0c8946bd40afb8e22c24d05329f43c16c (patch) | |
| tree | cad0f24477071411cd4c703bf0e3ab30d9444809 | |
| parent | 899fb73b33cb6976c39a42ba26a31cf2acde63ee (diff) | |
| parent | 2a33be5f580e5d868efe674471f32d1d025fb3c4 (diff) | |
Merge remote-tracking branch 'upstream/master' into fetch_datasets
83 files changed, 789 insertions, 827 deletions
diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index e75e8db2..8462e731 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -14,7 +14,7 @@ publisher = {JMLR.org}, title = {{Statistical analysis and parameter selection for Mapper}}, volume = {19}, year = {2018}, -url = {http://jmlr.org/papers/v19/17-291.html}, +url = {https://jmlr.org/papers/v19/17-291.html}, } @inproceedings{Dey13, @@ -151,10 +151,10 @@ language={English}, %% hal-00922572, version 2 -%% http://hal.inria.fr/hal-00922572 +%% https://hal.inria.fr/hal-00922572 @techreport{boissonnat:hal-00922572, hal_id = {hal-00922572}, - url = {http://hal.inria.fr/hal-00922572}, + url = {https://hal.inria.fr/hal-00922572}, title = {Computing Persistent Homology with Various Coefficient Fields in a Single Pass}, author = {Boissonnat, Jean-Daniel and Maria, Cl{\'e}ment}, abstract = {{In this article, we introduce the multi-field persistence diagram for the persistence homology of a filtered complex. It encodes compactly the superimposition of the persistence diagrams of the complex with several field coefficients, and provides a substantially more precise description of the topology of the filtered complex. Specifically, the multi-field persistence diagram encodes the Betti numbers of integral homology and the prime divisors of the torsion coefficients of the underlying shape. Moreover, it enjoys similar stability properties as the ones of standard persistence diagrams, with the appropriate notion of distance. These properties make the multi-field persistence diagram a useful tool in computational topology.}}, @@ -167,7 +167,7 @@ language={English}, number = {RR-8436}, year = {2013}, month = Dec, - pdf = {http://hal.inria.fr/hal-00922572/PDF/RR-8436.pdf}, + pdf = {https://hal.inria.fr/hal-00922572v5/document}, } @@ -323,7 +323,7 @@ language={English}, %------------------------------------------------------------------ @article{rips2012, hal_id = {hal-00785072}, - url = {http://hal.archives-ouvertes.fr/hal-00785072}, + url = {https://hal.archives-ouvertes.fr/hal-00785072}, title = {{Vietoris-Rips Complexes also Provide Topologically Correct Reconstructions of Sampled Shapes}}, author = {Attali, Dominique and Lieutier, Andr{\'e} and Salinas, David}, keywords = {Shape reconstruction \sep Rips complexes \sep clique complexes \sep \v Cech complexes ; homotopy equivalence ; collapses ; high dimensions}, @@ -1115,7 +1115,7 @@ language={English} author = {Nicholas J. Cavanna and Mahmoodreza Jahanseir and Donald R. Sheehy}, booktitle = {Proceedings of the Canadian Conference on Computational Geometry}, title = {A Geometric Perspective on Sparse Filtrations}, - url = {http://research.cs.queensu.ca/cccg2015/CCCG15-papers/01.pdf}, + url = {https://research.cs.queensu.ca/cccg2015/CCCG15-papers/01.pdf}, year = {2015} } @@ -1151,7 +1151,7 @@ language={English} editor = {Lars Arge and J{\'a}nos Pach}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, - URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5098}, + URL = {https://drops.dagstuhl.de/opus/volltexte/2015/5098}, URN = {urn:nbn:de:0030-drops-50981}, doi = {10.4230/LIPIcs.SOCG.2015.642}, annote = {Keywords: Simplicial complex, Compact data structures, Automaton, NP-hard} @@ -1164,7 +1164,7 @@ language={English} journal = {CoRR}, volume = {abs/1607.08449}, year = {2016}, - url = {http://arxiv.org/abs/1607.08449}, + url = {https://arxiv.org/abs/1607.08449}, archivePrefix = {arXiv}, eprint = {1607.08449}, timestamp = {Mon, 13 Aug 2018 16:46:26 +0200}, @@ -1347,6 +1347,12 @@ doi="10.1007/978-3-030-43408-3_2", annote = {Keywords: Computational Topology, Topological Data Analysis, Edge Collapse, Simple Collapse, Persistent homology} } +@misc{edgecollapsearxiv, + author = {Marc Glisse and Siddharth Pritam}, + title = {{Swap, Shift and Trim to Edge Collapse a Filtration}}, + url = {https://arxiv.org/abs/2203.07022}, +} + @phdthesis{KachanovichThesis, TITLE = {{Meshing submanifolds using Coxeter triangulations}}, AUTHOR = {Kachanovich, Siargey}, @@ -1360,4 +1366,4 @@ doi="10.1007/978-3-030-43408-3_2", PDF = {https://hal.inria.fr/tel-02419148v2/file/2019AZUR4072.pdf}, HAL_ID = {tel-02419148}, HAL_VERSION = {v2}, -}
\ No newline at end of file +} diff --git a/src/Alpha_complex/doc/Intro_alpha_complex.h b/src/Alpha_complex/doc/Intro_alpha_complex.h index 5ab23720..41e5e16d 100644 --- a/src/Alpha_complex/doc/Intro_alpha_complex.h +++ b/src/Alpha_complex/doc/Intro_alpha_complex.h @@ -107,6 +107,7 @@ Table of Contents * \subsection filtrationcomputation Filtration value computation algorithm * <br> * \f$ + * \begin{array}{l} * \textbf{for } \text{i : dimension } \rightarrow 0 \textbf{ do}\\ * \quad \textbf{for all } \sigma \text{ of dimension i}\\ * \quad\quad \textbf{if } \text{filtration(} \sigma ) \text{ is NaN} \textbf{ then}\\ @@ -127,6 +128,7 @@ Table of Contents * \textbf{end for}\\ * \text{make_filtration_non_decreasing()}\\ * \text{prune_above_filtration()}\\ + * \end{array} * \f$ * * \subsubsection dimension2 Dimension 2 @@ -164,11 +166,11 @@ Table of Contents * <b>Requires:</b> \ref eigen ≥ 3.1.0 and \ref cgal ≥ 5.1.0. * * A weighted version for Alpha complex is available (cf. Alpha_complex). It is like a usual Alpha complex, but based - * on a <a href="https://doc.cgal.org/latest/Triangulation/index.html#title20">CGAL regular triangulation</a> instead + * on a <a href="https://doc.cgal.org/latest/Triangulation/index.html#TriangulationSecRT">CGAL regular triangulation</a> instead * of Delaunay. * * This example builds the CGAL weighted alpha shapes from a small molecule, and initializes the alpha complex with - * it. This example is taken from <a href="https://doc.cgal.org/latest/Alpha_shapes_3/index.html#title13">CGAL 3d + * it. This example is taken from <a href="https://doc.cgal.org/latest/Alpha_shapes_3/index.html#AlphaShape_3DExampleforWeightedAlphaShapes">CGAL 3d * weighted alpha shapes</a>. * * Then, it is asked to display information about the alpha complex. @@ -212,7 +214,7 @@ Table of Contents * Gudhi::alpha_complex::complexity::EXACT. * * This example builds the CGAL 3d weighted alpha shapes from a small molecule, and initializes the alpha complex with - * it. This example is taken from <a href="https://doc.cgal.org/latest/Alpha_shapes_3/index.html#title13">CGAL 3d + * it. This example is taken from <a href="https://doc.cgal.org/latest/Alpha_shapes_3/index.html#AlphaShape_3DExampleforWeightedAlphaShapes">CGAL 3d * weighted alpha shapes</a>. * * Then, it is asked to display information about the alpha complex. diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex.h b/src/Alpha_complex/include/gudhi/Alpha_complex.h index 028ec9bb..b1a9407b 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex.h @@ -69,7 +69,7 @@ template<typename D> struct Is_Epeck_D<CGAL::Epeck_d<D>> { static const bool val * \ingroup alpha_complex * * \details - * The data structure is constructing a CGAL Delaunay triangulation (for more informations on CGAL Delaunay + * The data structure is constructing a CGAL Delaunay triangulation (for more information on CGAL Delaunay * triangulation, please refer to the corresponding chapter in page http://doc.cgal.org/latest/Triangulation/) from a * range of points or from an OFF file (cf. Points_off_reader). * diff --git a/src/Alpha_complex/include/gudhi/Alpha_complex_3d.h b/src/Alpha_complex/include/gudhi/Alpha_complex_3d.h index b3dbc9bb..562ef139 100644 --- a/src/Alpha_complex/include/gudhi/Alpha_complex_3d.h +++ b/src/Alpha_complex/include/gudhi/Alpha_complex_3d.h @@ -98,7 +98,7 @@ struct Value_from_iterator<complexity::EXACT> { * \tparam Periodic Boolean used to set/unset the periodic version of Alpha_complex_3d. Default value is false. * * For the weighted version, weights values are explained on CGAL - * <a href="https://doc.cgal.org/latest/Alpha_shapes_3/index.html#title0">Alpha shapes 3d</a> and + * <a href="https://doc.cgal.org/latest/Alpha_shapes_3/index.html#Alpha_shapes_3Definitions">Alpha shapes 3d</a> and * <a href="https://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation3secclassRegulartriangulation">Regular * triangulation</a> documentation. * diff --git a/src/Alpha_complex/utilities/alphacomplex.md b/src/Alpha_complex/utilities/alphacomplex.md index 0d3c6027..1e3b8fab 100644 --- a/src/Alpha_complex/utilities/alphacomplex.md +++ b/src/Alpha_complex/utilities/alphacomplex.md @@ -64,7 +64,7 @@ N.B.: * Weights values are explained on CGAL
[dD Triangulations](https://doc.cgal.org/latest/Triangulation/index.html)
and
-[Regular triangulation](https://doc.cgal.org/latest/Triangulation/index.html#title20) documentation.
+[Regular triangulation](https://doc.cgal.org/latest/Triangulation/index.html#TriangulationSecRT) documentation.
## alpha_complex_3d_persistence ##
@@ -131,6 +131,6 @@ N.B.: * `alpha_complex_3d_persistence` only accepts OFF files in dimension 3.
* Filtration values are alpha square values.
* Weights values are explained on CGAL
-[Alpha shape](https://doc.cgal.org/latest/Alpha_shapes_3/index.html#title0)
+[Alpha shape](https://doc.cgal.org/latest/Alpha_shapes_3/index.html#Alpha_shapes_3Definitions)
and
[Regular triangulation](https://doc.cgal.org/latest/Triangulation_3/index.html#Triangulation3secclassRegulartriangulation) documentation.
diff --git a/src/Bitmap_cubical_complex/include/gudhi/Bitmap_cubical_complex.h b/src/Bitmap_cubical_complex/include/gudhi/Bitmap_cubical_complex.h index aa255ec2..4a6af3a4 100644 --- a/src/Bitmap_cubical_complex/include/gudhi/Bitmap_cubical_complex.h +++ b/src/Bitmap_cubical_complex/include/gudhi/Bitmap_cubical_complex.h @@ -237,7 +237,7 @@ class Bitmap_cubical_complex : public T { * Filtration_simplex_iterator class provides an iterator though the whole structure in the order of filtration. * Secondary criteria for filtration are: * (1) Dimension of a cube (lower dimensional comes first). - * (2) Position in the data structure (the ones that are earlies in the data structure comes first). + * (2) Position in the data structure (the ones that are earliest in the data structure come first). **/ class Filtration_simplex_range; diff --git a/src/Bitmap_cubical_complex/include/gudhi/Bitmap_cubical_complex_base.h b/src/Bitmap_cubical_complex/include/gudhi/Bitmap_cubical_complex_base.h index f8f80ded..bafe7981 100644 --- a/src/Bitmap_cubical_complex/include/gudhi/Bitmap_cubical_complex_base.h +++ b/src/Bitmap_cubical_complex/include/gudhi/Bitmap_cubical_complex_base.h @@ -43,7 +43,7 @@ namespace cubical_complex { * Each cell is represented by a single * bit (in case of black and white bitmaps, or by a single element of a type T * (here T is a filtration type of a bitmap, typically a double). - * All the informations needed for homology and + * All the information needed for homology and * persistent homology computations (like dimension of a cell, boundary and * coboundary elements of a cell, are then obtained from the * position of the element in C. diff --git a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h index c65e6082..1d56f0b4 100644 --- a/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h +++ b/src/Bottleneck_distance/include/gudhi/Neighbors_finder.h @@ -86,7 +86,7 @@ class Neighbors_finder { }; /** \internal \brief data structure used to find any point (including projections) in V near to a query point from U - * (which can be a projection) in a layered graph layer given as parmeter. + * (which can be a projection) in a layered graph layer given as parameter. * * V points have to be added manually using their index and before the first pull. A neighbor pulled is automatically * removed. diff --git a/src/Cech_complex/doc/Intro_cech_complex.h b/src/Cech_complex/doc/Intro_cech_complex.h index 698f9749..095fd320 100644 --- a/src/Cech_complex/doc/Intro_cech_complex.h +++ b/src/Cech_complex/doc/Intro_cech_complex.h @@ -70,9 +70,8 @@ namespace cech_complex { * This radius computation is the reason why the Cech_complex is taking much more time to be computed than the * \ref rips_complex but it offers more topological guarantees. * - * If the Cech_complex interfaces are not detailed enough for your need, please refer to - * <a href="cech_complex_step_by_step_8cpp-example.html"> - * cech_complex_step_by_step.cpp</a> example, where the graph construction over the Simplex_tree is more detailed. + * If the Cech_complex interfaces are not detailed enough for your need, please refer to the example + * \gudhi_example_link{Cech_complex,cech_complex_step_by_step.cpp}, where the graph construction over the Simplex_tree is more detailed. * * \subsection cechpointscloudexample Example from a point cloud * diff --git a/src/Cech_complex/include/gudhi/Miniball.hpp b/src/Cech_complex/include/gudhi/Miniball.hpp index ce6cbb5b..55387a8a 100644 --- a/src/Cech_complex/include/gudhi/Miniball.hpp +++ b/src/Cech_complex/include/gudhi/Miniball.hpp @@ -1,4 +1,4 @@ -// Copright (C) 1999-2013, Bernd Gaertner +// Copyright (C) 1999-2013, Bernd Gaertner // $Rev: 3581 $ // // This program is free software: you can redistribute it and/or modify diff --git a/src/Collapse/doc/intro_edge_collapse.h b/src/Collapse/doc/intro_edge_collapse.h index fde39707..12e909c8 100644 --- a/src/Collapse/doc/intro_edge_collapse.h +++ b/src/Collapse/doc/intro_edge_collapse.h @@ -17,68 +17,48 @@ namespace collapse { /** \defgroup edge_collapse Edge collapse * - * \author Siddharth Pritam + * \author Siddharth Pritam and Marc Glisse * * @{ * - * 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. + * This module implements edge collapse of a filtered flag complex as described in \cite edgecollapsearxiv, in + * particular it reduces a filtration of Vietoris-Rips complex represented by a graph to a smaller flag filtration with + * the same persistent homology. * * \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 \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: + * 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$ + * \e dominates \f$e\f$ and \f$e\f$ is \e dominated by \f$v^{\prime}\f$. + * An <b> elementary edge collapse </b> is the removal of a dominated edge \f$e\f$ from \f$K\f$ (the cofaces of \f$e\f$ + * are implicitly removed as well). + * Domination is used as a simple sufficient condition that ensures that this removal is a homotopy preserving + * operation. + * + * 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 \f$e\f$ also contain \f$v^{\prime}\f$ + * -- For a 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 \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$, <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$. + * -- 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 have an edge with both vertices of \f$e\f$ also have an edge with + * \f$v^{\prime}\f$. Notice that this only depends on the graph. * - * 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 + * In the context of a filtration, an edge collapse may translate into an increase of the filtration value of an edge, + * or its removal if it already had the largest filtration value. + * The algorithm to compute the smaller induced filtration is described in \cite edgecollapsearxiv. + * Edge collapse can be successfully employed to reduce any input 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 \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. - * + * The algorithm implemented here does not produce a minimal filtration. Taking its output and applying the algorithm a + * second time may further simplify the filtration. + * * \subsection edgecollapseexample Basic edge collapse * * This example calls `Gudhi::collapse::flag_complex_collapse_edges()` from a proximity graph represented as a list of * `Filtered_edge`. - * Then it collapses edges and displays a new list of `Filtered_edge` (with less edges) + * Then it collapses edges and displays a new list of `Filtered_edge` (with fewer edges) * that will preserve the persistence homology computation. * * \include edge_collapse_basic_example.cpp @@ -88,7 +68,7 @@ namespace collapse { * \code $> ./Edge_collapse_example_basic * \endcode * - * the program output is: + * the program output could be: * * \include edge_collapse_example_basic.txt */ diff --git a/src/Collapse/example/edge_collapse_conserve_persistence.cpp b/src/Collapse/example/edge_collapse_conserve_persistence.cpp index b2c55e7a..19960597 100644 --- a/src/Collapse/example/edge_collapse_conserve_persistence.cpp +++ b/src/Collapse/example/edge_collapse_conserve_persistence.cpp @@ -103,7 +103,7 @@ int main(int argc, char* argv[]) { Gudhi::Euclidean_distance()); if (num_edges(proximity_graph) <= 0) { - std::cerr << "Total number of egdes are zero." << std::endl; + std::cerr << "Total number of edges is zero." << std::endl; exit(-1); } diff --git a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h index 713c6608..d0b3fe4a 100644 --- a/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h +++ b/src/Collapse/include/gudhi/Flag_complex_edge_collapser.h @@ -1,11 +1,12 @@ /* 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 + * Author(s): Siddharth Pritam, Marc Glisse * * Copyright (C) 2020 Inria * * Modification(s): * - 2020/03 Vincent Rouvreau: integration to the gudhi library + * - 2021 Marc Glisse: complete rewrite * - YYYY/MM Author: Description of the modification */ @@ -14,367 +15,319 @@ #include <gudhi/Debug_utils.h> -#include <boost/functional/hash.hpp> -#include <boost/iterator/iterator_facade.hpp> - -#include <Eigen/Sparse> -#include <Eigen/src/Core/util/Macros.h> // for EIGEN_VERSION_AT_LEAST +#include <boost/container/flat_map.hpp> +#include <boost/container/flat_set.hpp> #ifdef GUDHI_USE_TBB #include <tbb/parallel_sort.h> #endif -#include <iostream> -#include <utility> // for std::pair +#include <utility> #include <vector> -#include <unordered_map> -#include <unordered_set> -#include <set> -#include <tuple> // for std::tie -#include <algorithm> // for std::includes -#include <iterator> // for std::inserter -#include <type_traits> // for std::decay - -// Make compilation fail - required for external projects - https://github.com/GUDHI/gudhi-devel/issues/10 -#if !EIGEN_VERSION_AT_LEAST(3,1,0) -# error Edge Collapse is only available for Eigen3 >= 3.1.0 -#endif +#include <tuple> +#include <algorithm> +#include <limits> namespace Gudhi { namespace collapse { /** \private - * - * \brief Flag complex sparse matrix data structure. * - * \details - * This class stores a <a target="_blank" href="https://en.wikipedia.org/wiki/Clique_complex">Flag complex</a> - * in an <a target="_blank" href="https://eigen.tuxfamily.org/dox/group__TutorialSparse.html">Eigen sparse matrix</a>. + * \brief Flag complex sparse matrix data structure. * - * \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 <. + * \tparam Vertex type must be an integer type. + * \tparam Filtration type for the value of the filtration function. */ -template<typename Vertex, typename Filtration> -class Flag_complex_edge_collapser { - public: - /** \brief Re-define Vertex as Vertex_handle type to ease the interface with `Gudhi::Proximity_graph`. */ - using Vertex_handle = Vertex; - /** \brief Re-define Filtration as Filtration_value type to ease the interface with `Gudhi::Proximity_graph`. */ - using Filtration_value = Filtration; - - private: - // internal numbering of vertices and edges - using IVertex = std::size_t; - using Edge_index = std::size_t; - using IEdge = std::pair<IVertex, IVertex>; - - // The sparse matrix data type - // (Eigen::SparseMatrix<Edge_index, Eigen::RowMajor> has slow insertions) - using Sparse_vector = Eigen::SparseVector<Edge_index>; - using Sparse_row_matrix = std::vector<Sparse_vector>; - - // Range of neighbors of a vertex - template<bool closed> - struct Neighbours { - class iterator : public boost::iterator_facade<iterator, - IVertex, /* value_type */ - std::input_iterator_tag, // or boost::single_pass_traversal_tag - IVertex /* reference */ > - { - public: - iterator():ptr(nullptr){} - iterator(Neighbours const*p):ptr(p){find_valid();} - private: - friend class boost::iterator_core_access; - Neighbours const*ptr; - void increment(){ - ++ptr->it; - find_valid(); - } - void find_valid(){ - auto& it = ptr->it; - do { - if(!it) { ptr=nullptr; break; } - if(IVertex(it.index()) == ptr->u) { - if(closed) break; - else continue; - } - Edge_index e = it.value(); - if(e <= ptr->ec->current_backward || ptr->ec->critical_edge_indicator_[e]) break; - } while(++it, true); - } - bool equal(iterator const& other) const { return ptr == other.ptr; } - IVertex dereference() const { return ptr->it.index(); } - }; - typedef iterator const_iterator; - mutable typename Sparse_vector::InnerIterator it; - Flag_complex_edge_collapser const*ec; - IVertex u; - iterator begin() const { return this; } - iterator end() const { return {}; } - explicit Neighbours(Flag_complex_edge_collapser const*p,IVertex u):it(p->sparse_row_adjacency_matrix_[u]),ec(p),u(u){} - }; - - // A range of row indices - using IVertex_vector = std::vector<IVertex>; - - public: - /** \brief Filtered_edge is a type to store an edge with its filtration value. */ - using Filtered_edge = std::tuple<Vertex_handle, Vertex_handle, Filtration_value>; - - private: - // Map from row index to its vertex handle - std::vector<Vertex_handle> row_to_vertex_; - - // Index of the current edge in the backwards walk. Edges <= current_backward are part of the temporary graph, - // while edges > current_backward are removed unless critical_edge_indicator_. - Edge_index current_backward = -1; - - // Map from IEdge to its index - std::unordered_map<IEdge, Edge_index, boost::hash<IEdge>> iedge_to_index_map_; - - // Boolean vector to indicate if the edge is critical. - std::vector<bool> critical_edge_indicator_; - - // Map from vertex handle to its row index - std::unordered_map<Vertex_handle, IVertex> vertex_to_row_; - - // Stores the Sparse matrix of Filtration values representing the original graph. - // The matrix rows and columns are indexed by IVertex. - Sparse_row_matrix sparse_row_adjacency_matrix_; - - // The input, a vector of filtered edges. - std::vector<Filtered_edge> f_edge_vector_; - - // Edge is the actual edge (u,v), with Vertex_handle u and v, not IVertex. - bool edge_is_dominated(Vertex_handle u, Vertex_handle v) const - { - const IVertex rw_u = vertex_to_row_.at(u); - const IVertex rw_v = vertex_to_row_.at(v); -#ifdef DEBUG_TRACES - std::cout << "The edge {" << u << ", " << v << "} is going for domination check." << std::endl; -#endif // DEBUG_TRACES - auto common_neighbours = open_common_neighbours_row_index(rw_u, rw_v); -#ifdef DEBUG_TRACES - std::cout << "And its common neighbours are." << std::endl; - for (auto neighbour : common_neighbours) { - std::cout << row_to_vertex_[neighbour] << ", " ; - } - std::cout<< std::endl; -#endif // DEBUG_TRACES - if (common_neighbours.size() == 1) - return true; - else - for (auto rw_c : common_neighbours) { - auto neighbours_c = neighbours_row_index<true>(rw_c); - // If neighbours_c contains the common neighbours. - if (std::includes(neighbours_c.begin(), neighbours_c.end(), - common_neighbours.begin(), common_neighbours.end())) - return true; - } - return false; +template<typename Vertex, typename Filtration_value> +struct Flag_complex_edge_collapser { + using Filtered_edge = std::tuple<Vertex, Vertex, Filtration_value>; + typedef std::pair<Vertex,Vertex> Edge; + struct Cmpi { template<class T, class U> bool operator()(T const&a, U const&b)const{return b<a; } }; + typedef boost::container::flat_map<Vertex, Filtration_value> Ngb_list; + typedef std::vector<Ngb_list> Neighbors; + Neighbors neighbors; // closed neighborhood + std::size_t num_vertices; + std::vector<std::tuple<Vertex, Vertex, Filtration_value>> res; + +#ifdef GUDHI_COLLAPSE_USE_DENSE_ARRAY + // Minimal matrix interface + // Using this matrix generally helps performance, but the memory use may be excessive for a very sparse graph + // (and in extreme cases the constant initialization of the matrix may start to dominate the running time). + // Are there cases where the matrix is too big but a hash table would help? + std::vector<Filtration_value> neighbors_data; + void init_neighbors_dense(){ + neighbors_data.clear(); + neighbors_data.resize(num_vertices*num_vertices, std::numeric_limits<Filtration_value>::infinity()); } + Filtration_value& neighbors_dense(Vertex i, Vertex j){return neighbors_data[num_vertices*j+i];} +#endif - // Returns the edges connecting u and v (extremities of crit) to their common neighbors (not themselves) - std::set<Edge_index> three_clique_indices(Edge_index crit) { - std::set<Edge_index> edge_indices; - - Vertex_handle u = std::get<0>(f_edge_vector_[crit]); - Vertex_handle v = std::get<1>(f_edge_vector_[crit]); - -#ifdef DEBUG_TRACES - std::cout << "The current critical edge to re-check criticality with filt value is : f {" << u << "," << v - << "} = " << std::get<2>(f_edge_vector_[crit]) << std::endl; -#endif // DEBUG_TRACES - auto rw_u = vertex_to_row_[u]; - auto rw_v = vertex_to_row_[v]; - - IVertex_vector common_neighbours = open_common_neighbours_row_index(rw_u, rw_v); + // This does not touch the events list, only the adjacency matrix(es) + void delay_neighbor(Vertex u, Vertex v, Filtration_value f) { + neighbors[u][v]=f; + neighbors[v][u]=f; +#ifdef GUDHI_COLLAPSE_USE_DENSE_ARRAY + neighbors_dense(u,v)=f; + neighbors_dense(v,u)=f; +#endif + } + void remove_neighbor(Vertex u, Vertex v) { + neighbors[u].erase(v); + neighbors[v].erase(u); +#ifdef GUDHI_COLLAPSE_USE_DENSE_ARRAY + neighbors_dense(u,v)=std::numeric_limits<Filtration_value>::infinity(); + neighbors_dense(v,u)=std::numeric_limits<Filtration_value>::infinity(); +#endif + } - for (auto rw_c : common_neighbours) { - IEdge e_with_new_nbhr_v = std::minmax(rw_u, rw_c); - IEdge e_with_new_nbhr_u = std::minmax(rw_v, rw_c); - edge_indices.emplace(iedge_to_index_map_[e_with_new_nbhr_v]); - edge_indices.emplace(iedge_to_index_map_[e_with_new_nbhr_u]); + template<class FilteredEdgeRange> + void read_edges(FilteredEdgeRange const&r){ + neighbors.resize(num_vertices); +#ifdef GUDHI_COLLAPSE_USE_DENSE_ARRAY + init_neighbors_dense(); +#endif + // Use the raw sequence to avoid maintaining the order + std::vector<typename Ngb_list::sequence_type> neighbors_seq(num_vertices); + for(auto&&e : r){ + using std::get; + Vertex u = get<0>(e); + Vertex v = get<1>(e); + Filtration_value f = get<2>(e); + neighbors_seq[u].emplace_back(v, f); + neighbors_seq[v].emplace_back(u, f); +#ifdef GUDHI_COLLAPSE_USE_DENSE_ARRAY + neighbors_dense(u,v)=f; + neighbors_dense(v,u)=f; +#endif + } + for(std::size_t i=0;i<neighbors_seq.size();++i){ + neighbors_seq[i].emplace_back(i, -std::numeric_limits<Filtration_value>::infinity()); + neighbors[i].adopt_sequence(std::move(neighbors_seq[i])); // calls sort +#ifdef GUDHI_COLLAPSE_USE_DENSE_ARRAY + neighbors_dense(i,i)=-std::numeric_limits<Filtration_value>::infinity(); +#endif } - return edge_indices; } - // Detect and set all edges that are becoming critical - template<typename FilteredEdgeOutput> - void set_edge_critical(Edge_index indx, Filtration_value filt, FilteredEdgeOutput filtered_edge_output) { -#ifdef DEBUG_TRACES - std::cout << "The curent index with filtration value " << indx << ", " << filt << " is primary critical" << - std::endl; -#endif // DEBUG_TRACES - std::set<Edge_index> effected_indices = three_clique_indices(indx); - // Cannot use boost::adaptors::reverse in such dynamic cases apparently - for (auto it = effected_indices.rbegin(); it != effected_indices.rend(); ++it) { - current_backward = *it; - Vertex_handle u = std::get<0>(f_edge_vector_[current_backward]); - Vertex_handle v = std::get<1>(f_edge_vector_[current_backward]); - // If current_backward is not critical so it should be processed, otherwise it stays in the graph - if (!critical_edge_indicator_[current_backward]) { - if (!edge_is_dominated(u, v)) { -#ifdef DEBUG_TRACES - std::cout << "The curent index became critical " << current_backward << std::endl; -#endif // DEBUG_TRACES - critical_edge_indicator_[current_backward] = true; - filtered_edge_output(u, v, filt); - std::set<Edge_index> inner_effected_indcs = three_clique_indices(current_backward); - for (auto inr_idx : inner_effected_indcs) { - if(inr_idx < current_backward) // && !critical_edge_indicator_[inr_idx] - effected_indices.emplace(inr_idx); - } -#ifdef DEBUG_TRACES - std::cout << "The following edge is critical with filt value: {" << u << "," << v << "}; " - << filt << std::endl; -#endif // DEBUG_TRACES - } + // Open neighborhood + // At some point it helped gcc to add __attribute__((noinline)) here, otherwise we had +50% on the running time + // on one example. It looks ok now, or I forgot which example that was. + void common_neighbors(boost::container::flat_set<Vertex>& e_ngb, + std::vector<std::pair<Filtration_value, Vertex>>& e_ngb_later, + Vertex u, Vertex v, Filtration_value f_event){ + // Using neighbors_dense here seems to hurt, even if we loop on the smaller of nu and nv. + Ngb_list const&nu = neighbors[u]; + Ngb_list const&nv = neighbors[v]; + auto ui = nu.begin(); + auto ue = nu.end(); + auto vi = nv.begin(); + auto ve = nv.end(); + assert(ui != ue && vi != ve); + while(ui != ue && vi != ve){ + Vertex w = ui->first; + if(w < vi->first) { ++ui; continue; } + if(w > vi->first) { ++vi; continue; } + // nu and nv are closed, so we need to exclude e here. + if(w != u && w != v) { + Filtration_value f = std::max(ui->second, vi->second); + if(f > f_event) + e_ngb_later.emplace_back(f, w); + else + e_ngb.insert(e_ngb.end(), w); } + ++ui; ++vi; } - // Clear the implicit "removed from graph" data structure - current_backward = -1; } - // Returns list of neighbors of a particular vertex. - template<bool closed> - auto neighbours_row_index(IVertex rw_u) const - { - return Neighbours<closed>(this, rw_u); + // Test if the neighborhood of e is included in the closed neighborhood of c + template<class Ngb> + bool is_dominated_by(Ngb const& e_ngb, Vertex c, Filtration_value f){ + // The best strategy probably depends on the distribution, how sparse / dense the adjacency matrix is, + // how (un)balanced the sizes of e_ngb and nc are. + // Some efficient operations on sets work best with bitsets, although the need for a map complicates things. +#ifdef GUDHI_COLLAPSE_USE_DENSE_ARRAY + for(auto v : e_ngb) { + // if(v==c)continue; + if(neighbors_dense(v,c) > f) return false; + } + return true; +#else + auto&&nc = neighbors[c]; + // if few neighbors, use dichotomy? Seems slower. + // I tried storing a copy of neighbors as a vector<absl::flat_hash_map> and using it for nc, but it was + // a bit slower here. It did help with neighbors[dominator].find(w) in the main function though, + // sometimes enough, sometimes not. + auto ci = nc.begin(); + auto ce = nc.end(); + auto eni = e_ngb.begin(); + auto ene = e_ngb.end(); + assert(eni != ene); + assert(ci != ce); + // if(*eni == c && ++eni == ene) return true; + for(;;){ + Vertex ve = *eni; + Vertex vc = ci->first; + while(ve > vc) { + // try a gallop strategy (exponential search)? Seems slower + if(++ci == ce) return false; + vc = ci->first; + } + if(ve < vc) return false; + // ve == vc + if(ci->second > f) return false; + if(++eni == ene)return true; + // If we stored an open neighborhood of c (excluding c), we would need to test for c here and before the loop + // if(*eni == c && ++eni == ene)return true; + if(++ci == ce) return false; + } +#endif } - // Returns the list of open neighbours of the edge :{u,v}. - IVertex_vector open_common_neighbours_row_index(IVertex rw_u, IVertex rw_v) const - { - auto non_zero_indices_u = neighbours_row_index<false>(rw_u); - auto non_zero_indices_v = neighbours_row_index<false>(rw_v); - IVertex_vector common; - std::set_intersection(non_zero_indices_u.begin(), non_zero_indices_u.end(), non_zero_indices_v.begin(), - non_zero_indices_v.end(), std::back_inserter(common)); - - return common; - } + template<class FilteredEdgeRange, class Delay> + void process_edges(FilteredEdgeRange const& edges, Delay&& delay) { + { + Vertex maxi = 0, maxj = 0; + for(auto& fe : edges) { + Vertex i = std::get<0>(fe); + Vertex j = std::get<1>(fe); + if (i > maxi) maxi = i; + if (j > maxj) maxj = j; + } + num_vertices = std::max(maxi, maxj) + 1; + } - // Insert a vertex in the data structure - IVertex insert_vertex(Vertex_handle vertex) { - auto n = row_to_vertex_.size(); - auto result = vertex_to_row_.emplace(vertex, n); - // If it was not already inserted - Value won't be updated by emplace if it is already present - if (result.second) { - // Expand the matrix. The size of rows is irrelevant. - sparse_row_adjacency_matrix_.emplace_back((std::numeric_limits<Eigen::Index>::max)()); - // Initializing the diagonal element of the adjency matrix corresponding to rw_b. - sparse_row_adjacency_matrix_[n].insert(n) = -1; // not an edge - // Must be done after reading its size() - row_to_vertex_.push_back(vertex); + read_edges(edges); + + boost::container::flat_set<Vertex> e_ngb; + e_ngb.reserve(num_vertices); + std::vector<std::pair<Filtration_value, Vertex>> e_ngb_later; + for(auto&e:edges) { + { + Vertex u = std::get<0>(e); + Vertex v = std::get<1>(e); + Filtration_value input_time = std::get<2>(e); + auto time = delay(input_time); + auto start_time = time; + e_ngb.clear(); + e_ngb_later.clear(); + common_neighbors(e_ngb, e_ngb_later, u, v, time); + // If we identify a good candidate (the first common neighbor) for being a dominator of e until infinity, + // we could check that a bit more cheaply. It does not seem to help though. + auto cmp1=[](auto const&a, auto const&b){return a.first > b.first;}; + auto e_ngb_later_begin=e_ngb_later.begin(); + auto e_ngb_later_end=e_ngb_later.end(); + bool heapified = false; + + bool dead = false; + while(true) { + Vertex dominator = -1; + // special case for size 1 + // if(e_ngb.size()==1){dominator=*e_ngb.begin();}else + // It is tempting to test the dominators in increasing order of filtration value, which is likely to reduce + // the number of calls to is_dominated_by before finding a dominator, but sorting, even partially / lazily, + // is very expensive. + for(auto c : e_ngb){ + if(is_dominated_by(e_ngb, c, time)){ + dominator = c; + break; + } + } + if(dominator==-1) break; + // Push as long as dominator remains a dominator. + // Iterate on times where at least one neighbor appears. + for (bool still_dominated = true; still_dominated; ) { + if(e_ngb_later_begin == e_ngb_later_end) { + dead = true; goto end_move; + } + if(!heapified) { + // Eagerly sorting can be slow + std::make_heap(e_ngb_later_begin, e_ngb_later_end, cmp1); + heapified=true; + } + time = e_ngb_later_begin->first; // first place it may become critical + // Update the neighborhood for this new time, while checking if any of the new neighbors break domination. + while (e_ngb_later_begin != e_ngb_later_end && e_ngb_later_begin->first <= time) { + Vertex w = e_ngb_later_begin->second; +#ifdef GUDHI_COLLAPSE_USE_DENSE_ARRAY + if (neighbors_dense(dominator,w) > e_ngb_later_begin->first) + still_dominated = false; +#else + auto& ngb_dom = neighbors[dominator]; + auto wit = ngb_dom.find(w); // neighborhood may be open or closed, it does not matter + if (wit == ngb_dom.end() || wit->second > e_ngb_later_begin->first) + still_dominated = false; +#endif + e_ngb.insert(w); + std::pop_heap(e_ngb_later_begin, e_ngb_later_end--, cmp1); + } + } // this doesn't seem to help that much... + } +end_move: + if(dead) { + remove_neighbor(u, v); + } else if(start_time != time) { + delay_neighbor(u, v, time); + res.emplace_back(u, v, time); + } else { + res.emplace_back(u, v, input_time); + } + } } - return result.first->second; } - // Insert an edge in the data structure - // @exception std::invalid_argument In debug mode, if u == v - IEdge insert_new_edge(Vertex_handle u, Vertex_handle v, Edge_index idx) - { - GUDHI_CHECK((u != v), std::invalid_argument("Flag_complex_edge_collapser::insert_new_edge with u == v")); - // The edge must not be added before, it should be a new edge. - IVertex rw_u = insert_vertex(u); - IVertex rw_v = insert_vertex(v); -#ifdef DEBUG_TRACES - std::cout << "Inserting the edge " << u <<", " << v << std::endl; -#endif // DEBUG_TRACES - sparse_row_adjacency_matrix_[rw_u].insert(rw_v) = idx; - sparse_row_adjacency_matrix_[rw_v].insert(rw_u) = idx; - return std::minmax(rw_u, rw_v); + std::vector<Filtered_edge> output() { + return std::move(res); } - public: - /** \brief Flag_complex_edge_collapser constructor from a range of filtered edges. - * - * @param[in] edges Range of Filtered edges range.There is no need the range to be sorted, as it will be performed in - * `Flag_complex_edge_collapser::process_edges`. - * - * \tparam FilteredEdgeRange must be a range for which std::begin and std::end return iterators on a - * `Flag_complex_edge_collapser::Filtered_edge`. - */ - template<typename FilteredEdgeRange> - Flag_complex_edge_collapser(const FilteredEdgeRange& edges) - : f_edge_vector_(std::begin(edges), std::end(edges)) { } +}; - /** \brief Performs edge collapse in a increasing sequence of the filtration value. - * - * \tparam filtered_edge_output is a functor that is called on the output edges, in non-decreasing order of - * filtration, as filtered_edge_output(u, v, f) where u and v are Vertex_handle representing the extremities of the - * edge, and f is its new Filtration_value. - */ - template<typename FilteredEdgeOutput> - void process_edges(FilteredEdgeOutput filtered_edge_output) { - // Sort edges - auto sort_by_filtration = [](const Filtered_edge& edge_a, const Filtered_edge& edge_b) -> bool - { - return (std::get<2>(edge_a) < std::get<2>(edge_b)); - }; +template<class R> R to_range(R&& r) { return std::move(r); } +template<class R, class T> R to_range(T&& t) { R r; r.insert(r.end(), t.begin(), t.end()); return r; } +template<class FilteredEdgeRange, class Delay> +auto flag_complex_collapse_edges(FilteredEdgeRange&& edges, Delay&&delay) { + // Would it help to label the points according to some spatial sorting? + auto first_edge_itr = std::begin(edges); + using Vertex = std::decay_t<decltype(std::get<0>(*first_edge_itr))>; + using Filtration_value = std::decay_t<decltype(std::get<2>(*first_edge_itr))>; + using Edge_collapser = Flag_complex_edge_collapser<Vertex, Filtration_value>; + if (first_edge_itr != std::end(edges)) { + auto edges2 = to_range<std::vector<typename Edge_collapser::Filtered_edge>>(std::forward<FilteredEdgeRange>(edges)); #ifdef GUDHI_USE_TBB - tbb::parallel_sort(f_edge_vector_.begin(), f_edge_vector_.end(), sort_by_filtration); + // I think this sorting is always negligible compared to the collapse, but parallelizing it shouldn't hurt. + tbb::parallel_sort(edges2.begin(), edges2.end(), + [](auto const&a, auto const&b){return std::get<2>(a)>std::get<2>(b);}); #else - std::sort(f_edge_vector_.begin(), f_edge_vector_.end(), sort_by_filtration); + std::sort(edges2.begin(), edges2.end(), [](auto const&a, auto const&b){return std::get<2>(a)>std::get<2>(b);}); #endif - - for (Edge_index endIdx = 0; endIdx < f_edge_vector_.size(); endIdx++) { - Filtered_edge fec = f_edge_vector_[endIdx]; - Vertex_handle u = std::get<0>(fec); - Vertex_handle v = std::get<1>(fec); - Filtration_value filt = std::get<2>(fec); - - // Inserts the edge in the sparse matrix to update the graph (G_i) - IEdge ie = insert_new_edge(u, v, endIdx); - - iedge_to_index_map_.emplace(ie, endIdx); - critical_edge_indicator_.push_back(false); - - if (!edge_is_dominated(u, v)) { - critical_edge_indicator_[endIdx] = true; - filtered_edge_output(u, v, filt); - if (endIdx > 1) - set_edge_critical(endIdx, filt, filtered_edge_output); - } - } + Edge_collapser edge_collapser; + edge_collapser.process_edges(edges2, std::forward<Delay>(delay)); + return edge_collapser.output(); } - -}; + return std::vector<typename Edge_collapser::Filtered_edge>(); +} /** \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. + * homology and returns the remaining edges as a range. The filtration value of vertices is irrelevant to this function. * - * \param[in] edges Range of Filtered edges.There is no need the range to be sorted, as it will be performed. + * \param[in] edges Range of Filtered edges. There is no need for the range to be sorted, as it will be done internally. * - * \tparam FilteredEdgeRange furnishes `std::begin` and `std::end` methods and returns an iterator on a - * FilteredEdge of type `std::tuple<Vertex_handle, Vertex_handle, Filtration_value>` where `Vertex_handle` is the type - * of a vertex index and `Filtration_value` is the type of an edge filtration value. + * \tparam FilteredEdgeRange Range of `std::tuple<Vertex_handle, Vertex_handle, Filtration_value>` + * where `Vertex_handle` is the type of a vertex index. * * \return Remaining edges after collapse as a range of * `std::tuple<Vertex_handle, Vertex_handle, Filtration_value>`. - * + * * \ingroup edge_collapse - * + * + * \note + * Advanced: Defining the macro GUDHI_COLLAPSE_USE_DENSE_ARRAY tells gudhi to allocate a square table of size the + * maximum vertex index. This usually speeds up the computation for dense graphs. However, for sparse graphs, the memory + * use may be problematic and initializing this large table may be slow. */ template<class FilteredEdgeRange> auto flag_complex_collapse_edges(const FilteredEdgeRange& edges) { - auto first_edge_itr = std::begin(edges); - using Vertex_handle = std::decay_t<decltype(std::get<0>(*first_edge_itr))>; - using Filtration_value = std::decay_t<decltype(std::get<2>(*first_edge_itr))>; - using Edge_collapser = Flag_complex_edge_collapser<Vertex_handle, Filtration_value>; - std::vector<typename Edge_collapser::Filtered_edge> remaining_edges; - if (first_edge_itr != std::end(edges)) { - Edge_collapser edge_collapser(edges); - 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); - }); - } - return remaining_edges; + return flag_complex_collapse_edges(edges, [](auto const&d){return d;}); } } // namespace collapse diff --git a/src/Collapse/test/collapse_unit_test.cpp b/src/Collapse/test/collapse_unit_test.cpp index b8876246..f41dbedd 100644 --- a/src/Collapse/test/collapse_unit_test.cpp +++ b/src/Collapse/test/collapse_unit_test.cpp @@ -98,8 +98,8 @@ BOOST_AUTO_TEST_CASE(collapse) { // o---o // 0 3 edges.emplace_back(0, 2, 2.); - edges.emplace_back(1, 3, 2.); - trace_and_check_collapse(edges, {{1, 3, 2.}}); + edges.emplace_back(1, 3, 2.1); + trace_and_check_collapse(edges, {{1, 3, 2.1}}); // 1 2 4 // o---o---o @@ -121,8 +121,8 @@ BOOST_AUTO_TEST_CASE(collapse) { // o---o---o // 0 3 5 edges.emplace_back(2, 5, 4.); - edges.emplace_back(4, 3, 4.); - trace_and_check_collapse(edges, {{1, 3, 2.}, {4, 3, 4.}}); + edges.emplace_back(4, 3, 4.1); + trace_and_check_collapse(edges, {{1, 3, 2.}, {4, 3, 4.1}}); // 1 2 4 // o---o---o @@ -132,8 +132,8 @@ BOOST_AUTO_TEST_CASE(collapse) { // o---o---o // 0 3 5 edges.emplace_back(1, 5, 5.); - edges.emplace_back(0, 4, 5.); - trace_and_check_collapse(edges, {{1, 3, 2.}, {4, 3, 4.}, {0, 4, 5.}}); + edges.emplace_back(0, 4, 5.1); + trace_and_check_collapse(edges, {{1, 3, 2.}, {4, 3, 4.}, {0, 4, 5.1}}); } BOOST_AUTO_TEST_CASE(collapse_from_array) { @@ -150,8 +150,8 @@ BOOST_AUTO_TEST_CASE(collapse_from_array) { {2, 3, 1.}, {3, 0, 1.}, {0, 2, 2.}, - {1, 3, 2.}}}; - trace_and_check_collapse(f_edge_array, {{1, 3, 2.}}); + {1, 3, 2.1}}}; + trace_and_check_collapse(f_edge_array, {{1, 3, 2.1}}); } BOOST_AUTO_TEST_CASE(collapse_from_proximity_graph) { 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 11ee5871..38efb9e6 100644 --- a/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/distance_matrix_edge_collapse_rips_persistence.cpp @@ -45,7 +45,7 @@ int main(int argc, char* argv[]) { min_persistence); Distance_matrix distances = Gudhi::read_lower_triangular_matrix_from_csv_file<Filtration_value>(csv_matrix_file); - std::cout << "Read the distance matrix succesfully, of size: " << distances.size() << std::endl; + std::cout << "Read the distance matrix successfully, of size: " << distances.size() << std::endl; Proximity_graph proximity_graph = Gudhi::compute_proximity_graph<Simplex_tree>(boost::irange((size_t)0, distances.size()), 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 0eea742c..d8f42ab6 100644 --- a/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp +++ b/src/Collapse/utilities/point_cloud_edge_collapse_rips_persistence.cpp @@ -77,7 +77,7 @@ int main(int argc, char* argv[]) { Gudhi::Euclidean_distance()); if (num_edges(proximity_graph) <= 0) { - std::cerr << "Total number of egdes are zero." << std::endl; + std::cerr << "Total number of edges is zero." << std::endl; exit(-1); } diff --git a/src/Contraction/doc/so3.svg b/src/Contraction/doc/so3.svg index adea3f38..f10cab98 100644 --- a/src/Contraction/doc/so3.svg +++ b/src/Contraction/doc/so3.svg @@ -177,7 +177,7 @@ x="309.4176" y="300.58682" id="tspan4515-4" - style="text-align:center;text-anchor:middle">Rips complex built uppon these points</tspan><tspan + style="text-align:center;text-anchor:middle">Rips complex built upon these points</tspan><tspan sodipodi:role="line" x="309.4176" y="308.96704" diff --git a/src/Contraction/example/Garland_heckbert/Error_quadric.h b/src/Contraction/example/Garland_heckbert/Error_quadric.h index 49250d7a..ae46232c 100644 --- a/src/Contraction/example/Garland_heckbert/Error_quadric.h +++ b/src/Contraction/example/Garland_heckbert/Error_quadric.h @@ -29,7 +29,7 @@ template <typename Point> class Error_quadric { * Quadric corresponding to the L2 distance to the plane. * * According to the notation of Garland Heckbert, they - * denote a quadric symetric matrix as : + * denote a quadric symmetric matrix as : * Q = [ q11 q12 q13 q14] * [ q12 q22 q23 q24] * [ q13 q23 q33 q34] diff --git a/src/Contraction/include/gudhi/Edge_contraction.h b/src/Contraction/include/gudhi/Edge_contraction.h index 6c0f4c78..0b43c3b3 100644 --- a/src/Contraction/include/gudhi/Edge_contraction.h +++ b/src/Contraction/include/gudhi/Edge_contraction.h @@ -26,6 +26,7 @@ namespace contraction { /** \defgroup contr Edge contraction +@{ \author David Salinas @@ -45,7 +46,7 @@ the operations needed for edge contraction algorithms have polynomial complexity Therefore, the simplification can be done without enumerating the set of simplices that is often non tracktable in high-dimension and is then very efficient (sub-linear with regards to the number of simplices in practice). -A typical application of this package is homology group computation. It is illustrated in the next figure where a Rips complex is built uppon a set of high-dimensional points and +A typical application of this package is homology group computation. It is illustrated in the next figure where a Rips complex is built upon a set of high-dimensional points and simplified with edge contractions. It has initially a big number of simplices (around 20 millions) but simplifying it to a much reduced form with only 15 vertices (and 714 simplices) takes only few seconds on a desktop machine (see the example bellow). One can then compute homology group with a simplicial complex having very few simplices instead of running the homology algorithm on the much bigger initial set of @@ -64,7 +65,7 @@ This class design is policy based and heavily inspired from the similar edge col Four policies can be customized in this package: \li Cost_policy: specify how much cost an edge contraction of a given edge. The edge with lowest cost is iteratively picked and contracted if valid. -\li Valid_contraction_policy: specify if a given edge contraction is valid. For instance, this policy can check the link condition which ensures that the homotopy type is preserved afer the edge contraction. +\li Valid_contraction_policy: specify if a given edge contraction is valid. For instance, this policy can check the link condition which ensures that the homotopy type is preserved after the edge contraction. \li Placement_policy: every time an edge is contracted, its points are merge to one point specified by this policy. This may be the middle of the edge of some more sophisticated point such as the minimum of a cost as in \cite Garland. @@ -91,7 +92,7 @@ Despite this package is able to deal with \a arbitrary simplicial complexes (any it is still \a 65% times faster than the CGAL package which is focused on 2-manifold. The main reason is that few blockers appears during the simplification and hence, the algorithm only have to deal with the graph and not higher-dimensional simplices -(in this case triangles). However, we recall that higher-dimensional simplices are \a implicitely +(in this case triangles). However, we recall that higher-dimensional simplices are \a implicitly stored in the \ref skbl data-structure. Hence, one has to store simplices in an external map if some information needs to be associated with them (information that could be a filtration value or an orientation for instance). @@ -152,7 +153,7 @@ void build_rips(ComplexType& complex, double offset){ int main (int argc, char *argv[]) { if (argc!=3){ - std::cerr << "Usage "<<argv[0]<<" ../../data/SO3_10000.off 0.3 to load the file ../../data/SO3_10000.off and contract the Rips complex built with paremeter 0.3.\n"; + std::cerr << "Usage "<<argv[0]<<" ../../data/SO3_10000.off 0.3 to load the file ../../data/SO3_10000.off and contract the Rips complex built with parameter 0.3.\n"; return -1; } @@ -195,7 +196,6 @@ int main (int argc, char *argv[]) return EXIT_SUCCESS; } -} \endcode \verbatim diff --git a/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h b/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h index a0d9f2b2..56b76318 100644 --- a/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h +++ b/src/Contraction/include/gudhi/Skeleton_blocker_contractor.h @@ -280,7 +280,7 @@ typename GeometricSimplifiableComplex::Vertex_handle> { std::size_t id = 0; - // xxx do a parralel for + // xxx do a parallel for for (auto edge : complex_.edge_range()) { complex_[edge].index() = id++; Profile const& profile = create_profile(edge); @@ -474,7 +474,7 @@ typename GeometricSimplifiableComplex::Vertex_handle> { } void update_changed_edges() { - // xxx do a parralel for + // xxx do a parallel for DBG("update edges"); // sequential loop @@ -530,7 +530,7 @@ typename GeometricSimplifiableComplex::Vertex_handle> { // by definition of a blocker // todo uniqument utile pour la link condition - // laisser a l'utilisateur ? booleen update_heap_on_removed_blocker? + // laisser a l'utilisateur ? boolean update_heap_on_removed_blocker? Simplex blocker_copy(*blocker); for (auto x = blocker_copy.begin(); x != blocker_copy.end(); ++x) { for (auto y = x; ++y != blocker_copy.end();) { diff --git a/src/Coxeter_triangulation/include/gudhi/Coxeter_triangulation/Cell_complex/Hasse_diagram_cell.h b/src/Coxeter_triangulation/include/gudhi/Coxeter_triangulation/Cell_complex/Hasse_diagram_cell.h index 59e9a350..9b57da3c 100644 --- a/src/Coxeter_triangulation/include/gudhi/Coxeter_triangulation/Cell_complex/Hasse_diagram_cell.h +++ b/src/Coxeter_triangulation/include/gudhi/Coxeter_triangulation/Cell_complex/Hasse_diagram_cell.h @@ -95,7 +95,7 @@ class Hasse_diagram_cell { deleted_(false) {} /** - * Construcor of a cell of dimension dim having given additional information. + * Constructor of a cell of dimension dim having given additional information. **/ Hasse_diagram_cell(Additional_information ai, int dim) : dimension(dim), additional_info(ai), position(0), deleted_(false) {} @@ -125,7 +125,7 @@ class Hasse_diagram_cell { inline Additional_information& get_additional_information() { return this->additional_info; } /** - * Procedure to retrive position of the cell in the structure. It is used in + * Procedure to retrieve the position of the cell in the structure. It is used in * the implementation of Hasse diagram and set by it. Note that removal of * cell and subsequent call of clean_up_the_structure will change those * positions. @@ -186,7 +186,7 @@ class Hasse_diagram_cell { friend std::ostream& operator<<( std::ostream& out, const Hasse_diagram_cell<Incidence_type, Filtration_type, Additional_information>& c) { // cout << "position : " << c.position << ", dimension : " << c.dimension << ", filtration: " << c.filtration << ", - // size of boudary : " << c.boundary.size() << "\n"; + // size of boundary : " << c.boundary.size() << "\n"; out << c.position << " " << c.dimension << " " << c.filtration << std::endl; for (std::size_t bd = 0; bd != c.boundary.size(); ++bd) { // do not write out the cells that has been deleted diff --git a/src/Coxeter_triangulation/include/gudhi/Functions/Function_affine_plane_in_Rd.h b/src/Coxeter_triangulation/include/gudhi/Functions/Function_affine_plane_in_Rd.h index b29f0906..dc6f5f90 100644 --- a/src/Coxeter_triangulation/include/gudhi/Functions/Function_affine_plane_in_Rd.h +++ b/src/Coxeter_triangulation/include/gudhi/Functions/Function_affine_plane_in_Rd.h @@ -51,7 +51,7 @@ struct Function_affine_plane_in_Rd { * plane in the d-dimensional Euclidean space. * * @param[in] normal_matrix A normal matrix of the affine plane. The number of rows should - * correspond to the ambient dimension, the number of columns should corespond to + * correspond to the ambient dimension, the number of columns should correspond to * the size of the normal basis (codimension). * @param[in] offset The offset vector of the affine plane. * The dimension of the vector should be the ambient dimension of the manifold. @@ -66,7 +66,7 @@ struct Function_affine_plane_in_Rd { * plane in the d-dimensional Euclidean space that passes through origin. * * @param[in] normal_matrix A normal matrix of the affine plane. The number of rows should - * correspond to the ambient dimension, the number of columns should corespond to + * correspond to the ambient dimension, the number of columns should correspond to * the size of the normal basis (codimension). */ Function_affine_plane_in_Rd(const Eigen::MatrixXd& normal_matrix) diff --git a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Size_range.h b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Size_range.h index c43effc8..6b137744 100644 --- a/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Size_range.h +++ b/src/Coxeter_triangulation/include/gudhi/Permutahedral_representation/Size_range.h @@ -19,7 +19,7 @@ namespace Gudhi { namespace coxeter_triangulation { -/** \brief Auxillary iterator class for sizes of parts in an ordered set partition. +/** \brief Auxiliary iterator class for sizes of parts in an ordered set partition. */ template <class T_it> class Size_iterator diff --git a/src/Doxyfile.in b/src/Doxyfile.in index ae8db1a3..54ec9078 100644 --- a/src/Doxyfile.in +++ b/src/Doxyfile.in @@ -229,13 +229,7 @@ TAB_SIZE = 2 # "Side Effects:". You can put \n's in the value part of an alias to insert # newlines. -ALIASES = - -# This tag can be used to specify a number of word-keyword mappings (TCL only). -# A mapping has the form "name=value". For example adding "class=itcl::class" -# will allow you to use the command class in the itcl::class meaning. - -TCL_SUBST = +ALIASES = gudhi_example_link{2}="@ref \2 \"\1/\2\"" # Set the OPTIMIZE_OUTPUT_FOR_C tag to YES if your project consists of C sources # only. Doxygen will then generate output that is more tailored for C. For @@ -874,7 +868,7 @@ EXCLUDE_SYMBOLS = # that contain example code fragments that are included (see the \include # command). -EXAMPLE_PATH = @CMAKE_SOURCE_DIR@/biblio/ \ +EXAMPLE_PATH = @CMAKE_SOURCE_DIR@ \ @CMAKE_SOURCE_DIR@/data/ \ @GUDHI_DOXYGEN_EXAMPLE_PATH@ @@ -1040,25 +1034,6 @@ USE_HTAGS = NO VERBATIM_HEADERS = YES -# If the CLANG_ASSISTED_PARSING tag is set to YES then doxygen will use the -# clang parser (see: http://clang.llvm.org/) for more accurate parsing at the -# cost of reduced performance. This can be particularly helpful with template -# rich C++ code for which doxygen's built-in parser lacks the necessary type -# information. -# Note: The availability of this option depends on whether or not doxygen was -# generated with the -Duse-libclang=ON option for CMake. -# The default value is: NO. - -CLANG_ASSISTED_PARSING = NO - -# If clang assisted parsing is enabled you can provide the compiler with command -# line options that you would normally use when invoking the compiler. Note that -# the include paths will already be set by doxygen for the files and directories -# specified with INPUT and INCLUDE_PATH. -# This tag requires that the tag CLANG_ASSISTED_PARSING is set to YES. - -CLANG_OPTIONS = - #--------------------------------------------------------------------------- # Configuration options related to the alphabetical class index #--------------------------------------------------------------------------- @@ -1070,13 +1045,6 @@ CLANG_OPTIONS = ALPHABETICAL_INDEX = YES -# The COLS_IN_ALPHA_INDEX tag can be used to specify the number of columns in -# which the alphabetical index list will be split. -# Minimum value: 1, maximum value: 20, default value: 5. -# This tag requires that the tag ALPHABETICAL_INDEX is set to YES. - -COLS_IN_ALPHA_INDEX = 5 - # In case all classes in a project start with a common prefix, all classes will # be put under the same header in the alphabetical index. The IGNORE_PREFIX tag # can be used to specify a prefix (or a list of prefixes) that should be ignored @@ -1505,6 +1473,17 @@ FORMULA_TRANSPARENT = YES USE_MATHJAX = YES +# With MATHJAX_VERSION it is possible to specify the MathJax version to be used. +# Note that the different versions of MathJax have different requirements with +# regards to the different settings, so it is possible that also other MathJax +# settings have to be changed when switching between the different MathJax +# versions. +# Possible values are: MathJax_2 and MathJax_3. +# The default value is: MathJax_2. +# This tag requires that the tag USE_MATHJAX is set to YES. + +@GUDHI_DOXYGEN_MATHJAX_VERSION@ + # When MathJax is enabled you can set the default output format to be used for # the MathJax output. See the MathJax site (see: # http://docs.mathjax.org/en/latest/output.html) for more details. @@ -1526,15 +1505,14 @@ MATHJAX_FORMAT = HTML-CSS # The default value is: http://cdn.mathjax.org/mathjax/latest. # This tag requires that the tag USE_MATHJAX is set to YES. -MATHJAX_RELPATH = https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2 +MATHJAX_RELPATH = # The MATHJAX_EXTENSIONS tag can be used to specify one or more MathJax # extension names that should be enabled during MathJax rendering. For example # MATHJAX_EXTENSIONS = TeX/AMSmath TeX/AMSsymbols # This tag requires that the tag USE_MATHJAX is set to YES. -MATHJAX_EXTENSIONS = TeX/AMSmath \ - TeX/AMSsymbols +MATHJAX_EXTENSIONS = @GUDHI_DOXYGEN_MATHJAX_EXTENSIONS@ # The MATHJAX_CODEFILE tag can be used to specify a file with javascript pieces # of code that will be used on startup of the MathJax code. See the MathJax site @@ -1775,16 +1753,6 @@ LATEX_BATCHMODE = NO LATEX_HIDE_INDICES = NO -# If the LATEX_SOURCE_CODE tag is set to YES then doxygen will include source -# code with syntax highlighting in the LaTeX output. -# -# Note that which sources are shown also depends on other settings such as -# SOURCE_BROWSER. -# The default value is: NO. -# This tag requires that the tag GENERATE_LATEX is set to YES. - -LATEX_SOURCE_CODE = NO - # The LATEX_BIB_STYLE tag can be used to specify the style to use for the # bibliography, e.g. plainnat, or ieeetr. See # http://en.wikipedia.org/wiki/BibTeX and \cite for more info. @@ -1857,16 +1825,6 @@ RTF_STYLESHEET_FILE = RTF_EXTENSIONS_FILE = -# If the RTF_SOURCE_CODE tag is set to YES then doxygen will include source code -# with syntax highlighting in the RTF output. -# -# Note that which sources are shown also depends on other settings such as -# SOURCE_BROWSER. -# The default value is: NO. -# This tag requires that the tag GENERATE_RTF is set to YES. - -RTF_SOURCE_CODE = NO - #--------------------------------------------------------------------------- # Configuration options related to the man page output #--------------------------------------------------------------------------- @@ -1956,15 +1914,6 @@ GENERATE_DOCBOOK = NO DOCBOOK_OUTPUT = docbook -# If the DOCBOOK_PROGRAMLISTING tag is set to YES, doxygen will include the -# program listings (including syntax highlighting and cross-referencing -# information) to the DOCBOOK output. Note that enabling this will significantly -# increase the size of the DOCBOOK output. -# The default value is: NO. -# This tag requires that the tag GENERATE_DOCBOOK is set to YES. - -DOCBOOK_PROGRAMLISTING = NO - #--------------------------------------------------------------------------- # Configuration options for the AutoGen Definitions output #--------------------------------------------------------------------------- @@ -2139,12 +2088,6 @@ EXTERNAL_GROUPS = YES EXTERNAL_PAGES = YES -# The PERL_PATH should be the absolute path and name of the perl script -# interpreter (i.e. the result of 'which perl'). -# The default file (with absolute path) is: /usr/bin/perl. - -PERL_PATH = /usr/bin/perl - #--------------------------------------------------------------------------- # Configuration options related to the dot tool #--------------------------------------------------------------------------- @@ -2158,15 +2101,6 @@ PERL_PATH = /usr/bin/perl CLASS_DIAGRAMS = NO -# You can define message sequence charts within doxygen comments using the \msc -# command. Doxygen will then run the mscgen tool (see: -# http://www.mcternan.me.uk/mscgen/)) to produce the chart and insert it in the -# documentation. The MSCGEN_PATH tag allows you to specify the directory where -# the mscgen tool resides. If left empty the tool is assumed to be found in the -# default search path. - -MSCGEN_PATH = - # You can include diagrams made with dia in doxygen documentation. Doxygen will # then run dia to produce the diagram and insert it in the documentation. The # DIA_PATH tag allows you to specify the directory where the dia binary resides. diff --git a/src/GudhUI/todo.txt b/src/GudhUI/todo.txt index 19d99a77..e59d06d4 100644 --- a/src/GudhUI/todo.txt +++ b/src/GudhUI/todo.txt @@ -18,5 +18,5 @@ x faire le lien MainWindow - Model -- bug -x bug ordre contraction -> just that first vertex placement dont work great +x bug ordre contraction -> just that first vertex placement doesn't work great x pb construction rips diff --git a/src/GudhUI/utils/Critical_points.h b/src/GudhUI/utils/Critical_points.h index 97e58737..65695434 100644 --- a/src/GudhUI/utils/Critical_points.h +++ b/src/GudhUI/utils/Critical_points.h @@ -103,7 +103,7 @@ template<typename SkBlComplex> class Critical_points { // reduced to one point -> contractible return 1; else - // we dont know + // we don't know return 2; } diff --git a/src/GudhUI/utils/Edge_contractor.h b/src/GudhUI/utils/Edge_contractor.h index 0707b186..a71d0742 100644 --- a/src/GudhUI/utils/Edge_contractor.h +++ b/src/GudhUI/utils/Edge_contractor.h @@ -65,7 +65,7 @@ template<typename SkBlComplex> class Edge_contractor { /** * @brief Modify complex to be the expansion of the k-nearest neighbor - * symetric graph. + * symmetric graph. */ Edge_contractor(SkBlComplex& complex, unsigned num_contractions) : complex_(complex), num_contractions_(num_contractions) { diff --git a/src/GudhUI/utils/Furthest_point_epsilon_net.h b/src/GudhUI/utils/Furthest_point_epsilon_net.h index 6eb71071..195d0014 100644 --- a/src/GudhUI/utils/Furthest_point_epsilon_net.h +++ b/src/GudhUI/utils/Furthest_point_epsilon_net.h @@ -27,7 +27,7 @@ template<typename SkBlComplex> class Furthest_point_epsilon_net { /** * Let V be the set of vertices. - * Initially v0 is one arbitrarly vertex and the set V0 is {v0}. + * Initially v0 is one, arbitrary, vertex and the set V0 is {v0}. * Then Vk is computed as follows. * First we compute the vertex pk that is the furthest from Vk * then Vk = Vk \cup pk. @@ -54,7 +54,7 @@ template<typename SkBlComplex> class Furthest_point_epsilon_net { /** * @brief Modify complex to be the expansion of the k-nearest neighbor - * symetric graph. + * symmetric graph. */ Furthest_point_epsilon_net(SkBlComplex& complex) : complex_(complex) { diff --git a/src/GudhUI/utils/K_nearest_builder.h b/src/GudhUI/utils/K_nearest_builder.h index 34483e58..454b2587 100644 --- a/src/GudhUI/utils/K_nearest_builder.h +++ b/src/GudhUI/utils/K_nearest_builder.h @@ -41,7 +41,7 @@ template<typename SkBlComplex> class K_nearest_builder { public: /** * @brief Modify complex to be the expansion of the k-nearest neighbor - * symetric graph. + * symmetric graph. */ K_nearest_builder(SkBlComplex& complex, unsigned k) : complex_(complex) { complex.keep_only_vertices(); diff --git a/src/GudhUI/utils/Lloyd_builder.h b/src/GudhUI/utils/Lloyd_builder.h index c042564f..57e3dc0f 100644 --- a/src/GudhUI/utils/Lloyd_builder.h +++ b/src/GudhUI/utils/Lloyd_builder.h @@ -27,7 +27,7 @@ template<typename SkBlComplex> class Lloyd_builder { /** * @brief Modify complex to be the expansion of the k-nearest neighbor - * symetric graph. + * symmetric graph. */ Lloyd_builder(SkBlComplex& complex, unsigned num_iterations) : complex_(complex), dim(-1) { if (!complex_.empty()) { diff --git a/src/GudhUI/utils/Vertex_collapsor.h b/src/GudhUI/utils/Vertex_collapsor.h index 030e4bb0..b1c48efd 100644 --- a/src/GudhUI/utils/Vertex_collapsor.h +++ b/src/GudhUI/utils/Vertex_collapsor.h @@ -31,7 +31,7 @@ template<typename SkBlComplex> class Vertex_collapsor { /** * @brief Modify complex to be the expansion of the k-nearest neighbor - * symetric graph. + * symmetric graph. */ Vertex_collapsor(SkBlComplex& complex, size_t num_collapses) : complex_(complex), num_collapses_(num_collapses) { diff --git a/src/Nerve_GIC/doc/Intro_graph_induced_complex.h b/src/Nerve_GIC/doc/Intro_graph_induced_complex.h index a6098860..e1ab7cb3 100644 --- a/src/Nerve_GIC/doc/Intro_graph_induced_complex.h +++ b/src/Nerve_GIC/doc/Intro_graph_induced_complex.h @@ -24,7 +24,7 @@ namespace cover_complex { * Visualizations of the simplicial complexes can be done with either * neato (from <a target="_blank" href="http://www.graphviz.org/">graphviz</a>), * <a target="_blank" href="http://www.geomview.org/">geomview</a>, - * <a target="_blank" href="https://github.com/MLWave/kepler-mapper">KeplerMapper</a>. + * <a target="_blank" href="https://github.com/scikit-tda/kepler-mapper">KeplerMapper</a>. * Input point clouds are assumed to be \ref FileFormatsOFF "OFF files" * * \section covers Covers diff --git a/src/Nerve_GIC/utilities/km.py.COPYRIGHT b/src/Nerve_GIC/utilities/km.py.COPYRIGHT index bef7b121..5358d287 100644 --- a/src/Nerve_GIC/utilities/km.py.COPYRIGHT +++ b/src/Nerve_GIC/utilities/km.py.COPYRIGHT @@ -1,7 +1,7 @@ km.py is a fork of https://github.com/MLWave/kepler-mapper. Only the visualization part has been kept (Mapper part has been removed). -This file has te following Copyright : +This file has the following Copyright : The MIT License (MIT) diff --git a/src/Persistence_representations/include/gudhi/Persistence_intervals.h b/src/Persistence_representations/include/gudhi/Persistence_intervals.h index a6c1d6f0..f4324cb2 100644 --- a/src/Persistence_representations/include/gudhi/Persistence_intervals.h +++ b/src/Persistence_representations/include/gudhi/Persistence_intervals.h @@ -109,7 +109,7 @@ class Persistence_intervals { std::vector<size_t> cumulative_histogram_of_lengths(size_t number_of_bins = 10) const; /** - * In this procedure we assume that each barcode is a characteristic function of a hight equal to its length. The + * In this procedure we assume that each barcode is a characteristic function of a height equal to its length. The *persistence diagram is a sum of such a functions. The procedure below construct a function being a * sum of the characteristic functions of persistence intervals. The first two parameters are the range in which the *function is to be computed and the last parameter is the number of bins in @@ -207,7 +207,7 @@ class Persistence_intervals { /** * This is a simple function projecting the persistence intervals to a real number. The function we use here is a sum *of squared lengths of intervals. It can be naturally interpreted as - * sum of step function, where the step hight it equal to the length of the interval. + * sum of step function, where the step height it equal to the length of the interval. * At the moment this function is not tested, since it is quite likely to be changed in the future. Given this, when *using it, keep in mind that it * will be most likely changed in the next versions. diff --git a/src/Persistent_cohomology/benchmark/performance_rips_persistence.cpp b/src/Persistent_cohomology/benchmark/performance_rips_persistence.cpp index 030b072a..3bec8830 100644 --- a/src/Persistent_cohomology/benchmark/performance_rips_persistence.cpp +++ b/src/Persistent_cohomology/benchmark/performance_rips_persistence.cpp @@ -49,7 +49,7 @@ void timing_persistence(FilteredComplex & cpx * with a Hasse diagram. The Hasse diagram represents explicitly all * codimension 1 incidence relations in the complex, and hence leads to * a faster computation of persistence because boundaries are precomputed. - * Hovewer, the simplex tree may be constructed directly from a point cloud and + * However, the simplex tree may be constructed directly from a point cloud and * is more compact. * We compute persistent homology with coefficient fields Z/2Z and Z/1223Z. * We present also timings for the computation of multi-field persistent diff --git a/src/Persistent_cohomology/doc/Intro_persistent_cohomology.h b/src/Persistent_cohomology/doc/Intro_persistent_cohomology.h index a3613d0d..94579564 100644 --- a/src/Persistent_cohomology/doc/Intro_persistent_cohomology.h +++ b/src/Persistent_cohomology/doc/Intro_persistent_cohomology.h @@ -131,8 +131,7 @@ namespace persistent_cohomology { We provide several example files: run these examples with -h for details on their use, and read the README file. -\li <a href="rips_persistence_8cpp-example.html"> -Rips_complex/rips_persistence.cpp</a> computes the Rips complex of a point cloud and outputs its persistence +\li \gudhi_example_link{Rips_complex,rips_persistence.cpp} computes the Rips complex of a point cloud and outputs its persistence diagram. \code $> ./rips_persistence ../../data/points/tore3D_1307.off -r 0.25 -m 0.5 -d 3 -p 3 \endcode \code The complex contains 177838 simplices @@ -144,12 +143,10 @@ diagram. More details on the <a href="../../ripscomplex/">Rips complex utilities</a> dedicated page. -\li <a href="rips_multifield_persistence_8cpp-example.html"> -Persistent_cohomology/rips_multifield_persistence.cpp</a> computes the Rips complex of a point cloud and outputs its +\li \gudhi_example_link{Persistent_cohomology,rips_multifield_persistence.cpp} computes the Rips complex of a point cloud and outputs its persistence diagram with a family of field coefficients. -\li <a href="rips_distance_matrix_persistence_8cpp-example.html"> -Rips_complex/rips_distance_matrix_persistence.cpp</a> computes the Rips complex of a distance matrix and +\li \gudhi_example_link{Rips_complex,rips_distance_matrix_persistence.cpp} computes the Rips complex of a distance matrix and outputs its persistence diagram. The file should contain square or lower triangular distance matrix with semicolons as separators. @@ -158,8 +155,7 @@ Please refer to data/distance_matrix/lower_triangular_distance_matrix.csv for an More details on the <a href="../../ripscomplex/">Rips complex utilities</a> dedicated page. -\li <a href="rips_correlation_matrix_persistence_8cpp-example.html"> -Rips_complex/rips_correlation_matrix_persistence.cpp</a> +\li \gudhi_example_link{Rips_complex,rips_correlation_matrix_persistence.cpp} computes the Rips complex of a correlation matrix and outputs its persistence diagram. Note that no check is performed if the matrix given as the input is a correlation matrix. @@ -169,8 +165,7 @@ Please refer to data/correlation_matrix/lower_triangular_correlation_matrix.csv More details on the <a href="../../ripscomplex/">Rips complex utilities</a> dedicated page. -\li <a href="alpha_complex_3d_persistence_8cpp-example.html"> -Alpha_complex/alpha_complex_3d_persistence.cpp</a> computes the persistent homology with +\li \gudhi_example_link{Alpha_complex,alpha_complex_3d_persistence.cpp} computes the persistent homology with \f$\mathbb{Z}/2\mathbb{Z}\f$ coefficients of the alpha complex on points sampling from an OFF file. \code $> ./alpha_complex_3d_persistence ../../data/points/tore3D_300.off -p 2 -m 0.45 \endcode \code Simplex_tree dim: 3 @@ -235,8 +230,7 @@ Note that the lengths of the sides of the periodic cuboid have to be the same.<b 3 2 36.8838 inf 3 3 58.6783 inf \endcode -\li <a href="alpha_complex_persistence_8cpp-example.html"> -Alpha_complex/alpha_complex_persistence.cpp</a> computes the persistent homology with +\li \gudhi_example_link{Alpha_complex,alpha_complex_persistence.cpp} computes the persistent homology with \f$\mathbb{Z}/p\mathbb{Z}\f$ coefficients of the alpha complex on points sampling from an OFF file. \code $> ./alpha_complex_persistence -r 32 -p 2 -m 0.45 ../../data/points/tore3D_300.off \endcode \code Alpha complex is of dimension 3 - 9273 simplices - 300 vertices. @@ -248,8 +242,7 @@ Simplex_tree dim: 3 More details on the <a href="../../alphacomplex/">Alpha complex utilities</a> dedicated page. -\li <a href="plain_homology_8cpp-example.html"> -Persistent_cohomology/plain_homology.cpp</a> computes the plain homology of a simple simplicial complex without +\li \gudhi_example_link{Persistent_cohomology,plain_homology.cpp} computes the plain homology of a simple simplicial complex without filtration values. */ diff --git a/src/Persistent_cohomology/example/custom_persistence_sort.cpp b/src/Persistent_cohomology/example/custom_persistence_sort.cpp index 410cd987..bba0b2f7 100644 --- a/src/Persistent_cohomology/example/custom_persistence_sort.cpp +++ b/src/Persistent_cohomology/example/custom_persistence_sort.cpp @@ -33,7 +33,7 @@ using Persistent_cohomology = Gudhi::persistent_cohomology::Persistent_cohomolog Gudhi::persistent_cohomology::Field_Zp >; std::vector<Point> random_points() { - // Instanciate a random point generator + // Instantiate a random point generator CGAL::Random rng(0); // Generate "points_number" random points in a vector diff --git a/src/Persistent_cohomology/example/persistence_from_simple_simplex_tree.cpp b/src/Persistent_cohomology/example/persistence_from_simple_simplex_tree.cpp index bffaabdd..3da6771e 100644 --- a/src/Persistent_cohomology/example/persistence_from_simple_simplex_tree.cpp +++ b/src/Persistent_cohomology/example/persistence_from_simple_simplex_tree.cpp @@ -95,7 +95,7 @@ int main(int argc, char * const argv[]) { SimplexVector = {9, 10, 11}; st.insert_simplex_and_subfaces(SimplexVector, 0.3); - // ++ NINETH + // ++ NINTH std::clog << " - INSERT (2,10,12)" << std::endl; SimplexVector = {2, 10, 12}; st.insert_simplex_and_subfaces(SimplexVector, 0.3); diff --git a/src/Persistent_cohomology/example/rips_multifield_persistence.cpp b/src/Persistent_cohomology/example/rips_multifield_persistence.cpp index 2edf5bc4..ca26a5b9 100644 --- a/src/Persistent_cohomology/example/rips_multifield_persistence.cpp +++ b/src/Persistent_cohomology/example/rips_multifield_persistence.cpp @@ -104,7 +104,7 @@ void program_options(int argc, char * argv[] ("min-field-charac,p", po::value<int>(&min_p)->default_value(2), "Minimal characteristic p of the coefficient field Z/pZ.") ("max-field-charac,q", po::value<int>(&max_p)->default_value(1223), - "Minimial characteristic q of the coefficient field Z/pZ.") + "Maximal characteristic q of the coefficient field Z/pZ.") ("min-persistence,m", po::value<Filtration_value>(&min_persistence), "Minimal lifetime of homology feature to be recorded. Default is 0"); diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index d428e497..2301a66b 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -211,7 +211,7 @@ class Persistent_cohomology { /** \brief Update the cohomology groups under the insertion of an edge. * * The 0-homology is maintained with a simple Union-Find data structure, which - * explains the existance of a specific function of edge insertions. */ + * explains the existence of a specific function of edge insertions. */ void update_cohomology_groups_edge(Simplex_handle sigma) { Simplex_handle u, v; boost::tie(u, v) = cpx_->endpoints(sigma); diff --git a/src/Rips_complex/doc/Intro_rips_complex.h b/src/Rips_complex/doc/Intro_rips_complex.h index 3888ec8f..cd77b327 100644 --- a/src/Rips_complex/doc/Intro_rips_complex.h +++ b/src/Rips_complex/doc/Intro_rips_complex.h @@ -63,9 +63,8 @@ namespace rips_complex { * value set with \f$max(filtration(4,5), filtration(4,6), filtration(5,6))\f$. * And so on for simplex (0,1,2,3). * - * If the Rips_complex interfaces are not detailed enough for your need, please refer to - * <a href="rips_persistence_step_by_step_8cpp-example.html"> - * rips_persistence_step_by_step.cpp</a> example, where the constructions of the graph and + * If the Rips_complex interfaces are not detailed enough for your need, please refer to the example + * \gudhi_example_link{Persistent_cohomology,rips_persistence_step_by_step.cpp} , where the constructions of the graph and * the Simplex_tree are more detailed. * * \section sparserips Sparse Rips complex diff --git a/src/Rips_complex/example/example_one_skeleton_rips_from_correlation_matrix.cpp b/src/Rips_complex/example/example_one_skeleton_rips_from_correlation_matrix.cpp index 3d2ba54f..3811d1f1 100644 --- a/src/Rips_complex/example/example_one_skeleton_rips_from_correlation_matrix.cpp +++ b/src/Rips_complex/example/example_one_skeleton_rips_from_correlation_matrix.cpp @@ -40,7 +40,7 @@ int main() { throw "The input matrix is not a correlation matrix. The program will now terminate.\n"; } correlations[i][j] = 1 - correlations[i][j]; - // Here we make sure that we will get the treshold value equal to maximal + // Here we make sure that we will get the threshold value equal to maximal // distance in the matrix. if (correlations[i][j] > threshold) threshold = correlations[i][j]; } diff --git a/src/Simplex_tree/doc/Intro_simplex_tree.h b/src/Simplex_tree/doc/Intro_simplex_tree.h index ef8dec91..2d3ecdec 100644 --- a/src/Simplex_tree/doc/Intro_simplex_tree.h +++ b/src/Simplex_tree/doc/Intro_simplex_tree.h @@ -39,11 +39,9 @@ namespace Gudhi { * \subsubsection filteredcomplexessimplextreeexamples Examples * * Here is a list of simplex tree examples : - * \li <a href="simple_simplex_tree_8cpp-example.html"> - * Simplex_tree/simple_simplex_tree.cpp</a> - Simple simplex tree construction and basic function use. + * \li \gudhi_example_link{Simplex_tree,simple_simplex_tree.cpp} - Simple simplex tree construction and basic function use. * - * \li <a href="simplex_tree_from_cliques_of_graph_8cpp-example.html"> - * Simplex_tree/simplex_tree_from_cliques_of_graph.cpp</a> - Simplex tree construction from cliques of graph read in + * \li \gudhi_example_link{Simplex_tree,simplex_tree_from_cliques_of_graph.cpp} - Simplex tree construction from cliques of graph read in * a file. * * Simplex tree construction with \f$\mathbb{Z}/3\mathbb{Z}\f$ coefficients on weighted graph Klein bottle file: @@ -54,12 +52,10 @@ Expand the simplex tree in 3.8e-05 s. Information of the Simplex Tree: Number of vertices = 10 Number of simplices = 98 \endcode * - * \li <a href="example_alpha_shapes_3_simplex_tree_from_off_file_8cpp-example.html"> - * Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp</a> - Simplex tree is computed and displayed + * \li \gudhi_example_link{Simplex_tree,example_alpha_shapes_3_simplex_tree_from_off_file.cpp} - Simplex tree is computed and displayed * from a 3D alpha complex (Requires CGAL, GMP and GMPXX to be installed). * - * \li <a href="graph_expansion_with_blocker_8cpp-example.html"> - * Simplex_tree/graph_expansion_with_blocker.cpp</a> - Simple simplex tree construction from a one-skeleton graph with + * \li \gudhi_example_link{Simplex_tree,graph_expansion_with_blocker.cpp} - Simple simplex tree construction from a one-skeleton graph with * a simple blocker expansion method. * * \subsection filteredcomplexeshassecomplex Hasse complex diff --git a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp index df52bf43..eef8b665 100644 --- a/src/Simplex_tree/example/graph_expansion_with_blocker.cpp +++ b/src/Simplex_tree/example/graph_expansion_with_blocker.cpp @@ -42,7 +42,7 @@ int main(int argc, char* const argv[]) { std::clog << vertex << ", "; } std::clog << "] ( " << stree.filtration(sh); - // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) + // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boundaries) stree.assign_filtration(sh, stree.filtration(sh) + 1.); std::clog << " + 1. ) = " << result << std::endl; diff --git a/src/Simplex_tree/example/simple_simplex_tree.cpp b/src/Simplex_tree/example/simple_simplex_tree.cpp index e8bec596..965711da 100644 --- a/src/Simplex_tree/example/simple_simplex_tree.cpp +++ b/src/Simplex_tree/example/simple_simplex_tree.cpp @@ -129,7 +129,7 @@ int main(int argc, char* const argv[]) { std::clog << " - 3 NOT INSERTED" << std::endl; } - // ++ NINETH + // ++ NINTH std::clog << " * INSERT (3,0)" << std::endl; typeVectorVertex ninethSimplexVector = {3, 0}; returnValue = simplexTree.insert_simplex(ninethSimplexVector, Filtration_value(SECOND_FILTRATION_VALUE)); diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index d48f6616..4d94c037 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -187,6 +187,12 @@ class Simplex_tree { typedef Simplex_tree_boundary_simplex_iterator<Simplex_tree> Boundary_simplex_iterator; /** \brief Range over the simplices of the boundary of a simplex. */ typedef boost::iterator_range<Boundary_simplex_iterator> Boundary_simplex_range; + /** \brief Iterator over the simplices of the boundary of a simplex and their opposite vertices. + * + * 'value_type' is std::pair<Simplex_handle, Vertex_handle>. */ + typedef Simplex_tree_boundary_opposite_vertex_simplex_iterator<Simplex_tree> Boundary_opposite_vertex_simplex_iterator; + /** \brief Range over the simplices of the boundary of a simplex and their opposite vertices. */ + typedef boost::iterator_range<Boundary_opposite_vertex_simplex_iterator> Boundary_opposite_vertex_simplex_range; /** \brief Iterator over the simplices of the simplicial complex. * * 'value_type' is Simplex_handle. */ @@ -296,6 +302,23 @@ class Simplex_tree { Boundary_simplex_iterator(this)); } + /** \brief Given a simplex, returns a range over the simplices of its boundary and their opposite vertices. + * + * The boundary of a simplex is the set of codimension \f$1\f$ subsimplices of the simplex. + * If the simplex is \f$[v_0, \cdots ,v_d]\f$, with canonical orientation induced by \f$ v_0 < \cdots < v_d \f$, the + * iterator enumerates the simplices of the boundary in the order: + * \f$[v_0,\cdots,\widehat{v_i},\cdots,v_d]\f$ for \f$i\f$ from \f$d\f$ to \f$0\f$, where \f$\widehat{v_i}\f$ means + * that the vertex \f$v_i\f$, known as the opposite vertex, is omitted from boundary, but returned as the second + * element of a pair. + * + * @param[in] sh Simplex for which the boundary is computed. + */ + template<class SimplexHandle> + Boundary_opposite_vertex_simplex_range boundary_opposite_vertex_simplex_range(SimplexHandle sh) { + return Boundary_opposite_vertex_simplex_range(Boundary_opposite_vertex_simplex_iterator(this, sh), + Boundary_opposite_vertex_simplex_iterator(this)); + } + /** @} */ // end range and iterator methods /** \name Constructor/Destructor * @{ */ @@ -942,7 +965,7 @@ class Simplex_tree { // If we reached the end of the vertices, and the simplex has more vertices than the given simplex // => we found a coface - // Add a coface if we wan't the star or if the number of vertices of the current simplex matches with nbVertices + // Add a coface if we want the star or if the number of vertices of the current simplex matches with nbVertices bool addCoface = (star || curr_nbVertices == nbVertices); if (addCoface) cofaces.push_back(simplex); @@ -1060,8 +1083,8 @@ class Simplex_tree { * * Inserts all vertices and edges given by a OneSkeletonGraph. * OneSkeletonGraph must be a model of - * <a href="http://www.boost.org/doc/libs/1_76_0/libs/graph/doc/VertexAndEdgeListGraph.html">boost::VertexAndEdgeListGraph</a> - * and <a href="http://www.boost.org/doc/libs/1_76_0/libs/graph/doc/PropertyGraph.html">boost::PropertyGraph</a>. + * <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/VertexAndEdgeListGraph.html">boost::VertexAndEdgeListGraph</a> + * and <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/PropertyGraph.html">boost::PropertyGraph</a>. * * The vertex filtration value is accessible through the property tag * vertex_filtration_t. @@ -1468,7 +1491,7 @@ class Simplex_tree { int sh_dimension = dimension(sh); if (sh_dimension >= dimension_) - // Stop browsing as soon as the dimension is reached, no need to go furter + // Stop browsing as soon as the dimension is reached, no need to go further return false; new_dimension = (std::max)(new_dimension, sh_dimension); } diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h index e5522cc7..394c6ee1 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_iterators.h @@ -5,6 +5,7 @@ * Copyright (C) 2014 Inria * * Modification(s): + * - 2022/04 Vincent Rouvreau: Add Simplex_tree_boundary_opposite_vertex_simplex_iterator for alpha and cech purpose * - YYYY/MM Author: Description of the modification */ @@ -17,6 +18,7 @@ #include <boost/container/static_vector.hpp> #include <vector> +#include <utility> // for std::pair namespace Gudhi { @@ -123,7 +125,7 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< private: friend class boost::iterator_core_access; -// valid when iterating along the SAME boundary. + // valid when iterating along the SAME boundary. bool equal(Simplex_tree_boundary_simplex_iterator const& other) const { return sh_ == other.sh_; } @@ -178,6 +180,116 @@ class Simplex_tree_boundary_simplex_iterator : public boost::iterator_facade< Simplex_handle sh_; // current Simplex_handle in the boundary SimplexTree * st_; // simplex containing the simplicial complex }; + +/* \brief Iterator over the simplices of the boundary of a simplex and their opposite vertices. + * + * Forward iterator, value_type is std::pair<SimplexTree::Simplex_handle, SimplexTree::Vertex_handle>.*/ +template<class SimplexTree> +class Simplex_tree_boundary_opposite_vertex_simplex_iterator : public boost::iterator_facade< + Simplex_tree_boundary_opposite_vertex_simplex_iterator<SimplexTree>, + std::pair<typename SimplexTree::Simplex_handle, typename SimplexTree::Vertex_handle> const, boost::forward_traversal_tag> { + public: + using Simplex_handle = typename SimplexTree::Simplex_handle; + using Vertex_handle = typename SimplexTree::Vertex_handle; + using Siblings = typename SimplexTree::Siblings; + + // For cython purpose only. The object it initializes should be overwritten ASAP and never used before it is + // overwritten. + Simplex_tree_boundary_opposite_vertex_simplex_iterator() + : sib_(nullptr), + st_(nullptr) { + } + + // any end() iterator + explicit Simplex_tree_boundary_opposite_vertex_simplex_iterator(SimplexTree * st) + : last_(st->null_vertex()), + next_(st->null_vertex()), + sib_(nullptr), + baov_(st->null_simplex(), st->null_vertex()), + st_(st) { + } + + template<class SimplexHandle> + Simplex_tree_boundary_opposite_vertex_simplex_iterator(SimplexTree * st, SimplexHandle sh) + : last_(sh->first), + next_(st->null_vertex()), + sib_(nullptr), + baov_(st->null_simplex(), sh->first), + st_(st) { + // Only check once at the beginning instead of for every increment, as this is expensive. + if (SimplexTree::Options::contiguous_vertices) + GUDHI_CHECK(st_->contiguous_vertices(), "The set of vertices is not { 0, ..., n } without holes"); + Siblings * sib = st->self_siblings(sh); + next_ = sib->parent(); + sib_ = sib->oncles(); + if (sib_ != nullptr) { + if (SimplexTree::Options::contiguous_vertices && sib_->oncles() == nullptr) + // Only relevant for edges + baov_.first = sib_->members_.begin()+next_; + else + baov_.first = sib_->find(next_); + } + } + + private: + friend class boost::iterator_core_access; + + // valid when iterating along the SAME boundary. + bool equal(Simplex_tree_boundary_opposite_vertex_simplex_iterator const& other) const { + return (baov_.first == other.baov_.first); + } + + std::pair<Simplex_handle, Vertex_handle> const& dereference() const { + return baov_; + } + + void increment() { + if (sib_ == nullptr) { + baov_.first = st_->null_simplex(); + return; // ------>> + } + Siblings * for_sib = sib_; + Siblings * new_sib = sib_->oncles(); + auto rit = suffix_.rbegin(); + if (SimplexTree::Options::contiguous_vertices && new_sib == nullptr) { + // We reached the root, use a short-cut to find a vertex. + if (rit == suffix_.rend()) { + baov_.second = baov_.first->first; + // Segment, this vertex is the last boundary simplex + baov_.first = for_sib->members_.begin()+last_; + sib_ = nullptr; + return; + } else { + // Dim >= 2, initial step of the descent + baov_.first = for_sib->members_.begin()+*rit; + for_sib = baov_.first->second.children(); + ++rit; + } + } + for (; rit != suffix_.rend(); ++rit) { + baov_.first = for_sib->find(*rit); + for_sib = baov_.first->second.children(); + } + baov_.first = for_sib->find(last_); // baov_.first points to the right simplex now + suffix_.push_back(next_); + next_ = sib_->parent(); + sib_ = new_sib; + baov_.second = suffix_.back(); + } + + // Most of the storage should be moved to the range, iterators should be light. + Vertex_handle last_; // last vertex of the simplex + Vertex_handle next_; // next vertex to push in suffix_ + // 40 seems a conservative bound on the dimension of a Simplex_tree for now, + // as it would not fit on the biggest hard-drive. + boost::container::static_vector<Vertex_handle, 40> suffix_; + // static_vector still has some overhead compared to a trivial hand-made + // version using std::aligned_storage, or compared to making suffix_ static. + Siblings * sib_; // where the next search will start from + std::pair<Simplex_handle, Vertex_handle> baov_; // a pair containing the current Simplex_handle in the boundary and its opposite vertex + SimplexTree * st_; // simplex containing the simplicial complex +}; + /*---------------------------------------------------------------------------*/ /* \brief Iterator over the simplices of a simplicial complex. * diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h index ae140859..ad53710c 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h @@ -24,7 +24,7 @@ namespace Gudhi { * \brief Node of a simplex tree with filtration value * and simplex key. * - * It stores explicitely its own filtration value and its own Simplex_key. + * It stores explicitly its own filtration value and its own Simplex_key. */ template<class SimplexTree> struct Simplex_tree_node_explicit_storage : SimplexTree::Filtration_simplex_base, SimplexTree::Key_simplex_base { diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h index b53bad29..ae25d290 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_siblings.h @@ -36,6 +36,7 @@ class Simplex_tree_siblings { template<class T> friend class Simplex_tree_boundary_simplex_iterator; template<class T> friend class Simplex_tree_complex_simplex_iterator; template<class T> friend class Simplex_tree_skeleton_simplex_iterator; + template<class T> friend class Simplex_tree_boundary_opposite_vertex_simplex_iterator; typedef typename SimplexTree::Vertex_handle Vertex_handle; typedef typename SimplexTree::Filtration_value Filtration_value; diff --git a/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp index 6d63d8ae..54e23204 100644 --- a/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_graph_expansion_unit_test.cpp @@ -93,7 +93,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_3, typeST, li std::clog << vertex << ", "; } std::clog << "] ( " << simplex_tree.filtration(sh); - // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) + // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boundaries) simplex_tree.assign_filtration(sh, simplex_tree.filtration(sh) + 1.); std::clog << " + 1. ) = " << result << std::endl; @@ -160,7 +160,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_expansion_with_blockers_2, typeST, li std::clog << vertex << ", "; } std::clog << "] ( " << simplex_tree.filtration(sh); - // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boudaries) + // User can re-assign a new filtration value directly in the blocker (default is the maximal value of boundaries) simplex_tree.assign_filtration(sh, simplex_tree.filtration(sh) + 1.); std::clog << " + 1. ) = " << result << std::endl; diff --git a/src/Simplex_tree/test/simplex_tree_unit_test.cpp b/src/Simplex_tree/test/simplex_tree_unit_test.cpp index bdd41d34..79bb5a93 100644 --- a/src/Simplex_tree/test/simplex_tree_unit_test.cpp +++ b/src/Simplex_tree/test/simplex_tree_unit_test.cpp @@ -17,6 +17,8 @@ #include <limits> #include <functional> // greater #include <tuple> // std::tie +#include <iterator> // for std::distance +#include <cstddef> // for std::size_t #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MODULE "simplex_tree" @@ -285,7 +287,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var set_and_test_simplex_tree_dim_fil(st, eighthSimplexVector.size(), eighthSimplex.second); BOOST_CHECK(st.num_vertices() == (size_t) 4); - // ++ NINETH + // ++ NINTH std::clog << " - INSERT (3,0)" << std::endl; typeVectorVertex ninethSimplexVector{3, 0}; BOOST_CHECK(ninethSimplexVector.size() == 2); @@ -359,7 +361,7 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_insertion, typeST, list_of_tested_var test_simplex_tree_contains(st, seventhSimplex, 8); // (2,1,0) -> 8 std::clog << "simplex_tree_insertion - eighth - 3" << std::endl; test_simplex_tree_contains(st, eighthSimplex, 3); // (3) -> 3 - std::clog << "simplex_tree_insertion - nineth - 7" << std::endl; + std::clog << "simplex_tree_insertion - ninth - 7" << std::endl; test_simplex_tree_contains(st, ninethSimplex, 7); // (3,0) -> 7 // Display the Simplex_tree - Can not be done in the middle of 2 inserts @@ -991,3 +993,48 @@ BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_reset_filtration, typeST, list_of_tes } +BOOST_AUTO_TEST_CASE_TEMPLATE(simplex_tree_boundaries_and_opposite_vertex_iterator, typeST, list_of_tested_variants) { + std::clog << "********************************************************************" << std::endl; + std::clog << "TEST OF BOUNDARIES AND OPPOSITE VERTEX ITERATORS" << std::endl; + typeST st; + + st.insert_simplex_and_subfaces({2, 1, 0}, 3.); + st.insert_simplex_and_subfaces({3, 0}, 2.); + st.insert_simplex_and_subfaces({3, 4, 5}, 3.); + st.insert_simplex_and_subfaces({0, 1, 6, 7}, 4.); + + /* Inserted simplex: */ + /* 1 6 */ + /* o---o */ + /* /X\7/ */ + /* o---o---o---o */ + /* 2 0 3\X/4 */ + /* o */ + /* 5 */ + using Simplex = std::vector<typename typeST::Vertex_handle>; + // simplices must be kept sorted by vertex number for std::vector to use operator== - cf. last BOOST_CHECK + std::vector<Simplex> simplices = {{0, 1, 2}, {0, 3}, {0, 1, 6, 7}, {3, 4, 5}, {3, 5}, {2}}; + for (auto simplex : simplices) { + Simplex opposite_vertices; + for(auto boundary_and_opposite_vertex : st.boundary_opposite_vertex_simplex_range(st.find(simplex))) { + Simplex output; + for (auto vertex : st.simplex_vertex_range(boundary_and_opposite_vertex.first)) { + std::clog << vertex << " "; + output.emplace_back(vertex); + } + std::clog << " - opposite vertex = " << boundary_and_opposite_vertex.second << std::endl; + // Check that boundary simplex + opposite vertex = simplex given as input + output.emplace_back(boundary_and_opposite_vertex.second); + std::sort(output.begin(), output.end()); + BOOST_CHECK(simplex == output); + opposite_vertices.emplace_back(boundary_and_opposite_vertex.second); + } + // Check that the list of all opposite vertices = simplex given as input + // no opposite vertices if simplex given as input is of dimension 1 + std::sort(opposite_vertices.begin(), opposite_vertices.end()); + if (simplex.size() > 1) + BOOST_CHECK(simplex == opposite_vertices); + else + BOOST_CHECK(opposite_vertices.size() == 0); + } +} diff --git a/src/Skeleton_blocker/concept/SkeletonBlockerDS.h b/src/Skeleton_blocker/concept/SkeletonBlockerDS.h index 0c2014bd..23eb3670 100644 --- a/src/Skeleton_blocker/concept/SkeletonBlockerDS.h +++ b/src/Skeleton_blocker/concept/SkeletonBlockerDS.h @@ -29,7 +29,7 @@ struct SkeletonBlockerDS { /** * @brief Root_vertex_handle and Vertex_handle are similar to global and local vertex descriptor - * used in <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a> + * used in <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/subgraph.html">boost subgraphs</a> * and allow to localize a vertex of a subcomplex on its parent root complex. * * In gross, vertices are stored in a vector diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h index 0c0cc624..d091d7dd 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simple_traits.h @@ -28,7 +28,7 @@ namespace skeleton_blocker { */ struct Skeleton_blocker_simple_traits { /** - * @brief Global and local handle similar to <a href="http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/subgraph.html">boost subgraphs</a>. + * @brief Global and local handle similar to <a href="https://www.boost.org/doc/libs/release/libs/graph/doc/subgraph.html">boost subgraphs</a>. * Vertices are stored in a vector. * For the root simplicial complex, the local and global descriptors are the same. * For a subcomplex L and one of its vertices 'v', the local descriptor of 'v' is its position in diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h index 12fe6469..d83c0ab3 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_simplex.h @@ -134,7 +134,7 @@ class Skeleton_blocker_simplex { } /** - * Substracts a from the simplex. + * Subtracts a from the simplex. */ void difference(const Skeleton_blocker_simplex & a) { std::vector<T> v; diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h index 4c48ff31..5abd64d7 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/Skeleton_blocker_sub_complex.h @@ -76,8 +76,8 @@ class Skeleton_blocker_sub_complex : public ComplexType { public: /** * Add a vertex 'global' of K to L. When added to L, this vertex will receive - * another number, addresses(global), its local adress. - * return the adress where the vertex lay on L. + * another number, addresses(global), its local address. + * return the address where the vertex lay on L. * The vertex corresponding to 'global' must not be already present * in the complex. */ @@ -174,7 +174,7 @@ class Skeleton_blocker_sub_complex : public ComplexType { // /** // * Allocates a simplex in L corresponding to the simplex s in K - // * with its local adresses and returns an AddressSimplex. + // * with its local addresses and returns an AddressSimplex. // */ // boost::optional<Simplex> get_address(const Root_simplex_handle & s) const; @@ -226,7 +226,7 @@ bool proper_face_in_union( } // Remark: this function should be friend in order to leave get_adresses private -// however doing so seemes currently not possible due to a visual studio bug c2668 +// however doing so seems currently not possible due to a visual studio bug c2668 // "the compiler does not support partial ordering of template functions as specified in the C++ Standard" // http://www.serkey.com/error-c2668-ambiguous-call-to-overloaded-function-bb45ft.html diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h index a43fa034..18ae6a92 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/internal/Trie.h @@ -107,7 +107,7 @@ struct Trie { } /** - * Goes to the root in the trie to consitute simplex + * Goes to the root in the trie to constitute simplex */ void add_vertices_up_to_the_root(Simplex& res) const { res.add_vertex(v); diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h index 37c0b4d3..2c49a1b8 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker/iterators/Skeleton_blockers_triangles_iterators.h @@ -21,7 +21,7 @@ namespace skeleton_blocker { /** * \brief Iterator over the triangles that are * adjacent to a vertex of the simplicial complex. - * \remark Will be removed soon -> dont look + * \remark Will be removed soon -> don't look */ template<typename Complex, typename LinkType> class Triangle_around_vertex_iterator : public boost::iterator_facade @@ -95,7 +95,7 @@ class Triangle_around_vertex_iterator : public boost::iterator_facade /** * \brief Iterator over the triangles of the * simplicial complex. - * \remark Will be removed soon -> dont look + * \remark Will be removed soon -> don't look * */ template<typename SkeletonBlockerComplex> diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h index 125c6387..8ceaa480 100644 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_complex.h @@ -438,7 +438,7 @@ class Skeleton_blocker_complex { } /** - * return the id of a vertex of adress local present in the graph + * return the id of a vertex of address local present in the graph */ Root_vertex_handle get_id(Vertex_handle local) const { assert(0 <= local.vertex && local.vertex < boost::num_vertices(skeleton)); @@ -740,7 +740,7 @@ class Skeleton_blocker_complex { * complex to the smallest flag complex that contains it. */ void remove_blockers() { - // Desallocate the blockers + // Deallocate the blockers while (!blocker_map_.empty()) { delete_blocker(blocker_map_.begin()->second); } @@ -764,8 +764,8 @@ class Skeleton_blocker_complex { public: /** - * Removes the simplex s from the set of blockers - * and desallocate s. + * Removes the simplex sigma from the set of blockers + * and deallocate sigma. */ void delete_blocker(Blocker_handle sigma) { if (visitor) @@ -960,7 +960,7 @@ class Skeleton_blocker_complex { } /* - * @brief returnrs true iff the complex is empty. + * @brief returns true iff the complex is empty. */ bool empty() const { return num_vertices() == 0; @@ -1043,7 +1043,7 @@ class Skeleton_blocker_complex { if (num_vertices() == 1) return true; for (auto vi : vertex_range()) { - // xxx todo faire une methode bool is_in_blocker(Vertex_handle) + // xxx todo create a method: bool is_in_blocker(Vertex_handle) if (blocker_map_.find(vi) == blocker_map_.end()) { // no blocker passes through the vertex, we just need to // check if the current vertex is linked to all others vertices of the complex @@ -1071,7 +1071,6 @@ class Skeleton_blocker_complex { /** * Removes all the popable blockers of the complex and delete them. - * @returns the number of popable blockers deleted */ void remove_popable_blockers(); @@ -1103,7 +1102,6 @@ class Skeleton_blocker_complex { public: /** * Remove the star of the edge connecting vertices a and b. - * @returns the number of blocker that have been removed */ void remove_star(Vertex_handle a, Vertex_handle b); diff --git a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h index 404f04f9..5db9c2fd 100644..100755 --- a/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h +++ b/src/Skeleton_blocker/include/gudhi/Skeleton_blocker_simplifiable_complex.h @@ -39,7 +39,6 @@ bool Skeleton_blocker_complex<SkeletonBlockerDS>::is_popable_blocker(Blocker_han /** * Removes all the popable blockers of the complex and delete them. - * @returns the number of popable blockers deleted */ template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_popable_blockers() { @@ -160,7 +159,6 @@ void Skeleton_blocker_complex<SkeletonBlockerDS>::update_blockers_after_remove_s /** * Remove the star of the edge connecting vertices a and b. - * @returns the number of blocker that have been removed */ template<typename SkeletonBlockerDS> void Skeleton_blocker_complex<SkeletonBlockerDS>::remove_star(Vertex_handle a, Vertex_handle b) { diff --git a/src/Tangential_complex/include/gudhi/Tangential_complex.h b/src/Tangential_complex/include/gudhi/Tangential_complex.h index f3491f91..cc424810 100644 --- a/src/Tangential_complex/include/gudhi/Tangential_complex.h +++ b/src/Tangential_complex/include/gudhi/Tangential_complex.h @@ -1152,7 +1152,7 @@ class Tangential_complex { #ifdef GUDHI_TC_VERY_VERBOSE std::cerr << "Inserted " << num_inserted_points << " points / " << num_attempts_to_insert_points - << " attemps to compute the star\n"; + << " attempts to compute the star\n"; #endif update_star(i); diff --git a/src/cmake/modules/FindTBB.cmake b/src/cmake/modules/FindTBB.cmake index 13f4d929..e6c42dc7 100644 --- a/src/cmake/modules/FindTBB.cmake +++ b/src/cmake/modules/FindTBB.cmake @@ -34,7 +34,7 @@ # # GvdB: Mac OS X distribution places libraries directly in lib directory. # -# For backwards compatibility, you may explicitely set the CMake variables TBB_ARCHITECTURE and TBB_COMPILER. +# For backwards compatibility, you may explicitly set the CMake variables TBB_ARCHITECTURE and TBB_COMPILER. # TBB_ARCHITECTURE [ ia32 | em64t | itanium ] # which architecture to use # TBB_COMPILER e.g. vc9 or cc3.2.3_libc2.3.2_kernel2.4.21 or cc4.0.1_os10.4.9 @@ -54,8 +54,8 @@ # TBB_MALLOC_DEBUG_LIBRARY, the TBB debug malloc library # TBB_FOUND, If false, don't try to use TBB. # TBB_INTERFACE_VERSION, as defined in tbb/tbb_stddef.h -# TBB_MALLOCPROXY_DEBUG_LIBRARY, the TBB debug malloc_proxy library (not included in TBB_LIBRARIES since it's optionnal) -# TBB_MALLOCPROXY_RELEASE_LIBRARY, the TBB release malloc_proxy library (not included in TBB_LIBRARIES since it's optionnal) +# TBB_MALLOCPROXY_DEBUG_LIBRARY, the TBB debug malloc_proxy library (not included in TBB_LIBRARIES since it's optional) +# TBB_MALLOCPROXY_RELEASE_LIBRARY, the TBB release malloc_proxy library (not included in TBB_LIBRARIES since it's optional) include(CheckCXXSourceCompiles) diff --git a/src/cmake/modules/GUDHI_doxygen_target.cmake b/src/cmake/modules/GUDHI_doxygen_target.cmake index 0f80b187..6b9514de 100644 --- a/src/cmake/modules/GUDHI_doxygen_target.cmake +++ b/src/cmake/modules/GUDHI_doxygen_target.cmake @@ -44,6 +44,14 @@ if(DOXYGEN_FOUND) set(GUDHI_DOXYGEN_UTILS_PATH "utilities/*") endif() + message("++ Doxygen version ${DOXYGEN_VERSION}") + if (DOXYGEN_VERSION VERSION_LESS 1.9.2) + set(GUDHI_DOXYGEN_MATHJAX_VERSION "MATHJAX_VERSION = MathJax_2") + set(GUDHI_DOXYGEN_MATHJAX_EXTENSIONS "TeX/AMSmath TeX/AMSsymbols") + else() + set(GUDHI_DOXYGEN_MATHJAX_VERSION "MATHJAX_VERSION = MathJax_3") + set(GUDHI_DOXYGEN_MATHJAX_EXTENSIONS "ams") + endif() configure_file(${GUDHI_DOXYGEN_SOURCE_PREFIX}/Doxyfile.in "${CMAKE_CURRENT_BINARY_DIR}/Doxyfile" @ONLY) add_custom_target(doxygen ${DOXYGEN_EXECUTABLE} ${CMAKE_CURRENT_BINARY_DIR}/Doxyfile diff --git a/src/cmake/modules/GUDHI_modules.cmake b/src/cmake/modules/GUDHI_modules.cmake index 13248f7e..ec1f756b 100644 --- a/src/cmake/modules/GUDHI_modules.cmake +++ b/src/cmake/modules/GUDHI_modules.cmake @@ -2,7 +2,7 @@ set(GUDHI_MODULES_FULL_LIST "") function(add_gudhi_module file_path) - option("WITH_MODULE_GUDHI_${file_path}" "Activate/desactivate ${file_path} compilation and installation" ON) + option("WITH_MODULE_GUDHI_${file_path}" "Activate/deactivate ${file_path} compilation and installation" ON) if (WITH_MODULE_GUDHI_${file_path}) set(GUDHI_MODULES ${GUDHI_MODULES} ${file_path} CACHE INTERNAL "GUDHI_MODULES") else() @@ -10,7 +10,7 @@ function(add_gudhi_module file_path) endif() # Required by user_version set(GUDHI_MODULES_FULL_LIST ${GUDHI_MODULES_FULL_LIST} ${file_path} PARENT_SCOPE) - # Include module headers is independant - You may ask for no Alpha complex module but Python interface i.e. + # Include module headers is independent - You may ask for no Alpha complex module but Python interface i.e. if(IS_DIRECTORY ${CMAKE_SOURCE_DIR}/src/${file_path}/include/) include_directories(src/${file_path}/include/) endif() diff --git a/src/cmake/modules/GUDHI_third_party_libraries.cmake b/src/cmake/modules/GUDHI_third_party_libraries.cmake index 6a94d1f5..6ba822ad 100644 --- a/src/cmake/modules/GUDHI_third_party_libraries.cmake +++ b/src/cmake/modules/GUDHI_third_party_libraries.cmake @@ -174,7 +174,7 @@ if (WITH_GUDHI_PYTHON) message(FATAL_ERROR "ERROR: GUDHI_PYTHON_PATH is not valid.") endif(NOT GUDHI_PYTHON_PATH) - option(WITH_GUDHI_PYTHON_RUNTIME_LIBRARY_DIRS "Build with setting runtime_library_dirs. Usefull when setting rpath is not allowed" ON) + option(WITH_GUDHI_PYTHON_RUNTIME_LIBRARY_DIRS "Build with setting runtime_library_dirs. Useful when setting rpath is not allowed" ON) if(PYTHONINTERP_FOUND AND CYTHON_FOUND) if(SPHINX_FOUND) diff --git a/src/common/doc/examples.h b/src/common/doc/examples.h index 879fb96a..556a24f1 100644 --- a/src/common/doc/examples.h +++ b/src/common/doc/examples.h @@ -1,6 +1,6 @@ // List of GUDHI examples and utils - Doxygen needs at least a file tag to analyse comments // Generated from scripts/cpp_examples_for_doxygen.py -/*! @file Examples +/*! @file * \section Witness_complex_example_section Witness_complex * @example strong_witness_persistence.cpp * @example weak_witness_persistence.cpp diff --git a/src/common/doc/installation.h b/src/common/doc/installation.h index afbad14d..229c9f59 100644 --- a/src/common/doc/installation.h +++ b/src/common/doc/installation.h @@ -5,8 +5,8 @@ * Examples of GUDHI headers inclusion can be found in \ref utilities. * * \section compiling Compiling - * The library uses c++14 and requires <a target="_blank" href="http://www.boost.org/">Boost</a> ≥ 1.66.0 - * and <a target="_blank" href="https://www.cmake.org/">CMake</a> ≥ 3.5. + * The library uses c++14 and requires <a target="_blank" href="https://www.boost.org/">Boost</a> ≥ 1.66.0 + * and <a target="_blank" href="https://cmake.org/">CMake</a> ≥ 3.5. * It is a multi-platform library and compiles on Linux, Mac OSX and Visual Studio 2015. * * \subsection utilities Utilities and examples @@ -58,10 +58,9 @@ make \endverbatim * The multi-field persistent homology algorithm requires GMP which is a free library for arbitrary-precision * arithmetic, operating on signed integers, rational numbers, and floating point numbers. * - * The following example requires the <a target="_blank" href="http://gmplib.org/">GNU Multiple Precision Arithmetic + * The following example requires the <a target="_blank" href="https://gmplib.org/">GNU Multiple Precision Arithmetic * Library</a> (GMP) and will not be built if GMP is not installed: - * \li <a href="rips_multifield_persistence_8cpp-example.html"> - * Persistent_cohomology/rips_multifield_persistence.cpp</a> + * \li \gudhi_example_link{Persistent_cohomology,rips_multifield_persistence.cpp} * * Having GMP version 4.2 or higher installed is recommended. * @@ -78,179 +77,101 @@ make \endverbatim * * The following examples/utilities require the <a target="_blank" href="http://www.cgal.org/">Computational Geometry Algorithms * Library</a> (CGAL \cite cgal:eb-19b) and will not be built if CGAL version 4.11.0 or higher is not installed: - * \li <a href="example_alpha_shapes_3_simplex_tree_from_off_file_8cpp-example.html"> - * Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp</a> - * \li <a href="strong_witness_persistence_8cpp-example.html"> - * Witness_complex/strong_witness_persistence.cpp</a> - * \li <a href="weak_witness_persistence_8cpp-example.html"> - * Witness_complex/weak_witness_persistence.cpp</a> - * \li <a href="example_strong_witness_complex_off_8cpp-example.html"> - * Witness_complex/example_strong_witness_complex_off.cpp</a> - * \li <a href="example_witness_complex_off_8cpp-example.html"> - * Witness_complex/example_witness_complex_off.cpp</a> - * \li <a href="example_witness_complex_sphere_8cpp-example.html"> - * Witness_complex/example_witness_complex_sphere.cpp</a> - * \li <a href="_alpha_complex_from_off_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_off.cpp</a> - * \li <a href="_alpha_complex_from_points_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_points.cpp</a> - * \li <a href="alpha_complex_persistence_8cpp-example.html"> - * Alpha_complex/alpha_complex_persistence.cpp</a> - * \li <a href="custom_persistence_sort_8cpp-example.html"> - * Persistent_cohomology/custom_persistence_sort.cpp</a> - * \li <a href="alpha_rips_persistence_bottleneck_distance_8cpp-example.html"> - * Bottleneck_distance/alpha_rips_persistence_bottleneck_distance.cpp.cpp</a> - * \li <a href="bottleneck_basic_example_8cpp-example.html"> - * Bottleneck_distance/bottleneck_basic_example.cpp</a> - * \li <a href="bottleneck_distance_8cpp-example.html"> - * Bottleneck_distance/bottleneck_distance.cpp</a> - * \li <a href="_coord_g_i_c_8cpp-example.html"> - * Nerve_GIC/CoordGIC.cpp</a> - * \li <a href="_func_g_i_c_8cpp-example.html"> - * Nerve_GIC/FuncGIC.cpp</a> - * \li <a href="_nerve_8cpp-example.html"> - * Nerve_GIC/Nerve.cpp</a> - * \li <a href="_voronoi_g_i_c_8cpp-example.html"> - * Nerve_GIC/VoronoiGIC.cpp</a> - * \li <a href="example_spatial_searching_8cpp-example.html"> - * Spatial_searching/example_spatial_searching.cpp</a> - * \li <a href="example_choose_n_farthest_points_8cpp-example.html"> - * Subsampling/example_choose_n_farthest_points.cpp</a> - * \li <a href="example_pick_n_random_points_8cpp-example.html"> - * Subsampling/example_pick_n_random_points.cpp</a> - * \li <a href="example_sparsify_point_set_8cpp-example.html"> - * Subsampling/example_sparsify_point_set.cpp</a> - * \li <a href="example_basic_8cpp-example.html"> - * Tangential_complex/example_basic.cpp</a> - * \li <a href="example_with_perturb_8cpp-example.html"> - * Tangential_complex/example_with_perturb.cpp</a> - * \li <a href="_weighted_alpha_complex_3d_from_points_8cpp-example.html"> - * Alpha_complex/Weighted_alpha_complex_3d_from_points.cpp</a> - * \li <a href="alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/alpha_complex_3d_persistence.cpp</a> - * \li <a href="_coxeter_triangulation_2manifold_tracing_flat_torus_with_boundary_8cpp-example.html"> - * Coxeter_triangulation/manifold_tracing_flat_torus_with_boundary.cpp</a> + * \li \gudhi_example_link{Simplex_tree,example_alpha_shapes_3_simplex_tree_from_off_file.cpp} + * \li \gudhi_example_link{Witness_complex,strong_witness_persistence.cpp} + * \li \gudhi_example_link{Witness_complex,weak_witness_persistence.cpp} + * \li \gudhi_example_link{Witness_complex,example_strong_witness_complex_off.cpp} + * \li \gudhi_example_link{Witness_complex,example_witness_complex_off.cpp} + * \li \gudhi_example_link{Witness_complex,example_witness_complex_sphere.cpp} + * \li \gudhi_example_link{Alpha_complex,Alpha_complex_from_off.cpp} + * \li \gudhi_example_link{Alpha_complex,Alpha_complex_from_points.cpp} + * \li \gudhi_example_link{Alpha_complex,alpha_complex_persistence.cpp} + * \li \gudhi_example_link{Persistent_cohomology,custom_persistence_sort.cpp} + * \li \gudhi_example_link{Bottleneck_distance,alpha_rips_persistence_bottleneck_distance.cpp} + * \li \gudhi_example_link{Bottleneck_distance,bottleneck_basic_example.cpp} + * \li \gudhi_example_link{Bottleneck_distance,bottleneck_distance.cpp} + * \li \gudhi_example_link{Nerve_GIC,CoordGIC.cpp} + * \li \gudhi_example_link{Nerve_GIC,FuncGIC.cpp} + * \li \gudhi_example_link{Nerve_GIC,Nerve.cpp} + * \li \gudhi_example_link{Nerve_GIC,VoronoiGIC.cpp} + * \li \gudhi_example_link{Spatial_searching,example_spatial_searching.cpp} + * \li \gudhi_example_link{Subsampling,example_choose_n_farthest_points.cpp} + * \li \gudhi_example_link{Subsampling,example_pick_n_random_points.cpp} + * \li \gudhi_example_link{Subsampling,example_sparsify_point_set.cpp} + * \li \gudhi_example_link{Tangential_complex,example_basic.cpp} + * \li \gudhi_example_link{Tangential_complex,example_with_perturb.cpp} + * \li \gudhi_example_link{Alpha_complex,Weighted_alpha_complex_3d_from_points.cpp} + * \li \gudhi_example_link{Alpha_complex,alpha_complex_3d_persistence.cpp} + * \li \gudhi_example_link{Coxeter_triangulation,manifold_tracing_flat_torus_with_boundary.cpp} * * \subsection eigen Eigen * Some GUDHI modules (cf. \ref main_page "modules list"), and few examples require - * <a target="_blank" href="http://eigen.tuxfamily.org/">Eigen</a> is a C++ template library for linear algebra: + * <a target="_blank" href="https://eigen.tuxfamily.org">Eigen</a> is a C++ template library for linear algebra: * matrices, vectors, numerical solvers, and related algorithms. * - * The following examples/utilities require the <a target="_blank" href="http://eigen.tuxfamily.org/">Eigen</a> and will not be + * The following examples/utilities require the <a target="_blank" href="https://eigen.tuxfamily.org">Eigen</a> and will not be * built if Eigen is not installed: - * \li <a href="_alpha_complex_from_off_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_off.cpp</a> - * \li <a href="_alpha_complex_from_points_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_points.cpp</a> - * \li <a href="alpha_complex_persistence_8cpp-example.html"> - * Alpha_complex/alpha_complex_persistence.cpp</a> - * \li <a href="alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/alpha_complex_3d_persistence.cpp</a> - * \li <a href="_weighted_alpha_complex_3d_from_points_8cpp-example.html"> - * Alpha_complex/Weighted_alpha_complex_3d_from_points.cpp</a> - * \li <a href="alpha_rips_persistence_bottleneck_distance_8cpp-example.html"> - * Bottleneck_distance/alpha_rips_persistence_bottleneck_distance.cpp.cpp</a> - * \li <a href="custom_persistence_sort_8cpp-example.html"> - * Persistent_cohomology/custom_persistence_sort.cpp</a> - * \li <a href="example_spatial_searching_8cpp-example.html"> - * Spatial_searching/example_spatial_searching.cpp</a> - * \li <a href="example_choose_n_farthest_points_8cpp-example.html"> - * Subsampling/example_choose_n_farthest_points.cpp</a> - * \li <a href="example_pick_n_random_points_8cpp-example.html"> - * Subsampling/example_pick_n_random_points.cpp</a> - * \li <a href="example_sparsify_point_set_8cpp-example.html"> - * Subsampling/example_sparsify_point_set.cpp</a> - * \li <a href="example_basic_8cpp-example.html"> - * Tangential_complex/example_basic.cpp</a> - * \li <a href="example_with_perturb_8cpp-example.html"> - * Tangential_complex/example_with_perturb.cpp</a> - * \li <a href="strong_witness_persistence_8cpp-example.html"> - * Witness_complex/strong_witness_persistence.cpp</a> - * \li <a href="weak_witness_persistence_8cpp-example.html"> - * Witness_complex/weak_witness_persistence.cpp</a> - * \li <a href="example_strong_witness_complex_off_8cpp-example.html"> - * Witness_complex/example_strong_witness_complex_off.cpp</a> - * \li <a href="example_witness_complex_off_8cpp-example.html"> - * Witness_complex/example_witness_complex_off.cpp</a> - * \li <a href="example_witness_complex_sphere_8cpp-example.html"> - * Witness_complex/example_witness_complex_sphere.cpp</a> - * \li <a href="_coxeter_triangulation_2cell_complex_from_basic_circle_manifold_8cpp-example.html"> - * Coxeter_triangulation/cell_complex_from_basic_circle_manifold.cpp</a> - * \li <a href="_coxeter_triangulation_2manifold_tracing_custom_function_8cpp-example.html"> - * Coxeter_triangulation/manifold_tracing_custom_function.cpp</a> - * \li <a href="_coxeter_triangulation_2manifold_tracing_flat_torus_with_boundary_8cpp-example.html"> - * Coxeter_triangulation/manifold_tracing_flat_torus_with_boundary.cpp</a> + * \li \gudhi_example_link{Alpha_complex,Alpha_complex_from_off.cpp} + * \li \gudhi_example_link{Alpha_complex,Alpha_complex_from_points.cpp} + * \li \gudhi_example_link{Alpha_complex,alpha_complex_persistence.cpp} + * \li \gudhi_example_link{Alpha_complex,alpha_complex_3d_persistence.cpp} + * \li \gudhi_example_link{Alpha_complex,Weighted_alpha_complex_3d_from_points.cpp} + * \li \gudhi_example_link{Bottleneck_distance,alpha_rips_persistence_bottleneck_distance.cpp} + * \li \gudhi_example_link{Persistent_cohomology,custom_persistence_sort.cpp} + * \li \gudhi_example_link{Spatial_searching,example_spatial_searching.cpp} + * \li \gudhi_example_link{Subsampling,example_choose_n_farthest_points.cpp} + * \li \gudhi_example_link{Subsampling,example_pick_n_random_points.cpp} + * \li \gudhi_example_link{Subsampling,example_sparsify_point_set.cpp} + * \li \gudhi_example_link{Tangential_complex,example_basic.cpp} + * \li \gudhi_example_link{Tangential_complex,example_with_perturb.cpp} + * \li \gudhi_example_link{Witness_complex,strong_witness_persistence.cpp} + * \li \gudhi_example_link{Witness_complex,weak_witness_persistence.cpp} + * \li \gudhi_example_link{Witness_complex,example_strong_witness_complex_off.cpp} + * \li \gudhi_example_link{Witness_complex,example_witness_complex_off.cpp} + * \li \gudhi_example_link{Witness_complex,example_witness_complex_sphere.cpp} + * \li \gudhi_example_link{Coxeter_triangulation,cell_complex_from_basic_circle_manifold.cpp} + * \li \gudhi_example_link{Coxeter_triangulation,manifold_tracing_custom_function.cpp} + * \li \gudhi_example_link{Coxeter_triangulation,manifold_tracing_flat_torus_with_boundary.cpp} * * \subsection tbb Threading Building Blocks - * <a target="_blank" href="https://www.threadingbuildingblocks.org/">Intel® TBB</a> lets you easily write parallel + * <a target="_blank" href="https://github.com/oneapi-src/oneTBB">Intel® TBB</a> lets you easily write parallel * C++ programs that take full advantage of multicore performance, that are portable and composable, and that have * future-proof scalability. * * Having Intel® TBB installed is recommended to parallelize and accelerate some GUDHI computations. * * The following examples/utilities are using Intel® TBB if installed: - * \li <a href="_alpha_complex_from_off_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_off.cpp</a> - * \li <a href="_alpha_complex_from_points_8cpp-example.html"> - * Alpha_complex/Alpha_complex_from_points.cpp</a> - * \li <a href="alpha_complex_3d_persistence_8cpp-example.html"> - * Alpha_complex/alpha_complex_3d_persistence.cpp</a> - * \li <a href="alpha_complex_persistence_8cpp-example.html"> - * Alpha_complex/alpha_complex_persistence.cpp</a> - * \li <a href="cubical_complex_persistence_8cpp-example.html"> - * Bitmap_cubical_complex/cubical_complex_persistence.cpp</a> - * \li <a href="periodic_cubical_complex_persistence_8cpp-example.html"> - * Bitmap_cubical_complex/periodic_cubical_complex_persistence.cpp</a> - * \li <a href="_random_bitmap_cubical_complex_8cpp-example.html"> - * Bitmap_cubical_complex/Random_bitmap_cubical_complex.cpp</a> - * \li <a href="_coord_g_i_c_8cpp-example.html"> - * Nerve_GIC/CoordGIC.cpp</a> - * \li <a href="_func_g_i_c_8cpp-example.html"> - * Nerve_GIC/FuncGIC.cpp</a> - * \li <a href="_nerve_8cpp-example.html"> - * Nerve_GIC/Nerve.cpp</a> - * \li <a href="_voronoi_g_i_c_8cpp-example.html"> - * Nerve_GIC/VoronoiGIC.cpp</a> - * \li <a href="simple_simplex_tree_8cpp-example.html"> - * Simplex_tree/simple_simplex_tree.cpp</a> - * \li <a href="example_alpha_shapes_3_simplex_tree_from_off_file_8cpp-example.html"> - * Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp</a> - * \li <a href="simplex_tree_from_cliques_of_graph_8cpp-example.html"> - * Simplex_tree/simplex_tree_from_cliques_of_graph.cpp</a> - * \li <a href="graph_expansion_with_blocker_8cpp-example.html"> - * Simplex_tree/graph_expansion_with_blocker.cpp</a> - * \li <a href="alpha_complex_3d_persistence_8cpp-example.html"> - * Persistent_cohomology/alpha_complex_3d_persistence.cpp</a> - * \li <a href="alpha_complex_persistence_8cpp-example.html"> - * Persistent_cohomology/alpha_complex_persistence.cpp</a> - * \li <a href="rips_persistence_via_boundary_matrix_8cpp-example.html"> - * Persistent_cohomology/rips_persistence_via_boundary_matrix.cpp</a> - * \li <a href="persistence_from_file_8cpp-example.html"> - * Persistent_cohomology/persistence_from_file.cpp</a> - * \li <a href="persistence_from_simple_simplex_tree_8cpp-example.html"> - * Persistent_cohomology/persistence_from_simple_simplex_tree.cpp</a> - * \li <a href="plain_homology_8cpp-example.html"> - * Persistent_cohomology/plain_homology.cpp</a> - * \li <a href="rips_multifield_persistence_8cpp-example.html"> - * Persistent_cohomology/rips_multifield_persistence.cpp</a> - * \li <a href="rips_persistence_step_by_step_8cpp-example.html"> - * Persistent_cohomology/rips_persistence_step_by_step.cpp</a> - * \li <a href="custom_persistence_sort_8cpp-example.html"> - * Persistent_cohomology/custom_persistence_sort.cpp</a> - * \li <a href="example_one_skeleton_rips_from_points_8cpp-example.html"> - * Rips_complex/example_one_skeleton_rips_from_points.cpp</a> - * \li <a href="example_rips_complex_from_off_file_8cpp-example.html"> - * Rips_complex/example_rips_complex_from_off_file.cpp</a> - * \li <a href="rips_distance_matrix_persistence_8cpp-example.html"> - * Rips_complex/rips_distance_matrix_persistence.cpp</a> - * \li <a href="rips_persistence_8cpp-example.html"> - * Rips_complex/rips_persistence.cpp</a> - * \li <a href="strong_witness_persistence_8cpp-example.html"> - * Witness_complex/strong_witness_persistence.cpp</a> - * \li <a href="weak_witness_persistence_8cpp-example.html"> - * Witness_complex/weak_witness_persistence.cpp</a> - * \li <a href="example_nearest_landmark_table_8cpp-example.html"> - * Witness_complex/example_nearest_landmark_table.cpp</a> + * \li \gudhi_example_link{Alpha_complex,Alpha_complex_from_off.cpp} + * \li \gudhi_example_link{Alpha_complex,Alpha_complex_from_points.cpp} + * \li \gudhi_example_link{Alpha_complex,alpha_complex_3d_persistence.cpp} + * \li \gudhi_example_link{Alpha_complex,alpha_complex_persistence.cpp} + * \li \gudhi_example_link{Bitmap_cubical_complex,cubical_complex_persistence.cpp} + * \li \gudhi_example_link{Bitmap_cubical_complex,periodic_cubical_complex_persistence.cpp} + * \li \gudhi_example_link{Bitmap_cubical_complex,Random_bitmap_cubical_complex.cpp} + * \li \gudhi_example_link{Nerve_GIC,CoordGIC.cpp} + * \li \gudhi_example_link{Nerve_GIC,FuncGIC.cpp} + * \li \gudhi_example_link{Nerve_GIC,Nerve.cpp} + * \li \gudhi_example_link{Nerve_GIC,VoronoiGIC.cpp} + * \li \gudhi_example_link{Simplex_tree,simple_simplex_tree.cpp} + * \li \gudhi_example_link{Simplex_tree,example_alpha_shapes_3_simplex_tree_from_off_file.cpp} + * \li \gudhi_example_link{Simplex_tree,simplex_tree_from_cliques_of_graph.cpp} + * \li \gudhi_example_link{Simplex_tree,graph_expansion_with_blocker.cpp} + * \li \gudhi_example_link{Persistent_cohomology,alpha_complex_3d_persistence.cpp} + * \li \gudhi_example_link{Persistent_cohomology,alpha_complex_persistence.cpp} + * \li \gudhi_example_link{Persistent_cohomology,rips_persistence_via_boundary_matrix.cpp} + * \li \gudhi_example_link{Persistent_cohomology,persistence_from_file.cpp} + * \li \gudhi_example_link{Persistent_cohomology,persistence_from_simple_simplex_tree.cpp} + * \li \gudhi_example_link{Persistent_cohomology,plain_homology.cpp} + * \li \gudhi_example_link{Persistent_cohomology,rips_multifield_persistence.cpp} + * \li \gudhi_example_link{Persistent_cohomology,rips_persistence_step_by_step.cpp} + * \li \gudhi_example_link{Persistent_cohomology,custom_persistence_sort.cpp} + * \li \gudhi_example_link{Rips_complex,example_one_skeleton_rips_from_points.cpp} + * \li \gudhi_example_link{Rips_complex,example_rips_complex_from_off_file.cpp} + * \li \gudhi_example_link{Rips_complex,rips_distance_matrix_persistence.cpp} + * \li \gudhi_example_link{Rips_complex,rips_persistence.cpp} + * \li \gudhi_example_link{Witness_complex,strong_witness_persistence.cpp} + * \li \gudhi_example_link{Witness_complex,weak_witness_persistence.cpp} + * \li \gudhi_example_link{Witness_complex,example_nearest_landmark_table.cpp} * * \section Contributions Bug reports and contributions * Please help us improving the quality of the GUDHI library. diff --git a/src/common/doc/main_page.md b/src/common/doc/main_page.md index 17354179..4f2f1692 100644 --- a/src/common/doc/main_page.md +++ b/src/common/doc/main_page.md @@ -231,13 +231,12 @@ 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. + \cite edgecollapsearxiv. </td> <td width="15%"> - <b>Author:</b> Siddharth Pritam<br> + <b>Author:</b> Siddharth Pritam, Marc Glisse<br> <b>Introduced in:</b> GUDHI 3.3.0<br> - <b>Copyright:</b> MIT<br> - <b>Requires:</b> \ref eigen + <b>Copyright:</b> MIT </td> </tr> <tr> diff --git a/src/common/include/gudhi/reader_utils.h b/src/common/include/gudhi/reader_utils.h index 29d5423d..a7d82541 100644 --- a/src/common/include/gudhi/reader_utils.h +++ b/src/common/include/gudhi/reader_utils.h @@ -231,7 +231,7 @@ std::vector<std::vector<Filtration_value>> read_lower_triangular_matrix_from_csv std::string line; - // the first line is emtpy, so we ignore it: + // the first line is empty, so we ignore it: std::getline(in, line); std::vector<Filtration_value> values_in_this_line; result.push_back(values_in_this_line); diff --git a/src/common/include/gudhi/writing_persistence_to_file.h b/src/common/include/gudhi/writing_persistence_to_file.h index 2e36b831..3a0df1a8 100644 --- a/src/common/include/gudhi/writing_persistence_to_file.h +++ b/src/common/include/gudhi/writing_persistence_to_file.h @@ -48,7 +48,7 @@ class Persistence_interval_common { : birth_(birth), death_(death), dimension_(dim), arith_element_(field) {} /** - * Operator to compare two persistence pairs. During the comparision all the + * Operator to compare two persistence pairs. During the comparison all the * fields: birth, death, dimensiona and arith_element_ are taken into account * and they all have to be equal for two pairs to be equal. **/ @@ -65,7 +65,7 @@ class Persistence_interval_common { /** * Operator to compare objects of a type Persistence_interval_common. * One intervals is smaller than the other if it has lower persistence. - * Note that this operator do not take Arith_element into account when doing comparisions. + * Note that this operator do not take Arith_element into account when doing comparisons. **/ bool operator<(const Persistence_interval_common& i2) const { return fabs(this->death_ - this->birth_) < fabs(i2.death_ - i2.birth_); diff --git a/src/python/CMakeLists.txt b/src/python/CMakeLists.txt index 3a231a61..c3768475 100644 --- a/src/python/CMakeLists.txt +++ b/src/python/CMakeLists.txt @@ -148,10 +148,6 @@ if(PYTHONINTERP_FOUND) add_gudhi_debug_info("Eigen3 version ${EIGEN3_VERSION}") # No problem, even if no CGAL found set(GUDHI_PYTHON_EXTRA_COMPILE_ARGS "${GUDHI_PYTHON_EXTRA_COMPILE_ARGS}'-DCGAL_EIGEN3_ENABLED', ") - set(GUDHI_PYTHON_EXTRA_COMPILE_ARGS "${GUDHI_PYTHON_EXTRA_COMPILE_ARGS}'-DGUDHI_USE_EIGEN3', ") - set(GUDHI_USE_EIGEN3 "True") - else (EIGEN3_FOUND) - set(GUDHI_USE_EIGEN3 "False") endif (EIGEN3_FOUND) set(GUDHI_CYTHON_MODULES "${GUDHI_CYTHON_MODULES}'off_reader', ") @@ -333,9 +329,9 @@ if(PYTHONINTERP_FOUND) if(NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 5.1.0) set (GUDHI_SPHINX_MESSAGE "Generating API documentation with Sphinx in ${CMAKE_CURRENT_BINARY_DIR}/sphinx/") # User warning - Sphinx is a static pages generator, and configured to work fine with user_version - # Images and biblio warnings because not found on developper version + # Images and biblio warnings because not found on developer version if (GUDHI_PYTHON_PATH STREQUAL "src/python") - set (GUDHI_SPHINX_MESSAGE "${GUDHI_SPHINX_MESSAGE} \n WARNING : Sphinx is configured for user version, you run it on developper version. Images and biblio will miss") + set (GUDHI_SPHINX_MESSAGE "${GUDHI_SPHINX_MESSAGE} \n WARNING : Sphinx is configured for user version, you run it on developer version. Images and biblio will miss") endif() # sphinx target requires gudhi.so, because conf.py reads gudhi version from it add_custom_target(sphinx @@ -488,7 +484,7 @@ if(PYTHONINTERP_FOUND) add_gudhi_py_test(test_euclidean_witness_complex) # Datasets generators - add_gudhi_py_test(test_datasets_generators) # TODO separate full python datasets generators in another test file independant from CGAL ? + add_gudhi_py_test(test_datasets_generators) # TODO separate full python datasets generators in another test file independent from CGAL ? endif (NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.11.0) diff --git a/src/python/doc/alpha_complex_user.rst b/src/python/doc/alpha_complex_user.rst index b060c86e..9e67d38a 100644 --- a/src/python/doc/alpha_complex_user.rst +++ b/src/python/doc/alpha_complex_user.rst @@ -178,11 +178,11 @@ Weighted version ^^^^^^^^^^^^^^^^ A weighted version for Alpha complex is available. It is like a usual Alpha complex, but based on a -`CGAL regular triangulation <https://doc.cgal.org/latest/Triangulation/index.html#title20>`_. +`CGAL regular triangulation <https://doc.cgal.org/latest/Triangulation/index.html#TriangulationSecRT>`_. This example builds the weighted alpha-complex of a small molecule, where atoms have different sizes. It is taken from -`CGAL 3d weighted alpha shapes <https://doc.cgal.org/latest/Alpha_shapes_3/index.html#title13>`_. +`CGAL 3d weighted alpha shapes <https://doc.cgal.org/latest/Alpha_shapes_3/index.html#AlphaShape_3DExampleforWeightedAlphaShapes>`_. Then, it is asked to display information about the alpha complex. diff --git a/src/python/doc/nerve_gic_complex_user.rst b/src/python/doc/nerve_gic_complex_user.rst index 0b820abf..8633cadb 100644 --- a/src/python/doc/nerve_gic_complex_user.rst +++ b/src/python/doc/nerve_gic_complex_user.rst @@ -12,7 +12,7 @@ Definition Visualizations of the simplicial complexes can be done with either neato (from `graphviz <http://www.graphviz.org/>`_), `geomview <http://www.geomview.org/>`_, -`KeplerMapper <https://github.com/MLWave/kepler-mapper>`_. +`KeplerMapper <https://github.com/scikit-tda/kepler-mapper>`_. Input point clouds are assumed to be OFF files (cf. `OFF file format <fileformats.html#off-file-format>`_). Covers diff --git a/src/python/example/rips_complex_diagram_persistence_from_correlation_matrix_file_example.py b/src/python/example/rips_complex_diagram_persistence_from_correlation_matrix_file_example.py index ea2eb7e1..0b35dbc5 100755 --- a/src/python/example/rips_complex_diagram_persistence_from_correlation_matrix_file_example.py +++ b/src/python/example/rips_complex_diagram_persistence_from_correlation_matrix_file_example.py @@ -40,7 +40,7 @@ parser.add_argument( args = parser.parse_args() if not (-1.0 < args.min_edge_correlation < 1.0): - print("Wrong value of the treshold corelation (should be between -1 and 1).") + print("Wrong value of the threshold corelation (should be between -1 and 1).") sys.exit(1) print("#####################################################################") diff --git a/src/python/gudhi/__init__.py.in b/src/python/gudhi/__init__.py.in index 3043201a..79e12fbc 100644 --- a/src/python/gudhi/__init__.py.in +++ b/src/python/gudhi/__init__.py.in @@ -23,10 +23,6 @@ __all__ = [@GUDHI_PYTHON_MODULES@ @GUDHI_PYTHON_MODULES_EXTRA@] __available_modules = '' __missing_modules = '' -# For unitary tests purpose -# could use "if 'collapse_edges' in gudhi.__all__" when collapse edges will have a python module -__GUDHI_USE_EIGEN3 = @GUDHI_USE_EIGEN3@ - # Try to import * from gudhi.__module_name for default modules. # Extra modules require an explicit import by the user (mostly because of # unusual dependencies, but also to avoid cluttering namespace gudhi and diff --git a/src/python/gudhi/hera/wasserstein.cc b/src/python/gudhi/hera/wasserstein.cc index 1a21f02f..fa0cf8aa 100644 --- a/src/python/gudhi/hera/wasserstein.cc +++ b/src/python/gudhi/hera/wasserstein.cc @@ -29,7 +29,7 @@ double wasserstein_distance( if(std::isinf(internal_p)) internal_p = hera::get_infinity<double>(); params.internal_p = internal_p; params.delta = delta; - // The extra parameters are purposedly not exposed for now. + // The extra parameters are purposely not exposed for now. return hera::wasserstein_dist(diag1, diag2, params); } diff --git a/src/python/gudhi/persistence_graphical_tools.py b/src/python/gudhi/persistence_graphical_tools.py index 7ed11360..21275cdd 100644 --- a/src/python/gudhi/persistence_graphical_tools.py +++ b/src/python/gudhi/persistence_graphical_tools.py @@ -332,7 +332,7 @@ def plot_persistence_diagram( axes.plot([axis_start, axis_end], [infinity, infinity], linewidth=1.0, color="k", alpha=alpha) # Infinity label yt = axes.get_yticks() - yt = yt[np.where(yt < axis_end)] # to avoid ploting ticklabel higher than infinity + yt = yt[np.where(yt < axis_end)] # to avoid plotting ticklabel higher than infinity yt = np.append(yt, infinity) ytl = ["%.3f" % e for e in yt] # to avoid float precision error ytl[-1] = r"$+\infty$" diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd index 4f229663..5642f82d 100644 --- a/src/python/gudhi/simplex_tree.pxd +++ b/src/python/gudhi/simplex_tree.pxd @@ -63,7 +63,6 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": bool prune_above_filtration(double filtration) nogil bool make_filtration_non_decreasing() nogil void compute_extended_filtration() nogil - vector[vector[pair[int, pair[double, double]]]] compute_extended_persistence_subdiagrams(vector[pair[int, pair[double, double]]] dgm, double min_persistence) nogil Simplex_tree_interface_full_featured* collapse_edges(int nb_collapse_iteration) nogil except + void reset_filtration(double filtration, int dimension) nogil bint operator==(Simplex_tree_interface_full_featured) nogil @@ -81,7 +80,7 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": void expansion_with_blockers_callback(int dimension, blocker_func_t user_func, void *user_data) cdef extern from "Persistent_cohomology_interface.h" namespace "Gudhi": - cdef cppclass Simplex_tree_persistence_interface "Gudhi::Persistent_cohomology_interface<Gudhi::Simplex_tree<Gudhi::Simplex_tree_options_full_featured>>": + cdef cppclass Simplex_tree_persistence_interface "Gudhi::Persistent_cohomology_interface<Gudhi::Simplex_tree_interface<Gudhi::Simplex_tree_options_full_featured>>": Simplex_tree_persistence_interface(Simplex_tree_interface_full_featured * st, bool persistence_dim_max) nogil void compute_persistence(int homology_coeff_field, double min_persistence) nogil except + vector[pair[int, pair[double, double]]] get_persistence() nogil @@ -92,3 +91,4 @@ cdef extern from "Persistent_cohomology_interface.h" namespace "Gudhi": vector[pair[vector[int], vector[int]]] persistence_pairs() nogil pair[vector[vector[int]], vector[vector[int]]] lower_star_generators() nogil pair[vector[vector[int]], vector[vector[int]]] flag_generators() nogil + vector[vector[pair[int, pair[double, double]]]] compute_extended_persistence_subdiagrams(double min_persistence) nogil diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index a4914184..521a7763 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -474,8 +474,7 @@ cdef class SimplexTree: del self.pcohptr self.pcohptr = new Simplex_tree_persistence_interface(self.get_ptr(), False) self.pcohptr.compute_persistence(homology_coeff_field, -1.) - persistence_result = self.pcohptr.get_persistence() - return self.get_ptr().compute_extended_persistence_subdiagrams(persistence_result, min_persistence) + return self.pcohptr.compute_extended_persistence_subdiagrams(min_persistence) def expansion_with_blocker(self, max_dim, blocker_func): """Expands the Simplex_tree containing only a graph. Simplices corresponding to cliques in the graph are added @@ -676,18 +675,17 @@ cdef class SimplexTree: return (normal0, normals, infinite0, infinites) def collapse_edges(self, nb_iterations = 1): - """Assuming the simplex tree is a 1-skeleton graph, this method collapse edges (simplices of higher dimension - are ignored) and resets the simplex tree from the remaining edges. - A good candidate is to build a simplex tree on top of a :class:`~gudhi.RipsComplex` of dimension 1 before - collapsing edges + """Assuming the complex is a graph (simplices of higher dimension are ignored), this method implicitly + interprets it as the 1-skeleton of a flag complex, and replaces it with another (smaller) graph whose + expansion has the same persistent homology, using a technique known as edge collapses + (see :cite:`edgecollapsearxiv`). + + A natural application is to get a simplex tree of dimension 1 from :class:`~gudhi.RipsComplex`, + then collapse edges, perform :meth:`expansion()` and finally compute persistence (cf. :download:`rips_complex_edge_collapse_example.py <../example/rips_complex_edge_collapse_example.py>`). - For implementation details, please refer to :cite:`edgecollapsesocg2020`. :param nb_iterations: The number of edge collapse iterations to perform. Default is 1. :type nb_iterations: int - - :note: collapse_edges method requires `Eigen <installation.html#eigen>`_ >= 3.1.0 and an exception is thrown - if this method is not available. """ # Backup old pointer cdef Simplex_tree_interface_full_featured* ptr = self.get_ptr() diff --git a/src/python/gudhi/wasserstein/barycenter.py b/src/python/gudhi/wasserstein/barycenter.py index d67bcde7..bb6e641e 100644 --- a/src/python/gudhi/wasserstein/barycenter.py +++ b/src/python/gudhi/wasserstein/barycenter.py @@ -37,7 +37,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): :param init: The initial value for barycenter estimate. If ``None``, init is made on a random diagram from the dataset. Otherwise, it can be an ``int`` (then initialization is made on ``pdiagset[init]``) - or a `(n x 2)` ``numpy.array`` enconding a persistence diagram with `n` points. + or a `(n x 2)` ``numpy.array`` encoding a persistence diagram with `n` points. :type init: ``int``, or (n x 2) ``np.array`` :param verbose: if ``True``, returns additional information about the barycenter. :type verbose: boolean @@ -45,7 +45,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): (local minimum of the energy function). If ``pdiagset`` is empty, returns ``None``. If verbose, returns a couple ``(Y, log)`` where ``Y`` is the barycenter estimate, - and ``log`` is a ``dict`` that contains additional informations: + and ``log`` is a ``dict`` that contains additional information: - `"groupings"`, a list of list of pairs ``(i,j)``. Namely, ``G[k] = [...(i, j)...]``, where ``(i,j)`` indicates that `pdiagset[k][i]`` is matched to ``Y[j]`` if ``i = -1`` or ``j = -1``, it means they represent the diagonal. @@ -73,7 +73,7 @@ def lagrangian_barycenter(pdiagset, init=None, verbose=False): nb_iter = 0 - converged = False # stoping criterion + converged = False # stopping criterion while not converged: nb_iter += 1 K = len(Y) # current nb of points in Y (some might be on diagonal) diff --git a/src/python/include/Persistent_cohomology_interface.h b/src/python/include/Persistent_cohomology_interface.h index e5a3dfba..945378a0 100644 --- a/src/python/include/Persistent_cohomology_interface.h +++ b/src/python/include/Persistent_cohomology_interface.h @@ -12,6 +12,8 @@ #define INCLUDE_PERSISTENT_COHOMOLOGY_INTERFACE_H_ #include <gudhi/Persistent_cohomology.h> +#include <gudhi/Simplex_tree.h> // for Extended_simplex_type + #include <cstdlib> #include <vector> @@ -223,6 +225,44 @@ persistent_cohomology::Persistent_cohomology<FilteredComplex, persistent_cohomol return out; } + using Filtration_value = typename FilteredComplex::Filtration_value; + using Birth_death = std::pair<Filtration_value, Filtration_value>; + using Persistence_subdiagrams = std::vector<std::vector<std::pair<int, Birth_death>>>; + + Persistence_subdiagrams compute_extended_persistence_subdiagrams(Filtration_value min_persistence){ + Persistence_subdiagrams pers_subs(4); + auto const& persistent_pairs = Base::get_persistent_pairs(); + for (auto pair : persistent_pairs) { + std::pair<Filtration_value, Extended_simplex_type> px = stptr_->decode_extended_filtration(stptr_->filtration(get<0>(pair)), + stptr_->efd); + std::pair<Filtration_value, Extended_simplex_type> py = stptr_->decode_extended_filtration(stptr_->filtration(get<1>(pair)), + stptr_->efd); + std::pair<int, Birth_death> pd_point = std::make_pair(stptr_->dimension(get<0>(pair)), + std::make_pair(px.first, py.first)); + if(std::abs(px.first - py.first) > min_persistence){ + //Ordinary + if (px.second == Extended_simplex_type::UP && py.second == Extended_simplex_type::UP){ + pers_subs[0].push_back(pd_point); + } + // Relative + else if (px.second == Extended_simplex_type::DOWN && py.second == Extended_simplex_type::DOWN){ + pers_subs[1].push_back(pd_point); + } + else{ + // Extended+ + if (px.first < py.first){ + pers_subs[2].push_back(pd_point); + } + //Extended- + else{ + pers_subs[3].push_back(pd_point); + } + } + } + } + return pers_subs; + } + private: // A copy FilteredComplex* stptr_; diff --git a/src/python/include/Simplex_tree_interface.h b/src/python/include/Simplex_tree_interface.h index aa3dac18..3848c5ad 100644 --- a/src/python/include/Simplex_tree_interface.h +++ b/src/python/include/Simplex_tree_interface.h @@ -15,9 +15,7 @@ #include <gudhi/distance_functions.h> #include <gudhi/Simplex_tree.h> #include <gudhi/Points_off_io.h> -#ifdef GUDHI_USE_EIGEN3 #include <gudhi/Flag_complex_edge_collapser.h> -#endif #include <iostream> #include <vector> @@ -134,38 +132,7 @@ class Simplex_tree_interface : public Simplex_tree<SimplexTreeOptions> { return; } - std::vector<std::vector<std::pair<int, std::pair<Filtration_value, Filtration_value>>>> compute_extended_persistence_subdiagrams(const std::vector<std::pair<int, std::pair<Filtration_value, Filtration_value>>>& dgm, Filtration_value min_persistence){ - std::vector<std::vector<std::pair<int, std::pair<Filtration_value, Filtration_value>>>> new_dgm(4); - for (unsigned int i = 0; i < dgm.size(); i++){ - std::pair<Filtration_value, Extended_simplex_type> px = this->decode_extended_filtration(dgm[i].second.first, this->efd); - std::pair<Filtration_value, Extended_simplex_type> py = this->decode_extended_filtration(dgm[i].second.second, this->efd); - std::pair<int, std::pair<Filtration_value, Filtration_value>> pd_point = std::make_pair(dgm[i].first, std::make_pair(px.first, py.first)); - if(std::abs(px.first - py.first) > min_persistence){ - //Ordinary - if (px.second == Extended_simplex_type::UP && py.second == Extended_simplex_type::UP){ - new_dgm[0].push_back(pd_point); - } - // Relative - else if (px.second == Extended_simplex_type::DOWN && py.second == Extended_simplex_type::DOWN){ - new_dgm[1].push_back(pd_point); - } - else{ - // Extended+ - if (px.first < py.first){ - new_dgm[2].push_back(pd_point); - } - //Extended- - else{ - new_dgm[3].push_back(pd_point); - } - } - } - } - return new_dgm; - } - Simplex_tree_interface* collapse_edges(int nb_collapse_iteration) { -#ifdef GUDHI_USE_EIGEN3 using Filtered_edge = std::tuple<Vertex_handle, Vertex_handle, Filtration_value>; std::vector<Filtered_edge> edges; for (Simplex_handle sh : Base::skeleton_simplex_range(1)) { @@ -179,7 +146,7 @@ class Simplex_tree_interface : public Simplex_tree<SimplexTreeOptions> { } for (int iteration = 0; iteration < nb_collapse_iteration; iteration++) { - edges = Gudhi::collapse::flag_complex_collapse_edges(edges); + edges = Gudhi::collapse::flag_complex_collapse_edges(std::move(edges)); } Simplex_tree_interface* collapsed_stree_ptr = new Simplex_tree_interface(); // Copy the original 0-skeleton @@ -191,9 +158,6 @@ class Simplex_tree_interface : public Simplex_tree<SimplexTreeOptions> { collapsed_stree_ptr->insert({std::get<0>(remaining_edge), std::get<1>(remaining_edge)}, std::get<2>(remaining_edge)); } return collapsed_stree_ptr; -#else - throw std::runtime_error("Unable to collapse edges as it requires Eigen3 >= 3.1.0."); -#endif } void expansion_with_blockers_callback(int dimension, blocker_func_t user_func, void *user_data) { diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index eb481a49..54bafed5 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -8,7 +8,7 @@ - YYYY/MM Author: Description of the modification """ -from gudhi import SimplexTree, __GUDHI_USE_EIGEN3 +from gudhi import SimplexTree import numpy as np import pytest @@ -320,6 +320,10 @@ def test_extend_filtration(): ] dgms = st.extended_persistence(min_persistence=-1.) + assert len(dgms) == 4 + # Sort by (death-birth) descending - we are only interested in those with the longest life span + for idx in range(4): + dgms[idx] = sorted(dgms[idx], key=lambda x:(-abs(x[1][0]-x[1][1]))) assert dgms[0][0][1][0] == pytest.approx(2.) assert dgms[0][0][1][1] == pytest.approx(3.) @@ -354,16 +358,11 @@ def test_collapse_edges(): assert st.num_simplices() == 10 - if __GUDHI_USE_EIGEN3: - st.collapse_edges() - assert st.num_simplices() == 9 - assert st.find([1, 3]) == False - for simplex in st.get_skeleton(0): - assert simplex[1] == 1. - else: - # If no Eigen3, collapse_edges throws an exception - with pytest.raises(RuntimeError): - st.collapse_edges() + st.collapse_edges() + assert st.num_simplices() == 9 + assert st.find([0, 2]) == False # [1, 3] would be fine as well + for simplex in st.get_skeleton(0): + assert simplex[1] == 1. def test_reset_filtration(): st = SimplexTree() @@ -533,7 +532,7 @@ def test_expansion_with_blocker(): def blocker(simplex): try: - # Block all simplices that countains vertex 6 + # Block all simplices that contain vertex 6 simplex.index(6) print(simplex, ' is blocked') return True diff --git a/src/python/test/test_subsampling.py b/src/python/test/test_subsampling.py index 4019852e..3431f372 100755 --- a/src/python/test/test_subsampling.py +++ b/src/python/test/test_subsampling.py @@ -91,7 +91,7 @@ def test_simple_choose_n_farthest_points_randomed(): assert gudhi.choose_n_farthest_points(points=[], nb_points=1) == [] assert gudhi.choose_n_farthest_points(points=point_set, nb_points=0) == [] - # Go furter than point set on purpose + # Go further than point set on purpose for iter in range(1, 10): sub_set = gudhi.choose_n_farthest_points(points=point_set, nb_points=iter) for sub in sub_set: @@ -117,7 +117,7 @@ def test_simple_pick_n_random_points(): assert gudhi.pick_n_random_points(points=[], nb_points=1) == [] assert gudhi.pick_n_random_points(points=point_set, nb_points=0) == [] - # Go furter than point set on purpose + # Go further than point set on purpose for iter in range(1, 10): sub_set = gudhi.pick_n_random_points(points=point_set, nb_points=iter) for sub in sub_set: |
