From 42e599ebd89231c276a3c6e1b9121ea13f25d118 Mon Sep 17 00:00:00 2001 From: glisse Date: Tue, 2 Oct 2018 09:21:13 +0000 Subject: More doc changes for python sparse rips git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3921 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: f9a33e3c4a6fc6d68a81b753a88ff9d39bdcfb9f --- biblio/bibliography.bib | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'biblio') diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 16f43d6f..e85876d3 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -1073,9 +1073,10 @@ language={English} @article{buchet16efficient, title = {Efficient and Robust Persistent Homology for Measures}, author = {Micka\"{e}l Buchet and Fr\'{e}d\'{e}ric Chazal and Steve Y. Oudot and Donald Sheehy}, - booktitle = {Computational Geometry: Theory and Applications}, + journal = {Computational Geometry: Theory and Applications}, volume = {58}, pages = {70--96}, + doi = "https://doi.org/10.1016/j.comgeo.2016.07.001", year = {2016} } -- cgit v1.2.3 From 0567f550258966a12911cd3ffe490852c022c358 Mon Sep 17 00:00:00 2001 From: glisse Date: Sat, 6 Oct 2018 14:01:16 +0000 Subject: Doc tweaks. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3936 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 3c75c674876bcb38d0a87de41d406832baf61b55 --- biblio/bibliography.bib | 2 ++ src/cython/cython/rips_complex.pyx | 1 + src/cython/doc/rips_complex_user.rst | 5 ++--- 3 files changed, 5 insertions(+), 3 deletions(-) (limited to 'biblio') diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index e85876d3..a8c040ed 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -1084,6 +1084,7 @@ language={English} author = {Nicholas J. Cavanna and Mahmoodreza Jahanseir and Donald R. Sheehy}, booktitle = {Proceedings of the Canadian Conference on Computational Geometry}, title = {A Geometric Perspective on Sparse Filtrations}, + url = {http://research.cs.queensu.ca/cccg2015/CCCG15-papers/01.pdf}, year = {2015} } @@ -1102,5 +1103,6 @@ language={English} volume = {49}, number = {4}, pages = {778--796}, + doi = "10.1007/s00454-013-9513-1", year = {2013} } diff --git a/src/cython/cython/rips_complex.pyx b/src/cython/cython/rips_complex.pyx index ecf039b6..cb9aad2e 100644 --- a/src/cython/cython/rips_complex.pyx +++ b/src/cython/cython/rips_complex.pyx @@ -66,6 +66,7 @@ cdef class RipsComplex: :type points: list of list of double And in both cases + :param sparse: If this is not None, it switches to building a sparse Rips and represents the approximation parameter epsilon. :type sparse: float """ diff --git a/src/cython/doc/rips_complex_user.rst b/src/cython/doc/rips_complex_user.rst index 9fa3a677..95bb40b6 100644 --- a/src/cython/doc/rips_complex_user.rst +++ b/src/cython/doc/rips_complex_user.rst @@ -15,12 +15,11 @@ Definition | :doc:`rips_complex_user` | :doc:`rips_complex_ref` | +-------------------------------------------+----------------------------------------------------------------------+ -The `Rips complex `_ is a simplicial complex defined as the clique complex of a graph. The graph is defined on a set of points with one vertex for each point and an edge between any 2 points, of weight (aka filtration value) the distance between the 2 points. This graph (and thus the complex) can be restricted to edges shorter than some threshold, to reduce its size. +The `Rips complex `_ is a simplicial complex that generalizes proximity (ε-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, `RipsComplex` inserts the graph into the data -structure, and 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. +When creating a simplicial complex from the graph, `RipsComplex` 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). -- cgit v1.2.3 From 6f9bbc57d9abb1bd395b7c4d58184ee53656fc72 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Mon, 18 Feb 2019 17:15:41 +0000 Subject: Add biblio and doc references git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@4111 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 42a6e48271d333d604cb5cb0c9c9f1e56b8f1965 --- biblio/bibliography.bib | 34 ++++++++++++++++++++++++++++++++++ src/Toplex_map/doc/Intro_Toplex_map.h | 6 ++++-- 2 files changed, 38 insertions(+), 2 deletions(-) (limited to 'biblio') diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 16f43d6f..47c6b35b 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -1103,3 +1103,37 @@ language={English} pages = {778--796}, year = {2013} } + +@InProceedings{boissonnat_et_al:LIPIcs:2015:5098, + author = {Jean-Daniel Boissonnat and Karthik C. S. and S{\'e}bastien Tavenas}, + title = {{Building Efficient and Compact Data Structures for Simplicial Complexes}}, + booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, + pages = {642--656}, + series = {Leibniz International Proceedings in Informatics (LIPIcs)}, + ISBN = {978-3-939897-83-5}, + ISSN = {1868-8969}, + year = {2015}, + volume = {34}, + editor = {Lars Arge and J{\'a}nos Pach}, + publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, + address = {Dagstuhl, Germany}, + URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5098}, + URN = {urn:nbn:de:0030-drops-50981}, + doi = {10.4230/LIPIcs.SOCG.2015.642}, + annote = {Keywords: Simplicial complex, Compact data structures, Automaton, NP-hard} +} + +@article{DBLP:journals/corr/BoissonnatS16, + author = {Jean{-}Daniel Boissonnat and + {Karthik {C. S.}}}, + title = {An Efficient Representation for Filtrations of Simplicial Complexes}, + journal = {CoRR}, + volume = {abs/1607.08449}, + year = {2016}, + url = {http://arxiv.org/abs/1607.08449}, + archivePrefix = {arXiv}, + eprint = {1607.08449}, + timestamp = {Mon, 13 Aug 2018 16:46:26 +0200}, + biburl = {https://dblp.org/rec/bib/journals/corr/BoissonnatS16}, + bibsource = {dblp computer science bibliography, https://dblp.org} +} \ No newline at end of file diff --git a/src/Toplex_map/doc/Intro_Toplex_map.h b/src/Toplex_map/doc/Intro_Toplex_map.h index 0cfbae03..a925dc2b 100644 --- a/src/Toplex_map/doc/Intro_Toplex_map.h +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -45,11 +45,13 @@ namespace Gudhi { * needed for these operation is linear or quadratic in \f$\Gamma_0\f$ and \f$d\f$. * * Toplex map is composed firstly of a raw storage of toplices and secondly of a map which associate any vertex to a - * set of pointers toward all toplices containing this vertex. + * set of pointers toward all toplices containing this vertex. The data structure is described in + * \cite boissonnat_et_al:LIPIcs:2015:5098 (aka. Simplex Array List or SAL). * * \image html map.png * - * The performances are a lot better than the `Simplex_tree` as soon you use maximal simplices and not simplices. + * The performances are a lot better than the `Simplex_tree` as soon you use maximal simplices and not simplices + * (cf. \cite DBLP:journals/corr/BoissonnatS16 ). * */ /** @} */ // end defgroup toplex_map -- cgit v1.2.3 From b9a6a203a71eed7f17de219070ca24e448b53b9e Mon Sep 17 00:00:00 2001 From: Marc Glisse Date: Wed, 29 May 2019 14:17:00 +0200 Subject: Citations for bottleneck distance --- biblio/bibliography.bib | 22 +++++++++++++++++++++- .../doc/Intro_bottleneck_distance.h | 3 +++ 2 files changed, 24 insertions(+), 1 deletion(-) (limited to 'biblio') diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index be4c2db5..288692b2 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -1139,4 +1139,24 @@ language={English} timestamp = {Mon, 13 Aug 2018 16:46:26 +0200}, biburl = {https://dblp.org/rec/bib/journals/corr/BoissonnatS16}, bibsource = {dblp computer science bibliography, https://dblp.org} -} \ No newline at end of file +} + +@article{Kerber:2017:GHC:3047249.3064175, + author = {Kerber, Michael and Morozov, Dmitriy and Nigmetov, Arnur}, + title = {Geometry Helps to Compare Persistence Diagrams}, + journal = {J. Exp. Algorithmics}, + issue_date = {2017}, + volume = {22}, + month = sep, + year = {2017}, + issn = {1084-6654}, + pages = {1.4:1--1.4:20}, + articleno = {1.4}, + numpages = {20}, + url = {http://doi.acm.org/10.1145/3064175}, + doi = {10.1145/3064175}, + acmid = {3064175}, + publisher = {ACM}, + address = {New York, NY, USA}, + keywords = {Assignment problems, bipartite matching, k-d tree, persistent homology}, +} diff --git a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h index f8fce96c..6fd058a8 100644 --- a/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h +++ b/src/Bottleneck_distance/doc/Intro_bottleneck_distance.h @@ -41,6 +41,9 @@ namespace persistence_diagram { * * \image html perturb_pd.png On this picture, the red edges represent the matching. The bottleneck distance is the length of the longest edge. * + * 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. */ /** @} */ // end defgroup bottleneck_distance -- cgit v1.2.3