Merge tag 'tags/gudhi-release-3.2.0' into dfsg/latest

10 files changed, 441 insertions, 0 deletions

diff --git a/.github/CONTRIBUTING.md b/.github/CONTRIBUTING.md
new file mode 100644
index 00000000..a18ff8bd
--- /dev/null
+++ b/.github/CONTRIBUTING.md
@@ -0,0 +1,48 @@
+# Contributing to GUDHI
+
+First of all, thank you for the time you may take to contribute to GUDHI !
+
+# In case you have a question
+
+Please, check our [contact web page](https://gudhi.inria.fr/contact/).
+
+# In case you found an issue
+
+Please, first check [opened issues on GUDHI](https://github.com/GUDHI/gudhi-devel/issues).
+
+If the problem you are facing is not referenced, do not hesitate to open a [new issue](https://github.com/GUDHI/gudhi-devel/issues/new).
+
+This place is also a good place if you have some enhancement you want to propose.
+There is a label **enhancement** in the [new issue](https://github.com/GUDHI/gudhi-devel/issues/new) page.
+
+# In case you want to contribute to GUDHI
+
+## You are not familiar with GitHub ?
+
+Please take some time to read our [how to use GitHub to contribute to GUDHI](how_to_use_github_to_contribute_to_gudhi.md).
+
+## Something you want to improve in the documentation
+
+For C++ documentation, you can find it in the directories:
+* *src/common/doc* for the main page and installation instructions
+* *src/NAME_OF_THE_MODULE/doc* for the main page of a module
+* *src/NAME_OF_THE_MODULE/include/gudhi* for the documentation generated from the code.
+We use Doxygen to generate the code and you will be able to verify the result in CircleCI Doxygen target in the artifacts.
+
+For Python documentation, you can find it in the directories:
+* *src/python/doc* for the main page, installation instructionsand for the main pages of the modules
+* *src/python/gudhi/NAME_OF_THE_MODULE.pyx* for the documentation generated from the code.
+We use Sphinx to generate the code and you will be able to verify the result in CircleCI Sphinx target in the artifacts.
+
+## Something you want to improve in the code
+
+We don't ask for any paperwork but we expect you don't submit anything you are not allowed to:
+* check that your work contract and your employer allow you to contribute to this open source project.
+* insure you do not violate someone's intellectual property.
+* ...
+
+Please, take some time to read our [code conventions](code_conventions.md)
+
+As a convention, we set a Pull Request as a **Draft Pull Request** when we work on something we want the other contributors to see.
+
+We click on **Ready for review** to ask for a peer review of the contribution.
diff --git a/.github/build-requirements.txt b/.github/build-requirements.txt
new file mode 100644
index 00000000..7de60d23
--- /dev/null
+++ b/.github/build-requirements.txt
@@ -0,0 +1,5 @@
+setuptools
+wheel
+numpy
+Cython
+pybind11
\ No newline at end of file
diff --git a/.github/code_conventions.md b/.github/code_conventions.md
new file mode 100644
index 00000000..9724f722
--- /dev/null
+++ b/.github/code_conventions.md
@@ -0,0 +1,47 @@
+# Naming conventions
+
+## C++
+
+### In the code:
+* The classes and functions of a package should be in a sub-namespace of the `Gudhi` namespace. The sub-namespace names are in lowercase and use underscore separators. E.g. `Gudhi::package_name::`
+* Concepts are named with camel case starting with uppercase. E.g. `PersistentHomology` for the concept of Persitence homology.
+* Classes start with an uppercase letter and use underscore separators. E.g. `Skeleton_blocker_contractor`.
+* Member functions and free functions are in lowercase and use underscore separators. E.g. `int num_vertices()`.
+* Constants and macros are in uppercase.
+* Macros should begin with the prefix `GUDHI_`.
+
+### File names:
+* All headers are named *.h and all sources are named *.cpp.
+* If a single class or function is provided in a file, its name (with the same letter case) should be used for the file name.
+* If a file does not contain a single class, its name should not begin with a capital letter.
+* Test files should be called `test_[what_is_tested].cpp`. E.g. `test_sparsify_point_set.cpp`
+* Example files should be called `example_[what_it_is].cpp`. E.g. `example_sparsify_point_set.cpp`
+
+### In CMakeLists.txt files:
+* The name of the "project" should be in this form: `Package_[tests|examples|…]`. E.g. `project(Simplex_tree_examples)`.
+* The name if each "target" (first parameter of add_executable) should be in this form: `Package_{name of the cpp file without extension}`. E.g `add_executable(Subsampling_test_sparsify_point_set test_sparsify_point_set.cpp)`.
+
+### Code style
+We are using [google c++ style guide](https://google.github.io/styleguide/cppguide.html) recommendations with 120 characters per line of code.
+[clang-format](https://clang.llvm.org/docs/ClangFormat.html) can be used to format automatically your code:
+```bash
+cd src # there is a .clang-format file with these specifications
+clang-format -style=file -i Simplex_tree/include/gudhi/Simplex_tree.h # -i means in place, your file will be modified
+```
+
+### Template
+Please use the file [following template](copyright_template.h).
+
+## Python
+
+In progress...
+
+### Code style
+We are using [PEP8 Python style guide](https://www.python.org/dev/peps/pep-0008/) recommendations with 120 characters per line of code.
+[black](https://black.readthedocs.io/en/stable/) can be used to format automatically your code:
+```bash
+black -l 120 src/python/example/bottleneck_basic_example.py
+```
+
+### Template
+Please use the file [following template](copyright_template.py).
diff --git a/.github/copyright_template.h b/.github/copyright_template.h
new file mode 100644
index 00000000..30034f1b
--- /dev/null
+++ b/.github/copyright_template.h
@@ -0,0 +1,14 @@
+/*    This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ *    See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ *    Author(s):       [AUTHOR NAME]
+ *
+ *    Copyright (C) [YEAR] [COPYRIGHT]
+ *
+ *    Modification(s):
+ *      - YYYY/MM Author: Description of the modification
+ */
+
+#ifndef [FILE_NAME]_H_
+#define [FILE_NAME]_H_
+
+#endif  // [FILE_NAME]_H_
\ No newline at end of file
diff --git a/.github/copyright_template.py b/.github/copyright_template.py
new file mode 100644
index 00000000..667f985d
--- /dev/null
+++ b/.github/copyright_template.py
@@ -0,0 +1,8 @@
+# This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+# See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+# Author(s):       [AUTHOR NAME]
+#
+# Copyright (C) [YEAR] [COPYRIGHT]
+#
+# Modification(s):
+#   - YYYY/MM Author: Description of the modification
diff --git a/.github/for_maintainers/new_gudhi_version_creation.md b/.github/for_maintainers/new_gudhi_version_creation.md
new file mode 100644
index 00000000..8674222b
--- /dev/null
+++ b/.github/for_maintainers/new_gudhi_version_creation.md
@@ -0,0 +1,95 @@
+# Create a new GUDHI version
+
+We will consider that all operations will be performed in a brand new clone of the main project:
+```bash
+git clone https://github.com/GUDHI/gudhi-devel.git
+cd gudhi-devel
+```
+
+## Version file modification
+
+**Edit the file CMakeGUDHIVersion.txt**, and increment major, minor, or patch version number, in function of the version new delivery.
+```bash
+# cf. .gitignore - ignore this if it is a fresh clone version
+rm -rf data/points/COIL_database/lucky_cat.off_dist data/points/COIL_database/lucky_cat.off_sc.dot data/points/KleinBottle5D.off_dist data/points/KleinBottle5D.off_sc.dot data/points/human.off_dist data/points/human.off_sc.off data/points/human.off_sc.txt
+```
+
+Checkin the modifications, build and test the version:
+```bash
+git submodule update --init
+mkdir build
+cd build
+cmake -DCGAL_DIR=/your/path/to/CGAL -DWITH_GUDHI_EXAMPLE=ON -DWITH_GUDHI_BENCHMARK=ON  -DUSER_VERSION_DIR=gudhi.@GUDHI_VERSION@ -DPython_ADDITIONAL_VERSIONS=3 ..
+make user_version
+date +"%d-%m-%Y-%T" > gudhi.@GUDHI_VERSION@/timestamp.txt
+tar -czvf gudhi.@GUDHI_VERSION@.tar.gz gudhi.@GUDHI_VERSION@
+md5sum gudhi.@GUDHI_VERSION@.tar.gz > md5sum.txt
+sha256sum gudhi.@GUDHI_VERSION@.tar.gz > sha256sum.txt
+sha512sum gudhi.@GUDHI_VERSION@.tar.gz > sha512sum.txt
+
+make -j all test
+```
+
+***[Check there are no error]***
+
+## Create the documentation
+```bash
+mkdir gudhi.doc.@GUDHI_VERSION@
+make doxygen  2>&1 | tee dox.log && grep warning dox.log
+```
+
+***[Check there are no error and the warnings]***
+
+```bash
+cp -R gudhi.@GUDHI_VERSION@/doc/html gudhi.doc.@GUDHI_VERSION@/cpp
+cd gudhi.@GUDHI_VERSION@
+rm -rf build; mkdir build; cd build; cmake -DCGAL_DIR=/your/path/to/CGAL -DWITH_GUDHI_EXAMPLE=ON -DPython_ADDITIONAL_VERSIONS=3 ..
+export LC_ALL=en_US.UTF-8  # cf. bug
+make sphinx
+```
+
+***[Check there are no error]***
+
+```bash
+cp -R python/sphinx ../../gudhi.doc.@GUDHI_VERSION@/python
+cd ../..
+tar -czvf gudhi.doc.@GUDHI_VERSION@.tar.gz gudhi.doc.@GUDHI_VERSION@
+
+cd gudhi.@GUDHI_VERSION@/build
+make all test
+```
+
+***[Check there are no error]***
+
+## Upload the documentation
+
+Upload by ftp the content of the directory gudhi.doc.@GUDHI_VERSION@/cpp in a new directory on ForgeLogin@scm.gforge.inria.fr:/home/groups/gudhi/htdocs/doc/@GUDHI_VERSION@
+
+Upload by ftp the content of the directory gudhi.doc.@GUDHI_VERSION@/python in a new directory on ForgeLogin@scm.gforge.inria.fr:/home/groups/gudhi/htdocs/python/@GUDHI_VERSION@
+
+Through ssh, make the **latest** link to your new version of the documentation:
+```bash
+ssh ForgeLogin@scm.gforge.inria.fr
+cd /home/groups/gudhi/htdocs/doc
+rm latest
+ln -s @GUDHI_VERSION@ latest
+cd /home/groups/gudhi/htdocs/python
+rm latest
+ln -s @GUDHI_VERSION@ latest
+```
+
+## Put a version label on files
+
+* Go on page https://github.com/GUDHI/gudhi-devel/releases/new
+* Name the tag: tags/gudhi-release-@GUDHI_VERSION@
+* Name the release GUDHI @GUDHI_VERSION@
+* Write the release note
+* Drag'n drop *gudhi.@GUDHI_VERSION@.tar.gz*, *md5sum.txt*, *sha256sum.txt*, *sha512sum.txt* files
+* Tick the *This is a pre-release* check button if this is a release candidate (untick if this is an official version)
+* Click the *Publish the release* button
+
+## Mail sending
+Send version mail to the following lists :
+* gudhi-devel@lists.gforge.inria.fr
+* gudhi-users@lists.gforge.inria.fr (not for release candidate)
+
diff --git a/.github/for_maintainers/next_release_template.md b/.github/for_maintainers/next_release_template.md
new file mode 100644
index 00000000..a2805a55
--- /dev/null
+++ b/.github/for_maintainers/next_release_template.md
@@ -0,0 +1,28 @@
+We are pleased to announce the release 3.X.X of the GUDHI library.
+
+As a major new feature, the GUDHI library now offers ...
+
+We are now using GitHub to develop the GUDHI library, do not hesitate to [fork the GUDHI project on GitHub](https://github.com/GUDHI/gudhi-devel). From a user point of view, we recommend to download GUDHI user version (gudhi.3.X.X.tar.gz).
+
+Below is a list of changes made since GUDHI 3.X-1.X-1:
+
+- [Module](link)
+     - ...
+
+- [Module](link)
+     - ...
+
+- Miscellaneous
+     - The [list of bugs that were solved since GUDHI-3.X-1.X-1](https://github.com/GUDHI/gudhi-devel/issues?q=label%3A3.1.1+is%3Aclosed) is available on GitHub.
+
+All modules are distributed under the terms of the MIT license.
+However, there are still GPL dependencies for many modules. We invite you to check our [license dedicated web page](https://gudhi.inria.fr/licensing/) for further details.
+
+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.
+
+We provide [bibtex entries](https://gudhi.inria.fr/doc/latest/_citation.html) for the modules of the User and Reference Manual, as well as for publications directly related to the GUDHI library. 
+
+Feel free to [contact us](https://gudhi.inria.fr/contact/) in case you have any questions or remarks.
+
+For further information about downloading and installing the library ([C++](https://gudhi.inria.fr/doc/latest/installation.html) or [Python](https://gudhi.inria.fr/python/latest/installation.html)), please visit the [GUDHI web site](https://gudhi.inria.fr/).
+
diff --git a/.github/how_to_use_github_to_contribute_to_gudhi.md b/.github/how_to_use_github_to_contribute_to_gudhi.md
new file mode 100644
index 00000000..747ca39b
--- /dev/null
+++ b/.github/how_to_use_github_to_contribute_to_gudhi.md
@@ -0,0 +1,125 @@
+# How to use github to contribute to gudhi
+
+Similar information is available in many places:
+* https://jarv.is/notes/how-to-pull-request-fork-github/ (this one is using `upstream/master` when creating a new branch)
+* https://help.github.com/en/github/getting-started-with-github/fork-a-repo
+* https://blog.scottlowe.org/2015/01/27/using-fork-branch-git-workflow/
+* https://gist.github.com/Chaser324/ce0505fbed06b947d962
+* etc
+
+## Get a github account
+I assume the account is called **LOGIN**, please replace as appropriate below. Log in to github.com using this account.
+
+## Fork GUDHI/gudhi-devel project
+Go to https://github.com/GUDHI/gudhi-devel and click on **fork** (top right).
+Feel free to also click on the star next to it to show you like the project!
+You can see your fork at https://github.com/LOGIN/gudhi-devel
+
+## Create a local clone on your computer
+```bash
+git clone https://github.com/LOGIN/gudhi-devel.git
+```
+
+This creates a directory gudhi-devel, which you are free to move around or rename. For the following, change to that directory:
+```bash
+cd gudhi-devel
+```
+
+When you clone the repository, you also need to download the *submodules*.
+
+## Submodules
+Hera, used for Wasserstein distance, is available on an external git repository. To download it:
+```bash
+git submodule update --init
+```
+
+## Configuring a remote for a fork
+```bash
+git remote add upstream https://github.com/GUDHI/gudhi-devel.git
+```
+
+because you want to see the real gudhi, not just your clone.
+(It is perfectly possible to do things in the reverse order, clone from GUDHI and add the one in LOGIN as extra remote, but the names of the remotes may not match the rest of this document. You can change the name of a remote with `git remote rename oldname newname`)
+
+## Optional remotes
+Optional, if you are interested in one of the old branches
+```bash
+git remote add oldies https://github.com/GUDHI/branches.git
+```
+
+Or if you want to spy on someone's work. I assume the someone's account is called **SOMEONE**
+```bash
+git remote add someone https://github.com/SOMEONE/gudhi-devel.git
+```
+
+## Stay up-to-date
+```bash
+git fetch -p --all
+```
+This is a command you can run quite regularly.
+It tells git to check all that happened on github.
+It is safe, it will not mess with your files.
+
+**Reminder:** If the version of a submodule has changed, or if a submodule was added, you may need to:
+```bash
+git submodule sync
+git submodule update --init
+```
+
+## Create a branch, based on the current master
+```bash
+git checkout -b some-fancy-name --no-track upstream/master
+```
+Your local branch `master` and the one on your github clone are useless and often outdated, but for technical reasons there has to exist at least one branch at all times, it might as well be that one. upstream/master is the real deal, that's what you want to base your new branch on.
+
+## The real coding is here!
+Edit files, test, etc.
+
+## Commit your changes (locally)
+The basic command is just `git commit`, but it will do nothing by default.
+You need `git add my_new_file` for every new file you want to commit.
+And usually you'll want to use `git commit -a` so that all files that git already knows about and that have been modified get committed.
+
+## Push your changes (remotely)
+```bash
+git push -u origin some-fancy-name
+```
+This puts a copy of your branch on your online clone of gudhi-devel.
+Because of `-u`, it will remember where you like to push this branch, and next time you can just use `git push`.
+
+## Play again!
+Possibly iterate a few times, add more commits and push them.
+
+## Your pull request is ready
+Do not forget to update `.github/next_release.md` to announce your development in the next release note.
+
+Get your web browser to https://github.com/LOGIN/gudhi-devel, click on the button that says **Branch: some-name** (below the number of commits, above the list of files) and select the branch you are so proud of.
+Click on **New pull request** next to it.
+
+## Follow the instructions ;-)
+Note that if your branch is not quite ready, you can make a **draft pull request** (see the arrow next to the confirmation button), and later you will have access to a button to say that the branch is ready for reviews now.
+Draft pull requests can be a way to advertise that you are working on something, and possibly ask others for comments or help.
+
+## Code review
+Make sure you follow the discussion on your pull request, answer questions, take comments into account.
+You can keep pushing new commits on your branch to your fork of gudhi-devel, the pull request will automatically notice the new commits there.
+There is no need to create a new pull request.
+Once the branch is under review, fixing issues is good, but please refrain from adding extra features, that just makes the reviewers' job harder and thus slower.
+You may want to look at https://github.com/settings/notifications (and other settings nearby) if you don't receive emails when people comment on your pull request.
+Some bold reviewer might make changes to your branch. You will then need `git pull` for your local branch to reflect those.
+
+## Your work is merged!
+Once your pull request has been closed (your branch merged), you can remove your branch, both locally and also the branch on your github fork:
+```bash
+git checkout master # or any other branch, but you cannot remove the branch you are currently in
+git branch -d some-fancy-name # local branch delete
+git push origin --delete some-fancy-name # remote branch delete
+```
+If you add @VincentRouvreau or @mglisse as collaborator (https://github.com/LOGIN/gudhi-devel/settings/collaboration), they may remove the branch on your clone at the same time as they merge the branch, so you only have the local one to remove (or keep if you are nostalgic).
+
+## Keep in touch
+Create a new branch and keep contributing!
+
+Do not try to reuse an old branch that has already been merged.
+Make sure you run the fetch command just before creating any new branch, so you don't base it on some outdated version of master.
+You can also work on several branches at the same time, using `git checkout some-fancy-name` and `git checkout name-of-other-branch` to switch between them (commit before switching or things may get complicated).
diff --git a/.github/next_release.md b/.github/next_release.md
new file mode 100644
index 00000000..d3c9ce68
--- /dev/null
+++ b/.github/next_release.md
@@ -0,0 +1,58 @@
+We are pleased to announce the release 3.2.0 of the GUDHI library.
+
+As a major new feature, the GUDHI library now offers a Python interface to [Hera](https://bitbucket.org/grey_narn/hera/src/master/) to compute the Wasserstein distance.
+[PyBind11](https://github.com/pybind/pybind11) is now required to build the Python module.
+
+We are now using GitHub to develop the GUDHI library, do not hesitate to [fork the GUDHI project on GitHub](https://github.com/GUDHI/gudhi-devel). From a user point of view, we recommend to download GUDHI user version (gudhi.3.2.0.tar.gz).
+
+Below is a list of changes made since GUDHI 3.1.1:
+
+- Point cloud utilities
+     - A new module [Time Delay Embedding](https://gudhi.inria.fr/python/latest/point_cloud.html#time-delay-embedding)
+       to embed time-series data in the R^d according to [Takens' Embedding Theorem](https://en.wikipedia.org/wiki/Takens%27s_theorem)
+       and obtain the coordinates of each point.
+     - A new module [K Nearest Neighbors](https://gudhi.inria.fr/python/latest/point_cloud.html#k-nearest-neighbors)
+       that wraps several implementations for computing the k nearest neighbors in a point set.
+     - A new module [Distance To Measure](https://gudhi.inria.fr/python/latest/point_cloud.html#distance-to-measure)
+       to compute the distance to the empirical measure defined by a point set
+
+- [Persistence representations](https://gudhi.inria.fr/python/latest/representations.html)
+     - Interface to Wasserstein distances.
+
+- Rips complex
+     - A new module [Weighted Rips Complex](https://gudhi.inria.fr/python/latest/rips_complex_user.html#weighted-rips-complex)
+       to construct a simplicial complex from a distance matrix and weights on vertices.
+
+- [Wassertein distance](https://gudhi.inria.fr/python/latest/wasserstein_distance_user.html)
+     - An [another implementation](https://gudhi.inria.fr/python/latest/wasserstein_distance_user.html#hera)
+       comes from Hera (BSD-3-Clause) which is based on [Geometry Helps to Compare Persistence Diagrams](http://doi.acm.org/10.1145/3064175)
+       by Michael Kerber, Dmitriy Morozov, and Arnur Nigmetov.
+     - `gudhi.wasserstein.wasserstein_distance` has now an option to return the optimal matching that achieves the distance between the two diagrams.
+     - A new module [Barycenters](https://gudhi.inria.fr/python/latest/wasserstein_distance_user.html#barycenters)
+       to estimate the Frechet mean (aka Wasserstein barycenter) between persistence diagrams.
+
+- [Simplex tree](https://gudhi.inria.fr/python/latest/simplex_tree_ref.html)
+     - Extend filtration method to compute extended persistence
+     - Flag and lower star persistence pairs generators
+     - A new interface to filtration, simplices and skeleton getters to return an iterator
+
+- [Alpha complex](https://gudhi.inria.fr/doc/latest/group__alpha__complex.html)
+     - Improve computations (cache circumcenters computation and point comparison improvement)
+
+- [Persistence graphical tools](https://gudhi.inria.fr/python/latest/persistence_graphical_tools_user.html)
+     - New rendering option proposed (use LaTeX style, add grey block, improved positioning of labels, etc.). 
+     - Can now handle (N x 2) numpy arrays as input 
+
+- Miscellaneous
+     - The [list of bugs that were solved since GUDHI-3.2.0](https://github.com/GUDHI/gudhi-devel/issues?q=label%3A3.2.0+is%3Aclosed) is available on GitHub.
+
+All modules are distributed under the terms of the MIT license.
+However, there are still GPL dependencies for many modules. We invite you to check our [license dedicated web page](https://gudhi.inria.fr/licensing/) for further details.
+
+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.
+
+We provide [bibtex entries](https://gudhi.inria.fr/doc/latest/_citation.html) for the modules of the User and Reference Manual, as well as for publications directly related to the GUDHI library. 
+
+Feel free to [contact us](https://gudhi.inria.fr/contact/) in case you have any questions or remarks.
+
+For further information about downloading and installing the library ([C++](https://gudhi.inria.fr/doc/latest/installation.html) or [Python](https://gudhi.inria.fr/python/latest/installation.html)), please visit the [GUDHI web site](https://gudhi.inria.fr/).
diff --git a/.github/test-requirements.txt b/.github/test-requirements.txt
new file mode 100644
index 00000000..fb1df134
--- /dev/null
+++ b/.github/test-requirements.txt
@@ -0,0 +1,13 @@
+pytest
+sphinx
+sphinxcontrib-bibtex
+sphinx-paramlinks
+matplotlib
+scipy
+scikit-learn
+POT
+tensorflow
+torch
+pykeops
+hnswlib
+eagerpy