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 --- src/cython/doc/rips_complex_user.rst | 52 +++++++++++++++++++++++------------- 1 file changed, 34 insertions(+), 18 deletions(-) (limited to 'src/cython/doc/rips_complex_user.rst') diff --git a/src/cython/doc/rips_complex_user.rst b/src/cython/doc/rips_complex_user.rst index a8c06cf9..9fa3a677 100644 --- a/src/cython/doc/rips_complex_user.rst +++ b/src/cython/doc/rips_complex_user.rst @@ -7,27 +7,22 @@ Rips complex user manual Definition ---------- -======================================================= ===================================== ===================================== -:Authors: Clément Maria, Pawel Dlotko, Vincent Rouvreau :Introduced in: GUDHI 2.0.0 :Copyright: GPL v3 -======================================================= ===================================== ===================================== +==================================================================== ================================ ====================== +: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` | +-------------------------------------------+----------------------------------------------------------------------+ -`Rips complex `_ is a one skeleton graph that allows to -construct a simplicial complex from it. The input can be a point cloud with a given distance function, or a distance -matrix. +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 filtration value of each edge is computed from a user-given distance function, or directly from the distance -matrix. +The input discrete metric space can be provided as a point cloud plus a distance function, or as a distance matrix. -All edges that have a filtration value strictly greater than a given threshold value are not inserted into the complex. +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 this one skeleton graph, Rips inserts the one skeleton graph into the data -structure, and then expands the simplicial complex when required. - -Vertex name correspond to the index of the point in the given range (aka. the point cloud). +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 @@ -38,8 +33,27 @@ Vertex name correspond to the index of the point in the given range (aka. the po 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 Rips_complex interfaces are not detailed enough for your need, please refer to rips_persistence_step_by_step.cpp -example, where the graph construction over the Simplex_tree is more detailed. +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), which proves a +:math:`\frac{1+\epsilon}{1-\epsilon}`-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 `ε=0.3`, while the default `sparse=None` builds the +regular Rips complex. + Point cloud ----------- @@ -47,7 +61,7 @@ Point cloud Example from a point cloud ^^^^^^^^^^^^^^^^^^^^^^^^^^ -This example builds the one skeleton graph from the given points, and max_edge_length value. +This example builds the neighborhood graph from the given points, up to max_edge_length. Then it creates a :doc:`Simplex_tree ` with it. Finally, it is asked to display information about the simplicial complex. @@ -92,10 +106,12 @@ until dimension 1 - one skeleton graph in other words), the output is: [4, 6] -> 9.49 [3, 6] -> 11.00 +Notice that if we use `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 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:`Rips_complex ` from the given +This example builds the :doc:`RipsComplex ` from the given points in an OFF file, and max_edge_length value. Then it creates a :doc:`Simplex_tree ` with it. @@ -200,7 +216,7 @@ until dimension 1 - one skeleton graph in other words), the output is: Example from csv file ^^^^^^^^^^^^^^^^^^^^^ -This example builds the :doc:`Rips_complex ` from the given +This example builds the :doc:`RipsComplex ` from the given distance matrix in a csv file, and max_edge_length value. Then it creates a :doc:`Simplex_tree ` with it. -- 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 'src/cython/doc/rips_complex_user.rst') 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 d16910a5c74552b3b1feffc3e793ec5b6d52f952 Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 10 Oct 2018 21:43:35 +0000 Subject: Use math instead of unicode for epsilon git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3938 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 8cccce774b7406d90a55d0e2827fad6dc3855b39 --- src/cython/doc/rips_complex_user.rst | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/cython/doc/rips_complex_user.rst') diff --git a/src/cython/doc/rips_complex_user.rst b/src/cython/doc/rips_complex_user.rst index 95bb40b6..cddf4f16 100644 --- a/src/cython/doc/rips_complex_user.rst +++ b/src/cython/doc/rips_complex_user.rst @@ -45,7 +45,7 @@ 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), which proves a -:math:`\frac{1+\epsilon}{1-\epsilon}`-interleaving, although in practice the +:math:`\frac{1+\varepsilon}{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 -- cgit v1.2.3 From b6f3903f0ce07fe243ea7a3c18098043114f7f6a Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 10 Oct 2018 21:52:27 +0000 Subject: epsilon + code block git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3939 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 6a88d96a67d9d02f95e63fd627c295abebb49ce8 --- src/cython/doc/rips_complex_user.rst | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-) (limited to 'src/cython/doc/rips_complex_user.rst') diff --git a/src/cython/doc/rips_complex_user.rst b/src/cython/doc/rips_complex_user.rst index cddf4f16..933643e2 100644 --- a/src/cython/doc/rips_complex_user.rst +++ b/src/cython/doc/rips_complex_user.rst @@ -15,7 +15,7 @@ Definition | :doc:`rips_complex_user` | :doc:`rips_complex_ref` | +-------------------------------------------+----------------------------------------------------------------------+ -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 `Rips 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. @@ -50,7 +50,7 @@ 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 `ε=0.3`, while the default `sparse=None` builds the +parameter :math:`\varepsilon=0.3`, while the default `sparse=None` builds the regular Rips complex. @@ -105,7 +105,13 @@ until dimension 1 - one skeleton graph in other words), the output is: [4, 6] -> 9.49 [3, 6] -> 11.00 -Notice that if we use `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 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. +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 ^^^^^^^^^^^^^^^^^^^^^ -- cgit v1.2.3 From 354da3ae06ffa2479d56e9ea45cefbe218da2c76 Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 10 Oct 2018 22:11:23 +0000 Subject: Make RipsComplex a clickable link git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3942 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 642ae449f85cf8516fc632716ea14b22f74ec517 --- src/cython/doc/rips_complex_user.rst | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/cython/doc/rips_complex_user.rst') diff --git a/src/cython/doc/rips_complex_user.rst b/src/cython/doc/rips_complex_user.rst index 933643e2..e0c71cd1 100644 --- a/src/cython/doc/rips_complex_user.rst +++ b/src/cython/doc/rips_complex_user.rst @@ -19,7 +19,7 @@ The `Rips complex ` 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` 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. +When creating a simplicial complex from the graph, :doc:`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 07c214f675595b75a2a9d1f8dc2888487aa6086a Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Wed, 17 Oct 2018 08:11:14 +0000 Subject: Some indentation fix git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3960 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 6dce53b98bc0b299a3621602f385b3b44e16d489 --- src/cython/doc/rips_complex_user.rst | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'src/cython/doc/rips_complex_user.rst') diff --git a/src/cython/doc/rips_complex_user.rst b/src/cython/doc/rips_complex_user.rst index e0c71cd1..0aeffe55 100644 --- a/src/cython/doc/rips_complex_user.rst +++ b/src/cython/doc/rips_complex_user.rst @@ -69,7 +69,7 @@ Finally, it is asked to display information about the simplicial complex. 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) + 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()) + ' - ' + \ @@ -109,9 +109,11 @@ 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) + 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. +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 ^^^^^^^^^^^^^^^^^^^^^ -- cgit v1.2.3