diff options
Diffstat (limited to 'src/python/doc')
50 files changed, 1516 insertions, 611 deletions
diff --git a/src/python/doc/_templates/layout.html b/src/python/doc/_templates/layout.html index 2f2d9c72..e074b6c7 100644 --- a/src/python/doc/_templates/layout.html +++ b/src/python/doc/_templates/layout.html @@ -175,58 +175,60 @@ <h1 class="show-for-small-only"><a href="" class="icon-tree"> GUDHI library</a></h1> </li> <!-- Remove the class "menu-icon" to get rid of menu icon. Take out "Menu" to just have icon alone --> - <li class="toggle-topbar menu-icon"><a href="#"><span>Navigation</span></a></li> + <li class="toggle-topbar menu-icon"><a href="#"><span>Nav</span></a></li> </ul> <section class="top-bar-section"> <ul class="right"> <li class="divider"></li> - <li><a href="/contact/">Contact</a></li> + <li><a href="/contact/">Contact</a></li> </ul> <ul class="left"> - <li><a href="/"> <img src="/assets/img/home.png" alt=" GUDHI"> GUDHI </a></li> + <li><a href="/"> <img src="/assets/img/home.png" alt=" GUDHI"> GUDHI </a></li> <li class="divider"></li> <li class="has-dropdown"> - <a href="#">Project</a> + <a href="#">Project</a> <ul class="dropdown"> - <li><a href="/people/">People</a></li> - <li><a href="/keepintouch/">Keep in touch</a></li> - <li><a href="/partners/">Partners and Funding</a></li> - <li><a href="/relatedprojects/">Related projects</a></li> - <li><a href="/theyaretalkingaboutus/">They are talking about us</a></li> - <li><a href="/inaction/">GUDHI in action</a></li> + <li><a href="/people/">People</a></li> + <li><a href="/keepintouch/">Keep in touch</a></li> + <li><a href="/partners/">Partners and Funding</a></li> + <li><a href="/relatedprojects/">Related projects</a></li> + <li><a href="/theyaretalkingaboutus/">They are talking about us</a></li> + <li><a href="/inaction/">GUDHI in action</a></li> + <li><a href="/etymology/">Etymology</a></li> </ul> </li> <li class="divider"></li> <li class="has-dropdown"> - <a href="#">Download</a> + <a href="#">Download</a> <ul class="dropdown"> - <li><a href="/licensing/">Licensing</a></li> - <li><a href="https://gforge.inria.fr/frs/download.php/latestzip/5253/library-latest.zip" target="_blank">Get the latest sources</a></li> - <li><a href="/conda/">Conda package</a></li> - <li><a href="/dockerfile/">Dockerfile</a></li> + <li><a href="/licensing/">Licensing</a></li> + <li><a href="https://github.com/GUDHI/gudhi-devel/releases/latest" target="_blank">Get the latest sources</a></li> + <li><a href="/conda/">Conda package</a></li> + <li><a href="https://pypi.org/project/gudhi/" target="_blank">Pip package</a></li> + <li><a href="/dockerfile/">Dockerfile</a></li> </ul> </li> <li class="divider"></li> <li class="has-dropdown"> - <a href="#">Documentation</a> + <a href="#">Documentation</a> <ul class="dropdown"> - <li><a href="/introduction/">Introduction</a></li> - <li><a href="https://gudhi.inria.fr/doc/latest/installation.html">C++ installation manual</a></li> - <li><a href="https://gudhi.inria.fr/doc/latest/">C++ documentation</a></li> - <li><a href="https://gudhi.inria.fr/python/latest/installation.html">Python installation manual</a></li> - <li><a href="https://gudhi.inria.fr/python/latest/">Python documentation</a></li> - <li><a href="/utils/">Utilities</a></li> - <li><a href="/tutorials/">Tutorials</a></li> + <li><a href="/introduction/">Introduction</a></li> + <li><a href="/doc/latest/installation.html">C++ installation manual</a></li> + <li><a href="/doc/latest/">C++ documentation</a></li> + <li><a href="/python/latest/installation.html">Python installation manual</a></li> + <li><a href="/python/latest/">Python documentation</a></li> + <li><a href="/utils/">Utilities</a></li> + <li><a href="/tutorials/">Tutorials</a></li> </ul> </li> <li class="divider"></li> - <li><a href="/interfaces/">Interfaces</a></li> + <li><a href="/interfaces/">Interfaces</a></li> <li class="divider"></li> </ul> </section> </nav> - </div><!-- /#navigation --> - <!-- GUDHI website header BEGIN --> + </div><!-- /#navigation --> + <!-- GUDHI website header END --> {%- block header %}{% endblock %} diff --git a/src/python/doc/alpha_complex_ref.rst b/src/python/doc/alpha_complex_ref.rst index 7da79543..eaa72551 100644 --- a/src/python/doc/alpha_complex_ref.rst +++ b/src/python/doc/alpha_complex_ref.rst @@ -9,6 +9,5 @@ Alpha complex reference manual .. autoclass:: gudhi.AlphaComplex :members: :undoc-members: - :show-inheritance: .. automethod:: gudhi.AlphaComplex.__init__ diff --git a/src/python/doc/alpha_complex_sum.inc b/src/python/doc/alpha_complex_sum.inc index b5af0d27..5c76fd54 100644 --- a/src/python/doc/alpha_complex_sum.inc +++ b/src/python/doc/alpha_complex_sum.inc @@ -1,17 +1,15 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------+ - | .. figure:: | Alpha complex is a simplicial complex constructed from the finite | :Author: Vincent Rouvreau | - | ../../doc/Alpha_complex/alpha_complex_representation.png | cells of a Delaunay Triangulation. | | - | :alt: Alpha complex representation | | :Introduced in: GUDHI 2.0.0 | - | :figclass: align-center | The filtration value of each simplex is computed as the **square** of | | - | | the circumradius of the simplex if the circumsphere is empty (the | :Copyright: MIT (`GPL v3 </licensing/>`_) | - | | simplex is then said to be Gabriel), and as the minimum of the | | - | | filtration values of the codimension 1 cofaces that make it not | :Requires: `Eigen <installation.html#eigen>`__ :math:`\geq` 3.1.0 and `CGAL <installation.html#cgal>`__ :math:`\geq` 4.11.0 | - | | Gabriel otherwise. | | - | | | | - | | For performances reasons, it is advised to use CGAL ≥ 5.0.0. | | - +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------+ - | * :doc:`alpha_complex_user` | * :doc:`alpha_complex_ref` | - +----------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ + +----------------------------------------------------------------+-------------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------+ + | .. figure:: | Alpha complex is a simplicial complex constructed from the finite | :Author: Vincent Rouvreau | + | ../../doc/Alpha_complex/alpha_complex_representation.png | cells of a Delaunay Triangulation. It has the same persistent homology | | + | :alt: Alpha complex representation | as the Čech complex and is significantly smaller. | :Since: GUDHI 2.0.0 | + | :figclass: align-center | | | + | | | :License: MIT (`GPL v3 </licensing/>`_) | + | | | | + | | | :Requires: `Eigen <installation.html#eigen>`_ :math:`\geq` 3.1.0 and `CGAL <installation.html#cgal>`_ :math:`\geq` 5.1 | + | | | | + +----------------------------------------------------------------+-------------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------+ + | * :doc:`alpha_complex_user` | * :doc:`alpha_complex_ref` | + +----------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/alpha_complex_user.rst b/src/python/doc/alpha_complex_user.rst index 60319e84..9e67d38a 100644 --- a/src/python/doc/alpha_complex_user.rst +++ b/src/python/doc/alpha_complex_user.rst @@ -9,15 +9,31 @@ Definition .. include:: alpha_complex_sum.inc -`AlphaComplex` is constructing a :doc:`SimplexTree <simplex_tree_ref>` using -`Delaunay Triangulation <http://doc.cgal.org/latest/Triangulation/index.html#Chapter_Triangulations>`_ -:cite:`cgal:hdj-t-19b` from `CGAL <http://www.cgal.org/>`_ (the Computational Geometry Algorithms Library -:cite:`cgal:eb-19b`). +:class:`~gudhi.AlphaComplex` is constructing a :doc:`SimplexTree <simplex_tree_ref>` using +`Delaunay Triangulation <http://doc.cgal.org/latest/Triangulation/index.html#Chapter_Triangulations>`_ +:cite:`cgal:hdj-t-19b` from the `Computational Geometry Algorithms Library <http://www.cgal.org/>`_ +:cite:`cgal:eb-19b`. Remarks ^^^^^^^ -When an :math:`\alpha`-complex is constructed with an infinite value of :math:`\alpha^2`, -the complex is a Delaunay complex (with special filtration values). +* When an :math:`\alpha`-complex is constructed with an infinite value of :math:`\alpha^2`, the complex is a Delaunay + complex (with special filtration values). The Delaunay complex without filtration values is also available by + passing :code:`default_filtration_value = True` to :func:`~gudhi.AlphaComplex.create_simplex_tree`. +* For people only interested in the topology of the Alpha complex (for instance persistence), Alpha complex is + equivalent to the `Čech complex <https://gudhi.inria.fr/doc/latest/group__cech__complex.html>`_ and much smaller if + you do not bound the radii. `Čech complex <https://gudhi.inria.fr/doc/latest/group__cech__complex.html>`_ can still + make sense in higher dimension precisely because you can bound the radii. +* Using the default :code:`precision = 'safe'` makes the construction safe. + If you pass :code:`precision = 'exact'` to :func:`~gudhi.AlphaComplex.__init__`, the filtration values are the exact + ones converted to float. This can be very slow. + If you pass :code:`precision = 'safe'` (the default), the filtration values are only + guaranteed to have a small multiplicative error compared to the exact value, see + :func:`~gudhi.AlphaComplex.set_float_relative_precision` to modify the precision. + A drawback, when computing persistence, is that an empty exact interval [10^12,10^12] may become a + non-empty approximate interval [10^12,10^12+10^6]. + Using :code:`precision = 'fast'` makes the computations slightly faster, and the combinatorics are still exact, but + the computation of filtration values can exceptionally be arbitrarily bad. In all cases, we still guarantee that the + output is a valid filtration (faces have a filtration value no larger than their cofaces). Example from points ------------------- @@ -26,23 +42,22 @@ This example builds the alpha-complex from the given points: .. testcode:: - import gudhi - alpha_complex = gudhi.AlphaComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]]) + from gudhi import AlphaComplex + ac = AlphaComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]]) + + stree = ac.create_simplex_tree() + print('Alpha complex is of dimension ', stree.dimension(), ' - ', + stree.num_simplices(), ' simplices - ', stree.num_vertices(), ' vertices.') - simplex_tree = alpha_complex.create_simplex_tree() - result_str = 'Alpha complex is of dimension ' + repr(simplex_tree.dimension()) + ' - ' + \ - repr(simplex_tree.num_simplices()) + ' simplices - ' + \ - repr(simplex_tree.num_vertices()) + ' vertices.' - print(result_str) fmt = '%s -> %.2f' - for filtered_value in simplex_tree.get_filtration(): + for filtered_value in stree.get_filtration(): print(fmt % tuple(filtered_value)) The output is: .. testoutput:: - Alpha complex is of dimension 2 - 25 simplices - 7 vertices. + Alpha complex is of dimension 2 - 25 simplices - 7 vertices. [0] -> 0.00 [1] -> 0.00 [2] -> 0.00 @@ -89,25 +104,28 @@ In order to build the alpha complex, first, a Simplex tree is built from the cel Filtration value computation algorithm ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - **for** i : dimension :math:`\rightarrow` 0 **do** - **for all** :math:`\sigma` of dimension i - **if** filtration(:math:`\sigma`) is NaN **then** - filtration(:math:`\sigma`) = :math:`\alpha^2(\sigma)` - **end if** - - *//propagate alpha filtration value* - - **for all** :math:`\tau` face of :math:`\sigma` - **if** filtration(:math:`\tau`) is not NaN **then** - filtration(:math:`\tau`) = filtration(:math:`\sigma`) - **end if** - **end for** - **end for** - **end for** +.. code-block:: vim + + for i : dimension → 0 do + for all σ of dimension i + if filtration(σ) is NaN then + filtration(σ) = α²(σ) + end if + for all τ face of σ do // propagate alpha filtration value + if filtration(τ) is not NaN then + filtration(τ) = min( filtration(τ), filtration(σ) ) + else + if τ is not Gabriel for σ then + filtration(τ) = filtration(σ) + end if + end if + end for + end for + end for + + make_filtration_non_decreasing() + prune_above_filtration() - make_filtration_non_decreasing() - - prune_above_filtration() Dimension 2 ^^^^^^^^^^^ @@ -142,7 +160,10 @@ As the squared radii computed by CGAL are an approximation, it might happen that :math:`\alpha^2` values do not quite define a proper filtration (i.e. non-decreasing with respect to inclusion). We fix that up by calling :func:`~gudhi.SimplexTree.make_filtration_non_decreasing` (cf. -`C++ version <http://gudhi.gforge.inria.fr/doc/latest/index.html>`_). +`C++ version <https://gudhi.inria.fr/doc/latest/class_gudhi_1_1_simplex__tree.html>`_). + +.. note:: + This is not the case in `exact` version, this is the reason why it is not called in this case. Prune above given filtration value ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -153,59 +174,86 @@ of speed-up, since we always first build the full filtered complex, so it is rec :paramref:`~gudhi.AlphaComplex.create_simplex_tree.max_alpha_square`. In the following example, a threshold of :math:`\alpha^2 = 32.0` is used. +Weighted version +^^^^^^^^^^^^^^^^ -Example from OFF file -^^^^^^^^^^^^^^^^^^^^^ +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#TriangulationSecRT>`_. -This example builds the Delaunay triangulation from the points given by an OFF file, and initializes the alpha complex -with it. +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#AlphaShape_3DExampleforWeightedAlphaShapes>`_. - -Then, it is asked to display information about the alpha complex: +Then, it is asked to display information about the alpha complex. .. testcode:: - import gudhi - alpha_complex = gudhi.AlphaComplex(off_file=gudhi.__root_source_dir__ + \ - '/data/points/alphacomplexdoc.off') - simplex_tree = alpha_complex.create_simplex_tree(max_alpha_square=32.0) - result_str = 'Alpha complex is of dimension ' + repr(simplex_tree.dimension()) + ' - ' + \ - repr(simplex_tree.num_simplices()) + ' simplices - ' + \ - repr(simplex_tree.num_vertices()) + ' vertices.' - print(result_str) + from gudhi import AlphaComplex + wgt_ac = AlphaComplex(points=[[ 1., -1., -1.], + [-1., 1., -1.], + [-1., -1., 1.], + [ 1., 1., 1.], + [ 2., 2., 2.]], + weights = [4., 4., 4., 4., 1.]) + + stree = wgt_ac.create_simplex_tree() + print('Weighted alpha complex is of dimension ', stree.dimension(), ' - ', + stree.num_simplices(), ' simplices - ', stree.num_vertices(), ' vertices.') fmt = '%s -> %.2f' - for filtered_value in simplex_tree.get_filtration(): - print(fmt % tuple(filtered_value)) + for simplex in stree.get_simplices(): + print(fmt % tuple(simplex)) -the program output is: +The output is: .. testoutput:: - Alpha complex is of dimension 2 - 20 simplices - 7 vertices. - [0] -> 0.00 - [1] -> 0.00 - [2] -> 0.00 - [3] -> 0.00 - [4] -> 0.00 - [5] -> 0.00 - [6] -> 0.00 - [2, 3] -> 6.25 - [4, 5] -> 7.25 - [0, 2] -> 8.50 - [0, 1] -> 9.25 - [1, 3] -> 10.00 - [1, 2] -> 11.25 - [1, 2, 3] -> 12.50 - [0, 1, 2] -> 13.00 - [5, 6] -> 13.25 - [2, 4] -> 20.00 - [4, 6] -> 22.74 - [4, 5, 6] -> 22.74 - [3, 6] -> 30.25 + Weighted alpha complex is of dimension 3 - 29 simplices - 5 vertices. + [0, 1, 2, 3] -> -1.00 + [0, 1, 2] -> -1.33 + [0, 1, 3, 4] -> 95.00 + [0, 1, 3] -> -1.33 + [0, 1, 4] -> 95.00 + [0, 1] -> -2.00 + [0, 2, 3, 4] -> 95.00 + [0, 2, 3] -> -1.33 + [0, 2, 4] -> 95.00 + [0, 2] -> -2.00 + [0, 3, 4] -> 23.00 + [0, 3] -> -2.00 + [0, 4] -> 23.00 + [0] -> -4.00 + [1, 2, 3, 4] -> 95.00 + [1, 2, 3] -> -1.33 + [1, 2, 4] -> 95.00 + [1, 2] -> -2.00 + [1, 3, 4] -> 23.00 + [1, 3] -> -2.00 + [1, 4] -> 23.00 + [1] -> -4.00 + [2, 3, 4] -> 23.00 + [2, 3] -> -2.00 + [2, 4] -> 23.00 + [2] -> -4.00 + [3, 4] -> -1.00 + [3] -> -4.00 + [4] -> -1.00 + +Example from OFF file +^^^^^^^^^^^^^^^^^^^^^ + +This example builds the alpha complex from 300 random points on a 2-torus, given by an +`OFF file <fileformats.html#off-file-format>`_. + +Then, it computes the persistence diagram and displays it: -CGAL citations -============== +.. plot:: + :include-source: -.. bibliography:: ../../biblio/how_to_cite_cgal.bib - :filter: docnames - :style: unsrt + import matplotlib.pyplot as plt + import gudhi as gd + off_file = gd.__root_source_dir__ + '/data/points/tore3D_300.off' + points = gd.read_points_from_off_file(off_file = off_file) + stree = gd.AlphaComplex(points = points).create_simplex_tree() + dgm = stree.persistence() + gd.plot_persistence_diagram(dgm, legend = True) + plt.show() diff --git a/src/python/doc/bottleneck_distance_sum.inc b/src/python/doc/bottleneck_distance_sum.inc index 6eb0ac19..77dc368d 100644 --- a/src/python/doc/bottleneck_distance_sum.inc +++ b/src/python/doc/bottleneck_distance_sum.inc @@ -1,14 +1,14 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ - | .. figure:: | Bottleneck distance measures the similarity between two persistence | :Author: François Godi | - | ../../doc/Bottleneck_distance/perturb_pd.png | diagrams. It's the shortest distance b for which there exists a | | - | :figclass: align-center | perfect matching between the points of the two diagrams (+ all the | :Introduced in: GUDHI 2.0.0 | - | | diagonal points) such that any couple of matched points are at | | - | Bottleneck distance is the length of | distance at most b, where the distance between points is the sup | :Copyright: MIT (`GPL v3 </licensing/>`_) | - | the longest edge | norm in :math:`\mathbb{R}^2`. | | - | | | :Requires: `CGAL <installation.html#cgal>`__ :math:`\geq` 4.11.0 | - +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ - | * :doc:`bottleneck_distance_user` | | - +-----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+ + +-----------------------------------------------------------------+----------------------------------------------------------------------+-----------------------------------------------------------------+ + | .. figure:: | Bottleneck distance measures the similarity between two persistence | :Author: François Godi | + | ../../doc/Bottleneck_distance/perturb_pd.png | diagrams. It's the shortest distance b for which there exists a | | + | :figclass: align-center | perfect matching between the points of the two diagrams (+ all the | :Since: GUDHI 2.0.0 | + | | diagonal points) such that any couple of matched points are at | | + | Bottleneck distance is the length of | distance at most b, where the distance between points is the sup | :License: MIT (`GPL v3 </licensing/>`_) | + | the longest edge | norm in :math:`\mathbb{R}^2`. | | + | | | :Requires: `CGAL <installation.html#cgal>`_ :math:`\geq` 4.11.0 | + +-----------------------------------------------------------------+----------------------------------------------------------------------+-----------------------------------------------------------------+ + | * :doc:`bottleneck_distance_user` | | + +-----------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/bottleneck_distance_user.rst b/src/python/doc/bottleneck_distance_user.rst index 9435c7f1..7baa76cc 100644 --- a/src/python/doc/bottleneck_distance_user.rst +++ b/src/python/doc/bottleneck_distance_user.rst @@ -9,14 +9,23 @@ Definition .. include:: bottleneck_distance_sum.inc -This implementation is based on ideas from "Geometry Helps in Bottleneck Matching and Related Problems" -:cite:`DBLP:journals/algorithmica/EfratIK01`. Another relevant publication, although it was not used is -"Geometry Helps to Compare Persistence Diagrams" :cite:`Kerber:2017:GHC:3047249.3064175`. +This implementation by François Godi is based on ideas from "Geometry Helps in Bottleneck Matching and Related Problems" +:cite:`DBLP:journals/algorithmica/EfratIK01` and requires `CGAL <installation.html#cgal>`_ (`GPL v3 </licensing/>`_). -Function --------- .. autofunction:: gudhi.bottleneck_distance +This other implementation comes from `Hera +<https://bitbucket.org/grey_narn/hera/src/master/>`_ (BSD-3-Clause) which is +based on "Geometry Helps to Compare Persistence Diagrams" +:cite:`Kerber:2017:GHC:3047249.3064175` by Michael Kerber, Dmitriy +Morozov, and Arnur Nigmetov. + +.. warning:: + Beware that its approximation allows for a multiplicative error, while the function above uses an additive error. + +.. autofunction:: gudhi.hera.bottleneck_distance + + Distance computation -------------------- @@ -38,7 +47,7 @@ The following example explains how the distance is computed: :figclass: align-center The point (0, 13) is at distance 6.5 from the diagonal and more - specifically from the point (6.5, 6.5) + specifically from the point (6.5, 6.5). Basic example @@ -63,5 +72,6 @@ The output is: .. testoutput:: - Bottleneck distance approximation = 0.81 + Bottleneck distance approximation = 0.72 Bottleneck distance value = 0.75 + diff --git a/src/python/doc/clustering.inc b/src/python/doc/clustering.inc new file mode 100644 index 00000000..2d07ae88 --- /dev/null +++ b/src/python/doc/clustering.inc @@ -0,0 +1,12 @@ +.. table:: + :widths: 30 40 30 + + +--------------------------+-------------------------------------------------------+---------------------------------+ + | .. figure:: | Clustering tools. | :Author: Marc Glisse | + | img/spiral-color.png | | | + | | | :Since: GUDHI 3.3.0 | + | | | | + | | | :License: MIT | + +--------------------------+-------------------------------------------------------+---------------------------------+ + | * :doc:`clustering` | + +--------------------------+-----------------------------------------------------------------------------------------+ diff --git a/src/python/doc/clustering.rst b/src/python/doc/clustering.rst new file mode 100644 index 00000000..62422682 --- /dev/null +++ b/src/python/doc/clustering.rst @@ -0,0 +1,72 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +================= +Clustering manual +================= + +We provide an implementation of ToMATo :cite:`tomato`, a persistence-based clustering algorithm. In short, this algorithm uses a density estimator and a neighborhood graph, starts with a mode-seeking phase (naive hill-climbing) to build initial clusters, and finishes by merging clusters based on their prominence. + +The merging phase depends on a parameter, which is the minimum prominence a cluster needs to avoid getting merged into another, bigger cluster. This parameter determines the number of clusters, and for convenience we allow you to choose instead the number of clusters. Decreasing the prominence threshold defines a hierarchy of clusters: if 2 points are in separate clusters when we have k clusters, they are still in different clusters for k+1 clusters. + +As a by-product, we produce the persistence diagram of the merge tree of the initial clusters. This is a convenient graphical tool to help decide how many clusters we want. + +.. plot:: + :context: + :include-source: + + import gudhi + from gudhi.datasets.remote import fetch_spiral_2d + data = fetch_spiral_2d() + import matplotlib.pyplot as plt + plt.scatter(data[:,0],data[:,1],marker='.',s=1) + plt.show() + +.. plot:: + :context: close-figs + :include-source: + + from gudhi.clustering.tomato import Tomato + t = Tomato() + t.fit(data) + t.plot_diagram() + +As one can see in `t.n_clusters_`, the algorithm found 6316 initial clusters. The diagram shows their prominence as their distance to the diagonal. There is always one point infinitely far: there is at least one cluster. Among the others, one point seems significantly farther from the diagonal than the others, which indicates that splitting the points into 2 clusters may be a sensible idea. + +.. plot:: + :context: close-figs + :include-source: + + t.n_clusters_=2 + plt.scatter(data[:,0],data[:,1],marker='.',s=1,c=t.labels_) + plt.show() + +Of course this is just the result for one set of parameters. We can ask for a different density estimator and a different neighborhood graph computed with different parameters. + +.. plot:: + :context: close-figs + :include-source: + + t = Tomato(density_type='DTM', k=100) + t.fit(data) + t.plot_diagram() + +Makes the number of clusters clearer, and changes a bit the shape of the clusters. + +A quick look at the corresponding density estimate + +.. plot:: + :context: close-figs + :include-source: + + plt.scatter(data[:,0],data[:,1],marker='.',s=1,c=t.weights_) + plt.show() + +The code provides a few density estimators and graph constructions for convenience when first experimenting, but it is actually expected that advanced users provide their own graph and density estimates instead of point coordinates. + +Since the algorithm essentially computes basins of attraction, it is also encouraged to use it on functions that do not represent densities at all. + +.. autoclass:: gudhi.clustering.tomato.Tomato + :members: + :special-members: __init__ diff --git a/src/python/doc/conf.py b/src/python/doc/conf.py index 3cc5d1d6..e69e2751 100755 --- a/src/python/doc/conf.py +++ b/src/python/doc/conf.py @@ -44,6 +44,8 @@ extensions = [ 'sphinx_paramlinks', ] +bibtex_bibfiles = ['../../biblio/bibliography.bib'] + todo_include_todos = True # plot option : do not show hyperlinks (Source code, png, hires.png, pdf) plot_html_show_source_link = False @@ -118,15 +120,12 @@ pygments_style = 'sphinx' # The theme to use for HTML and HTML Help pages. See the documentation for # a list of builtin themes. -html_theme = 'classic' +html_theme = 'python_docs_theme' # Theme options are theme-specific and customize the look and feel of a theme # further. For a list of options available for each theme, see the # documentation. html_theme_options = { - "sidebarbgcolor": "#A1ADCD", - "sidebartextcolor": "black", - "sidebarlinkcolor": "#334D5C", "body_max_width": "100%", } diff --git a/src/python/doc/cubical_complex_sklearn_itf_ref.rst b/src/python/doc/cubical_complex_sklearn_itf_ref.rst new file mode 100644 index 00000000..90ae9ccd --- /dev/null +++ b/src/python/doc/cubical_complex_sklearn_itf_ref.rst @@ -0,0 +1,102 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Cubical complex persistence scikit-learn like interface +####################################################### + +.. list-table:: + :width: 100% + :header-rows: 0 + + * - :Since: GUDHI 3.6.0 + - :License: MIT + - :Requires: `Scikit-learn <installation.html#scikit-learn>`_ + +Cubical complex persistence scikit-learn like interface example +--------------------------------------------------------------- + +In this example, hand written digits are used as an input. +a TDA scikit-learn pipeline is constructed and is composed of: + +#. :class:`~gudhi.sklearn.cubical_persistence.CubicalPersistence` that builds a cubical complex from the inputs and + returns its persistence diagrams +#. :class:`~gudhi.representations.preprocessing.DiagramSelector` that removes non-finite persistence diagrams values +#. :class:`~gudhi.representations.vector_methods.PersistenceImage` that builds the persistence images from persistence diagrams +#. `SVC <https://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html>`_ which is a scikit-learn support + vector classifier. + +This ML pipeline is trained to detect if the hand written digit is an '8' or not, thanks to the fact that an '8' has +two holes in :math:`\mathbf{H}_1`, or, like in this example, three connected components in :math:`\mathbf{H}_0`. + +.. code-block:: python + + # Standard scientific Python imports + import numpy as np + + # Standard scikit-learn imports + from sklearn.datasets import fetch_openml + from sklearn.pipeline import Pipeline + from sklearn.model_selection import train_test_split + from sklearn.svm import SVC + from sklearn import metrics + + # Import TDA pipeline requirements + from gudhi.sklearn.cubical_persistence import CubicalPersistence + from gudhi.representations import PersistenceImage, DiagramSelector + + X, y = fetch_openml("mnist_784", version=1, return_X_y=True, as_frame=False) + + # Target is: "is an eight ?" + y = (y == "8") * 1 + print("There are", np.sum(y), "eights out of", len(y), "numbers.") + + X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.4, random_state=0) + pipe = Pipeline( + [ + ("cub_pers", CubicalPersistence(homology_dimensions=0, newshape=[-1, 28, 28], n_jobs=-2)), + # Or for multiple persistence dimension computation + # ("cub_pers", CubicalPersistence(homology_dimensions=[0, 1], newshape=[-1, 28, 28])), + # ("H0_diags", DimensionSelector(index=0), # where index is the index in homology_dimensions array + ("finite_diags", DiagramSelector(use=True, point_type="finite")), + ( + "pers_img", + PersistenceImage(bandwidth=50, weight=lambda x: x[1] ** 2, im_range=[0, 256, 0, 256], resolution=[20, 20]), + ), + ("svc", SVC()), + ] + ) + + # Learn from the train subset + pipe.fit(X_train, y_train) + # Predict from the test subset + predicted = pipe.predict(X_test) + + print(f"Classification report for TDA pipeline {pipe}:\n" f"{metrics.classification_report(y_test, predicted)}\n") + +.. code-block:: none + + There are 6825 eights out of 70000 numbers. + Classification report for TDA pipeline Pipeline(steps=[('cub_pers', + CubicalPersistence(newshape=[28, 28], n_jobs=-2)), + ('finite_diags', DiagramSelector(use=True)), + ('pers_img', + PersistenceImage(bandwidth=50, im_range=[0, 256, 0, 256], + weight=<function <lambda> at 0x7f3e54137ae8>)), + ('svc', SVC())]): + precision recall f1-score support + + 0 0.97 0.99 0.98 25284 + 1 0.92 0.68 0.78 2716 + + accuracy 0.96 28000 + macro avg 0.94 0.84 0.88 28000 + weighted avg 0.96 0.96 0.96 28000 + +Cubical complex persistence scikit-learn like interface reference +----------------------------------------------------------------- + +.. autoclass:: gudhi.sklearn.cubical_persistence.CubicalPersistence + :members: + :special-members: __init__ + :show-inheritance:
\ No newline at end of file diff --git a/src/python/doc/cubical_complex_sum.inc b/src/python/doc/cubical_complex_sum.inc index f200e695..b27843e5 100644 --- a/src/python/doc/cubical_complex_sum.inc +++ b/src/python/doc/cubical_complex_sum.inc @@ -1,14 +1,22 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +--------------------------------------------------------------------------+----------------------------------------------------------------------+-----------------------------+ - | .. figure:: | The cubical complex is an example of a structured complex useful in | :Author: Pawel Dlotko | - | ../../doc/Bitmap_cubical_complex/Cubical_complex_representation.png | computational mathematics (specially rigorous numerics) and image | | - | :alt: Cubical complex representation | analysis. | :Introduced in: GUDHI 2.0.0 | - | :figclass: align-center | | | - | | | :Copyright: MIT | - | | | | - +--------------------------------------------------------------------------+----------------------------------------------------------------------+-----------------------------+ - | * :doc:`cubical_complex_user` | * :doc:`cubical_complex_ref` | - | | * :doc:`periodic_cubical_complex_ref` | - +--------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------+ + +--------------------------------------------------------------------------+--------------------------------------------------------------+-------------------------------------------------------------+ + | .. figure:: | The cubical complex represents a grid as a cell complex with | :Author: Pawel Dlotko | + | ../../doc/Bitmap_cubical_complex/Cubical_complex_representation.png | cells of all dimensions. | :Since: GUDHI 2.0.0 | + | :alt: Cubical complex representation | | :License: MIT | + | :figclass: align-center | | | + +--------------------------------------------------------------------------+--------------------------------------------------------------+-------------------------------------------------------------+ + | * :doc:`cubical_complex_user` | * :doc:`cubical_complex_ref` | + | | * :doc:`periodic_cubical_complex_ref` | + +--------------------------------------------------------------------------+--------------------------------------------------------------+-------------------------------------------------------------+ + | .. image:: | * :doc:`cubical_complex_tflow_itf_ref` | :requires: `TensorFlow <installation.html#tensorflow>`_ | + | img/tensorflow.png | | | + | :target: https://www.tensorflow.org | | | + | :height: 30 | | | + +--------------------------------------------------------------------------+--------------------------------------------------------------+-------------------------------------------------------------+ + | .. image:: | * :doc:`cubical_complex_sklearn_itf_ref` | :Requires: `Scikit-learn <installation.html#scikit-learn>`_ | + | img/sklearn.png | | | + | :target: https://scikit-learn.org | | | + | :height: 30 | | | + +--------------------------------------------------------------------------+--------------------------------------------------------------+-------------------------------------------------------------+ diff --git a/src/python/doc/cubical_complex_tflow_itf_ref.rst b/src/python/doc/cubical_complex_tflow_itf_ref.rst new file mode 100644 index 00000000..b32f5e47 --- /dev/null +++ b/src/python/doc/cubical_complex_tflow_itf_ref.rst @@ -0,0 +1,40 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +TensorFlow layer for cubical persistence +######################################## + +.. include:: differentiation_sum.inc + +Example of gradient computed from cubical persistence +----------------------------------------------------- + +.. testcode:: + + from gudhi.tensorflow import CubicalLayer + import tensorflow as tf + + X = tf.Variable([[0.,2.,2.],[2.,2.,2.],[2.,2.,1.]], dtype=tf.float32, trainable=True) + cl = CubicalLayer(homology_dimensions=[0]) + + with tf.GradientTape() as tape: + dgm = cl.call(X)[0][0] + loss = tf.math.reduce_sum(tf.square(.5*(dgm[:,1]-dgm[:,0]))) + + grads = tape.gradient(loss, [X]) + print(grads[0].numpy()) + +.. testoutput:: + + [[ 0. 0. 0. ] + [ 0. 0.5 0. ] + [ 0. 0. -0.5]] + +Documentation for CubicalLayer +------------------------------ + +.. autoclass:: gudhi.tensorflow.CubicalLayer + :members: + :special-members: __init__ + :show-inheritance: diff --git a/src/python/doc/cubical_complex_user.rst b/src/python/doc/cubical_complex_user.rst index 56cf0170..42a23875 100644 --- a/src/python/doc/cubical_complex_user.rst +++ b/src/python/doc/cubical_complex_user.rst @@ -7,14 +7,7 @@ Cubical complex user manual Definition ---------- -===================================== ===================================== ===================================== -:Author: Pawel Dlotko :Introduced in: GUDHI PYTHON 2.0.0 :Copyright: GPL v3 -===================================== ===================================== ===================================== - -+---------------------------------------------+----------------------------------------------------------------------+ -| :doc:`cubical_complex_user` | * :doc:`cubical_complex_ref` | -| | * :doc:`periodic_cubical_complex_ref` | -+---------------------------------------------+----------------------------------------------------------------------+ +.. include:: cubical_complex_sum.inc The cubical complex is an example of a structured complex useful in computational mathematics (specially rigorous numerics) and image analysis. @@ -47,8 +40,8 @@ be a set of two elements). For further details and theory of cubical complexes, please consult :cite:`kaczynski2004computational` as well as the following paper :cite:`peikert2012topological`. -Data structure. ---------------- +Data structure +-------------- The implementation of Cubical complex provides a representation of complexes that occupy a rectangular region in :math:`\mathbb{R}^n`. This extra assumption allows for a memory efficient way of storing cubical complexes in a form @@ -77,8 +70,8 @@ Knowing the sizes of the bitmap, by a series of modulo operation, we can determi present in the product that gives the cube :math:`C`. In a similar way, we can compute boundary and the coboundary of each cube. Further details can be found in the literature. -Input Format. -------------- +Input Format +------------ In the current implantation, filtration is given at the maximal cubes, and it is then extended by the lower star filtration to all cubes. There are a number of constructors that can be used to construct cubical complex by users @@ -91,7 +84,7 @@ Currently one input from a text file is used. It uses a format inspired from the we allow any filtration values. As a consequence one cannot use ``-1``'s to indicate missing cubes. If you have missing cubes in your complex, please set their filtration to :math:`+\infty` (aka. ``inf`` in the file). -The file format is described in details in :ref:`Perseus file format` file format section. +The file format is described in details in `Perseus file format <fileformats.html#perseus>`_ section. .. testcode:: @@ -108,8 +101,8 @@ the program output is: Cubical complex is of dimension 2 - 49 simplices. -Periodic boundary conditions. ------------------------------ +Periodic boundary conditions +---------------------------- Often one would like to impose periodic boundary conditions to the cubical complex (cf. :doc:`periodic_cubical_complex_ref`). @@ -120,7 +113,7 @@ conditions are imposed in all directions, then complex :math:`\mathcal{K}` becam various constructors from the file Bitmap_cubical_complex_periodic_boundary_conditions_base.h to construct cubical complex with periodic boundary conditions. -One can also use Perseus style input files (see :doc:`Perseus <fileformats>`) for the specific periodic case: +One can also use Perseus style input files (see `Perseus file format <fileformats.html#perseus>`_) for the specific periodic case: .. testcode:: @@ -154,14 +147,13 @@ the program output is: Periodic cubical complex is of dimension 2 - 42 simplices. -Examples. ---------- +Examples +-------- End user programs are available in python/example/ folder. -Bibliography -============ +Tutorial +-------- -.. bibliography:: ../../biblio/bibliography.bib - :filter: docnames - :style: unsrt +This `notebook <https://github.com/GUDHI/TDA-tutorial/blob/master/Tuto-GUDHI-cubical-complexes.ipynb>`_ +explains how to represent sublevels sets of functions using cubical complexes. diff --git a/src/python/doc/datasets.inc b/src/python/doc/datasets.inc new file mode 100644 index 00000000..95a87678 --- /dev/null +++ b/src/python/doc/datasets.inc @@ -0,0 +1,14 @@ +.. table:: + :widths: 30 40 30 + + +-----------------------------------+--------------------------------------------+--------------------------------------------------------------------------------------+ + | .. figure:: | Datasets either generated or fetched. | :Authors: Hind Montassif | + | img/sphere_3d.png | | | + | | | :Since: GUDHI 3.5.0 | + | | | | + | | | :License: MIT (`LGPL v3 </licensing/>`_) | + | | | | + | | | :Requires: `CGAL <installation.html#cgal>`_ | + +-----------------------------------+--------------------------------------------+--------------------------------------------------------------------------------------+ + | * :doc:`datasets` | + +-----------------------------------+-----------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/datasets.rst b/src/python/doc/datasets.rst new file mode 100644 index 00000000..2d11a19d --- /dev/null +++ b/src/python/doc/datasets.rst @@ -0,0 +1,133 @@ + +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +================ +Datasets manual +================ + +Datasets generators +=================== + +We provide the generation of different customizable datasets to use as inputs for Gudhi complexes and data structures. + +Points generators +------------------ + +The module **points** enables the generation of random points on a sphere, random points on a torus and as a grid. + +Points on sphere +^^^^^^^^^^^^^^^^ + +The function **sphere** enables the generation of random i.i.d. points uniformly on a (d-1)-sphere in :math:`R^d`. +The user should provide the number of points to be generated on the sphere :code:`n_samples` and the ambient dimension :code:`ambient_dim`. +The :code:`radius` of sphere is optional and is equal to **1** by default. +Only random points generation is currently available. + +The generated points are given as an array of shape :math:`(n\_samples, ambient\_dim)`. + +Example +""""""" + +.. code-block:: python + + from gudhi.datasets.generators import points + from gudhi import AlphaComplex + + # Generate 50 points on a sphere in R^2 + gen_points = points.sphere(n_samples = 50, ambient_dim = 2, radius = 1, sample = "random") + + # Create an alpha complex from the generated points + alpha_complex = AlphaComplex(points = gen_points) + +.. autofunction:: gudhi.datasets.generators.points.sphere + +Points on a flat torus +^^^^^^^^^^^^^^^^^^^^^^ + +You can also generate points on a torus. + +Two functions are available and give the same output: the first one depends on **CGAL** and the second does not and consists of full python code. + +On another hand, two sample types are provided: you can either generate i.i.d. points on a d-torus in :math:`R^{2d}` *randomly* or on a *grid*. + +First function: **ctorus** +""""""""""""""""""""""""""" + +The user should provide the number of points to be generated on the torus :code:`n_samples`, and the dimension :code:`dim` of the torus on which points would be generated in :math:`R^{2dim}`. +The :code:`sample` argument is optional and is set to **'random'** by default. +In this case, the returned generated points would be an array of shape :math:`(n\_samples, 2*dim)`. +Otherwise, if set to **'grid'**, the points are generated on a grid and would be given as an array of shape: + +.. math:: + + ( ⌊n\_samples^{1 \over {dim}}⌋^{dim}, 2*dim ) + +**Note 1:** The output array first shape is rounded down to the closest perfect :math:`dim^{th}` power. + +**Note 2:** This version is recommended when the user wishes to use **'grid'** as sample type, or **'random'** with a relatively small number of samples (~ less than 150). + +Example +""""""" +.. code-block:: python + + from gudhi.datasets.generators import points + + # Generate 50 points randomly on a torus in R^6 + gen_points = points.ctorus(n_samples = 50, dim = 3) + + # Generate 27 points on a torus as a grid in R^6 + gen_points = points.ctorus(n_samples = 50, dim = 3, sample = 'grid') + +.. autofunction:: gudhi.datasets.generators.points.ctorus + +Second function: **torus** +""""""""""""""""""""""""""" + +The user should provide the number of points to be generated on the torus :code:`n_samples` and the dimension :code:`dim` of the torus on which points would be generated in :math:`R^{2dim}`. +The :code:`sample` argument is optional and is set to **'random'** by default. +The other allowed value of sample type is **'grid'**. + +**Note:** This version is recommended when the user wishes to use **'random'** as sample type with a great number of samples and a low dimension. + +Example +""""""" +.. code-block:: python + + from gudhi.datasets.generators import points + + # Generate 50 points randomly on a torus in R^6 + gen_points = points.torus(n_samples = 50, dim = 3) + + # Generate 27 points on a torus as a grid in R^6 + gen_points = points.torus(n_samples = 50, dim = 3, sample = 'grid') + + +.. autofunction:: gudhi.datasets.generators.points.torus + + +Fetching datasets +================= + +We provide some ready-to-use datasets that are not available by default when getting GUDHI, and need to be fetched explicitly. + +By **default**, the fetched datasets directory is set to a folder named **'gudhi_data'** in the **user home folder**. +Alternatively, it can be set using the **'GUDHI_DATA'** environment variable. + +.. autofunction:: gudhi.datasets.remote.fetch_bunny + +.. figure:: ./img/bunny.png + :figclass: align-center + + 3D Stanford bunny with 35947 vertices. + + +.. autofunction:: gudhi.datasets.remote.fetch_spiral_2d + +.. figure:: ./img/spiral_2d.png + :figclass: align-center + + 2D spiral with 114562 vertices. + +.. autofunction:: gudhi.datasets.remote.clear_data_home diff --git a/src/python/doc/differentiation_sum.inc b/src/python/doc/differentiation_sum.inc new file mode 100644 index 00000000..140cf180 --- /dev/null +++ b/src/python/doc/differentiation_sum.inc @@ -0,0 +1,12 @@ +.. list-table:: + :width: 100% + :header-rows: 0 + + * - :Since: GUDHI 3.6.0 + - :License: MIT + - :Requires: `TensorFlow <installation.html#tensorflow>`_ + +We provide TensorFlow 2 models that can handle automatic differentiation for the computation of persistence diagrams from complexes available in the Gudhi library. +This includes simplex trees, cubical complexes and Vietoris-Rips complexes. Detailed example on how to use these layers in practice are available +in the following `notebook <https://github.com/GUDHI/TDA-tutorial/blob/master/Tuto-GUDHI-optimization.ipynb>`_. Note that even if TensorFlow GPU is enabled, all +internal computations using Gudhi will be done on CPU. diff --git a/src/python/doc/examples.rst b/src/python/doc/examples.rst index a42227e3..1442f185 100644 --- a/src/python/doc/examples.rst +++ b/src/python/doc/examples.rst @@ -7,27 +7,31 @@ Examples .. only:: builder_html - * :download:`rips_complex_from_points_example.py <../example/rips_complex_from_points_example.py>` + * :download:`alpha_complex_diagram_persistence_from_off_file_example.py <../example/alpha_complex_diagram_persistence_from_off_file_example.py>` + * :download:`alpha_complex_from_generated_points_on_sphere_example.py <../example/alpha_complex_from_generated_points_on_sphere_example.py>` * :download:`alpha_complex_from_points_example.py <../example/alpha_complex_from_points_example.py>` - * :download:`simplex_tree_example.py <../example/simplex_tree_example.py>` * :download:`alpha_rips_persistence_bottleneck_distance.py <../example/alpha_rips_persistence_bottleneck_distance.py>` - * :download:`tangential_complex_plain_homology_from_off_file_example.py <../example/tangential_complex_plain_homology_from_off_file_example.py>` - * :download:`alpha_complex_diagram_persistence_from_off_file_example.py <../example/alpha_complex_diagram_persistence_from_off_file_example.py>` - * :download:`periodic_cubical_complex_barcode_persistence_from_perseus_file_example.py <../example/periodic_cubical_complex_barcode_persistence_from_perseus_file_example.py>` * :download:`bottleneck_basic_example.py <../example/bottleneck_basic_example.py>` - * :download:`gudhi_graphical_tools_example.py <../example/gudhi_graphical_tools_example.py>` - * :download:`plot_simplex_tree_dim012.py <../example/plot_simplex_tree_dim012.py>` - * :download:`plot_rips_complex.py <../example/plot_rips_complex.py>` - * :download:`plot_alpha_complex.py <../example/plot_alpha_complex.py>` - * :download:`witness_complex_from_nearest_landmark_table.py <../example/witness_complex_from_nearest_landmark_table.py>` + * :download:`coordinate_graph_induced_complex.py <../example/coordinate_graph_induced_complex.py>` + * :download:`diagram_vectorizations_distances_kernels.py <../example/diagram_vectorizations_distances_kernels.py>` * :download:`euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py>` * :download:`euclidean_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_witness_complex_diagram_persistence_from_off_file_example.py>` - * :download:`rips_complex_diagram_persistence_from_off_file_example.py <../example/rips_complex_diagram_persistence_from_off_file_example.py>` + * :download:`functional_graph_induced_complex.py <../example/functional_graph_induced_complex.py>` + * :download:`gudhi_graphical_tools_example.py <../example/gudhi_graphical_tools_example.py>` + * :download:`nerve_of_a_covering.py <../example/nerve_of_a_covering.py>` + * :download:`periodic_cubical_complex_barcode_persistence_from_perseus_file_example.py <../example/periodic_cubical_complex_barcode_persistence_from_perseus_file_example.py>` + * :download:`plot_alpha_complex.py <../example/plot_alpha_complex.py>` + * :download:`plot_rips_complex.py <../example/plot_rips_complex.py>` + * :download:`plot_simplex_tree_dim012.py <../example/plot_simplex_tree_dim012.py>` + * :download:`random_cubical_complex_persistence_example.py <../example/random_cubical_complex_persistence_example.py>` + * :download:`rips_complex_diagram_persistence_from_correlation_matrix_file_example.py <../example/rips_complex_diagram_persistence_from_correlation_matrix_file_example.py>` * :download:`rips_complex_diagram_persistence_from_distance_matrix_file_example.py <../example/rips_complex_diagram_persistence_from_distance_matrix_file_example.py>` + * :download:`rips_complex_diagram_persistence_from_off_file_example.py <../example/rips_complex_diagram_persistence_from_off_file_example.py>` + * :download:`rips_complex_edge_collapse_example.py <../example/rips_complex_edge_collapse_example.py>` + * :download:`rips_complex_from_points_example.py <../example/rips_complex_from_points_example.py>` * :download:`rips_persistence_diagram.py <../example/rips_persistence_diagram.py>` + * :download:`simplex_tree_example.py <../example/simplex_tree_example.py>` * :download:`sparse_rips_persistence_diagram.py <../example/sparse_rips_persistence_diagram.py>` - * :download:`random_cubical_complex_persistence_example.py <../example/random_cubical_complex_persistence_example.py>` - * :download:`coordinate_graph_induced_complex.py <../example/coordinate_graph_induced_complex.py>` - * :download:`functional_graph_induced_complex.py <../example/functional_graph_induced_complex.py>` + * :download:`tangential_complex_plain_homology_from_off_file_example.py <../example/tangential_complex_plain_homology_from_off_file_example.py>` * :download:`voronoi_graph_induced_complex.py <../example/voronoi_graph_induced_complex.py>` - * :download:`nerve_of_a_covering.py <../example/nerve_of_a_covering.py>` + * :download:`witness_complex_from_nearest_landmark_table.py <../example/witness_complex_from_nearest_landmark_table.py>` diff --git a/src/python/doc/fileformats.rst b/src/python/doc/fileformats.rst index 345dfdba..ae1b00f3 100644 --- a/src/python/doc/fileformats.rst +++ b/src/python/doc/fileformats.rst @@ -80,8 +80,6 @@ Here is a simple sample file in the 3D case:: 1. 1. 1. -.. _Perseus file format: - Perseus ******* diff --git a/src/python/doc/img/barycenter.png b/src/python/doc/img/barycenter.png Binary files differnew file mode 100644 index 00000000..cad6af70 --- /dev/null +++ b/src/python/doc/img/barycenter.png diff --git a/src/python/doc/img/sklearn.png b/src/python/doc/img/sklearn.png Binary files differnew file mode 100644 index 00000000..d1fecbbf --- /dev/null +++ b/src/python/doc/img/sklearn.png diff --git a/src/python/doc/img/sphere_3d.png b/src/python/doc/img/sphere_3d.png Binary files differnew file mode 100644 index 00000000..70f3184f --- /dev/null +++ b/src/python/doc/img/sphere_3d.png diff --git a/src/python/doc/img/spiral-color.png b/src/python/doc/img/spiral-color.png Binary files differnew file mode 100644 index 00000000..21b62dfc --- /dev/null +++ b/src/python/doc/img/spiral-color.png diff --git a/src/python/doc/img/spiral_2d.png b/src/python/doc/img/spiral_2d.png Binary files differnew file mode 100644 index 00000000..abd247cd --- /dev/null +++ b/src/python/doc/img/spiral_2d.png diff --git a/src/python/doc/index.rst b/src/python/doc/index.rst index 3387a64f..35f4ba46 100644 --- a/src/python/doc/index.rst +++ b/src/python/doc/index.rst @@ -53,8 +53,8 @@ Tangential complex Topological descriptors computation *********************************** -Persistence cohomology -====================== +Persistent cohomology +===================== .. include:: persistent_cohomology_sum.inc @@ -71,6 +71,7 @@ Wasserstein distance .. include:: wasserstein_distance_sum.inc + Persistence representations =========================== @@ -86,9 +87,12 @@ Point cloud utilities .. include:: point_cloud_sum.inc -Bibliography -************ +Clustering +********** + +.. include:: clustering.inc + +Datasets +******** -.. bibliography:: ../../biblio/bibliography.bib - :filter: docnames - :style: unsrt +.. include:: datasets.inc diff --git a/src/python/doc/installation.rst b/src/python/doc/installation.rst index 40f3f44b..5491542f 100644 --- a/src/python/doc/installation.rst +++ b/src/python/doc/installation.rst @@ -5,38 +5,61 @@ Installation ############ -Conda -***** -The easiest way to install the Python version of GUDHI is using -`conda <https://gudhi.inria.fr/conda/>`_. +Packages +******** +The easiest way to install the Python version of GUDHI is using pre-built packages. +We recommend `conda <https://gudhi.inria.fr/conda/>`_ + +.. code-block:: bash + + conda install -c conda-forge gudhi + +Gudhi is also available on `PyPI <https://pypi.org/project/gudhi/>`_ + +.. code-block:: bash + + pip install gudhi + +Third party packages are also available, for instance on Debian or Ubuntu + +.. code-block:: bash + + apt install python3-gudhi + +In all cases, you may still want to install some of the optional `run time dependencies`_. Compiling ********* -The library uses c++14 and requires `Boost <https://www.boost.org/>`_ ≥ 1.56.0, -`CMake <https://www.cmake.org/>`_ ≥ 3.1 to generate makefiles, -`NumPy <http://numpy.org>`_ and `Cython <https://www.cython.org/>`_ to compile -the GUDHI Python module. -It is a multi-platform library and compiles on Linux, Mac OSX and Visual -Studio 2015. - -On `Windows <https://wiki.python.org/moin/WindowsCompilers>`_ , only Python -≥ 3.5 are available because of the required Visual Studio version. - -On other systems, if you have several Python/python installed, the version 2.X -will be used by default, but you can force it by adding +These instructions are for people who want to compile gudhi from source, they are +unnecessary if you installed a binary package of Gudhi as above. They assume that +you have downloaded a `release <https://github.com/GUDHI/gudhi-devel/releases>`_, +with a name like `gudhi.3.X.Y.tar.gz`, then run `tar xf gudhi.3.X.Y.tar.gz`, which +created a directory `gudhi.3.X.Y`, hereinafter referred to as `/path-to-gudhi/`. +If you are instead using a git checkout, beware that the paths are a bit +different, and in particular the `python/` subdirectory is actually `src/python/` +there. + +The library uses c++17 and requires `Boost <https://www.boost.org/>`_ :math:`\geq` 1.66.0, +`CMake <https://www.cmake.org/>`_ :math:`\geq` 3.5 to generate makefiles, +Python :math:`\geq` 3.5, `NumPy <http://numpy.org>`_ :math:`\geq` 1.15.0, `Cython <https://www.cython.org/>`_ +:math:`\geq` 0.27 and `pybind11 <https://github.com/pybind/pybind11>`_ to compile the GUDHI Python module. +It is a multi-platform library and compiles on Linux, Mac OSX and Visual Studio 2017 or later. + +If you have several Python/python installed, the version 2.X may be used by default, but you can force it by adding :code:`-DPython_ADDITIONAL_VERSIONS=3` to the cmake command. GUDHI Python module compilation =============================== -To build the GUDHI Python module, run the following commands in a terminal: +After making sure that the `Compilation dependencies`_ are properly installed, +one can build the GUDHI Python module, by running the following commands in a terminal: .. code-block:: bash cd /path-to-gudhi/ mkdir build cd build/ - cmake .. + cmake -DCMAKE_BUILD_TYPE=Release .. cd python make @@ -70,20 +93,14 @@ Or install it definitely in your Python packages folder: .. code-block:: bash cd /path-to-gudhi/build/python - # May require sudo or administrator privileges - make install + python setup.py install # add --user to the command if you do not have the permission + # Or 'pip install .' .. note:: - :code:`make install` is only a - `CMake custom targets <https://cmake.org/cmake/help/latest/command/add_custom_target.html>`_ - to shortcut :code:`python setup.py install` command. It does not take into account :code:`CMAKE_INSTALL_PREFIX`. - But one can use :code:`python setup.py install ...` specific options in the python directory: - -.. code-block:: bash - - python setup.py install --prefix /home/gudhi # Install in /home/gudhi directory + But one can use + `alternate location installation <https://docs.python.org/3/install/#alternate-installation>`_. Test suites =========== @@ -119,63 +136,74 @@ If :code:`import gudhi` succeeds, please have a look to debug information: .. code-block:: python - import gudhi - print(gudhi.__debug_info__) + import gudhi as gd + print(gd.__debug_info__) + print("+ Installed modules are: " + gd.__available_modules) + print("+ Missing modules are: " + gd.__missing_modules) You shall have something like: .. code-block:: none - Python version 2.7.15 - Cython version 0.26.1 - Numpy version 1.14.1 - Eigen3 version 3.1.1 - Installed modules are: off_reader;simplex_tree;rips_complex; - cubical_complex;periodic_cubical_complex;reader_utils;witness_complex; - strong_witness_complex;alpha_complex; - Missing modules are: bottleneck_distance;nerve_gic;subsampling; - tangential_complex;persistence_graphical_tools; - euclidean_witness_complex;euclidean_strong_witness_complex; - CGAL version 4.7.1000 - GMP_LIBRARIES = /usr/lib/x86_64-linux-gnu/libgmp.so - GMPXX_LIBRARIES = /usr/lib/x86_64-linux-gnu/libgmpxx.so - TBB version 9107 found and used + Pybind11 version 2.8.1 + Python version 3.7.12 + Cython version 0.29.25 + Numpy version 1.21.4 + Boost version 1.77.0 + + Installed modules are: off_utils;simplex_tree;rips_complex;cubical_complex;periodic_cubical_complex; + persistence_graphical_tools;reader_utils;witness_complex;strong_witness_complex; + + Missing modules are: bottleneck;nerve_gic;subsampling;tangential_complex;alpha_complex;euclidean_witness_complex; + euclidean_strong_witness_complex; -Here, you can see that bottleneck_distance, nerve_gic, subsampling and -tangential_complex are missing because of the CGAL version. -persistence_graphical_tools is not available as matplotlib is not -available. +Here, you can see that the modules that need CGAL are missing, because CGAL is not installed. +:code:`persistence_graphical_tools` is installed, but +`its functions <https://gudhi.inria.fr/python/latest/persistence_graphical_tools_ref.html>`_ will produce an error as +matplotlib is not available. Unitary tests cannot be run as pytest is missing. A complete configuration would be : .. code-block:: none - Python version 3.6.5 - Cython version 0.28.2 - Pytest version 3.3.2 - Matplotlib version 2.2.2 - Numpy version 1.14.5 - Eigen3 version 3.3.4 - Installed modules are: off_reader;simplex_tree;rips_complex; - cubical_complex;periodic_cubical_complex;persistence_graphical_tools; - reader_utils;witness_complex;strong_witness_complex; - persistence_graphical_tools;bottleneck_distance;nerve_gic;subsampling; - tangential_complex;alpha_complex;euclidean_witness_complex; - euclidean_strong_witness_complex; - CGAL header only version 4.11.0 + Pybind11 version 2.8.1 + Python version 3.9.7 + Cython version 0.29.24 + Pytest version 6.2.5 + Matplotlib version 3.5.0 + Numpy version 1.21.4 + Scipy version 1.7.3 + Scikit-learn version 1.0.1 + POT version 0.8.0 + HNSWlib found + PyKeOps version [pyKeOps]: 2.1 + EagerPy version 0.30.0 + TensorFlow version 2.7.0 + Sphinx version 4.3.0 + Sphinx-paramlinks version 0.5.2 + python_docs_theme found + Eigen3 version 3.4.0 + Boost version 1.74.0 + CGAL version 5.3 GMP_LIBRARIES = /usr/lib/x86_64-linux-gnu/libgmp.so GMPXX_LIBRARIES = /usr/lib/x86_64-linux-gnu/libgmpxx.so + MPFR_LIBRARIES = /usr/lib/x86_64-linux-gnu/libmpfr.so TBB version 9107 found and used + + Installed modules are: bottleneck;off_utils;simplex_tree;rips_complex;cubical_complex;periodic_cubical_complex; + persistence_graphical_tools;reader_utils;witness_complex;strong_witness_complex;nerve_gic;subsampling; + tangential_complex;alpha_complex;euclidean_witness_complex;euclidean_strong_witness_complex; + + Missing modules are: + Documentation ============= -To build the documentation, `sphinx-doc <http://www.sphinx-doc.org>`_ and -`sphinxcontrib-bibtex <https://sphinxcontrib-bibtex.readthedocs.io>`_ are +To build the documentation, `sphinx-doc <http://www.sphinx-doc.org>`_, +`sphinxcontrib-bibtex <https://sphinxcontrib-bibtex.readthedocs.io>`_, +`sphinxcontrib-paramlinks <https://github.com/sqlalchemyorg/sphinx-paramlinks>`_ and +`python-docs-theme <https://github.com/python/python-docs-theme>`_ are required. As the documentation is auto-tested, `CGAL`_, `Eigen`_, -`Matplotlib`_, `NumPy`_ and `SciPy`_ are also mandatory to build the -documentation. +`Matplotlib`_, `NumPy`_, `POT`_, `Scikit-learn`_ and `SciPy`_ are +also mandatory to build the documentation. Run the following commands in a terminal: @@ -187,19 +215,25 @@ Run the following commands in a terminal: Optional third-party library **************************** +Compilation dependencies +======================== + +These third party dependencies are detected by `CMake <https://www.cmake.org/>`_. +They have to be installed before performing the `GUDHI Python module compilation`_. + CGAL -==== +---- Some GUDHI modules (cf. :doc:`modules list </index>`), and few examples -require CGAL, a C++ library that provides easy access to efficient and -reliable geometric algorithms. +require `CGAL <https://www.cgal.org/>`_, a C++ library that provides easy +access to efficient and reliable geometric algorithms. The procedure to install this library according to your operating system is detailed `here <http://doc.cgal.org/latest/Manual/installation.html>`_. -The following examples requires CGAL version ≥ 4.11.0: +The following examples require CGAL version :math:`\geq` 4.11.0: .. only:: builder_html @@ -211,14 +245,14 @@ The following examples requires CGAL version ≥ 4.11.0: * :download:`euclidean_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_witness_complex_diagram_persistence_from_off_file_example.py>` Eigen -===== +----- Some GUDHI modules (cf. :doc:`modules list </index>`), and few examples require `Eigen <http://eigen.tuxfamily.org/>`_, a C++ template library for linear algebra: matrices, vectors, numerical solvers, and related algorithms. -The following examples require `Eigen <http://eigen.tuxfamily.org/>`_ version ≥ 3.1.0: +The following examples require `Eigen <http://eigen.tuxfamily.org/>`_ version :math:`\geq` 3.1.0: .. only:: builder_html @@ -228,8 +262,46 @@ The following examples require `Eigen <http://eigen.tuxfamily.org/>`_ version ≠* :download:`euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py>` * :download:`euclidean_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_witness_complex_diagram_persistence_from_off_file_example.py>` +Threading Building Blocks +------------------------- + +`Intel® TBB <https://www.threadingbuildingblocks.org/>`_ 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. + +Run time dependencies +===================== + +These third party dependencies are detected by Python `import` mechanism at run time. +They can be installed when required. + +EagerPy +------- + +Some Python functions can handle automatic differentiation (possibly only when +a flag `enable_autodiff=True` is used). In order to reduce code duplication, we +use `EagerPy <https://eagerpy.jonasrauber.de/>`_ which wraps arrays from +PyTorch, TensorFlow and JAX in a common interface. + +Joblib +------ + +`Joblib <https://joblib.readthedocs.io/>`_ is used both as a dependency of `Scikit-learn`_, +and directly for parallelism in some modules (:class:`~gudhi.point_cloud.knn.KNearestNeighbors`, +:func:`~gudhi.representations.metrics.pairwise_persistence_diagram_distances`). + +Hnswlib +------- + +:class:`~gudhi.point_cloud.knn.KNearestNeighbors` can use the Python package +`Hnswlib <https://github.com/nmslib/hnswlib>`_ as a backend if explicitly +requested, to speed-up queries. + Matplotlib -========== +---------- The :doc:`persistence graphical tools </persistence_graphical_tools_user>` module requires `Matplotlib <http://matplotlib.org>`_, a Python 2D plotting @@ -250,43 +322,92 @@ The following examples require the `Matplotlib <http://matplotlib.org>`_: * :download:`euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py>` * :download:`euclidean_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_witness_complex_diagram_persistence_from_off_file_example.py>` +LaTeX +~~~~~ + +If a sufficiently complete LaTeX toolchain is available (including dvipng and ghostscript), the LaTeX option of +matplotlib is enabled for prettier captions (cf. +`matplotlib text rendering with LaTeX <https://matplotlib.org/3.3.0/tutorials/text/usetex.html>`_). +It also requires `type1cm` LaTeX package (not detected by matplotlib). + +If you are facing issues with LaTeX rendering, like this one: + +.. code-block:: none + + Traceback (most recent call last): + File "/usr/lib/python3/dist-packages/matplotlib/texmanager.py", line 302, in _run_checked_subprocess + report = subprocess.check_output(command, + ... + ! LaTeX Error: File `type1cm.sty' not found. + ... + +This is because the LaTeX package is not installed on your system. On Ubuntu systems you can install texlive-full +(for all LaTeX packages), or more specific packages like texlive-latex-extra, cm-super. + +You can still deactivate LaTeX rendering by saying: + +.. code-block:: python + + import gudhi as gd + gd.persistence_graphical_tools._gudhi_matplotlib_use_tex=False + +PyKeOps +------- + +:class:`~gudhi.point_cloud.knn.KNearestNeighbors` can use the Python package +`PyKeOps <https://www.kernel-operations.io/keops/python/>`_ as a backend if +explicitly requested, to speed-up queries using a GPU. + Python Optimal Transport -======================== +------------------------ The :doc:`Wasserstein distance </wasserstein_distance_user>` -module requires `POT <https://pot.readthedocs.io/>`_, a library that provides +module requires `POT <https://pythonot.github.io/>`_, a library that provides several solvers for optimization problems related to Optimal Transport. +PyTorch +------- + +`PyTorch <https://pytorch.org/>`_ is currently only used as a dependency of +`PyKeOps`_, and in some tests. + Scikit-learn -============ +------------ The :doc:`persistence representations </representations>` module require `scikit-learn <https://scikit-learn.org/>`_, a Python-based ecosystem of open-source software for machine learning. +:class:`~gudhi.point_cloud.knn.KNearestNeighbors` can use the Python package +`scikit-learn <https://scikit-learn.org/>`_ as a backend if explicitly +requested. + SciPy -===== +----- The :doc:`persistence graphical tools </persistence_graphical_tools_user>` and :doc:`Wasserstein distance </wasserstein_distance_user>` modules require `SciPy <http://scipy.org>`_, a Python-based ecosystem of open-source software for mathematics, science, and engineering. -Threading Building Blocks -========================= +:class:`~gudhi.point_cloud.knn.KNearestNeighbors` can use the Python package +`SciPy <http://scipy.org>`_ :math:`\geq` 1.6.0 as a backend if explicitly requested. -`Intel® TBB <https://www.threadingbuildingblocks.org/>`_ 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. +TensorFlow +---------- -Having Intel® TBB installed is recommended to parallelize and accelerate some -GUDHI computations. +The :doc:`cubical complex </cubical_complex_tflow_itf_ref>`, :doc:`simplex tree </ls_simplex_tree_tflow_itf_ref>` +and :doc:`Rips complex </rips_complex_tflow_itf_ref>` modules require `TensorFlow <https://www.tensorflow.org>`_ +for incorporating them in neural nets. + +`TensorFlow <https://www.tensorflow.org>`_ is also used in some automatic differentiation tests. Bug reports and contributions ***************************** -Please help us improving the quality of the GUDHI library. You may report bugs or suggestions to: - - Contact: gudhi-users@lists.gforge.inria.fr +Please help us improving the quality of the GUDHI library. +You may `report bugs <https://github.com/GUDHI/gudhi-devel/issues>`_ or +`contact us <https://gudhi.inria.fr/contact/>`_ for any suggestions. -GUDHI is open to external contributions. If you want to join our development team, please contact us. +GUDHI is open to external contributions. If you want to join our development team, please take some time to read our +`contributing guide <https://github.com/GUDHI/gudhi-devel/blob/master/.github/CONTRIBUTING.md>`_. diff --git a/src/python/doc/ls_simplex_tree_tflow_itf_ref.rst b/src/python/doc/ls_simplex_tree_tflow_itf_ref.rst new file mode 100644 index 00000000..9d7d633f --- /dev/null +++ b/src/python/doc/ls_simplex_tree_tflow_itf_ref.rst @@ -0,0 +1,53 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +TensorFlow layer for lower-star persistence on simplex trees +############################################################ + +.. include:: differentiation_sum.inc + +Example of gradient computed from lower-star filtration of a simplex tree +------------------------------------------------------------------------- + +.. testcode:: + + from gudhi.tensorflow import LowerStarSimplexTreeLayer + import tensorflow as tf + import gudhi as gd + + st = gd.SimplexTree() + st.insert([0, 1]) + st.insert([1, 2]) + st.insert([2, 3]) + st.insert([3, 4]) + st.insert([4, 5]) + st.insert([5, 6]) + st.insert([6, 7]) + st.insert([7, 8]) + st.insert([8, 9]) + st.insert([9, 10]) + + F = tf.Variable([6.,4.,3.,4.,5.,4.,3.,2.,3.,4.,5.], dtype=tf.float32, trainable=True) + sl = LowerStarSimplexTreeLayer(simplextree=st, homology_dimensions=[0]) + + with tf.GradientTape() as tape: + dgm = sl.call(F)[0][0] + loss = tf.math.reduce_sum(tf.square(.5*(dgm[:,1]-dgm[:,0]))) + + grads = tape.gradient(loss, [F]) + print(grads[0].indices.numpy()) + print(grads[0].values.numpy()) + +.. testoutput:: + + [2 4] + [-1. 1.] + +Documentation for LowerStarSimplexTreeLayer +------------------------------------------- + +.. autoclass:: gudhi.tensorflow.LowerStarSimplexTreeLayer + :members: + :special-members: __init__ + :show-inheritance: diff --git a/src/python/doc/nerve_gic_complex_sum.inc b/src/python/doc/nerve_gic_complex_sum.inc index d633c4ff..7db6c124 100644 --- a/src/python/doc/nerve_gic_complex_sum.inc +++ b/src/python/doc/nerve_gic_complex_sum.inc @@ -1,16 +1,16 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +----------------------------------------------------------------+------------------------------------------------------------------------+------------------------------------------------------------------+ - | .. figure:: | Nerves and Graph Induced Complexes are cover complexes, i.e. | :Author: Mathieu Carrière | - | ../../doc/Nerve_GIC/gicvisu.jpg | simplicial complexes that provably contain topological information | | - | :alt: Graph Induced Complex of a point cloud. | about the input data. They can be computed with a cover of the data, | :Introduced in: GUDHI 2.3.0 | - | :figclass: align-center | that comes i.e. from the preimage of a family of intervals covering | | - | | the image of a scalar-valued function defined on the data. | :Copyright: MIT (`GPL v3 </licensing/>`_) | - | | | | - | | | :Requires: `CGAL <installation.html#cgal>`__ :math:`\geq` 4.11.0 | - | | | | - | | | | - +----------------------------------------------------------------+------------------------------------------------------------------------+------------------------------------------------------------------+ - | * :doc:`nerve_gic_complex_user` | * :doc:`nerve_gic_complex_ref` | - +----------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------+ + +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------------------------------------------+ + | .. figure:: | Nerves and Graph Induced Complexes are cover complexes, i.e. | :Author: Mathieu Carrière | + | ../../doc/Nerve_GIC/gicvisu.jpg | simplicial complexes that provably contain topological information | | + | :alt: Graph Induced Complex of a point cloud. | about the input data. They can be computed with a cover of the data, | :Since: GUDHI 2.3.0 | + | :figclass: align-center | that comes i.e. from the preimage of a family of intervals covering | | + | | the image of a scalar-valued function defined on the data. | :License: MIT (`GPL v3 </licensing/>`_) | + | | | | + | | | :Requires: `CGAL <installation.html#cgal>`_ :math:`\geq` 4.11.0 | + | | | | + | | | | + +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------------------------------------------+ + | * :doc:`nerve_gic_complex_user` | * :doc:`nerve_gic_complex_ref` | + +----------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/nerve_gic_complex_user.rst b/src/python/doc/nerve_gic_complex_user.rst index 9101f45d..8633cadb 100644 --- a/src/python/doc/nerve_gic_complex_user.rst +++ b/src/python/doc/nerve_gic_complex_user.rst @@ -12,8 +12,8 @@ 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>`_. -Input point clouds are assumed to be OFF files (cf. :doc:`fileformats`). +`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 ------ @@ -50,7 +50,7 @@ The cover C comes from the preimages of intervals (10 intervals with gain 0.3) covering the height function (coordinate 2), which are then refined into their connected components using the triangulation of the .OFF file. -.. testcode:: +.. code-block:: python import gudhi nerve_complex = gudhi.CoverComplex() @@ -99,9 +99,6 @@ the program output is: [-0.171433, 0.367393] [-0.909111, 0.745853] 0 interval(s) in dimension 1: - -.. testoutput:: - Nerve is of dimension 1 - 41 simplices - 21 vertices. [0] [1] diff --git a/src/python/doc/persistence_graphical_tools_sum.inc b/src/python/doc/persistence_graphical_tools_sum.inc index 0cdf8072..7ff63ae2 100644 --- a/src/python/doc/persistence_graphical_tools_sum.inc +++ b/src/python/doc/persistence_graphical_tools_sum.inc @@ -1,14 +1,14 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +-----------------------------------------------------------------+-----------------------------------------------------------------------+-----------------------------------------------+ - | .. figure:: | These graphical tools comes on top of persistence results and allows | :Author: Vincent Rouvreau | - | img/graphical_tools_representation.png | the user to build easily persistence barcode, diagram or density. | | - | | | :Introduced in: GUDHI 2.0.0 | - | | | | - | | | :Copyright: MIT | - | | | | - | | | :Requires: matplotlib, numpy and scipy | - +-----------------------------------------------------------------+-----------------------------------------------------------------------+-----------------------------------------------+ - | * :doc:`persistence_graphical_tools_user` | * :doc:`persistence_graphical_tools_ref` | - +-----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ + +-----------------------------------------------------------------+-----------------------------------------------------------------------+---------------------------------------------------------+ + | .. figure:: | These graphical tools comes on top of persistence results and allows | :Author: Vincent Rouvreau, Theo Lacombe | + | img/graphical_tools_representation.png | the user to display easily persistence barcode, diagram or density. | | + | | | :Since: GUDHI 2.0.0 | + | | Note that these functions return the matplotlib axis, allowing | | + | | for further modifications (title, aspect, etc.) | :License: MIT | + | | | | + | | | :Requires: `Matplotlib <installation.html#matplotlib>`_ | + +-----------------------------------------------------------------+-----------------------------------------------------------------------+---------------------------------------------------------+ + | * :doc:`persistence_graphical_tools_user` | * :doc:`persistence_graphical_tools_ref` | + +-----------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/persistence_graphical_tools_user.rst b/src/python/doc/persistence_graphical_tools_user.rst index 80002db6..e1d28c71 100644 --- a/src/python/doc/persistence_graphical_tools_user.rst +++ b/src/python/doc/persistence_graphical_tools_user.rst @@ -12,15 +12,12 @@ Definition Show persistence as a barcode ----------------------------- -.. note:: - this function requires matplotlib and numpy to be available - This function can display the persistence result as a barcode: .. plot:: :include-source: - import matplotlib.pyplot as plot + import matplotlib.pyplot as plt import gudhi off_file = gudhi.__root_source_dir__ + '/data/points/tore3D_300.off' @@ -31,41 +28,53 @@ This function can display the persistence result as a barcode: diag = simplex_tree.persistence(min_persistence=0.4) gudhi.plot_persistence_barcode(diag) - plot.show() + plt.show() Show persistence as a diagram ----------------------------- -.. note:: - this function requires matplotlib and numpy to be available - This function can display the persistence result as a diagram: .. plot:: :include-source: - import matplotlib.pyplot as plot + import matplotlib.pyplot as plt import gudhi # rips_on_tore3D_1307.pers obtained from write_persistence_diagram method persistence_file=gudhi.__root_source_dir__ + \ '/data/persistence_diagram/rips_on_tore3D_1307.pers' - gudhi.plot_persistence_diagram(persistence_file=persistence_file, + ax = gudhi.plot_persistence_diagram(persistence_file=persistence_file, legend=True) - plot.show() + # We can modify the title, aspect, etc. + ax.set_title("Persistence diagram of a torus") + ax.set_aspect("equal") # forces to be square shaped + plt.show() + +Note that (as barcode and density) it can also take a simple `np.array` +of shape (N x 2) encoding a persistence diagram (in a given dimension). + +.. plot:: + :include-source: + + import matplotlib.pyplot as plt + import gudhi + import numpy as np + d = np.array([[0., 1.], [1., 2.], [1., np.inf]]) + gudhi.plot_persistence_diagram(d) + plt.show() Persistence density ------------------- -.. note:: - this function requires matplotlib, numpy and scipy to be available +:Requires: `SciPy <installation.html#scipy>`_ If you want more information on a specific dimension, for instance: .. plot:: :include-source: - import matplotlib.pyplot as plot + import matplotlib.pyplot as plt import gudhi # rips_on_tore3D_1307.pers obtained from write_persistence_diagram method persistence_file=gudhi.__root_source_dir__ + \ @@ -75,9 +84,20 @@ If you want more information on a specific dimension, for instance: only_this_dim=1) pers_diag = [(1, elt) for elt in birth_death] # Use subplots to display diagram and density side by side - fig, axes = plot.subplots(nrows=1, ncols=2, figsize=(12, 5)) + fig, axes = plt.subplots(nrows=1, ncols=2, figsize=(12, 5)) gudhi.plot_persistence_diagram(persistence=pers_diag, axes=axes[0]) gudhi.plot_persistence_density(persistence=pers_diag, dimension=1, legend=True, axes=axes[1]) - plot.show() + plt.show() + +LaTeX support +------------- + +If you are facing issues with `LaTeX <installation.html#latex>`_ rendering, you can still deactivate LaTeX rendering by +saying: + +.. code-block:: python + + import gudhi + gudhi.persistence_graphical_tools._gudhi_matplotlib_use_tex=False diff --git a/src/python/doc/persistent_cohomology_sum.inc b/src/python/doc/persistent_cohomology_sum.inc index 4d7b077e..58e44b8a 100644 --- a/src/python/doc/persistent_cohomology_sum.inc +++ b/src/python/doc/persistent_cohomology_sum.inc @@ -1,18 +1,16 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 +-----------------------------------------------------------------+-----------------------------------------------------------------------+-----------------------------------------------+ | .. figure:: | The theory of homology consists in attaching to a topological space | :Author: Clément Maria | | ../../doc/Persistent_cohomology/3DTorus_poch.png | a sequence of (homology) groups, capturing global topological | | - | :figclass: align-center | features like connected components, holes, cavities, etc. Persistent | :Introduced in: GUDHI 2.0.0 | + | :figclass: align-center | features like connected components, holes, cavities, etc. Persistent | :Since: GUDHI 2.0.0 | | | homology studies the evolution -- birth, life and death -- of these | | - | Rips Persistent Cohomology on a 3D | features when the topological space is changing. Consequently, the | :Copyright: MIT | - | Torus | theory is essentially composed of three elements: topological spaces, | | - | | their homology groups and an evolution scheme. | | + | Rips Persistent Cohomology on a 3D Torus | features when the topological space is changing. | :License: MIT | | | | | | | Computation of persistent cohomology using the algorithm of | | | | :cite:`DBLP:journals/dcg/SilvaMV11` and | | - | | :cite:`DBLP:journals/corr/abs-1208-5018` and the Compressed | | + | | :cite:`DBLP:conf/compgeom/DeyFW14` and the Compressed | | | | Annotation Matrix implementation of | | | | :cite:`DBLP:conf/esa/BoissonnatDM13`. | | | | | | diff --git a/src/python/doc/persistent_cohomology_user.rst b/src/python/doc/persistent_cohomology_user.rst index de83cda1..39744b95 100644 --- a/src/python/doc/persistent_cohomology_user.rst +++ b/src/python/doc/persistent_cohomology_user.rst @@ -6,22 +6,27 @@ Persistent cohomology user manual ================================= Definition ---------- -===================================== ===================================== ===================================== -:Author: Clément Maria :Introduced in: GUDHI PYTHON 2.0.0 :Copyright: GPL v3 -===================================== ===================================== ===================================== -+-----------------------------------------------------------------+-----------------------------------------------------------------------+ -| :doc:`persistent_cohomology_user` | Please refer to each data structure that contains persistence | -| | feature for reference: | -| | | -| | * :doc:`simplex_tree_ref` | -| | * :doc:`cubical_complex_ref` | -| | * :doc:`periodic_cubical_complex_ref` | -+-----------------------------------------------------------------+-----------------------------------------------------------------------+ +.. list-table:: + :width: 100% + :header-rows: 0 + * - :Author: Clément Maria + - :Since: GUDHI 2.0.0 + - :License: MIT + +.. list-table:: + :width: 100% + :header-rows: 0 + + * - :doc:`persistent_cohomology_user` + - Please refer to each data structure that contains persistence feature for reference: + * :doc:`simplex_tree_ref` + * :doc:`cubical_complex_ref` + * :doc:`periodic_cubical_complex_ref` Computation of persistent cohomology using the algorithm of :cite:`DBLP:journals/dcg/SilvaMV11` and -:cite:`DBLP:journals/corr/abs-1208-5018` and the Compressed Annotation Matrix implementation of +:cite:`DBLP:conf/compgeom/DeyFW14` and the Compressed Annotation Matrix implementation of :cite:`DBLP:conf/esa/BoissonnatDM13`. The theory of homology consists in attaching to a topological space a sequence of (homology) groups, capturing global @@ -111,10 +116,3 @@ We provide several example files: run these examples with -h for details on thei * :download:`rips_complex_diagram_persistence_from_distance_matrix_file_example.py <../example/rips_complex_diagram_persistence_from_distance_matrix_file_example.py>` * :download:`random_cubical_complex_persistence_example.py <../example/random_cubical_complex_persistence_example.py>` * :download:`tangential_complex_plain_homology_from_off_file_example.py <../example/tangential_complex_plain_homology_from_off_file_example.py>` - -Bibliography -============ - -.. bibliography:: ../../biblio/bibliography.bib - :filter: docnames - :style: unsrt diff --git a/src/python/doc/point_cloud.rst b/src/python/doc/point_cloud.rst index d668428a..473b303f 100644 --- a/src/python/doc/point_cloud.rst +++ b/src/python/doc/point_cloud.rst @@ -13,10 +13,40 @@ File Readers .. autofunction:: gudhi.read_lower_triangular_matrix_from_csv_file +File Writers +------------ + +.. autofunction:: gudhi.write_points_to_off_file + Subsampling ----------- +:Requires: `Eigen <installation.html#eigen>`_ :math:`\geq` 3.1.0 and `CGAL <installation.html#cgal>`_ :math:`\geq` 4.11.0 + .. automodule:: gudhi.subsampling :members: :special-members: :show-inheritance: + +Time Delay Embedding +-------------------- + +.. autoclass:: gudhi.point_cloud.timedelay.TimeDelayEmbedding + :members: + :special-members: __call__ + +K nearest neighbors +------------------- + +.. automodule:: gudhi.point_cloud.knn + :members: + :undoc-members: + :special-members: __init__ + +Distance to measure +------------------- + +.. automodule:: gudhi.point_cloud.dtm + :members: + :undoc-members: + :special-members: __init__ diff --git a/src/python/doc/point_cloud_sum.inc b/src/python/doc/point_cloud_sum.inc index 85d52de7..f955c3ab 100644 --- a/src/python/doc/point_cloud_sum.inc +++ b/src/python/doc/point_cloud_sum.inc @@ -1,15 +1,12 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------+ - | | :math:`(x_1, x_2, \ldots, x_d)` | Utilities to process point clouds: read from file, subsample, etc. | :Author: Vincent Rouvreau | - | | :math:`(y_1, y_2, \ldots, y_d)` | | | - | | | :Introduced in: GUDHI 2.0.0 | - | | | | - | | | :Copyright: MIT (`GPL v3 </licensing/>`_) | - | | Parts of this package require CGAL. | | - | | | :Requires: `Eigen <installation.html#eigen>`__ :math:`\geq` 3.1.0 and `CGAL <installation.html#cgal>`__ :math:`\geq` 4.11.0 | - | | | | - +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------+ - | * :doc:`point_cloud` | - +----------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ + +-----------------------------------+---------------------------------------------------------------+-------------------------------------------------------------------+ + | | :math:`(x_1, x_2, \ldots, x_d)` | Utilities to process point clouds: read from file, subsample, | :Authors: Vincent Rouvreau, Marc Glisse, Masatoshi Takenouchi | + | | :math:`(y_1, y_2, \ldots, y_d)` | find neighbors, embed time series in higher dimension, | | + | | estimate a density, etc. | :Since: GUDHI 2.0.0 | + | | | | + | | | :License: MIT (`GPL v3 </licensing/>`_, BSD-3-Clause, Apache-2.0) | + +-----------------------------------+---------------------------------------------------------------+-------------------------------------------------------------------+ + | * :doc:`point_cloud` | + +-----------------------------------+-----------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/python3-sphinx-build.py b/src/python/doc/python3-sphinx-build.py deleted file mode 100755 index 84d158cf..00000000 --- a/src/python/doc/python3-sphinx-build.py +++ /dev/null @@ -1,11 +0,0 @@ -#!/usr/bin/env python3 - -""" -Emulate sphinx-build for python3 -""" - -from sys import exit, argv -from sphinx import main - -if __name__ == '__main__': - exit(main(argv)) diff --git a/src/python/doc/representations.rst b/src/python/doc/representations.rst index 11dcbcf9..b0477197 100644 --- a/src/python/doc/representations.rst +++ b/src/python/doc/representations.rst @@ -10,13 +10,47 @@ Representations manual This module, originally available at https://github.com/MathieuCarriere/sklearn-tda and named sklearn_tda, aims at bridging the gap between persistence diagrams and machine learning, by providing implementations of most of the vector representations for persistence diagrams in the literature, in a scikit-learn format. More specifically, it provides tools, using the scikit-learn standard interface, to compute distances and kernels on persistence diagrams, and to convert these diagrams into vectors in Euclidean space. -A diagram is represented as a numpy array of shape (n,2), as can be obtained from :func:`~gudhi.SimplexTree.persistence_intervals_in_dimension` for instance. Points at infinity are represented as a numpy array of shape (n,1), storing only the birth time. +A diagram is represented as a numpy array of shape (n,2), as can be obtained from :func:`~gudhi.SimplexTree.persistence_intervals_in_dimension` for instance. Points at infinity are represented as a numpy array of shape (n,1), storing only the birth time. The classes in this module can handle several persistence diagrams at once. In that case, the diagrams are provided as a list of numpy arrays. Note that it is not necessary for the diagrams to have the same number of points, i.e., for the corresponding arrays to have the same number of rows: all classes can handle arrays with different shapes. -A small example is provided +Examples +-------- -.. only:: builder_html +Landscapes +^^^^^^^^^^ - * :download:`diagram_vectorizations_distances_kernels.py <../example/diagram_vectorizations_distances_kernels.py>` +This example computes the first two Landscapes associated to a persistence diagram with four points. The landscapes are evaluated on ten samples, leading to two vectors with ten coordinates each, that are eventually concatenated in order to produce a single vector representation. + +.. testcode:: + + import numpy as np + from gudhi.representations import Landscape + # A single diagram with 4 points + D = np.array([[0.,4.],[1.,2.],[3.,8.],[6.,8.]]) + diags = [D] + l=Landscape(num_landscapes=2,resolution=10).fit_transform(diags) + print(l) + +The output is: + +.. testoutput:: + + [[1.02851895 2.05703791 2.57129739 1.54277843 0.89995409 1.92847304 + 2.95699199 3.08555686 2.05703791 1.02851895 0. 0.64282435 + 0. 0. 0.51425948 0. 0. 0. + 0.77138922 1.02851895]] + +Various kernels +^^^^^^^^^^^^^^^ + +This small example is also provided +:download:`diagram_vectorizations_distances_kernels.py <../example/diagram_vectorizations_distances_kernels.py>` + +Machine Learning and Topological Data Analysis +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +This `notebook <https://github.com/GUDHI/TDA-tutorial/blob/master/Tuto-GUDHI-representations.ipynb>`_ explains how to +efficiently combine machine learning and topological data analysis with the +:doc:`representations module<representations>`. Preprocessing @@ -46,27 +80,3 @@ Metrics :members: :special-members: :show-inheritance: - -Basic example -------------- - -This example computes the first two Landscapes associated to a persistence diagram with four points. The landscapes are evaluated on ten samples, leading to two vectors with ten coordinates each, that are eventually concatenated in order to produce a single vector representation. - -.. testcode:: - - import numpy as np - from gudhi.representations import Landscape - # A single diagram with 4 points - D = np.array([[0.,4.],[1.,2.],[3.,8.],[6.,8.]]) - diags = [D] - l=Landscape(num_landscapes=2,resolution=10).fit_transform(diags) - print(l) - -The output is: - -.. testoutput:: - - [[1.02851895 2.05703791 2.57129739 1.54277843 0.89995409 1.92847304 - 2.95699199 3.08555686 2.05703791 1.02851895 0. 0.64282435 - 0. 0. 0.51425948 0. 0. 0. - 0.77138922 1.02851895]] diff --git a/src/python/doc/representations_sum.inc b/src/python/doc/representations_sum.inc index 700828f1..9515f044 100644 --- a/src/python/doc/representations_sum.inc +++ b/src/python/doc/representations_sum.inc @@ -1,14 +1,14 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +------------------------------------------------------------------+----------------------------------------------------------------+-----------------------------------------------+ - | .. figure:: | Vectorizations, distances and kernels that work on persistence | :Author: Mathieu Carrière | - | img/sklearn-tda.png | diagrams, compatible with scikit-learn. | | - | | | :Introduced in: GUDHI 3.1.0 | - | | | | - | | | :Copyright: MIT | - | | | | - | | | :Requires: scikit-learn | - +------------------------------------------------------------------+----------------------------------------------------------------+-----------------------------------------------+ - | * :doc:`representations` | - +------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------+ + +------------------------------------------------------------------+----------------------------------------------------------------+-------------------------------------------------------------------------+ + | .. figure:: | Vectorizations, distances and kernels that work on persistence | :Author: Mathieu Carrière, Martin Royer, Gard Spreemann, Wojciech Reise | + | img/sklearn-tda.png | diagrams, compatible with scikit-learn. | | + | | | :Since: GUDHI 3.1.0 | + | | | | + | | | :License: MIT | + | | | | + | | | :Requires: `Scikit-learn <installation.html#scikit-learn>`_ | + +------------------------------------------------------------------+----------------------------------------------------------------+-------------------------------------------------------------------------+ + | * :doc:`representations` | + +------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/rips_complex_ref.rst b/src/python/doc/rips_complex_ref.rst index 22b5616c..f0582d5c 100644 --- a/src/python/doc/rips_complex_ref.rst +++ b/src/python/doc/rips_complex_ref.rst @@ -12,3 +12,25 @@ Rips complex reference manual :show-inheritance: .. automethod:: gudhi.RipsComplex.__init__ + +====================================== +Weighted Rips complex reference manual +====================================== + +.. autoclass:: gudhi.weighted_rips_complex.WeightedRipsComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.weighted_rips_complex.WeightedRipsComplex.__init__ + +================================= +DTM Rips complex reference manual +================================= + +.. autoclass:: gudhi.dtm_rips_complex.DTMRipsComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.dtm_rips_complex.DTMRipsComplex.__init__
\ No newline at end of file diff --git a/src/python/doc/rips_complex_sum.inc b/src/python/doc/rips_complex_sum.inc index 857c6893..2b125e54 100644 --- a/src/python/doc/rips_complex_sum.inc +++ b/src/python/doc/rips_complex_sum.inc @@ -1,16 +1,19 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +----------------------------------------------------------------+------------------------------------------------------------------------+----------------------------------------------------------------------+ - | .. figure:: | Rips complex is a simplicial complex constructed from a one skeleton | :Authors: Clément Maria, Pawel Dlotko, Vincent Rouvreau, Marc Glisse | - | ../../doc/Rips_complex/rips_complex_representation.png | graph. | | - | :figclass: align-center | | :Introduced in: GUDHI 2.0.0 | - | | The filtration value of each edge is computed from a user-given | | - | | distance function and is inserted until a user-given threshold | :Copyright: MIT | - | | value. | | - | | | | - | | This complex can be built from a point cloud and a distance function, | | - | | or from a distance matrix. | | - +----------------------------------------------------------------+------------------------------------------------------------------------+----------------------------------------------------------------------+ - | * :doc:`rips_complex_user` | * :doc:`rips_complex_ref` | - +----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------+ + +----------------------------------------------------------------+------------------------------------------------------------------------+----------------------------------------------------------------------------------+ + | .. figure:: | The Vietoris-Rips complex is a simplicial complex built as the | :Authors: Clément Maria, Pawel Dlotko, Vincent Rouvreau, Marc Glisse, Yuichi Ike | + | ../../doc/Rips_complex/rips_complex_representation.png | clique-complex of a proximity graph. | | + | :figclass: align-center | | :Since: GUDHI 2.0.0 | + | | We also provide sparse approximations, to speed-up the computation | | + | | of persistent homology, and weighted versions, which are more robust | :License: MIT | + | | to outliers. | | + | | | | + +----------------------------------------------------------------+------------------------------------------------------------------------+----------------------------------------------------------------------------------+ + | * :doc:`rips_complex_user` | * :doc:`rips_complex_ref` | + +----------------------------------------------------------------+------------------------------------------------------------------------+----------------------------------------------------------------------------------+ + | .. image:: | * :doc:`rips_complex_tflow_itf_ref` | :requires: `TensorFlow <installation.html#tensorflow>`_ | + | img/tensorflow.png | | | + | :target: https://www.tensorflow.org | | | + | :height: 30 | | | + +----------------------------------------------------------------+------------------------------------------------------------------------+----------------------------------------------------------------------------------+ diff --git a/src/python/doc/rips_complex_tflow_itf_ref.rst b/src/python/doc/rips_complex_tflow_itf_ref.rst new file mode 100644 index 00000000..3ce75868 --- /dev/null +++ b/src/python/doc/rips_complex_tflow_itf_ref.rst @@ -0,0 +1,48 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +TensorFlow layer for Vietoris-Rips persistence +############################################## + +.. include:: differentiation_sum.inc + +Example of gradient computed from Vietoris-Rips persistence +----------------------------------------------------------- + +.. testsetup:: + + import numpy + numpy.set_printoptions(precision=4) + +.. testcode:: + + from gudhi.tensorflow import RipsLayer + import tensorflow as tf + + X = tf.Variable([[1.,1.],[2.,2.]], dtype=tf.float32, trainable=True) + rl = RipsLayer(maximum_edge_length=2., homology_dimensions=[0]) + + with tf.GradientTape() as tape: + dgm = rl.call(X)[0][0] + loss = tf.math.reduce_sum(tf.square(.5*(dgm[:,1]-dgm[:,0]))) + + grads = tape.gradient(loss, [X]) + print(grads[0].numpy()) + +.. testcleanup:: + + numpy.set_printoptions(precision=8) + +.. testoutput:: + + [[-0.5 -0.5] + [ 0.5 0.5]] + +Documentation for RipsLayer +--------------------------- + +.. autoclass:: gudhi.tensorflow.RipsLayer + :members: + :special-members: __init__ + :show-inheritance: diff --git a/src/python/doc/rips_complex_user.rst b/src/python/doc/rips_complex_user.rst index a27573e8..a4e83462 100644 --- a/src/python/doc/rips_complex_user.rst +++ b/src/python/doc/rips_complex_user.rst @@ -7,13 +7,7 @@ Rips complex user manual Definition ---------- -==================================================================== ================================ ====================== -:Authors: Clément Maria, Pawel Dlotko, Vincent Rouvreau, Marc Glisse :Introduced in: GUDHI 2.0.0 :Copyright: GPL v3 -==================================================================== ================================ ====================== - -+-------------------------------------------+----------------------------------------------------------------------+ -| :doc:`rips_complex_user` | :doc:`rips_complex_ref` | -+-------------------------------------------+----------------------------------------------------------------------+ +.. include:: rips_complex_sum.inc The `Rips complex <https://en.wikipedia.org/wiki/Vietoris%E2%80%93Rips_complex>`_ is a simplicial complex that generalizes proximity (:math:`\varepsilon`-ball) graphs to higher dimensions. The vertices correspond to the input @@ -40,9 +34,6 @@ A vertex name corresponds to the index of the point in the given range (aka. the On this example, as edges (4,5), (4,6) and (5,6) are in the complex, simplex (4,5,6) is added with the filtration value set with :math:`max(filtration(4,5), filtration(4,6), filtration(5,6))`. And so on for simplex (0,1,2,3). -If the :doc:`RipsComplex <rips_complex_ref>` interfaces are not detailed enough for your need, please refer to -rips_persistence_step_by_step.cpp C++ example, where the graph construction over the Simplex_tree is more detailed. - A Rips complex can easily become huge, even if we limit the length of the edges and the dimension of the simplices. One easy trick, before building a Rips complex on a point cloud, is to call :func:`~gudhi.sparsify_point_set` which removes points @@ -61,6 +52,13 @@ construction of a :class:`~gudhi.RipsComplex` object asks it to build a sparse R parameter :math:`\varepsilon=0.3`, while the default `sparse=None` builds the regular Rips complex. +Another option which is especially useful if you want to compute persistent homology in "high" dimension (2 or more, +sometimes even 1), is to build the Rips complex only up to dimension 1 (a graph), then use +:func:`~gudhi.SimplexTree.collapse_edges` to reduce the size of this graph, and finally call +:func:`~gudhi.SimplexTree.expansion` to get a simplicial complex of a suitable dimension to compute its homology. This +trick gives the same persistence diagram as one would get with a plain use of `RipsComplex`, with a complex that is +often significantly smaller and thus faster to process. + Point cloud ----------- @@ -123,54 +121,44 @@ Notice that if we use asking for a very sparse version (theory only gives some guarantee on the meaning of the output if `sparse<1`), 2 to 5 edges disappear, depending on the random vertex used to start the sparsification. -Example from OFF file -^^^^^^^^^^^^^^^^^^^^^ +Example step by step +^^^^^^^^^^^^^^^^^^^^ -This example builds the :doc:`RipsComplex <rips_complex_ref>` from the given -points in an OFF file, and max_edge_length value. -Then it creates a :doc:`SimplexTree <simplex_tree_ref>` with it. +While :doc:`RipsComplex <rips_complex_ref>` is convenient, for instance to build a simplicial complex in one line -Finally, it is asked to display information about the Rips complex. +.. testcode:: + + import gudhi + points = [[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]] + cplx = gudhi.RipsComplex(points=points, max_edge_length=12.0).create_simplex_tree(max_dimension=2) +you can achieve the same result without this class for more flexibility .. testcode:: - import gudhi - off_file = gudhi.__root_source_dir__ + '/data/points/alphacomplexdoc.off' - point_cloud = gudhi.read_points_from_off_file(off_file = off_file) - rips_complex = gudhi.RipsComplex(points=point_cloud, max_edge_length=12.0) - simplex_tree = rips_complex.create_simplex_tree(max_dimension=1) - result_str = 'Rips complex is of dimension ' + repr(simplex_tree.dimension()) + ' - ' + \ - repr(simplex_tree.num_simplices()) + ' simplices - ' + \ - repr(simplex_tree.num_vertices()) + ' vertices.' - print(result_str) - fmt = '%s -> %.2f' - for filtered_value in simplex_tree.get_filtration(): - print(fmt % tuple(filtered_value)) + import gudhi + from scipy.spatial.distance import cdist + points = [[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]] + distance_matrix = cdist(points, points) + cplx = gudhi.SimplexTree.create_from_array(distance_matrix, max_filtration=12.0) + cplx.expansion(2) -the program output is: +or -.. testoutput:: +.. testcode:: - Rips complex is of dimension 1 - 18 simplices - 7 vertices. - [0] -> 0.00 - [1] -> 0.00 - [2] -> 0.00 - [3] -> 0.00 - [4] -> 0.00 - [5] -> 0.00 - [6] -> 0.00 - [2, 3] -> 5.00 - [4, 5] -> 5.39 - [0, 2] -> 5.83 - [0, 1] -> 6.08 - [1, 3] -> 6.32 - [1, 2] -> 6.71 - [5, 6] -> 7.28 - [2, 4] -> 8.94 - [0, 3] -> 9.43 - [4, 6] -> 9.49 - [3, 6] -> 11.00 + import gudhi + from scipy.spatial import cKDTree + points = [[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]] + tree = cKDTree(points) + edges = tree.sparse_distance_matrix(tree, max_distance=12.0, output_type="coo_matrix") + cplx = gudhi.SimplexTree() + cplx.insert_edges_from_coo_matrix(edges) + cplx.expansion(2) + + +This way, you can easily add a call to :func:`~gudhi.SimplexTree.collapse_edges` before the expansion, +use a different metric to compute the matrix, or other variations. Distance matrix --------------- @@ -229,54 +217,7 @@ until dimension 1 - one skeleton graph in other words), the output is: [4, 6] -> 9.49 [3, 6] -> 11.00 -Example from csv file -^^^^^^^^^^^^^^^^^^^^^ - -This example builds the :doc:`RipsComplex <rips_complex_ref>` from the given -distance matrix in a csv file, and max_edge_length value. -Then it creates a :doc:`SimplexTree <simplex_tree_ref>` with it. - -Finally, it is asked to display information about the Rips complex. - - -.. testcode:: - - import gudhi - distance_matrix = gudhi.read_lower_triangular_matrix_from_csv_file(csv_file=gudhi.__root_source_dir__ + \ - '/data/distance_matrix/full_square_distance_matrix.csv') - rips_complex = gudhi.RipsComplex(distance_matrix=distance_matrix, max_edge_length=12.0) - simplex_tree = rips_complex.create_simplex_tree(max_dimension=1) - result_str = 'Rips complex is of dimension ' + repr(simplex_tree.dimension()) + ' - ' + \ - repr(simplex_tree.num_simplices()) + ' simplices - ' + \ - repr(simplex_tree.num_vertices()) + ' vertices.' - print(result_str) - fmt = '%s -> %.2f' - for filtered_value in simplex_tree.get_filtration(): - print(fmt % tuple(filtered_value)) - -the program output is: - -.. testoutput:: - - Rips complex is of dimension 1 - 18 simplices - 7 vertices. - [0] -> 0.00 - [1] -> 0.00 - [2] -> 0.00 - [3] -> 0.00 - [4] -> 0.00 - [5] -> 0.00 - [6] -> 0.00 - [2, 3] -> 5.00 - [4, 5] -> 5.39 - [0, 2] -> 5.83 - [0, 1] -> 6.08 - [1, 3] -> 6.32 - [1, 2] -> 6.71 - [5, 6] -> 7.28 - [2, 4] -> 8.94 - [0, 3] -> 9.43 - [4, 6] -> 9.49 - [3, 6] -> 11.00 +In case this lower triangular matrix is stored in a CSV file, like `data/distance_matrix/full_square_distance_matrix.csv` in the Gudhi distribution, you can read it with :func:`~gudhi.read_lower_triangular_matrix_from_csv_file`. Correlation matrix ------------------ @@ -347,3 +288,76 @@ until dimension 1 - one skeleton graph in other words), the output is: points in the persistence diagram will be under the diagonal, and bottleneck distance and persistence graphical tool will not work properly, this is a known issue. + +Weighted Rips Complex +--------------------- + +`WeightedRipsComplex <rips_complex_ref.html#weighted-rips-complex-reference-manual>`_ builds a simplicial complex from a distance matrix and weights on vertices. + + +Example from a distance matrix and weights +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +The following example computes the weighted Rips filtration associated with a distance matrix and weights on vertices. + +.. testcode:: + + from gudhi.weighted_rips_complex import WeightedRipsComplex + dist = [[], [1]] + weights = [1, 100] + w_rips = WeightedRipsComplex(distance_matrix=dist, weights=weights) + st = w_rips.create_simplex_tree(max_dimension=2) + print(list(st.get_filtration())) + +The output is: + +.. testoutput:: + + [([0], 2.0), ([1], 200.0), ([0, 1], 200.0)] + +Example from a point cloud combined with DistanceToMeasure +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Combining with DistanceToMeasure, one can compute the DTM-filtration of a point set, as in `this notebook <https://github.com/GUDHI/TDA-tutorial/blob/master/Tuto-GUDHI-DTM-filtrations.ipynb>`_. +Remark that `DTMRipsComplex <rips_complex_user.html#dtm-rips-complex>`_ class provides exactly this function. + +.. testcode:: + + import numpy as np + from scipy.spatial.distance import cdist + from gudhi.point_cloud.dtm import DistanceToMeasure + from gudhi.weighted_rips_complex import WeightedRipsComplex + pts = np.array([[2.0, 2.0], [0.0, 1.0], [3.0, 4.0]]) + dist = cdist(pts,pts) + dtm = DistanceToMeasure(2, q=2, metric="precomputed") + r = dtm.fit_transform(dist) + w_rips = WeightedRipsComplex(distance_matrix=dist, weights=r) + st = w_rips.create_simplex_tree(max_dimension=2) + print(st.persistence()) + +The output is: + +.. testoutput:: + + [(0, (3.1622776601683795, inf)), (0, (3.1622776601683795, 5.39834563766817)), (0, (3.1622776601683795, 5.39834563766817))] + +DTM Rips Complex +---------------- + +:class:`~gudhi.dtm_rips_complex.DTMRipsComplex` builds a simplicial complex from a point set or a full distance matrix (in the form of ndarray), as described in the above example. +This class constructs a weighted Rips complex giving larger weights to outliers, which reduces their impact on the persistence diagram. See `this notebook <https://github.com/GUDHI/TDA-tutorial/blob/master/Tuto-GUDHI-DTM-filtrations.ipynb>`_ for some experiments. + +.. testcode:: + + import numpy as np + from gudhi.dtm_rips_complex import DTMRipsComplex + pts = np.array([[2.0, 2.0], [0.0, 1.0], [3.0, 4.0]]) + dtm_rips = DTMRipsComplex(points=pts, k=2) + st = dtm_rips.create_simplex_tree(max_dimension=2) + print(st.persistence()) + +The output is: + +.. testoutput:: + + [(0, (3.1622776601683795, inf)), (0, (3.1622776601683795, 5.39834563766817)), (0, (3.1622776601683795, 5.39834563766817))] diff --git a/src/python/doc/simplex_tree_ref.rst b/src/python/doc/simplex_tree_ref.rst index 9eb8c199..46b2c1e5 100644 --- a/src/python/doc/simplex_tree_ref.rst +++ b/src/python/doc/simplex_tree_ref.rst @@ -8,7 +8,6 @@ Simplex tree reference manual .. autoclass:: gudhi.SimplexTree :members: - :undoc-members: :show-inheritance: .. automethod:: gudhi.SimplexTree.__init__ diff --git a/src/python/doc/simplex_tree_sum.inc b/src/python/doc/simplex_tree_sum.inc index 5ba58d2b..6b534c9e 100644 --- a/src/python/doc/simplex_tree_sum.inc +++ b/src/python/doc/simplex_tree_sum.inc @@ -1,13 +1,18 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------+ - | .. figure:: | The simplex tree is an efficient and flexible data structure for | :Author: Clément Maria | - | ../../doc/Simplex_tree/Simplex_tree_representation.png | representing general (filtered) simplicial complexes. | | - | :alt: Simplex tree representation | | :Introduced in: GUDHI 2.0.0 | - | :figclass: align-center | The data structure is described in | | - | | :cite:`boissonnatmariasimplextreealgorithmica` | :Copyright: MIT | - | | | | - +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------+ - | * :doc:`simplex_tree_user` | * :doc:`simplex_tree_ref` | - +----------------------------------------------------------------+------------------------------------------------------------------------------------------------------+ + +----------------------------------------------------------------+------------------------------------------------------------------------+---------------------------------------------------------+ + | .. figure:: | The simplex tree is an efficient and flexible data structure for | :Author: Clément Maria | + | ../../doc/Simplex_tree/Simplex_tree_representation.png | representing general (filtered) simplicial complexes. | | + | :alt: Simplex tree representation | | :Since: GUDHI 2.0.0 | + | :figclass: align-center | The data structure is described in | | + | | :cite:`boissonnatmariasimplextreealgorithmica` | :License: MIT | + | | | | + +----------------------------------------------------------------+------------------------------------------------------------------------+---------------------------------------------------------+ + | * :doc:`simplex_tree_user` | * :doc:`simplex_tree_ref` | + +----------------------------------------------------------------+------------------------------------------------------------------------+---------------------------------------------------------+ + | .. image:: | * :doc:`ls_simplex_tree_tflow_itf_ref` | :requires: `TensorFlow <installation.html#tensorflow>`_ | + | img/tensorflow.png | | | + | :target: https://www.tensorflow.org | | | + | :height: 30 | | | + +----------------------------------------------------------------+------------------------------------------------------------------------+---------------------------------------------------------+ diff --git a/src/python/doc/tangential_complex_sum.inc b/src/python/doc/tangential_complex_sum.inc index d84aa433..2f330a07 100644 --- a/src/python/doc/tangential_complex_sum.inc +++ b/src/python/doc/tangential_complex_sum.inc @@ -1,14 +1,14 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------+ - | .. figure:: | A Tangential Delaunay complex is a simplicial complex designed to | :Author: Clément Jamin | - | ../../doc/Tangential_complex/tc_examples.png | reconstruct a :math:`k`-dimensional manifold embedded in :math:`d`- | | - | :figclass: align-center | dimensional Euclidean space. The input is a point sample coming from | :Introduced in: GUDHI 2.0.0 | - | | an unknown manifold. The running time depends only linearly on the | | - | | extrinsic dimension :math:`d` and exponentially on the intrinsic | :Copyright: MIT (`GPL v3 </licensing/>`_) | - | | dimension :math:`k`. | | - | | | :Requires: `Eigen <installation.html#eigen>`__ :math:`\geq` 3.1.0 and `CGAL <installation.html#cgal>`__ :math:`\geq` 4.11.0 | - +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------+ - | * :doc:`tangential_complex_user` | * :doc:`tangential_complex_ref` | - +----------------------------------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ + +----------------------------------------------------------------+------------------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------+ + | .. figure:: | A Tangential Delaunay complex is a simplicial complex designed to | :Author: Clément Jamin | + | ../../doc/Tangential_complex/tc_examples.png | reconstruct a :math:`k`-dimensional manifold embedded in | | + | :figclass: align-center | :math:`d`-dimensional Euclidean space. The input is a point sample | :Since: GUDHI 2.0.0 | + | | coming from an unknown manifold. The running time depends only linearly| | + | | on the extrinsic dimension :math:`d` and exponentially on the intrinsic| :License: MIT (`GPL v3 </licensing/>`_) | + | | dimension :math:`k`. | | + | | | :Requires: `Eigen <installation.html#eigen>`_ :math:`\geq` 3.1.0 and `CGAL <installation.html#cgal>`_ :math:`\geq` 4.11.0 | + +----------------------------------------------------------------+------------------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------+ + | * :doc:`tangential_complex_user` | * :doc:`tangential_complex_ref` | + +----------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/tangential_complex_user.rst b/src/python/doc/tangential_complex_user.rst index 852cf5b6..3d45473b 100644 --- a/src/python/doc/tangential_complex_user.rst +++ b/src/python/doc/tangential_complex_user.rst @@ -194,11 +194,3 @@ The output is: Tangential contains 4 vertices. Inconsistencies has been fixed. - - -Bibliography -============ - -.. bibliography:: ../../biblio/bibliography.bib - :filter: docnames - :style: unsrt diff --git a/src/python/doc/wasserstein_distance_sum.inc b/src/python/doc/wasserstein_distance_sum.inc index a97f428d..c41de017 100644 --- a/src/python/doc/wasserstein_distance_sum.inc +++ b/src/python/doc/wasserstein_distance_sum.inc @@ -1,14 +1,12 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ - | .. figure:: | The q-Wasserstein distance measures the similarity between two | :Author: Theo Lacombe | - | ../../doc/Bottleneck_distance/perturb_pd.png | persistence diagrams. It's the minimum value c that can be achieved | | - | :figclass: align-center | by a perfect matching between the points of the two diagrams (+ all | :Introduced in: GUDHI 3.1.0 | - | | diagonal points), where the value of a matching is defined as the | | - | Wasserstein distance is the q-th root of the sum of the | q-th root of the sum of all edge lengths to the power q. Edge lengths| :Copyright: MIT | - | edge lengths to the power q. | are measured in norm p, for :math:`1 \leq p \leq \infty`. | | - | | | :Requires: Python Optimal Transport (POT) :math:`\geq` 0.5.1 | - +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ - | * :doc:`wasserstein_distance_user` | | - +-----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+ + +-----------------------------------------------------------------+----------------------------------------------------------------------+-----------------------------------------+ + | .. figure:: | The q-Wasserstein distance measures the similarity between two | :Author: Theo Lacombe, Marc Glisse | + | ../../doc/Bottleneck_distance/perturb_pd.png | persistence diagrams using the sum of all edges lengths (instead of | | + | :figclass: align-center | the maximum). It allows to define sophisticated objects such as | :Since: GUDHI 3.1.0 | + | | barycenters of a family of persistence diagrams. | | + | | | :License: MIT, BSD-3-Clause | + +-----------------------------------------------------------------+----------------------------------------------------------------------+-----------------------------------------+ + | * :doc:`wasserstein_distance_user` | | + +-----------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/wasserstein_distance_user.rst b/src/python/doc/wasserstein_distance_user.rst index 32999a0c..76eb1469 100644 --- a/src/python/doc/wasserstein_distance_user.rst +++ b/src/python/doc/wasserstein_distance_user.rst @@ -9,28 +9,52 @@ Definition .. include:: wasserstein_distance_sum.inc -This implementation is based on ideas from "Large Scale Computation of Means and Cluster for Persistence Diagrams via Optimal Transport". +The q-Wasserstein distance is defined as the minimal value achieved +by a perfect matching between the points of the two diagrams (+ all +diagonal points), where the value of a matching is defined as the +q-th root of the sum of all edge lengths to the power q. Edge lengths +are measured in norm p, for :math:`1 \leq p \leq \infty`. + +Distance Functions +------------------ + +Optimal Transport +***************** + +:Requires: `Python Optimal Transport <installation.html#python-optimal-transport>`_ (POT) :math:`\geq` 0.5.1 + +This first implementation uses the `Python Optimal Transport <installation.html#python-optimal-transport>`_ +library and is based on ideas from "Large Scale Computation of Means and Cluster for Persistence +Diagrams via Optimal Transport" :cite:`10.5555/3327546.3327645`. -Function --------- .. autofunction:: gudhi.wasserstein.wasserstein_distance +Hera +**** + +This other implementation comes from `Hera +<https://bitbucket.org/grey_narn/hera/src/master/>`_ (BSD-3-Clause) which is +based on "Geometry Helps to Compare Persistence Diagrams" +:cite:`Kerber:2017:GHC:3047249.3064175` by Michael Kerber, Dmitriy +Morozov, and Arnur Nigmetov. + +.. autofunction:: gudhi.hera.wasserstein_distance Basic example -------------- +************* -This example computes the 1-Wasserstein distance from 2 persistence diagrams with euclidean ground metric. -Note that persistence diagrams must be submitted as (n x 2) numpy arrays and must not contain inf values. +This example computes the 1-Wasserstein distance from 2 persistence diagrams with Euclidean ground metric. +Note that persistence diagrams must be submitted as (n x 2) numpy arrays. .. testcode:: import gudhi.wasserstein import numpy as np - diag1 = np.array([[2.7, 3.7],[9.6, 14.],[34.2, 34.974]]) - diag2 = np.array([[2.8, 4.45],[9.5, 14.1]]) + dgm1 = np.array([[2.7, 3.7],[9.6, 14.],[34.2, 34.974]]) + dgm2 = np.array([[2.8, 4.45],[9.5, 14.1]]) - message = "Wasserstein distance value = " + '%.2f' % gudhi.wasserstein.wasserstein_distance(diag1, diag2, order=1., internal_p=2.) + message = "Wasserstein distance value = " + '%.2f' % gudhi.wasserstein.wasserstein_distance(dgm1, dgm2, order=1., internal_p=2.) print(message) The output is: @@ -38,3 +62,140 @@ The output is: .. testoutput:: Wasserstein distance value = 1.45 + +We can also have access to the optimal matching by letting `matching=True`. +It is encoded as a list of indices (i,j), meaning that the i-th point in X +is mapped to the j-th point in Y. +An index of -1 represents the diagonal. +It handles essential parts (points with infinite coordinates). However if the cardinalities of the essential parts differ, +any matching has a cost +inf and thus can be considered to be optimal. In such a case, the function returns `(np.inf, None)`. + +.. testcode:: + + import gudhi.wasserstein + import numpy as np + + dgm1 = np.array([[2.7, 3.7],[9.6, 14.],[34.2, 34.974], [3, np.inf]]) + dgm2 = np.array([[2.8, 4.45], [5, 6], [9.5, 14.1], [4, np.inf]]) + cost, matchings = gudhi.wasserstein.wasserstein_distance(dgm1, dgm2, matching=True, order=1, internal_p=2) + + message_cost = "Wasserstein distance value = %.2f" %cost + print(message_cost) + dgm1_to_diagonal = matchings[matchings[:,1] == -1, 0] + dgm2_to_diagonal = matchings[matchings[:,0] == -1, 1] + off_diagonal_match = np.delete(matchings, np.where(matchings == -1)[0], axis=0) + + for i,j in off_diagonal_match: + print("point %s in dgm1 is matched to point %s in dgm2" %(i,j)) + for i in dgm1_to_diagonal: + print("point %s in dgm1 is matched to the diagonal" %i) + for j in dgm2_to_diagonal: + print("point %s in dgm2 is matched to the diagonal" %j) + + # An example where essential part cardinalities differ + dgm3 = np.array([[1, 2], [0, np.inf]]) + dgm4 = np.array([[1, 2], [0, np.inf], [1, np.inf]]) + cost, matchings = gudhi.wasserstein.wasserstein_distance(dgm3, dgm4, matching=True, order=1, internal_p=2) + print("\nSecond example:") + print("cost:", cost) + print("matchings:", matchings) + + +The output is: + +.. testoutput:: + + Wasserstein distance value = 3.15 + point 0 in dgm1 is matched to point 0 in dgm2 + point 1 in dgm1 is matched to point 2 in dgm2 + point 3 in dgm1 is matched to point 3 in dgm2 + point 2 in dgm1 is matched to the diagonal + point 1 in dgm2 is matched to the diagonal + + Second example: + cost: inf + matchings: None + + +Barycenters +----------- + +:Requires: `Python Optimal Transport <installation.html#python-optimal-transport>`_ (POT) :math:`\geq` 0.5.1 + +A Frechet mean (or barycenter) is a generalization of the arithmetic +mean in a non linear space such as the one of persistence diagrams. +Given a set of persistence diagrams :math:`\mu_1 \dots \mu_n`, it is +defined as a minimizer of the variance functional, that is of +:math:`\mu \mapsto \sum_{i=1}^n d_2(\mu,\mu_i)^2`. +where :math:`d_2` denotes the Wasserstein-2 distance between +persistence diagrams. +It is known to exist and is generically unique. However, an exact +computation is in general untractable. Current implementation +available is based on (Turner et al., 2014), +:cite:`turner2014frechet` +and uses an EM-scheme to +provide a local minimum of the variance functional (somewhat similar +to the Lloyd algorithm to estimate a solution to the k-means +problem). The local minimum returned depends on the initialization of +the barycenter. +The combinatorial structure of the algorithm limits its +performances on large scale problems (thousands of diagrams and of points +per diagram). + +.. figure:: + ./img/barycenter.png + :figclass: align-center + + Illustration of Frechet mean between persistence + diagrams. + + +.. autofunction:: gudhi.wasserstein.barycenter.lagrangian_barycenter + +Basic example +************* + +This example estimates the Frechet mean (aka Wasserstein barycenter) between +four persistence diagrams. +It is initialized on the 4th diagram. +As the algorithm is not convex, its output depends on the initialization and +is only a local minimum of the objective function. +Initialization can be either given as an integer (in which case the i-th +diagram of the list is used as initial estimate) or as a diagram. +If None, it will randomly select one of the diagrams of the list +as initial estimate. +Note that persistence diagrams must be submitted as +(n x 2) numpy arrays and must not contain inf values. + + +.. testcode:: + + from gudhi.wasserstein.barycenter import lagrangian_barycenter + import numpy as np + + dg1 = np.array([[0.2, 0.5]]) + dg2 = np.array([[0.2, 0.7]]) + dg3 = np.array([[0.3, 0.6], [0.7, 0.8], [0.2, 0.3]]) + dg4 = np.array([]) + pdiagset = [dg1, dg2, dg3, dg4] + bary = lagrangian_barycenter(pdiagset=pdiagset,init=3) + + message = "Wasserstein barycenter estimated:" + print(message) + print(bary) + +The output is: + +.. testoutput:: + + Wasserstein barycenter estimated: + [[0.27916667 0.55416667] + [0.7375 0.7625 ] + [0.2375 0.2625 ]] + +Tutorial +******** + +This +`notebook <https://github.com/GUDHI/TDA-tutorial/blob/master/Tuto-GUDHI-Barycenters-of-persistence-diagrams.ipynb>`_ +presents the concept of barycenter, or Fréchet mean, of a family of persistence diagrams. diff --git a/src/python/doc/witness_complex_sum.inc b/src/python/doc/witness_complex_sum.inc index 71b65a71..4416fec0 100644 --- a/src/python/doc/witness_complex_sum.inc +++ b/src/python/doc/witness_complex_sum.inc @@ -1,18 +1,18 @@ .. table:: - :widths: 30 50 20 + :widths: 30 40 30 - +-------------------------------------------------------------------+----------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------+ - | .. figure:: | Witness complex :math:`Wit(W,L)` is a simplicial complex defined on | :Author: Siargey Kachanovich | - | ../../doc/Witness_complex/Witness_complex_representation.png | two sets of points in :math:`\mathbb{R}^D`. | | - | :alt: Witness complex representation | | :Introduced in: GUDHI 2.0.0 | - | :figclass: align-center | The data structure is described in | | - | | :cite:`boissonnatmariasimplextreealgorithmica`. | :Copyright: MIT (`GPL v3 </licensing/>`_ for Euclidean versions only) | - | | | | - | | | :Requires: `Eigen <installation.html#eigen>`__ :math:`\geq` 3.1.0 and `CGAL <installation.html#cgal>`__ :math:`\geq` 4.11.0 for Euclidean versions only | - +-------------------------------------------------------------------+----------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------+ - | * :doc:`witness_complex_user` | * :doc:`witness_complex_ref` | - | | * :doc:`strong_witness_complex_ref` | - | | * :doc:`euclidean_witness_complex_ref` | - | | * :doc:`euclidean_strong_witness_complex_ref` | - +-------------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ + +-------------------------------------------------------------------+----------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------------------------------+ + | .. figure:: | Witness complex :math:`Wit(W,L)` is a simplicial complex defined on | :Author: Siargey Kachanovich | + | ../../doc/Witness_complex/Witness_complex_representation.png | two sets of points in :math:`\mathbb{R}^D`. | | + | :alt: Witness complex representation | | :Since: GUDHI 2.0.0 | + | :figclass: align-center | The data structure is described in | | + | | :cite:`boissonnatmariasimplextreealgorithmica`. | :License: MIT (`GPL v3 </licensing/>`_ for Euclidean versions only) | + | | | | + | | | :Requires: `Eigen <installation.html#eigen>`_ :math:`\geq` 3.1.0 and `CGAL <installation.html#cgal>`_ :math:`\geq` 4.11.0 for Euclidean versions only | + +-------------------------------------------------------------------+----------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------------------------------+ + | * :doc:`witness_complex_user` | * :doc:`witness_complex_ref` | + | | * :doc:`strong_witness_complex_ref` | + | | * :doc:`euclidean_witness_complex_ref` | + | | * :doc:`euclidean_strong_witness_complex_ref` | + +-------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/witness_complex_user.rst b/src/python/doc/witness_complex_user.rst index 7087fa98..08dcd288 100644 --- a/src/python/doc/witness_complex_user.rst +++ b/src/python/doc/witness_complex_user.rst @@ -126,10 +126,3 @@ Example2: Computing persistence using strong relaxed witness complex Here is an example of constructing a strong witness complex filtration and computing persistence on it: * :download:`euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py <../example/euclidean_strong_witness_complex_diagram_persistence_from_off_file_example.py>` - -Bibliography -============ - -.. bibliography:: ../../biblio/bibliography.bib - :filter: docnames - :style: unsrt diff --git a/src/python/doc/zbibliography.rst b/src/python/doc/zbibliography.rst new file mode 100644 index 00000000..e23fcf25 --- /dev/null +++ b/src/python/doc/zbibliography.rst @@ -0,0 +1,10 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Bibliography +------------ + +.. bibliography:: ../../biblio/bibliography.bib + :style: plain + |
