diff options
Diffstat (limited to 'src/python/doc')
43 files changed, 3068 insertions, 0 deletions
diff --git a/src/python/doc/_templates/layout.html b/src/python/doc/_templates/layout.html new file mode 100644 index 00000000..bc0e9658 --- /dev/null +++ b/src/python/doc/_templates/layout.html @@ -0,0 +1,275 @@ +{# + basic/layout.html + ~~~~~~~~~~~~~~~~~ + + Master layout template for Sphinx themes. + + :copyright: Copyright 2007-2016 by the Sphinx team, see AUTHORS. + :license: BSD, see LICENSE for details. +#} +{%- block doctype -%} +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" + "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> +{%- endblock %} +{%- set reldelim1 = reldelim1 is not defined and ' »' or reldelim1 %} +{%- set reldelim2 = reldelim2 is not defined and ' |' or reldelim2 %} +{%- set render_sidebar = (not embedded) and (not theme_nosidebar|tobool) and + (sidebars != []) %} +{%- set url_root = pathto('', 1) %} +{# XXX necessary? #} +{%- if url_root == '#' %}{% set url_root = '' %}{% endif %} +{%- if not embedded and docstitle %} + {%- set titlesuffix = " — "|safe + docstitle|e %} +{%- else %} + {%- set titlesuffix = "" %} +{%- endif %} + +{%- macro relbar() %} + <div class="related" role="navigation" aria-label="related navigation"> + <h3>{{ _('Navigation') }}</h3> + <ul> + {%- for rellink in rellinks %} + <li class="right" {% if loop.first %}style="margin-right: 10px"{% endif %}> + <a href="{{ pathto(rellink[0]) }}" title="{{ rellink[1]|striptags|e }}" + {{ accesskey(rellink[2]) }}>{{ rellink[3] }}</a> + {%- if not loop.first %}{{ reldelim2 }}{% endif %}</li> + {%- endfor %} + {%- block rootrellink %} + <li class="nav-item nav-item-0"><a href="{{ pathto(master_doc) }}">{{ shorttitle|e }}</a>{{ reldelim1 }}</li> + {%- endblock %} + {%- for parent in parents %} + <li class="nav-item nav-item-{{ loop.index }}"><a href="{{ parent.link|e }}" {% if loop.last %}{{ accesskey("U") }}{% endif %}>{{ parent.title }}</a>{{ reldelim1 }}</li> + {%- endfor %} + {%- block relbaritems %} {% endblock %} + </ul> + </div> +{%- endmacro %} + +{%- macro sidebar() %} + {%- if render_sidebar %} + <div class="sphinxsidebar" role="navigation" aria-label="main navigation"> + <div class="sphinxsidebarwrapper"> + {%- block sidebarlogo %} + {%- if logo %} + <p class="logo"><a href="{{ pathto(master_doc) }}"> + <img class="logo" src="{{ pathto('_static/' + logo, 1) }}" alt="Logo"/> + </a></p> + {%- endif %} + {%- endblock %} + <h2><a href="index.html">GUDHI</a></h2> + <h2><a href="fileformats.html">File formats</a></h2> + <h2><a href="installation.html">GUDHI installation</a></h2> + <h2><a href="citation.html">Acknowledging the GUDHI library</a></h2> + <h2><a href="genindex.html">Index</a></h2> + <h2><a href="examples.html">Examples</a></h2> + {%- if sidebars != None %} + {#- new style sidebar: explicitly include/exclude templates #} + {%- for sidebartemplate in sidebars %} + {%- include sidebartemplate %} + {%- endfor %} + {%- else %} + {#- old style sidebars: using blocks -- should be deprecated #} + {%- block sidebartoc %} + {%- include "localtoc.html" %} + {%- endblock %} + {%- block sidebarrel %} + {%- include "relations.html" %} + {%- endblock %} + {%- block sidebarsourcelink %} + {%- include "sourcelink.html" %} + {%- endblock %} + {%- if customsidebar %} + {%- include customsidebar %} + {%- endif %} + {%- block sidebarsearch %} + {%- include "searchbox.html" %} + {%- endblock %} + {%- endif %} + </div> + </div> + {%- endif %} +{%- endmacro %} + +{%- macro script() %} + <script type="text/javascript"> + var DOCUMENTATION_OPTIONS = { + URL_ROOT: '{{ url_root }}', + VERSION: '{{ release|e }}', + COLLAPSE_INDEX: false, + FILE_SUFFIX: '{{ '' if no_search_suffix else file_suffix }}', + HAS_SOURCE: {{ has_source|lower }} + }; + </script> + {%- for scriptfile in script_files %} + <script type="text/javascript" src="{{ pathto(scriptfile, 1) }}"></script> + {%- endfor %} +{%- endmacro %} + +{%- macro css() %} +<!-- GUDHI website css for header BEGIN --> +<link rel="stylesheet" type="text/css" href="https://gudhi.inria.fr/assets/css/styles_feeling_responsive.css" /> +<!-- GUDHI website css for header END --> + <link rel="stylesheet" href="{{ pathto('_static/' + style, 1) }}" type="text/css" /> + <link rel="stylesheet" href="{{ pathto('_static/pygments.css', 1) }}" type="text/css" /> + {%- for cssfile in css_files %} + <link rel="stylesheet" href="{{ pathto(cssfile, 1) }}" type="text/css" /> + {%- endfor %} +{%- endmacro %} +<!-- GUDHI website html class for header BEGIN --> +<html xmlns="http://www.w3.org/1999/xhtml" class="no-js" lang="en"> +<!-- GUDHI website html class for header END --> + <head> + <meta http-equiv="Content-Type" content="text/html; charset={{ encoding }}" /> + {{ metatags }} + {%- block htmltitle %} + <title>{{ title|striptags|e }}{{ titlesuffix }}</title> + {%- endblock %} + {{ css() }} + {%- if not embedded %} + {{ script() }} + {%- if use_opensearch %} + <link rel="search" type="application/opensearchdescription+xml" + title="{% trans docstitle=docstitle|e %}Search within {{ docstitle }}{% endtrans %}" + href="{{ pathto('_static/opensearch.xml', 1) }}"/> + {%- endif %} + {%- if favicon %} + <link rel="shortcut icon" href="{{ pathto('_static/' + favicon, 1) }}"/> + {%- endif %} + {%- endif %} +{%- block linktags %} + {%- if hasdoc('about') %} + <link rel="author" title="{{ _('About these documents') }}" href="{{ pathto('about') }}" /> + {%- endif %} + {%- if hasdoc('genindex') %} + <link rel="index" title="{{ _('Index') }}" href="{{ pathto('genindex') }}" /> + {%- endif %} + {%- if hasdoc('search') %} + <link rel="search" title="{{ _('Search') }}" href="{{ pathto('search') }}" /> + {%- endif %} + {%- if hasdoc('copyright') %} + <link rel="copyright" title="{{ _('Copyright') }}" href="{{ pathto('copyright') }}" /> + {%- endif %} + <link rel="top" title="{{ docstitle|e }}" href="{{ pathto(master_doc) }}" /> + {%- if parents %} + <link rel="up" title="{{ parents[-1].title|striptags|e }}" href="{{ parents[-1].link|e }}" /> + {%- endif %} + {%- if next %} + <link rel="next" title="{{ next.title|striptags|e }}" href="{{ next.link|e }}" /> + {%- endif %} + {%- if prev %} + <link rel="prev" title="{{ prev.title|striptags|e }}" href="{{ prev.link|e }}" /> + {%- endif %} +{%- endblock %} +{%- block extrahead %} {% endblock %} + </head> + <body role="document"> + <!-- GUDHI website header BEGIN --> + <div id="navigation" class="sticky"> + <nav class="top-bar" role="navigation" data-topbar> + <ul class="title-area"> + <li class="name"> + <h1 class="show-for-small-only"><a href="" class="icon-tree"> GUDHI C++ 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> + </ul> + <section class="top-bar-section"> + <ul class="right"> + <li class="divider"></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 class="divider"></li> + <li class="has-dropdown"> + <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> + </ul> + </li> + <li class="divider"></li> + <li class="has-dropdown"> + <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="https://gforge.inria.fr/frs/download.php/latestzip/5280/utils_osx-latest.zip" target="_blank">Utils for Mac OSx</a></li> + <li><a href="https://gforge.inria.fr/frs/download.php/latestzip/5279/utils_win64-latest.zip" target="_blank">Utils for Win x64</a></li> + </ul> + </li> + <li class="divider"></li> + <li class="has-dropdown"> + <a href="#">Documentation</a> + <ul class="dropdown"> + <li><a href="/doc/latest/">C++ documentation</a></li> + <li><a href="/doc/latest/installation.html">C++ installation manual</a></li> + <li><a href="/python/latest/">Python documentation</a></li> + <li><a href="/python/latest/installation.html">Python installation manual</a></li> + <li><a href="/utils/">Utilities</a></li> + <li><a href="/tutorials/">Tutorials</a></li> + <li><a href="/dockerfile/">Dockerfile</a></li> + </ul> + </li> + <li class="divider"></li> + <li><a href="/interfaces/">Interfaces</a></li> + <li class="divider"></li> + </ul> + </section> + </nav> + </div><!-- /#navigation --> + <!-- GUDHI website header BEGIN --> + + +{%- block header %}{% endblock %} + +{%- block relbar1 %}{% endblock %} + +{%- block content %} + {%- block sidebar1 %} {# possible location for sidebar #} {% endblock %} + + <div class="document"> + {%- block document %} + <div class="documentwrapper"> + {%- if render_sidebar %} + <div class="bodywrapper"> + {%- endif %} + <div class="body" role="main"> + {% block body %} {% endblock %} + </div> + {%- if render_sidebar %} + </div> + {%- endif %} + </div> + {%- endblock %} + + {%- block sidebar2 %}{{ sidebar() }}{% endblock %} + <div class="clearer"></div> + </div> +{%- endblock %} + +{%- block relbar2 %}{% endblock %} + +{%- block footer %} + <div class="footer" role="contentinfo"> + {%- if show_copyright %} + {%- if hasdoc('copyright') %} + {% trans path=pathto('copyright'), copyright=copyright|e %}© <a href="{{ path }}">Copyright</a> {{ copyright }}.{% endtrans %} + {%- else %} + {% trans copyright=copyright|e %} {{ copyright }}.{% endtrans %} + {%- endif %} + {%- endif %} + {%- if last_updated %} + {% trans last_updated=last_updated|e %}Last updated on {{ last_updated }}.{% endtrans %} + {%- endif %} + {%- if show_sphinx %} + {% trans sphinx_version=sphinx_version|e %}Created using <a href="http://sphinx-doc.org/">Sphinx</a> {{ sphinx_version }}.{% endtrans %} + {%- endif %} + </div> +{%- endblock %} + </body> +</html> + diff --git a/src/python/doc/alpha_complex_ref.rst b/src/python/doc/alpha_complex_ref.rst new file mode 100644 index 00000000..7da79543 --- /dev/null +++ b/src/python/doc/alpha_complex_ref.rst @@ -0,0 +1,14 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +============================== +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 new file mode 100644 index 00000000..9049e654 --- /dev/null +++ b/src/python/doc/alpha_complex_sum.inc @@ -0,0 +1,20 @@ +.. table:: + :widths: 30 50 20 + + +----------------------------------------------------------------+------------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------+ + | .. 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 simplex | :Copyright: MIT (`GPL v3 </licensing/>`_) | + | | is then said to be Gabriel), and as the minimum of the filtration | | + | | values of the codimension 1 cofaces that make it not Gabriel | :Requires: `Eigen3 <installation.html#eigen3>`__ and `CGAL <installation.html#cgal>`__ :math:`\geq` 4.11.0 | + | | otherwise. All simplices that have a filtration value strictly | | + | | greater than a given alpha squared value are not inserted into the | | + | | complex. | | + | | | | + | | This package requires having CGAL version 4.7 or higher (4.8.1 is | | + | | advised for better performance). | | + +----------------------------------------------------------------+------------------------------------------------------------------------+------------------------------------------------------------------------------------------------------------+ + | * :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 new file mode 100644 index 00000000..d1e9c7cd --- /dev/null +++ b/src/python/doc/alpha_complex_user.rst @@ -0,0 +1,210 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Alpha complex user manual +========================= +Definition +---------- + +.. include:: alpha_complex_sum.inc + +Alpha_complex is constructing a :doc:`Simplex_tree <simplex_tree_ref>` using +`Delaunay Triangulation <http://doc.cgal.org/latest/Triangulation/index.html#Chapter_Triangulations>`_ +:cite:`cgal:hdj-t-15b` from `CGAL <http://www.cgal.org/>`_ (the Computational Geometry Algorithms Library +:cite:`cgal:eb-15b`). + +Remarks +^^^^^^^ +When Alpha_complex is constructed with an infinite value of :math:`\alpha`, the complex is a Delaunay complex. + +Example from points +------------------- + +This example builds the Delaunay triangulation from the given points, and initializes the alpha complex with it: + +.. testcode:: + + import gudhi + alpha_complex = gudhi.AlphaComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]]) + + simplex_tree = alpha_complex.create_simplex_tree(max_alpha_square=60.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) + fmt = '%s -> %.2f' + for filtered_value in simplex_tree.get_filtration(): + print(fmt % tuple(filtered_value)) + +The output is: + +.. testoutput:: + + Alpha complex is of dimension 2 - 25 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 + [2, 6] -> 36.50 + [2, 3, 6] -> 36.50 + [2, 4, 6] -> 37.24 + [0, 4] -> 59.71 + [0, 2, 4] -> 59.71 + + +Algorithm +--------- + +Data structure +^^^^^^^^^^^^^^ + +In order to build the alpha complex, first, a Simplex tree is built from the cells of a Delaunay Triangulation. +(The filtration value is set to NaN, which stands for unknown value): + +.. figure:: + ../../doc/Alpha_complex/alpha_complex_doc.png + :figclass: align-center + :alt: Simplex tree structure construction example + + Simplex tree structure construction example + +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** + + make_filtration_non_decreasing() + + prune_above_filtration() + +Dimension 2 +^^^^^^^^^^^ + +From the example above, it means the algorithm looks into each triangle ([0,1,2], [0,2,4], [1,2,3], ...), +computes the filtration value of the triangle, and then propagates the filtration value as described +here: + +.. figure:: + ../../doc/Alpha_complex/alpha_complex_doc_420.png + :figclass: align-center + :alt: Filtration value propagation example + + Filtration value propagation example + +Dimension 1 +^^^^^^^^^^^ + +Then, the algorithm looks into each edge ([0,1], [0,2], [1,2], ...), +computes the filtration value of the edge (in this case, propagation will have no effect). + +Dimension 0 +^^^^^^^^^^^ + +Finally, the algorithm looks into each vertex ([0], [1], [2], [3], [4], [5] and [6]) and +sets the filtration value (0 in case of a vertex - propagation will have no effect). + +Non decreasing filtration values +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +As the squared radii computed by CGAL are an approximation, it might happen that these alpha squared values do not +quite define a proper filtration (i.e. non-decreasing with respect to inclusion). +We fix that up by calling `Simplex_tree::make_filtration_non_decreasing()` (cf. +`C++ version <http://gudhi.gforge.inria.fr/doc/latest/index.html>`_). + +Prune above given filtration value +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +The simplex tree is pruned from the given maximum alpha squared value (cf. `Simplex_tree::prune_above_filtration()` +in the `C++ version <http://gudhi.gforge.inria.fr/doc/latest/index.html>`_). +In the following example, the value is given by the user as argument of the program. + + +Example from OFF file +^^^^^^^^^^^^^^^^^^^^^ + +This example builds the Delaunay triangulation from the points given by an OFF file, and initializes the alpha complex +with it. + + +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=59.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) + fmt = '%s -> %.2f' + for filtered_value in simplex_tree.get_filtration(): + print(fmt % tuple(filtered_value)) + +the program output is: + +.. testoutput:: + + Alpha complex is of dimension 2 - 23 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 + [2, 6] -> 36.50 + [2, 3, 6] -> 36.50 + [2, 4, 6] -> 37.24 + +CGAL citations +============== + +.. bibliography:: ../../biblio/how_to_cite_cgal.bib + :filter: docnames + :style: unsrt diff --git a/src/python/doc/bottleneck_distance_sum.inc b/src/python/doc/bottleneck_distance_sum.inc new file mode 100644 index 00000000..6eb0ac19 --- /dev/null +++ b/src/python/doc/bottleneck_distance_sum.inc @@ -0,0 +1,14 @@ +.. table:: + :widths: 30 50 20 + + +-----------------------------------------------------------------+----------------------------------------------------------------------+------------------------------------------------------------------+ + | .. 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` | | + +-----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/bottleneck_distance_user.rst b/src/python/doc/bottleneck_distance_user.rst new file mode 100644 index 00000000..9435c7f1 --- /dev/null +++ b/src/python/doc/bottleneck_distance_user.rst @@ -0,0 +1,67 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Bottleneck distance user manual +=============================== +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`. + +Function +-------- +.. autofunction:: gudhi.bottleneck_distance + +Distance computation +-------------------- + +The following example explains how the distance is computed: + +.. testcode:: + + import gudhi + + message = "Bottleneck distance = " + '%.1f' % gudhi.bottleneck_distance([[0., 0.]], [[0., 13.]]) + print(message) + +.. testoutput:: + + Bottleneck distance = 6.5 + +.. figure:: + ../../doc/Bottleneck_distance/bottleneck_distance_example.png + :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) + + +Basic example +------------- + +This other example computes the bottleneck distance from 2 persistence diagrams: + +.. testcode:: + + import gudhi + + diag1 = [[2.7, 3.7],[9.6, 14.],[34.2, 34.974], [3.,float('Inf')]] + diag2 = [[2.8, 4.45],[9.5, 14.1],[3.2,float('Inf')]] + + message = "Bottleneck distance approximation = " + '%.2f' % gudhi.bottleneck_distance(diag1, diag2, 0.1) + print(message) + + message = "Bottleneck distance value = " + '%.2f' % gudhi.bottleneck_distance(diag1, diag2) + print(message) + +The output is: + +.. testoutput:: + + Bottleneck distance approximation = 0.81 + Bottleneck distance value = 0.75 diff --git a/src/python/doc/citation.rst b/src/python/doc/citation.rst new file mode 100644 index 00000000..117eb9dd --- /dev/null +++ b/src/python/doc/citation.rst @@ -0,0 +1,19 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Acknowledging the GUDHI library +############################### + +We kindly ask users to cite the GUDHI library as appropriately as possible in +their papers, and to mention the use of the GUDHI library on the web pages of +their projects using GUDHI and provide us with links to these web pages. Feel +free to contact us in case you have any question or remark on this topic. + +We provide GUDHI bibtex entries for the modules of the User and Reference +Manual, as well as for publications directly related to the GUDHI library. + +GUDHI bibtex +************ + +.. literalinclude:: ../../biblio/how_to_cite_gudhi.bib diff --git a/src/python/doc/conf.py b/src/python/doc/conf.py new file mode 100755 index 00000000..e4c718c3 --- /dev/null +++ b/src/python/doc/conf.py @@ -0,0 +1,203 @@ +# -*- coding: utf-8 -*- +# +# GUDHI documentation build configuration file, created by +# sphinx-quickstart on Thu Jun 30 09:55:51 2016. +# +# This file is execfile()d with the current directory set to its +# containing dir. +# +# Note that not all possible configuration values are present in this +# autogenerated file. +# +# All configuration values have a default; values that are commented out +# serve to show the default. + +import sys +import os + +# If extensions (or modules to document with autodoc) are in another directory, +# add these directories to sys.path here. If the directory is relative to the +# documentation root, use os.path.abspath to make it absolute, like shown here. +#sys.path.insert(0, os.path.abspath('.')) + +# Path to Gudhi.so from source path +sys.path.insert(0, os.path.abspath('.')) + +# -- General configuration ------------------------------------------------ + +# If your documentation needs a minimal Sphinx version, state it here. +#needs_sphinx = '1.0' + +# Add any Sphinx extension module names here, as strings. They can be +# extensions coming with Sphinx (named 'sphinx.ext.*') or your custom +# ones. +extensions = [ + 'matplotlib.sphinxext.plot_directive', + 'sphinx.ext.autodoc', + 'sphinx.ext.doctest', + 'sphinx.ext.todo', + 'sphinx.ext.mathjax', + 'sphinx.ext.ifconfig', + 'sphinx.ext.viewcode', + 'sphinxcontrib.bibtex', +] + +todo_include_todos = True +# plot option : do not show hyperlinks (Source code, png, hires.png, pdf) +plot_html_show_source_link = False +plot_html_show_formats = False +# Add any paths that contain templates here, relative to this directory. +templates_path = ['_templates'] + +# The suffix of source filenames. +source_suffix = '.rst' + +# The encoding of source files. +#source_encoding = 'utf-8-sig' + +# The master toctree document. +master_doc = 'index' + +import gudhi + +# General information about the project. +project = gudhi.__name__ +copyright = gudhi.__copyright__ + ' - MIT' + +# The version info for the project you're documenting, acts as replacement for +# |version| and |release|, also used in various other places throughout the +# built documents. +# +# The short X.Y version. +version = gudhi.__version__ +# The full version, including alpha/beta/rc tags. +#release = '2.0.1-rc1' + +# The language for content autogenerated by Sphinx. Refer to documentation +# for a list of supported languages. +#language = None + +# There are two options for replacing |today|: either, you set today to some +# non-false value, then it is used: +#today = '' +# Else, today_fmt is used as the format for a strftime call. +#today_fmt = '%B %d, %Y' + +# List of patterns, relative to source directory, that match files and +# directories to ignore when looking for source files. +exclude_patterns = ['_build', '*.inc'] + +# The reST default role (used for this markup: `text`) to use for all +# documents. +#default_role = None + +# If true, '()' will be appended to :func: etc. cross-reference text. +#add_function_parentheses = True + +# If true, the current module name will be prepended to all description +# unit titles (such as .. function::). +#add_module_names = True + +# If true, sectionauthor and moduleauthor directives will be shown in the +# output. They are ignored by default. +#show_authors = False + +# The name of the Pygments (syntax highlighting) style to use. +pygments_style = 'sphinx' + +# A list of ignored prefixes for module index sorting. +#modindex_common_prefix = [] + +# If true, keep warnings as "system message" paragraphs in the built documents. +#keep_warnings = False + + +# -- Options for HTML output ---------------------------------------------- + +# The theme to use for HTML and HTML Help pages. See the documentation for +# a list of builtin themes. +html_theme = 'classic' + +# 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%", +} + +# Add any paths that contain custom themes here, relative to this directory. +#html_theme_path = [] + +# The name for this set of Sphinx documents. If None, it defaults to +# "<project> v<release> documentation". +#html_title = None + +# A shorter title for the navigation bar. Default is the same as html_title. +#html_short_title = None + +# The name of an image file (relative to this directory) to place at the top +# of the sidebar. +#html_logo = + +# The name of an image file (within the static path) to use as favicon of the +# docs. This file should be a Windows icon file (.ico) being 16x16 or 32x32 +# pixels large. +#html_favicon = + +# Add any paths that contain custom static files (such as style sheets) here, +# relative to this directory. They are copied after the builtin static files, +# so a file named "default.css" will overwrite the builtin "default.css". +html_static_path = ['_static'] + +# Add any extra paths that contain custom files (such as robots.txt or +# .htaccess) here, relative to this directory. These files are copied +# directly to the root of the documentation. +#html_extra_path = [] + +# If not '', a 'Last updated on:' timestamp is inserted at every page bottom, +# using the given strftime format. +html_last_updated_fmt = '%b %d, %Y' + +# If true, SmartyPants will be used to convert quotes and dashes to +# typographically correct entities. +#html_use_smartypants = True + +# Custom sidebar templates, maps document names to template names. +#html_sidebars = {} + +# Additional templates that should be rendered to pages, maps page names to +# template names. +#html_additional_pages = {'installation': 'installation.html'} + +# If false, no module index is generated. +#html_domain_indices = True + +# If false, no index is generated. +#html_use_index = True + +# If true, the index is split into individual pages for each letter. +#html_split_index = False + +# If true, links to the reST sources are added to the pages. +#html_show_sourcelink = True + +# If true, "Created using Sphinx" is shown in the HTML footer. Default is True. +#html_show_sphinx = True + +# If true, "(C) Copyright ..." is shown in the HTML footer. Default is True. +#html_show_copyright = True + +# If true, an OpenSearch description file will be output, and all pages will +# contain a <link> tag referring to it. The value of this option must be the +# base URL from which the finished HTML is served. +#html_use_opensearch = '' + +# This is the file name suffix for HTML files (e.g. ".xhtml"). +#html_file_suffix = None + +# Output file base name for HTML help builder. +htmlhelp_basename = 'GUDHIdoc' + diff --git a/src/python/doc/cubical_complex_ref.rst b/src/python/doc/cubical_complex_ref.rst new file mode 100644 index 00000000..1fe9d5fb --- /dev/null +++ b/src/python/doc/cubical_complex_ref.rst @@ -0,0 +1,13 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Cubical complex reference manual +################################ + +.. autoclass:: gudhi.CubicalComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.CubicalComplex.__init__ diff --git a/src/python/doc/cubical_complex_sum.inc b/src/python/doc/cubical_complex_sum.inc new file mode 100644 index 00000000..f200e695 --- /dev/null +++ b/src/python/doc/cubical_complex_sum.inc @@ -0,0 +1,14 @@ +.. table:: + :widths: 30 50 20 + + +--------------------------------------------------------------------------+----------------------------------------------------------------------+-----------------------------+ + | .. 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` | + +--------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/cubical_complex_user.rst b/src/python/doc/cubical_complex_user.rst new file mode 100644 index 00000000..b13b500e --- /dev/null +++ b/src/python/doc/cubical_complex_user.rst @@ -0,0 +1,168 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +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` | ++---------------------------------------------+----------------------------------------------------------------------+ + +The cubical complex is an example of a structured complex useful in computational mathematics (specially rigorous +numerics) and image analysis. + +An *elementary interval* is an interval of a form :math:`[n,n+1]`, or :math:`[n,n]`, for :math:`n \in \mathcal{Z}`. +The first one is called *non-degenerate*, while the second one is a *degenerate* interval. A +*boundary of a elementary interval* is a chain :math:`\partial [n,n+1] = [n+1,n+1]-[n,n]` in case of +non-degenerated elementary interval and :math:`\partial [n,n] = 0` in case of degenerate elementary interval. An +*elementary cube* :math:`C` is a product of elementary intervals, :math:`C=I_1 \times \ldots \times I_n`. +*Embedding dimension* of a cube is n, the number of elementary intervals (degenerate or not) in the product. +A *dimension of a cube* :math:`C=I_1 \times ... \times I_n` is the number of non degenerate elementary +intervals in the product. A *boundary of a cube* :math:`C=I_1 \times \ldots \times I_n` is a chain obtained +in the following way: + +.. math:: + + \partial C = (\partial I_1 \times \ldots \times I_n) + (I_1 \times \partial I_2 \times \ldots \times I_n) + + \ldots + (I_1 \times I_2 \times \ldots \times \partial I_n). + +A *cubical complex* :math:`\mathcal{K}` is a collection of cubes closed under operation of taking boundary +(i.e. boundary of every cube from the collection is in the collection). A cube :math:`C` in cubical complex +:math:`\mathcal{K}` is *maximal* if it is not in a boundary of any other cube in :math:`\mathcal{K}`. A +*support* of a cube :math:`C` is the set in :math:`\mathbb{R}^n` occupied by :math:`C` (:math:`n` is the embedding +dimension of :math:`C`). + +Cubes may be equipped with a filtration values in which case we have filtered cubical complex. All the cubical +complexes considered in this implementation are filtered cubical complexes (although, the range of a filtration may +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. +--------------- + +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 +of so called bitmaps. Let +:math:`R = [b_1,e_1] \times \ldots \times [b_n,e_n]`, for :math:`b_1,...b_n,e_1,...,e_n \in \mathbb{Z}`, +:math:`b_i \leq d_i` be the considered rectangular region and let :math:`\mathcal{K}` be a filtered +cubical complex having the rectangle :math:`R` as its support. Note that the structure of the coordinate system gives +a way a lexicographical ordering of cells of :math:`\mathcal{K}`. This ordering is a base of the presented +bitmap-based implementation. In this implementation, the whole cubical complex is stored as a vector of the values +of filtration. This, together with dimension of :math:`\mathcal{K}` and the sizes of :math:`\mathcal{K}` in all +directions, allows to determine, dimension, neighborhood, boundary and coboundary of every cube +:math:`C \in \mathcal{K}`. + +.. figure:: + ../../doc/Bitmap_cubical_complex/Cubical_complex_representation.png + :alt: Cubical complex. + :figclass: align-center + + Cubical complex. + +Note that the cubical complex in the figure above is, in a natural way, a product of one dimensional cubical +complexes in :math:`\mathbb{R}`. The number of all cubes in each direction is equal :math:`2n+1`, where :math:`n` is +the number of maximal cubes in the considered direction. Let us consider a cube at the position :math:`k` in the +bitmap. +Knowing the sizes of the bitmap, by a series of modulo operation, we can determine which elementary intervals are +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. +------------- + +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 +who want to use the code directly. They can be found in the :doc:`cubical_complex_ref`. +Currently one input from a text file is used. It uses a format inspired from the Perseus software +`Perseus software <http://www.sas.upenn.edu/~vnanda/perseus/>`_ by Vidit Nanda. + +.. note:: + While Perseus assume the filtration of all maximal cubes to be non-negative, over here we do not enforce this and + 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. + +.. testcode:: + + import gudhi + cubical_complex = gudhi.CubicalComplex(perseus_file=gudhi.__root_source_dir__ + \ + '/data/bitmap/cubicalcomplexdoc.txt') + result_str = 'Cubical complex is of dimension ' + repr(cubical_complex.dimension()) + ' - ' + \ + repr(cubical_complex.num_simplices()) + ' simplices.' + print(result_str) + +the program output is: + +.. testoutput:: + + Cubical complex is of dimension 2 - 49 simplices. + +Periodic boundary conditions. +----------------------------- + +Often one would like to impose periodic boundary conditions to the cubical complex (cf. +:doc:`periodic_cubical_complex_ref`). +Let :math:`I_1\times ... \times I_n` be a box that is decomposed with a cubical complex :math:`\mathcal{K}`. +Imposing periodic boundary conditions in the direction i, means that the left and the right side of a complex +:math:`\mathcal{K}` are considered the same. In particular, if for a bitmap :math:`\mathcal{K}` periodic boundary +conditions are imposed in all directions, then complex :math:`\mathcal{K}` became n-dimensional torus. One can use +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: + +.. testcode:: + + import gudhi + periodic_cc = gudhi.PeriodicCubicalComplex(perseus_file=gudhi.__root_source_dir__ + \ + '/data/bitmap/periodiccubicalcomplexdoc.txt') + result_str = 'Periodic cubical complex is of dimension ' + repr(periodic_cc.dimension()) + ' - ' + \ + repr(periodic_cc.num_simplices()) + ' simplices.' + print(result_str) + +the program output is: + +.. testoutput:: + + Periodic cubical complex is of dimension 2 - 42 simplices. + +Or it can be defined as follows: + +.. testcode:: + + from gudhi import PeriodicCubicalComplex as pcc + periodic_cc = pcc(dimensions=[3,3], + top_dimensional_cells= [0, 0, 0, 0, 1, 0, 0, 0, 0], + periodic_dimensions=[True, False]) + result_str = 'Periodic cubical complex is of dimension ' + repr(periodic_cc.dimension()) + ' - ' + \ + repr(periodic_cc.num_simplices()) + ' simplices.' + print(result_str) + +the program output is: + +.. testoutput:: + + Periodic cubical complex is of dimension 2 - 42 simplices. + +Examples. +--------- + +End user programs are available in python/example/ folder. + +Bibliography +============ + +.. bibliography:: ../../biblio/bibliography.bib + :filter: docnames + :style: unsrt diff --git a/src/python/doc/euclidean_strong_witness_complex_ref.rst b/src/python/doc/euclidean_strong_witness_complex_ref.rst new file mode 100644 index 00000000..1a602cd5 --- /dev/null +++ b/src/python/doc/euclidean_strong_witness_complex_ref.rst @@ -0,0 +1,14 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +================================================= +Euclidean strong witness complex reference manual +================================================= + +.. autoclass:: gudhi.EuclideanStrongWitnessComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.EuclideanStrongWitnessComplex.__init__ diff --git a/src/python/doc/euclidean_witness_complex_ref.rst b/src/python/doc/euclidean_witness_complex_ref.rst new file mode 100644 index 00000000..28daf965 --- /dev/null +++ b/src/python/doc/euclidean_witness_complex_ref.rst @@ -0,0 +1,14 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +========================================== +Euclidean witness complex reference manual +========================================== + +.. autoclass:: gudhi.EuclideanWitnessComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.EuclideanWitnessComplex.__init__ diff --git a/src/python/doc/examples.rst b/src/python/doc/examples.rst new file mode 100644 index 00000000..edbc2f72 --- /dev/null +++ b/src/python/doc/examples.rst @@ -0,0 +1,30 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Examples +######## + +.. only:: builder_html + + * :download:`rips_complex_from_points_example.py <../example/rips_complex_from_points_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:`witness_complex_from_nearest_landmark_table.py <../example/witness_complex_from_nearest_landmark_table.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:`rips_complex_diagram_persistence_from_distance_matrix_file_example.py <../example/rips_complex_diagram_persistence_from_distance_matrix_file_example.py>` + * :download:`rips_persistence_diagram.py <../example/rips_persistence_diagram.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:`voronoi_graph_induced_complex.py <../example/voronoi_graph_induced_complex.py>` + * :download:`nerve_of_a_covering.py <../example/nerve_of_a_covering.py>` diff --git a/src/python/doc/fileformats.rst b/src/python/doc/fileformats.rst new file mode 100644 index 00000000..345dfdba --- /dev/null +++ b/src/python/doc/fileformats.rst @@ -0,0 +1,127 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +File formats +############ + +OFF file format +*************** + +OFF files must be conform to format described here: +http://www.geomview.org/docs/html/OFF.html + +OFF files are mainly used as point cloud inputs. Here is an example of 7 points +in a 3-dimensional space. As edges and faces are not used for point set, there +is no need to specify them (just set their numbers to 0): + +.. literalinclude:: ../../data/points/alphacomplexdoc.off + +.. centered:: ../../points/alphacomplexdoc.off + +For dimensions bigger than 3, the dimension can be set like here:: + + # Dimension is no more 3 + nOFF + # dimension 4 - 7 vertices - 0 face - 0 edge + 4 7 0 0 + # Point set: + 1.0 1.0 0.0 0.0 + 7.0 0.0 0.0 0.0 + 4.0 6.0 0.0 0.0 + 9.0 6.0 0.0 0.0 + 0.0 14.0 0.0 0.0 + 2.0 19.0 0.0 0.0 + 9.0 17.0 0.0 0.0 + +Persistence Diagram +******************* + +Such a file, whose extension is usually ``.pers``, contains a list of +persistence intervals. + +Lines starting with ``#`` are ignored (comments). + +Other lines might contain 2, 3 or 4 values (the number of values on each line +must be the same for all lines):: + + [[field] dimension] birth death + +Here is a simple sample file:: + + # Persistence diagram example + 2 2.7 3.7 + 2 9.6 14. + # Some comments + 3 34.2 34.974 + 4 3. inf + +Other sample files can be found in the `data/persistence_diagram` folder. + +Such files can be generated with +:meth:`gudhi.SimplexTree.write_persistence_diagram`, read with +:meth:`gudhi.read_persistence_intervals_grouped_by_dimension`, or +:meth:`gudhi.read_persistence_intervals_in_dimension` and displayed with +:meth:`gudhi.plot_persistence_barcode` or +:meth:`gudhi.plot_persistence_diagram`. + +Iso-cuboid +********** + +Such a file describes an iso-oriented cuboid with diagonal opposite vertices +(min_x, min_y, min_z,...) and (max_x, max_y, max_z, ...). The format is:: + + min_x min_y [min_z ...] + max_x max_y [max_z ...] + +Here is a simple sample file in the 3D case:: + + -1. -1. -1. + 1. 1. 1. + + +.. _Perseus file format: + +Perseus +******* + +This file format is a format inspired from the +`Perseus software <http://www.sas.upenn.edu/~vnanda/perseus/>`_ by Vidit Nanda. +The first line contains a number d begin the dimension of the bitmap (2 in the +example below). Next d lines are the numbers of top dimensional cubes in each +dimensions (3 and 3 in the example below). Next, in lexicographical order, the +filtration of top dimensional cubes is given (1 4 6 8 20 4 7 6 5 in the example +below). + +.. figure:: + ../../doc/Bitmap_cubical_complex/exampleBitmap.png + :alt: Example of a input data. + :figclass: align-center + + Example of a input data. + +The input file for the following complex is: + +.. literalinclude:: ../../data/bitmap/cubicalcomplexdoc.txt + +.. centered:: ../../data/bitmap/cubicalcomplexdoc.txt + +To indicate periodic boundary conditions in a given direction, then number of +top dimensional cells in this direction have to be multiplied by -1. For +instance: + +.. literalinclude:: ../../data/bitmap/periodiccubicalcomplexdoc.txt + +.. centered:: ../../data/bitmap/periodiccubicalcomplexdoc.txt + + +Indicate that we have imposed periodic boundary conditions in the direction x, +but not in the direction y. + +Other sample files can be found in the `data/bitmap` folder. + +.. note:: + Unlike in Perseus format the filtration on the maximal cubes can be any + double precision number. Consequently one cannot mark the cubes that are + not present with ``-1``'s. To do that please set their filtration value to + :math:`+\infty` (aka. ``inf`` in the file).
\ No newline at end of file diff --git a/src/python/doc/img/graphical_tools_representation.png b/src/python/doc/img/graphical_tools_representation.png Binary files differnew file mode 100644 index 00000000..9759f7ba --- /dev/null +++ b/src/python/doc/img/graphical_tools_representation.png diff --git a/src/python/doc/index.rst b/src/python/doc/index.rst new file mode 100644 index 00000000..e379bc23 --- /dev/null +++ b/src/python/doc/index.rst @@ -0,0 +1,86 @@ +GUDHI Python module documentation +################################# + +.. figure:: + ../../doc/common/Gudhi_banner.png + :alt: Gudhi banner + :figclass: align-center + +Complexes +********* + +Cubical complexes +================= + +.. include:: cubical_complex_sum.inc + +Simplicial complexes +==================== + +Alpha complex +------------- + +.. include:: alpha_complex_sum.inc + +Rips complex +------------- + +.. include:: rips_complex_sum.inc + +Witness complex +--------------- + +.. include:: witness_complex_sum.inc + +Cover complexes +=============== + +.. include:: nerve_gic_complex_sum.inc + +Data structures and basic operations +************************************ + +Data structures +=============== + +Simplex tree +------------ + +.. include:: simplex_tree_sum.inc + +Topological descriptors computation +*********************************** + +Persistence cohomology +====================== + +.. include:: persistent_cohomology_sum.inc + +Manifold reconstruction +*********************** + +Tangential complex +================== + +.. include:: tangential_complex_sum.inc + + +Topological descriptors tools +***************************** + +Bottleneck distance +=================== + +.. include:: bottleneck_distance_sum.inc + +Persistence graphical tools +=========================== + +.. include:: persistence_graphical_tools_sum.inc + +Bibliography +************ + +.. bibliography:: ../../biblio/bibliography.bib + :filter: docnames + :style: unsrt diff --git a/src/python/doc/installation.rst b/src/python/doc/installation.rst new file mode 100644 index 00000000..1c672ce3 --- /dev/null +++ b/src/python/doc/installation.rst @@ -0,0 +1,256 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Installation +############ + +Compiling +********* +The library uses c++11 and requires `Boost <https://www.boost.org/>`_ ≥ 1.56.0, +`CMake <https://www.cmake.org/>`_ ≥ 3.1 to generate makefiles, and +`python <https://www.python.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 and 3.6 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 +: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: + +.. code-block:: bash + + cd /path-to-gudhi/ + mkdir build + cd build/ + cmake .. + cd python + make + +GUDHI Python module installation +================================ + +Once the compilation succeeds, one can add the GUDHI Python module path to the +PYTHONPATH: + +.. code-block:: bash + + # For windows, you have to set PYTHONPATH environment variable + export PYTHONPATH='$PYTHONPATH:/path-to-gudhi/build/python' + +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 + + +Test suites +=========== + +To test your build, `py.test <http://doc.pytest.org>`_ is optional. Run the +following command in a terminal: + +.. code-block:: bash + + cd /path-to-gudhi/build/python + # For windows, you have to set PYTHONPATH environment variable + export PYTHONPATH='$PYTHONPATH:/path-to-gudhi/build/python' + make test + +Debugging issues +================ + +If tests fail, please check your PYTHONPATH and try to :code:`import gudhi` +and check the errors. +The problem can come from a third-party library bad link or installation. + +If :code:`import gudhi` succeeds, please have a look to debug information: + +.. code-block:: python + + import gudhi + print(gudhi.__debug_info__) + +You shall have something like: + +.. code-block:: none + + Python version 2.7.15 + python version 0.26.1 + Eigen3 version 3.1.1 + Installed modules are: off_reader;simplex_tree;rips_complex;cubical_complex;periodic_cubical_complex; + persistence_graphical_tools;reader_utils;witness_complex;strong_witness_complex;alpha_complex; + euclidean_witness_complex;euclidean_strong_witness_complex; + Missing modules are: bottleneck_distance;nerve_gic;subsampling;tangential_complex;persistence_graphical_tools; + 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 + +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 numpy and matplotlib are not +available. +Unitary tests cannot be run as pytest is missing. + +A complete configuration would be : + +.. code-block:: none + + Python version 3.6.5 + python 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 + 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 + +Documentation +============= + +To build the documentation, `sphinx-doc <http://www.sphinx-doc.org>`_ and +`sphinxcontrib-bibtex <https://sphinxcontrib-bibtex.readthedocs.io>`_ are +required. As the documentation is auto-tested, `CGAL`_, `Eigen3`_, +`Matplotlib`_, `NumPy`_ and `SciPy`_ are also mandatory to build the +documentation. + +Run the following commands in a terminal: + +.. code-block:: bash + + cd /path-to-gudhi/build/python + make sphinx + +Optional third-party library +**************************** + +CGAL +==== + +The :doc:`Alpha complex </alpha_complex_user>`, +:doc:`Tangential complex </tangential_complex_user>` and +:doc:`Witness complex </witness_complex_user>` data structures, and +:doc:`Bottleneck distance </bottleneck_distance_user>` requires CGAL, which is a +C++ library which 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: + +.. only:: builder_html + + * :download:`alpha_complex_diagram_persistence_from_off_file_example.py <../example/alpha_complex_diagram_persistence_from_off_file_example.py>` + * :download:`alpha_complex_from_points_example.py <../example/alpha_complex_from_points_example.py>` + * :download:`bottleneck_basic_example.py <../example/bottleneck_basic_example.py>` + * :download:`tangential_complex_plain_homology_from_off_file_example.py <../example/tangential_complex_plain_homology_from_off_file_example.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>` + +Eigen3 +====== + +The :doc:`Alpha complex </alpha_complex_user>`, +:doc:`Tangential complex </tangential_complex_user>` and +:doc:`Witness complex </witness_complex_user>` data structures and few +examples requires `Eigen3 <http://eigen.tuxfamily.org/>`_, a C++ template +library for linear algebra: matrices, vectors, numerical solvers, and related +algorithms. + +The following examples require the `Eigen3 <http://eigen.tuxfamily.org/>`_: + +.. only:: builder_html + + * :download:`alpha_complex_diagram_persistence_from_off_file_example.py <../example/alpha_complex_diagram_persistence_from_off_file_example.py>` + * :download:`alpha_complex_from_points_example.py <../example/alpha_complex_from_points_example.py>` + * :download:`tangential_complex_plain_homology_from_off_file_example.py <../example/tangential_complex_plain_homology_from_off_file_example.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>` + +Matplotlib +========== + +The :doc:`persistence graphical tools </persistence_graphical_tools_user>` +module requires `Matplotlib <http://matplotlib.org>`_, a Python 2D plotting +library which produces publication quality figures in a variety of hardcopy +formats and interactive environments across platforms. + +The following examples require the `Matplotlib <http://matplotlib.org>`_: + +.. only:: builder_html + + * :download:`alpha_complex_diagram_persistence_from_off_file_example.py <../example/alpha_complex_diagram_persistence_from_off_file_example.py>` + * :download:`gudhi_graphical_tools_example.py <../example/gudhi_graphical_tools_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:`rips_complex_diagram_persistence_from_off_file_example.py <../example/rips_complex_diagram_persistence_from_off_file_example.py>` + * :download:`rips_persistence_diagram.py <../example/rips_persistence_diagram.py>` + * :download:`rips_complex_diagram_persistence_from_distance_matrix_file_example.py <../example/rips_complex_diagram_persistence_from_distance_matrix_file_example.py>` + * :download:`tangential_complex_plain_homology_from_off_file_example.py <../example/tangential_complex_plain_homology_from_off_file_example.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>` + +NumPy +===== + +The :doc:`persistence graphical tools </persistence_graphical_tools_user>` +module requires `NumPy <http://numpy.org>`_, a fundamental package for +scientific computing with Python. + +The following examples require the `NumPy <http://numpy.org>`_: + +.. only:: builder_html + + * :download:`alpha_complex_diagram_persistence_from_off_file_example.py <../example/alpha_complex_diagram_persistence_from_off_file_example.py>` + * :download:`gudhi_graphical_tools_example.py <../example/gudhi_graphical_tools_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:`rips_complex_diagram_persistence_from_off_file_example.py <../example/rips_complex_diagram_persistence_from_off_file_example.py>` + * :download:`rips_persistence_diagram.py <../example/rips_persistence_diagram.py>` + * :download:`rips_complex_diagram_persistence_from_distance_matrix_file_example.py <../example/rips_complex_diagram_persistence_from_distance_matrix_file_example.py>` + * :download:`tangential_complex_plain_homology_from_off_file_example.py <../example/tangential_complex_plain_homology_from_off_file_example.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>` + +SciPy +===== + +The :doc:`persistence graphical tools </persistence_graphical_tools_user>` +module requires `SciPy <http://scipy.org>`_, a Python-based ecosystem of +open-source software for mathematics, science, and engineering. + +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. + +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 + +GUDHI is open to external contributions. If you want to join our development team, please contact us. diff --git a/src/python/doc/nerve_gic_complex_ref.rst b/src/python/doc/nerve_gic_complex_ref.rst new file mode 100644 index 00000000..abde2e8c --- /dev/null +++ b/src/python/doc/nerve_gic_complex_ref.rst @@ -0,0 +1,14 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +================================ +Cover complexes reference manual +================================ + +.. autoclass:: gudhi.CoverComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.CoverComplex.__init__ diff --git a/src/python/doc/nerve_gic_complex_sum.inc b/src/python/doc/nerve_gic_complex_sum.inc new file mode 100644 index 00000000..d633c4ff --- /dev/null +++ b/src/python/doc/nerve_gic_complex_sum.inc @@ -0,0 +1,16 @@ +.. table:: + :widths: 30 50 20 + + +----------------------------------------------------------------+------------------------------------------------------------------------+------------------------------------------------------------------+ + | .. 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` | + +----------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/nerve_gic_complex_user.rst b/src/python/doc/nerve_gic_complex_user.rst new file mode 100644 index 00000000..9101f45d --- /dev/null +++ b/src/python/doc/nerve_gic_complex_user.rst @@ -0,0 +1,315 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Cover complexes user manual +=========================== +Definition +---------- + +.. include:: nerve_gic_complex_sum.inc + +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`). + +Covers +------ + +Nerves and Graph Induced Complexes require a cover C of the input point cloud P, +that is a set of subsets of P whose union is P itself. +Very often, this cover is obtained from the preimage of a family of intervals covering +the image of some scalar-valued function f defined on P. This family is parameterized +by its resolution, which can be either the number or the length of the intervals, +and its gain, which is the overlap percentage between consecutive intervals (ordered by their first values). + +Nerves +------ + +Nerve definition +^^^^^^^^^^^^^^^^ + +Assume you are given a cover C of your point cloud P. Then, the Nerve of this cover +is the simplicial complex that has one k-simplex per k-fold intersection of cover elements. +See also `Wikipedia <https://en.wikipedia.org/wiki/Nerve_of_a_covering>`_. + +.. figure:: + ../../doc/Nerve_GIC/nerve.png + :figclass: align-center + :alt: Nerve of a double torus + + Nerve of a double torus + +Example +^^^^^^^ + +This example builds the Nerve of a point cloud sampled on a 3D human shape (human.off). +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:: + + import gudhi + nerve_complex = gudhi.CoverComplex() + nerve_complex.set_verbose(True) + + if (nerve_complex.read_point_cloud(gudhi.__root_source_dir__ + \ + '/data/points/human.off')): + nerve_complex.set_type('Nerve') + nerve_complex.set_color_from_coordinate(2) + nerve_complex.set_function_from_coordinate(2) + nerve_complex.set_graph_from_OFF() + nerve_complex.set_resolution_with_interval_number(10) + nerve_complex.set_gain(0.3) + nerve_complex.set_cover_from_function() + nerve_complex.find_simplices() + nerve_complex.write_info() + simplex_tree = nerve_complex.create_simplex_tree() + nerve_complex.compute_PD() + result_str = 'Nerve is of dimension ' + repr(simplex_tree.dimension()) + ' - ' + \ + repr(simplex_tree.num_simplices()) + ' simplices - ' + \ + repr(simplex_tree.num_vertices()) + ' vertices.' + print(result_str) + for filtered_value in simplex_tree.get_filtration(): + print(filtered_value[0]) + +the program output is: + +.. code-block:: none + + Min function value = -0.979672 and Max function value = 0.816414 + Interval 0 = [-0.979672, -0.761576] + Interval 1 = [-0.838551, -0.581967] + Interval 2 = [-0.658942, -0.402359] + Interval 3 = [-0.479334, -0.22275] + Interval 4 = [-0.299725, -0.0431414] + Interval 5 = [-0.120117, 0.136467] + Interval 6 = [0.059492, 0.316076] + Interval 7 = [0.239101, 0.495684] + Interval 8 = [0.418709, 0.675293] + Interval 9 = [0.598318, 0.816414] + Computing preimages... + Computing connected components... + 5 interval(s) in dimension 0: + [-0.909111, 0.0081753] + [-0.171433, 0.367393] + [-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] + [4] + [1, 4] + [2] + [0, 2] + [8] + [2, 8] + [5] + [4, 5] + [9] + [8, 9] + [13] + [5, 13] + [14] + [9, 14] + [19] + [13, 19] + [25] + [32] + [20] + [20, 32] + [33] + [25, 33] + [26] + [14, 26] + [19, 26] + [42] + [26, 42] + [34] + [33, 34] + [27] + [20, 27] + [35] + [27, 35] + [34, 35] + [35, 42] + [44] + [35, 44] + [54] + [44, 54] + + +The program also writes a file ../../data/points/human.off_sc.txt. The first +three lines in this file are the location of the input point cloud and the +function used to compute the cover. +The fourth line contains the number of vertices nv and edges ne of the Nerve. +The next nv lines represent the vertices. Each line contains the vertex ID, +the number of data points it contains, and their average color function value. +Finally, the next ne lines represent the edges, characterized by the ID of +their vertices. + +Using KeplerMapper, one can obtain the following visualization: + +.. figure:: + ../../doc/Nerve_GIC/nervevisu.jpg + :figclass: align-center + :alt: Visualization with KeplerMapper + + Visualization with KeplerMapper + +Graph Induced Complexes (GIC) +----------------------------- + +GIC definition +^^^^^^^^^^^^^^ + +Again, assume you are given a cover C of your point cloud P. Moreover, assume +you are also given a graph G built on top of P. Then, for any clique in G +whose nodes all belong to different elements of C, the GIC includes a +corresponding simplex, whose dimension is the number of nodes in the clique +minus one. +See :cite:`Dey13` for more details. + +.. figure:: + ../../doc/Nerve_GIC/GIC.jpg + :figclass: align-center + :alt: GIC of a point cloud + + GIC of a point cloud + +Example with cover from Voronoï +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +This example builds the GIC of a point cloud sampled on a 3D human shape +(human.off). +We randomly subsampled 100 points in the point cloud, which act as seeds of +a geodesic Voronoï diagram. Each cell of the diagram is then an element of C. +The graph G (used to compute both the geodesics for Voronoï and the GIC) +comes from the triangulation of the human shape. Note that the resulting +simplicial complex is in dimension 3 in this example. + +.. testcode:: + + import gudhi + nerve_complex = gudhi.CoverComplex() + + if (nerve_complex.read_point_cloud(gudhi.__root_source_dir__ + \ + '/data/points/human.off')): + nerve_complex.set_type('GIC') + nerve_complex.set_color_from_coordinate() + nerve_complex.set_graph_from_OFF() + nerve_complex.set_cover_from_Voronoi(700) + nerve_complex.find_simplices() + nerve_complex.plot_off() + +the program outputs SC.off. Using e.g. + +.. code-block:: none + + geomview ../../data/points/human.off_sc.off + +one can obtain the following visualization: + +.. figure:: + ../../doc/Nerve_GIC/gicvoronoivisu.jpg + :figclass: align-center + :alt: Visualization with Geomview + + Visualization with Geomview + +Functional GIC +^^^^^^^^^^^^^^ + +If one restricts to the cliques in G whose nodes all belong to preimages of +consecutive intervals (assuming the cover of the height function is minimal, +i.e. no more than two intervals can intersect at a time), the GIC is of +dimension one, i.e. a graph. +We call this graph the functional GIC. See :cite:`Carriere16` for more details. + +Example +^^^^^^^ + +Functional GIC comes with automatic selection of the Rips threshold, +the resolution and the gain of the function cover. See :cite:`Carriere17c` for +more details. In this example, we compute the functional GIC of a Klein bottle +embedded in R^5, where the graph G comes from a Rips complex with automatic +threshold, and the cover C comes from the preimages of intervals covering the +first coordinate, with automatic resolution and gain. Note that automatic +threshold, resolution and gain can be computed as well for the Nerve. + +.. testcode:: + + import gudhi + nerve_complex = gudhi.CoverComplex() + + if (nerve_complex.read_point_cloud(gudhi.__root_source_dir__ + \ + '/data/points/KleinBottle5D.off')): + nerve_complex.set_type('GIC') + nerve_complex.set_color_from_coordinate(0) + nerve_complex.set_function_from_coordinate(0) + nerve_complex.set_graph_from_automatic_rips() + nerve_complex.set_automatic_resolution() + nerve_complex.set_gain() + nerve_complex.set_cover_from_function() + nerve_complex.find_simplices() + nerve_complex.plot_dot() + +the program outputs SC.dot. Using e.g. + +.. code-block:: none + + neato ../../data/points/KleinBottle5D.off_sc.dot -Tpdf -o ../../data/points/KleinBottle5D.off_sc.pdf + +one can obtain the following visualization: + +.. figure:: + ../../doc/Nerve_GIC/coordGICvisu2.jpg + :figclass: align-center + :alt: Visualization with neato + + Visualization with neato + +where nodes are colored by the filter function values and, for each node, the +first number is its ID and the second is the number of data points that its +contain. + +We also provide an example on a set of 72 pictures taken around the same object +(lucky_cat.off). +The function is now the first eigenfunction given by PCA, whose values are +written in a file (lucky_cat_PCA1). Threshold, resolution and gain are +automatically selected as before. + +.. testcode:: + + import gudhi + nerve_complex = gudhi.CoverComplex() + + if (nerve_complex.read_point_cloud(gudhi.__root_source_dir__ + \ + '/data/points/COIL_database/lucky_cat.off')): + nerve_complex.set_type('GIC') + pca_file = gudhi.__root_source_dir__ + \ + '/data/points/COIL_database/lucky_cat_PCA1' + nerve_complex.set_color_from_file(pca_file) + nerve_complex.set_function_from_file(pca_file) + nerve_complex.set_graph_from_automatic_rips() + nerve_complex.set_automatic_resolution() + nerve_complex.set_gain() + nerve_complex.set_cover_from_function() + nerve_complex.find_simplices() + nerve_complex.plot_dot() + +the program outputs again SC.dot which gives the following visualization after using neato: + +.. figure:: + ../../doc/Nerve_GIC/funcGICvisu.jpg + :figclass: align-center + :alt: Visualization with neato + + Visualization with neato diff --git a/src/python/doc/periodic_cubical_complex_ref.rst b/src/python/doc/periodic_cubical_complex_ref.rst new file mode 100644 index 00000000..4b831647 --- /dev/null +++ b/src/python/doc/periodic_cubical_complex_ref.rst @@ -0,0 +1,13 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Periodic cubical complex reference manual +######################################### + +.. autoclass:: gudhi.PeriodicCubicalComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.PeriodicCubicalComplex.__init__ diff --git a/src/python/doc/persistence_graphical_tools_ref.rst b/src/python/doc/persistence_graphical_tools_ref.rst new file mode 100644 index 00000000..0b0038d9 --- /dev/null +++ b/src/python/doc/persistence_graphical_tools_ref.rst @@ -0,0 +1,11 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +============================================ +Persistence graphical tools reference manual +============================================ + +.. autofunction:: gudhi.plot_persistence_barcode +.. autofunction:: gudhi.plot_persistence_diagram +.. autofunction:: gudhi.plot_persistence_density diff --git a/src/python/doc/persistence_graphical_tools_sum.inc b/src/python/doc/persistence_graphical_tools_sum.inc new file mode 100644 index 00000000..0cdf8072 --- /dev/null +++ b/src/python/doc/persistence_graphical_tools_sum.inc @@ -0,0 +1,14 @@ +.. table:: + :widths: 30 50 20 + + +-----------------------------------------------------------------+-----------------------------------------------------------------------+-----------------------------------------------+ + | .. 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` | + +-----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/persistence_graphical_tools_user.rst b/src/python/doc/persistence_graphical_tools_user.rst new file mode 100644 index 00000000..b2124fdd --- /dev/null +++ b/src/python/doc/persistence_graphical_tools_user.rst @@ -0,0 +1,73 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Persistence graphical tools user manual +======================================= +Definition +---------- +.. include:: persistence_graphical_tools_sum.inc + + +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 gudhi + + off_file = gudhi.__root_source_dir__ + '/data/points/tore3D_300.off' + point_cloud = gudhi.read_off(off_file=off_file) + + rips_complex = gudhi.RipsComplex(points=point_cloud, max_edge_length=0.7) + simplex_tree = rips_complex.create_simplex_tree(max_dimension=3) + diag = simplex_tree.persistence(min_persistence=0.4) + + plot = gudhi.plot_persistence_barcode(diag) + plot.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 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' + plt = gudhi.plot_persistence_diagram(persistence_file=persistence_file, + legend=True) + plt.show() + +Persistence density +------------------- + +.. note:: + this function requires matplotlib, numpy and scipy to be available + +If you want more information on a specific dimension, for instance: + +.. plot:: + :include-source: + + 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' + plt = gudhi.plot_persistence_density(persistence_file=persistence_file, + max_intervals=0, dimension=1, legend=True) + plt.show() diff --git a/src/python/doc/persistent_cohomology_sum.inc b/src/python/doc/persistent_cohomology_sum.inc new file mode 100644 index 00000000..4d7b077e --- /dev/null +++ b/src/python/doc/persistent_cohomology_sum.inc @@ -0,0 +1,26 @@ +.. table:: + :widths: 30 50 20 + + +-----------------------------------------------------------------+-----------------------------------------------------------------------+-----------------------------------------------+ + | .. 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 | + | | 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. | | + | | | | + | | 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/esa/BoissonnatDM13`. | | + | | | | + +-----------------------------------------------------------------+-----------------------------------------------------------------------+-----------------------------------------------+ + | * :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` | + +-----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/persistent_cohomology_user.rst b/src/python/doc/persistent_cohomology_user.rst new file mode 100644 index 00000000..de83cda1 --- /dev/null +++ b/src/python/doc/persistent_cohomology_user.rst @@ -0,0 +1,120 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +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` | ++-----------------------------------------------------------------+-----------------------------------------------------------------------+ + + +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/esa/BoissonnatDM13`. + +The theory of homology consists in attaching to a topological space a sequence of (homology) groups, capturing global +topological features like connected components, holes, cavities, etc. Persistent homology studies the evolution -- +birth, life and death -- of these features when the topological space is changing. Consequently, the theory is +essentially composed of three elements: + +* topological spaces +* their homology groups +* an evolution scheme. + +Topological Spaces +------------------ + +Topological spaces are represented by simplicial complexes. +Let :math:`V = \{1, \cdots ,|V|\}` be a set of *vertices*. +A *simplex* :math:`\sigma` is a subset of vertices :math:`\sigma \subseteq V`. +A *simplicial complex* :math:`\mathbf{K}` on :math:`V` is a collection of simplices :math:`\{\sigma\}`, +:math:`\sigma \subseteq V`, such that :math:`\tau \subseteq \sigma \in \mathbf{K} \Rightarrow \tau \in \mathbf{K}`. +The dimension :math:`n=|\sigma|-1` of :math:`\sigma` is its number of elements minus 1. +A *filtration* of a simplicial complex is a function :math:`f:\mathbf{K} \rightarrow \mathbb{R}` satisfying +:math:`f(\tau)\leq f(\sigma)` whenever :math:`\tau \subseteq \sigma`. + +Homology +-------- + +For a ring :math:`\mathcal{R}`, the group of *n-chains*, denoted :math:`\mathbf{C}_n(\mathbf{K},\mathcal{R})`, of +:math:`\mathbf{K}` is the group of formal sums of n-simplices with :math:`\mathcal{R}` coefficients. The +*boundary operator* is a linear operator +:math:`\partial_n: \mathbf{C}_n(\mathbf{K},\mathcal{R}) \rightarrow \mathbf{C}_{n-1}(\mathbf{K},\mathcal{R})` +such that :math:`\partial_n \sigma = \partial_n [v_0, \cdots , v_n] = \sum_{i=0}^n (-1)^{i}[v_0,\cdots ,\widehat{v_i}, \cdots,v_n]`, +where :math:`\widehat{v_i}` means :math:`v_i` is omitted from the list. The chain groups form a sequence: + +.. math:: + + \cdots \ \ \mathbf{C}_n(\mathbf{K},\mathcal{R}) \xrightarrow{\ \partial_n\ } + \mathbf{C}_{n-1}(\mathbf{K},\mathcal{R}) \xrightarrow{\partial_{n-1}} \cdots \xrightarrow{\ \partial_2 \ } + \mathbf{C}_1(\mathbf{K},\mathcal{R}) \xrightarrow{\ \partial_1 \ } \mathbf{C}_0(\mathbf{K},\mathcal{R}) + +of finitely many groups :math:`\mathbf{C}_n(\mathbf{K},\mathcal{R})` and homomorphisms :math:`\partial_n`, indexed by +the dimension :math:`n \geq 0`. The boundary operators satisfy the property :math:`\partial_n \circ \partial_{n+1}=0` +for every :math:`n > 0` and we define the homology groups: + +.. math:: + + \mathbf{H}_n(\mathbf{K},\mathcal{R}) = \ker \partial_n / \mathrm{im} \ \partial_{n+1} + +We refer to :cite:`Munkres-elementsalgtop1984` for an introduction to homology +theory and to :cite:`DBLP:books/daglib/0025666` for an introduction to persistent homology. + +Indexing Scheme +--------------- + +"Changing" a simplicial complex consists in applying a simplicial map. An *indexing scheme* is a directed graph +together with a traversal order, such that two consecutive nodes in the graph are connected by an arrow (either forward +or backward). +The nodes represent simplicial complexes and the directed edges simplicial maps. + +From the computational point of view, there are two types of indexing schemes of interest in persistent homology: + +* linear ones + :math:`\bullet \longrightarrow \bullet \longrightarrow \cdots \longrightarrow \bullet \longrightarrow \bullet` + in persistent homology :cite:`DBLP:journals/dcg/ZomorodianC05`, +* zigzag ones + :math:`\bullet \longrightarrow \bullet \longleftarrow \cdots \longrightarrow \bullet \longleftarrow \bullet` + in zigzag persistent homology :cite:`DBLP:journals/focm/CarlssonS10`. + +These indexing schemes have a natural left-to-right traversal order, and we describe them with ranges and iterators. +In the current release of the Gudhi library, only the linear case is implemented. + +In the following, we consider the case where the indexing scheme is induced by a filtration. + +Ordering the simplices by increasing filtration values (breaking ties so as a simplex appears after its subsimplices of +same filtration value) provides an indexing scheme. + +Examples +-------- + +We provide several example files: run these examples with -h for details on their use. + +.. only:: builder_html + + * :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:`rips_complex_diagram_persistence_from_off_file_example.py <../example/rips_complex_diagram_persistence_from_off_file_example.py>` + * :download:`rips_persistence_diagram.py <../example/rips_persistence_diagram.py>` + * :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/python3-sphinx-build.py b/src/python/doc/python3-sphinx-build.py new file mode 100755 index 00000000..84d158cf --- /dev/null +++ b/src/python/doc/python3-sphinx-build.py @@ -0,0 +1,11 @@ +#!/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/reader_utils_ref.rst b/src/python/doc/reader_utils_ref.rst new file mode 100644 index 00000000..f3ecebad --- /dev/null +++ b/src/python/doc/reader_utils_ref.rst @@ -0,0 +1,15 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +============================= +Reader utils reference manual +============================= + +.. autofunction:: gudhi.read_off + +.. autofunction:: gudhi.read_lower_triangular_matrix_from_csv_file + +.. autofunction:: gudhi.read_persistence_intervals_grouped_by_dimension + +.. autofunction:: gudhi.read_persistence_intervals_in_dimension diff --git a/src/python/doc/rips_complex_ref.rst b/src/python/doc/rips_complex_ref.rst new file mode 100644 index 00000000..22b5616c --- /dev/null +++ b/src/python/doc/rips_complex_ref.rst @@ -0,0 +1,14 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +============================= +Rips complex reference manual +============================= + +.. autoclass:: gudhi.RipsComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.RipsComplex.__init__ diff --git a/src/python/doc/rips_complex_sum.inc b/src/python/doc/rips_complex_sum.inc new file mode 100644 index 00000000..857c6893 --- /dev/null +++ b/src/python/doc/rips_complex_sum.inc @@ -0,0 +1,16 @@ +.. table:: + :widths: 30 50 20 + + +----------------------------------------------------------------+------------------------------------------------------------------------+----------------------------------------------------------------------+ + | .. 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` | + +----------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/rips_complex_user.rst b/src/python/doc/rips_complex_user.rst new file mode 100644 index 00000000..1d340dbe --- /dev/null +++ b/src/python/doc/rips_complex_user.rst @@ -0,0 +1,345 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +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` | ++-------------------------------------------+----------------------------------------------------------------------+ + +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 +points, and a simplex is present if and only if its diameter is smaller than some parameter α. Considering all +parameters α defines a filtered simplicial complex, where the filtration value of a simplex is its diameter. +The filtration can be restricted to values α smaller than some threshold, to reduce its size. + +The input discrete metric space can be provided as a point cloud plus a distance function, or as a distance matrix. + +When creating a simplicial complex from the graph, :doc:`RipsComplex <rips_complex_ref>` first builds the graph and +inserts it into the data structure. It then expands the simplicial complex (adds the simplices corresponding to cliques) +when required. The expansion can be stopped at dimension `max_dimension`, by default 1. + +A vertex name corresponds to the index of the point in the given range (aka. the point cloud). + +.. figure:: + ../../doc/Rips_complex/rips_complex_representation.png + :align: center + + Rips-complex one skeleton graph representation + +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 `RipsComplex` 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 `sparsify_point_set` which removes points +that are too close to each other. This does not change its persistence diagram +by more than the length used to define "too close". + +A more general technique is to use a sparse approximation of the Rips +introduced by Don Sheehy :cite:`sheehy13linear`. We are using the version +described in :cite:`buchet16efficient` (except that we multiply all filtration +values by 2, to match the usual Rips complex). :cite:`cavanna15geometric` proves +a :math:`\frac{1}{1-\varepsilon}`-interleaving, although in practice the +error is usually smaller. A more intuitive presentation of the idea is +available in :cite:`cavanna15geometric`, and in a video +:cite:`cavanna15visualizing`. Passing an extra argument `sparse=0.3` at the +construction of a `RipsComplex` object asks it to build a sparse Rips with +parameter :math:`\varepsilon=0.3`, while the default `sparse=None` builds the +regular Rips complex. + + +Point cloud +----------- + +Example from a point cloud +^^^^^^^^^^^^^^^^^^^^^^^^^^ + +This example builds the neighborhood graph from the given points, up to max_edge_length. +Then it creates a :doc:`Simplex_tree <simplex_tree_ref>` with it. + +Finally, it is asked to display information about the simplicial complex. + +.. testcode:: + + import gudhi + rips_complex = gudhi.RipsComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]], + 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)) + +When launching (Rips maximal distance between 2 points is 12.0, is expanded +until dimension 1 - one skeleton graph in other words), the 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 + +Notice that if we use + +.. code-block:: python + + rips_complex = gudhi.RipsComplex(points=[[1, 1], [7, 0], [4, 6], [9, 6], [0, 14], [2, 19], [9, 17]], + max_edge_length=12.0, sparse=2) + +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 +^^^^^^^^^^^^^^^^^^^^^ + +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:`Simplex_tree <simplex_tree_ref>` with it. + +Finally, it is asked to display information about the Rips complex. + + +.. testcode:: + + import gudhi + point_cloud = gudhi.read_off(off_file=gudhi.__root_source_dir__ + '/data/points/alphacomplexdoc.off') + 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)) + +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 + +Distance matrix +--------------- + +Example from a distance matrix +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +This example builds the one skeleton graph from the given distance matrix, and max_edge_length value. +Then it creates a :doc:`Simplex_tree <simplex_tree_ref>` with it. + +Finally, it is asked to display information about the simplicial complex. + +.. testcode:: + + import gudhi + rips_complex = gudhi.RipsComplex(distance_matrix=[[], + [6.0827625303], + [5.8309518948, 6.7082039325], + [9.4339811321, 6.3245553203, 5], + [13.0384048104, 15.6524758425, 8.94427191, 12.0415945788], + [18.0277563773, 19.6468827044, 13.152946438, 14.7648230602, 5.3851648071], + [17.88854382, 17.1172427686, 12.0830459736, 11, 9.4868329805, 7.2801098893]], + 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)) + +When launching (Rips maximal distance between 2 points is 12.0, is expanded +until dimension 1 - one skeleton graph in other words), the 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 + +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:`Simplex_tree <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 + +Correlation matrix +------------------ + +Example from a correlation matrix +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Analogously to the case of distance matrix, Rips complexes can be also constructed based on correlation matrix. +Given a correlation matrix M, comportment-wise 1-M is a distance matrix. +This example builds the one skeleton graph from the given corelation matrix and threshold value. +Then it creates a :doc:`Simplex_tree <simplex_tree_ref>` with it. + +Finally, it is asked to display information about the simplicial complex. + +.. testcode:: + + import gudhi + import numpy as np + + # User defined correlation matrix is: + # |1 0.06 0.23 0.01 0.89| + # |0.06 1 0.74 0.01 0.61| + # |0.23 0.74 1 0.72 0.03| + # |0.01 0.01 0.72 1 0.7 | + # |0.89 0.61 0.03 0.7 1 | + correlation_matrix=np.array([[1., 0.06, 0.23, 0.01, 0.89], + [0.06, 1., 0.74, 0.01, 0.61], + [0.23, 0.74, 1., 0.72, 0.03], + [0.01, 0.01, 0.72, 1., 0.7], + [0.89, 0.61, 0.03, 0.7, 1.]], float) + + distance_matrix = np.ones((correlation_matrix.shape),float) - correlation_matrix + rips_complex = gudhi.RipsComplex(distance_matrix=distance_matrix, max_edge_length=1.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)) + +When launching (Rips maximal distance between 2 points is 12.0, is expanded +until dimension 1 - one skeleton graph in other words), the output is: + +.. testoutput:: + + Rips complex is of dimension 1 - 15 simplices - 5 vertices. + [0] -> 0.00 + [1] -> 0.00 + [2] -> 0.00 + [3] -> 0.00 + [4] -> 0.00 + [0, 4] -> 0.11 + [1, 2] -> 0.26 + [2, 3] -> 0.28 + [3, 4] -> 0.30 + [1, 4] -> 0.39 + [0, 2] -> 0.77 + [0, 1] -> 0.94 + [2, 4] -> 0.97 + [0, 3] -> 0.99 + [1, 3] -> 0.99 + +.. note:: + As persistence diagrams points will be under the diagonal, + bottleneck distance and persistence graphical tool will not work properly, + this is a known issue. diff --git a/src/python/doc/simplex_tree_ref.rst b/src/python/doc/simplex_tree_ref.rst new file mode 100644 index 00000000..9eb8c199 --- /dev/null +++ b/src/python/doc/simplex_tree_ref.rst @@ -0,0 +1,14 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +============================= +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 new file mode 100644 index 00000000..5ba58d2b --- /dev/null +++ b/src/python/doc/simplex_tree_sum.inc @@ -0,0 +1,13 @@ +.. table:: + :widths: 30 50 20 + + +----------------------------------------------------------------+------------------------------------------------------------------------+-----------------------------+ + | .. 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` | + +----------------------------------------------------------------+------------------------------------------------------------------------------------------------------+ diff --git a/src/python/doc/simplex_tree_user.rst b/src/python/doc/simplex_tree_user.rst new file mode 100644 index 00000000..aebeb29f --- /dev/null +++ b/src/python/doc/simplex_tree_user.rst @@ -0,0 +1,72 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Simplex tree user manual +======================== +Definition +---------- + +.. include:: simplex_tree_sum.inc + +A simplicial complex :math:`\mathbf{K}` on a set of vertices :math:`V = \{1, \cdots ,|V|\}` is a collection of +simplices :math:`\{\sigma\}`, :math:`\sigma \subseteq V` such that +:math:`\tau \subseteq \sigma \in \mathbf{K} \rightarrow \tau \in \mathbf{K}`. The dimension :math:`n=|\sigma|-1` of +:math:`\sigma` is its number of elements minus `1`. + +A filtration of a simplicial complex is a function :math:`f:\mathbf{K} \rightarrow \mathbb{R}` satisfying +:math:`f(\tau)\leq f(\sigma)` whenever :math:`\tau \subseteq \sigma`. Ordering the simplices by increasing filtration +values (breaking ties so as a simplex appears after its subsimplices of same filtration value) provides an indexing +scheme. + + +Implementation +-------------- + +There are two implementation of complexes. The first on is the Simplex_tree data structure. +The simplex tree is an efficient and flexible data structure for representing general (filtered) simplicial complexes. +The data structure is described in :cite`boissonnatmariasimplextreealgorithmica`. + +The second one is the Hasse_complex. The Hasse complex is a data structure representing explicitly all co-dimension 1 +incidence relations in a complex. It is consequently faster when accessing the boundary of a simplex, but is less +compact and harder to construct from scratch. + +Example +------- + +.. testcode:: + + import gudhi + st = gudhi.SimplexTree() + if st.insert([0, 1]): + print("[0, 1] inserted") + if st.insert([0, 1, 2], filtration=4.0): + print("[0, 1, 2] inserted") + if st.find([0, 1]): + print("[0, 1] found") + result_str = 'num_vertices=' + repr(st.num_vertices()) + print(result_str) + result_str = 'num_simplices=' + repr(st.num_simplices()) + print(result_str) + print("skeleton(2) =") + for sk_value in st.get_skeleton(2): + print(sk_value) + + +The output is: + +.. testoutput:: + + [0, 1] inserted + [0, 1, 2] inserted + [0, 1] found + num_vertices=3 + num_simplices=7 + skeleton(2) = + ([0, 1, 2], 4.0) + ([0, 1], 0.0) + ([0, 2], 4.0) + ([0], 0.0) + ([1, 2], 4.0) + ([1], 0.0) + ([2], 4.0) diff --git a/src/python/doc/strong_witness_complex_ref.rst b/src/python/doc/strong_witness_complex_ref.rst new file mode 100644 index 00000000..d624d711 --- /dev/null +++ b/src/python/doc/strong_witness_complex_ref.rst @@ -0,0 +1,14 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +======================================= +Strong witness complex reference manual +======================================= + +.. autoclass:: gudhi.StrongWitnessComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.StrongWitnessComplex.__init__ diff --git a/src/python/doc/tangential_complex_ref.rst b/src/python/doc/tangential_complex_ref.rst new file mode 100644 index 00000000..cdfda082 --- /dev/null +++ b/src/python/doc/tangential_complex_ref.rst @@ -0,0 +1,14 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +=================================== +Tangential complex reference manual +=================================== + +.. autoclass:: gudhi.TangentialComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.TangentialComplex.__init__ diff --git a/src/python/doc/tangential_complex_sum.inc b/src/python/doc/tangential_complex_sum.inc new file mode 100644 index 00000000..c8bc1177 --- /dev/null +++ b/src/python/doc/tangential_complex_sum.inc @@ -0,0 +1,14 @@ +.. table:: + :widths: 30 50 20 + + +----------------------------------------------------------------+------------------------------------------------------------------------+------------------------------------------------------------------+ + | .. 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: `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 new file mode 100644 index 00000000..ebfe1e29 --- /dev/null +++ b/src/python/doc/tangential_complex_user.rst @@ -0,0 +1,204 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Tangential complex user manual +============================== +.. include:: tangential_complex_sum.inc + +Definition +---------- + +A Tangential Delaunay complex is a simplicial complex designed to reconstruct a +:math:`k`-dimensional smooth manifold embedded in :math:`d`-dimensional +Euclidean space. The input is a point sample coming from an unknown manifold, +which means that the points lie close to a structure of "small" intrinsic +dimension. The running time depends only linearly on the extrinsic dimension +:math:`d` and exponentially on the intrinsic dimension :math:`k`. + +An extensive description of the Tangential complex can be found in +:cite:`tangentialcomplex2014`. + +What is a Tangential Complex? +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +Let us start with the description of the Tangential complex of a simple +example, with :math:`k = 1` and :math:`d = 2`. The point set +:math:`\mathscr P` is located on a closed curve embedded in 2D. +Only 4 points will be displayed (more are required for PCA) to simplify the +figures. + +.. figure:: ../../doc/Tangential_complex/tc_example_01.png + :alt: The input + :figclass: align-center + + The input + +For each point :math:`P`, estimate its tangent subspace :math:`T_P` using PCA. + +.. figure:: ../../doc/Tangential_complex/tc_example_02.png + :alt: The estimated normals + :figclass: align-center + + The estimated normals + + +Let us add the Voronoi diagram of the points in orange. For each point +:math:`P`, construct its star in the Delaunay triangulation of +:math:`\mathscr P` restricted to :math:`T_P`. + +.. figure:: ../../doc/Tangential_complex/tc_example_03.png + :alt: The Voronoi diagram + :figclass: align-center + + The Voronoi diagram + +The Tangential Delaunay complex is the union of those stars. + +In practice, neither the ambient Voronoi diagram nor the ambient Delaunay +triangulation is computed. Instead, local :math:`k`-dimensional regular +triangulations are computed with a limited number of points as we only need the +star of each point. More details can be found in :cite:`tangentialcomplex2014`. + +Inconsistencies +^^^^^^^^^^^^^^^ +Inconsistencies between the stars can occur. An inconsistency occurs when a +simplex is not in the star of all its vertices. + +Let us take the same example. + +.. figure:: ../../doc/Tangential_complex/tc_example_07_before.png + :alt: Before + :figclass: align-center + + Before + +Let us slightly move the tangent subspace :math:`T_Q` + +.. figure:: ../../doc/Tangential_complex/tc_example_07_after.png + :alt: After + :figclass: align-center + + After + +Now, the star of :math:`Q` contains :math:`QP`, but the star of :math:`P` does +not contain :math:`QP`. We have an inconsistency. + +.. figure:: ../../doc/Tangential_complex/tc_example_08.png + :alt: After + :figclass: align-center + + After + +One way to solve inconsistencies is to randomly perturb the positions of the +points involved in an inconsistency. In the current implementation, this +perturbation is done in the tangent subspace of each point. The maximum +perturbation radius is given as a parameter to the constructor. + +In most cases, we recommend to provide a point set where the minimum distance +between any two points is not too small. This can be achieved using the +functions provided by the Subsampling module. Then, a good value to start with +for the maximum perturbation radius would be around half the minimum distance +between any two points. The Example with perturbation below shows an example of +such a process. + +In most cases, this process is able to dramatically reduce the number of +inconsistencies, but is not guaranteed to succeed. + +Output +^^^^^^ +The result of the computation is exported as a Simplex_tree. It is the union of +the stars of all the input points. A vertex in the Simplex Tree is the index of +the point in the range provided by the user. The point corresponding to a +vertex can also be obtained through the Tangential_complex::get_point function. +Note that even if the positions of the points are perturbed, their original +positions are kept (e.g. Tangential_complex::get_point returns the original +position of the point). + +The result can be obtained after the computation of the Tangential complex +itself and/or after the perturbation process. + + +Simple example +-------------- + +This example builds the Tangential complex of point set read in an OFF file. + +.. testcode:: + + import gudhi + tc = gudhi.TangentialComplex(intrisic_dim = 1, + off_file=gudhi.__root_source_dir__ + '/data/points/alphacomplexdoc.off') + tc.compute_tangential_complex() + result_str = 'Tangential contains ' + repr(tc.num_simplices()) + \ + ' simplices - ' + repr(tc.num_vertices()) + ' vertices.' + print(result_str) + + st = tc.create_simplex_tree() + result_str = 'Simplex tree is of dimension ' + repr(st.dimension()) + \ + ' - ' + repr(st.num_simplices()) + ' simplices - ' + \ + repr(st.num_vertices()) + ' vertices.' + print(result_str) + for filtered_value in st.get_filtration(): + print(filtered_value[0]) + +The output is: + +.. testoutput:: + + Tangential contains 12 simplices - 7 vertices. + Simplex tree is of dimension 1 - 15 simplices - 7 vertices. + [0] + [1] + [0, 1] + [2] + [0, 2] + [1, 2] + [3] + [1, 3] + [4] + [2, 4] + [5] + [4, 5] + [6] + [3, 6] + [5, 6] + + +Example with perturbation +------------------------- + +This example builds the Tangential complex of a point set, then tries to solve +inconsistencies by perturbing the positions of points involved in inconsistent +simplices. + +.. testcode:: + + import gudhi + tc = gudhi.TangentialComplex(intrisic_dim = 1, + points=[[0.0, 0.0], [1.0, 0.0], [0.0, 1.0], [1.0, 1.0]]) + tc.compute_tangential_complex() + result_str = 'Tangential contains ' + repr(tc.num_vertices()) + ' vertices.' + print(result_str) + + if tc.num_inconsistent_simplices() > 0: + print('Tangential contains inconsistencies.') + + tc.fix_inconsistencies_using_perturbation(10, 60) + if tc.num_inconsistent_simplices() == 0: + print('Inconsistencies has been fixed.') + +The output is: + +.. testoutput:: + + Tangential contains 4 vertices. + Inconsistencies has been fixed. + + +Bibliography +============ + +.. bibliography:: ../../biblio/bibliography.bib + :filter: docnames + :style: unsrt diff --git a/src/python/doc/todos.rst b/src/python/doc/todos.rst new file mode 100644 index 00000000..ca274ced --- /dev/null +++ b/src/python/doc/todos.rst @@ -0,0 +1,9 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +========== +To be done +========== + +.. todolist:: diff --git a/src/python/doc/witness_complex_ref.rst b/src/python/doc/witness_complex_ref.rst new file mode 100644 index 00000000..9987d3fd --- /dev/null +++ b/src/python/doc/witness_complex_ref.rst @@ -0,0 +1,14 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +================================ +Witness complex reference manual +================================ + +.. autoclass:: gudhi.WitnessComplex + :members: + :undoc-members: + :show-inheritance: + + .. automethod:: gudhi.WitnessComplex.__init__ diff --git a/src/python/doc/witness_complex_sum.inc b/src/python/doc/witness_complex_sum.inc new file mode 100644 index 00000000..2be8b220 --- /dev/null +++ b/src/python/doc/witness_complex_sum.inc @@ -0,0 +1,18 @@ +.. table:: + :widths: 30 50 20 + + +-------------------------------------------------------------------+----------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------+ + | .. 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: `Eigen3 <installation.html#eigen3>`__ 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 new file mode 100644 index 00000000..40e94134 --- /dev/null +++ b/src/python/doc/witness_complex_user.rst @@ -0,0 +1,135 @@ +:orphan: + +.. To get rid of WARNING: document isn't included in any toctree + +Witness complex user manual +=========================== + +.. include:: witness_complex_sum.inc + +Definitions +----------- + +Witness complex is a simplicial complex defined on two sets of points in :math:`\mathbb{R}^D`: + +- :math:`W` set of **witnesses** and +- :math:`L` set of **landmarks**. + +Even though often the set of landmarks :math:`L` is a subset of the set of witnesses :math:`W`, it is not a requirement +for the current implementation. + +Landmarks are the vertices of the simplicial complex and witnesses help to decide on which simplices are inserted via a +predicate "is witnessed". + +De Silva and Carlsson in their paper :cite:`de2004topological` differentiate **weak witnessing** and +**strong witnessing**: + +- *weak*: :math:`\sigma \subset L` is witnessed by :math:`w \in W` if :math:`\forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l) \leq d(w,l')` +- *strong*: :math:`\sigma \subset L` is witnessed by :math:`w \in W` if :math:`\forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l) \leq d(w,l')` + +where :math:`d(.,.)` is a distance function. + +Both definitions can be relaxed by a real value :math:`\alpha`: + +- *weak*: :math:`\sigma \subset L` is :math:`\alpha`-witnessed by :math:`w \in W` if :math:`\forall l \in \sigma,\ \forall l' \in \mathbf{L \setminus \sigma},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2` +- *strong*: :math:`\sigma \subset L` is :math:`\alpha`-witnessed by :math:`w \in W` if :math:`\forall l \in \sigma,\ \forall l' \in \mathbf{L},\ d(w,l)^2 \leq d(w,l')^2 + \alpha^2` + +which leads to definitions of **weak relaxed witness complex** (or just relaxed witness complex for short) and +**strong relaxed witness complex** respectively. + +.. figure:: ../../doc/Witness_complex/swit.svg + :alt: Strongly witnessed simplex + :figclass: align-center + + Strongly witnessed simplex + + +In particular case of 0-relaxation, weak complex corresponds to **witness complex** introduced in +:cite:`de2004topological`, whereas 0-relaxed strong witness complex consists of just vertices and is not very +interesting. Hence for small relaxation weak version is preferable. +However, to capture the homotopy type (for example using Gudhi::persistent_cohomology::Persistent_cohomology) it is +often necessary to work with higher filtration values. In this case strong relaxed witness complex is faster to compute +and offers similar results. + +Implementation +-------------- + +The two complexes described above are implemented in the corresponding classes + +- :doc:`witness_complex_ref` +- :doc:`strong_witness_complex_ref` +- :doc:`euclidean_witness_complex_ref` +- :doc:`euclidean_strong_witness_complex_ref` + +The construction of the Euclidean versions of complexes follow the same scheme: + +1. Construct a search tree on landmarks. +2. Construct lists of nearest landmarks for each witness. +3. Construct the witness complex for nearest landmark lists. + +In the non-Euclidean classes, the lists of nearest landmarks are supposed to be given as input. + +The constructors take on the steps 1 and 2, while the function 'create_complex' executes the step 3. + +Constructing weak relaxed witness complex from an off file +---------------------------------------------------------- + +Let's start with a simple example, which reads an off point file and computes a weak witness complex. + +.. code-block:: python + + import gudhi + import argparse + + parser = argparse.ArgumentParser(description='EuclideanWitnessComplex creation from ' + 'points read in a OFF file.', + epilog='Example: ' + 'example/witness_complex_diagram_persistence_from_off_file_example.py ' + '-f ../data/points/tore3D_300.off -a 1.0 -n 20 -d 2' + '- Constructs a alpha complex with the ' + 'points from the given OFF file.') + parser.add_argument("-f", "--file", type=str, required=True) + parser.add_argument("-a", "--max_alpha_square", type=float, required=True) + parser.add_argument("-n", "--number_of_landmarks", type=int, required=True) + parser.add_argument("-d", "--limit_dimension", type=int, required=True) + + args = parser.parse_args() + + with open(args.file, 'r') as f: + first_line = f.readline() + if (first_line == 'OFF\n') or (first_line == 'nOFF\n'): + print("#####################################################################") + print("EuclideanWitnessComplex creation from points read in a OFF file") + + witnesses = gudhi.read_off(off_file=args.file) + landmarks = gudhi.pick_n_random_points(points=witnesses, nb_points=args.number_of_landmarks) + + message = "EuclideanWitnessComplex with max_edge_length=" + repr(args.max_alpha_square) + \ + " - Number of landmarks=" + repr(args.number_of_landmarks) + print(message) + + witness_complex = gudhi.EuclideanWitnessComplex(witnesses=witnesses, landmarks=landmarks) + simplex_tree = witness_complex.create_simplex_tree(max_alpha_square=args.max_alpha_square, + limit_dimension=args.limit_dimension) + + message = "Number of simplices=" + repr(simplex_tree.num_simplices()) + print(message) + else: + print(args.file, "is not a valid OFF file") + + f.close() + + +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 |