From f5c97bc9fd1c247045d35ddf261f9afe4d024406 Mon Sep 17 00:00:00 2001 From: glisse Date: Fri, 20 Jul 2018 15:03:46 +0000 Subject: First try at interfacing the sparse rips in python. Needs at least documentation and tests. git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3697 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 75bef59e90355853ee24807ca7453c4bb0a38f43 --- src/Rips_complex/doc/Intro_rips_complex.h | 5 ++- src/Simplex_tree/include/gudhi/Simplex_tree.h | 1 + src/cython/cython/rips_complex.pyx | 50 ++++++++++++++++----------- src/cython/include/Rips_complex_interface.h | 39 ++++++++++++++------- src/cython/test/test_rips_complex.py | 1 - 5 files changed, 60 insertions(+), 36 deletions(-) (limited to 'src') diff --git a/src/Rips_complex/doc/Intro_rips_complex.h b/src/Rips_complex/doc/Intro_rips_complex.h index 712d3b6e..3db5287e 100644 --- a/src/Rips_complex/doc/Intro_rips_complex.h +++ b/src/Rips_complex/doc/Intro_rips_complex.h @@ -53,7 +53,10 @@ namespace rips_complex { * The number of simplices in the full Rips complex is exponential in the * number of vertices, it is thus usually restricted, by excluding all the * simplices with filtration value larger than some threshold, and keeping only - * the dim_max-skeleton. + * the dim_max-skeleton. It may also be a good idea to start by making the + * point set sparser, for instance with + * `Gudhi::subsampling::sparsify_point_set`, since small clusters of points + * have a disproportionate cost without affecting the persistence diagram much. * * In order to build this complex, the algorithm first builds the graph. * The filtration value of each edge is computed from a user-given distance diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index ee96d5a2..2c4c53a3 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -1035,6 +1035,7 @@ class Simplex_tree { * The Simplex_tree must contain no simplex of dimension bigger than * 1 when calling the method. */ void expansion(int max_dim) { + if (max_dim <= 1) return; dimension_ = max_dim; for (Dictionary_it root_it = root_.members_.begin(); root_it != root_.members_.end(); ++root_it) { diff --git a/src/cython/cython/rips_complex.pyx b/src/cython/cython/rips_complex.pyx index 59c16bff..620130ca 100644 --- a/src/cython/cython/rips_complex.pyx +++ b/src/cython/cython/rips_complex.pyx @@ -33,7 +33,11 @@ __license__ = "GPL v3" cdef extern from "Rips_complex_interface.h" namespace "Gudhi": cdef cppclass Rips_complex_interface "Gudhi::rips_complex::Rips_complex_interface": - Rips_complex_interface(vector[vector[double]] values, double threshold, bool euclidean) + Rips_complex_interface() + void init_points(vector[vector[double]] values, double threshold) + void init_matrix(vector[vector[double]] values, double threshold) + void init_points_sparse(vector[vector[double]] values, double threshold, double sparse) + void init_matrix_sparse(vector[vector[double]] values, double threshold, double sparse) void create_simplex_tree(Simplex_tree_interface_full_featured* simplex_tree, int dim_max) # RipsComplex python interface @@ -44,14 +48,14 @@ cdef class RipsComplex: function, or a distance matrix. """ - cdef Rips_complex_interface * thisptr + cdef Rips_complex_interface thisref # Fake constructor that does nothing but documenting the constructor - def __init__(self, points=None, distance_matrix=None, max_edge_length=float('inf')): + def __init__(self, points=None, distance_matrix=None, max_edge_length=float('inf'), sparse=None): """RipsComplex constructor. :param max_edge_length: Rips value. - :type max_edge_length: int + :type max_edge_length: float :param points: A list of points in d-Dimension. :type points: list of list of double @@ -61,27 +65,31 @@ cdef class RipsComplex: :param distance_matrix: A distance matrix (full square or lower triangular). :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 """ # The real cython constructor - def __cinit__(self, points=None, distance_matrix=None, max_edge_length=float('inf')): - if distance_matrix is not None: - self.thisptr = new Rips_complex_interface(distance_matrix, max_edge_length, False) + def __cinit__(self, points=None, distance_matrix=None, max_edge_length=float('inf'), sparse=None): + if sparse is not None: + if distance_matrix is not None: + self.thisref.init_matrix_sparse(distance_matrix, max_edge_length, sparse) + else: + if points is None: + # Empty Rips construction + points=[] + self.thisref.init_points_sparse(points, max_edge_length, sparse) else: - if points is None: - # Empty Rips construction - points=[] - self.thisptr = new Rips_complex_interface(points, max_edge_length, True) - - - def __dealloc__(self): - if self.thisptr != NULL: - del self.thisptr + if distance_matrix is not None: + self.thisref.init_matrix(distance_matrix, max_edge_length) + else: + if points is None: + # Empty Rips construction + points=[] + self.thisref.init_points(points, max_edge_length) - def __is_defined(self): - """Returns true if RipsComplex pointer is not NULL. - """ - return self.thisptr != NULL def create_simplex_tree(self, max_dimension=1): """ @@ -92,5 +100,5 @@ cdef class RipsComplex: :rtype: SimplexTree """ simplex_tree = SimplexTree() - self.thisptr.create_simplex_tree(simplex_tree.thisptr, max_dimension) + self.thisref.create_simplex_tree(simplex_tree.thisptr, max_dimension) return simplex_tree diff --git a/src/cython/include/Rips_complex_interface.h b/src/cython/include/Rips_complex_interface.h index 8b6c9c35..f6fc79a1 100644 --- a/src/cython/include/Rips_complex_interface.h +++ b/src/cython/include/Rips_complex_interface.h @@ -25,8 +25,11 @@ #include #include +#include #include +#include + #include "Simplex_tree_interface.h" #include @@ -43,28 +46,38 @@ class Rips_complex_interface { using Distance_matrix = std::vector::Filtration_value>>; public: - Rips_complex_interface(const std::vector>& values, double threshold, bool euclidean) { - if (euclidean) { - // Rips construction where values is a vector of points - rips_complex_ = new Rips_complex::Filtration_value>(values, threshold, - Gudhi::Euclidean_distance()); - } else { - // Rips construction where values is a distance matrix - rips_complex_ = new Rips_complex::Filtration_value>(values, threshold); - } + void init_points(const std::vector>& points, double threshold) { + rips_complex_.emplace(points, threshold, Gudhi::Euclidean_distance()); + } + void init_matrix(const std::vector>& matrix, double threshold) { + rips_complex_.emplace(matrix, threshold); } - ~Rips_complex_interface() { - delete rips_complex_; + void init_points_sparse(const std::vector>& points, double threshold, double epsilon) { + sparse_rips_complex_.emplace(points, Gudhi::Euclidean_distance(), epsilon); + threshold_ = threshold; + } + void init_matrix_sparse(const std::vector>& matrix, double threshold, double epsilon) { + sparse_rips_complex_.emplace(matrix, epsilon); + threshold_ = threshold; } void create_simplex_tree(Simplex_tree_interface<>* simplex_tree, int dim_max) { - rips_complex_->create_complex(*simplex_tree, dim_max); + if (rips_complex_) + rips_complex_->create_complex(*simplex_tree, dim_max); + else { + sparse_rips_complex_->create_complex(*simplex_tree, dim_max); + // This pruning should be done much earlier! It isn't that useful for sparse Rips, but it would be inconsistent not to do it. + simplex_tree->prune_above_filtration(threshold_); + } simplex_tree->initialize_filtration(); } private: - Rips_complex::Filtration_value>* rips_complex_; + // std::variant would work, but we don't require C++17 yet, and boost::variant is not super convenient. Anyway, storing a graph would make more sense. Or changing the interface completely so there is no such storage. + boost::optional::Filtration_value>> rips_complex_; + boost::optional::Filtration_value>> sparse_rips_complex_; + double threshold_; }; } // namespace rips_complex diff --git a/src/cython/test/test_rips_complex.py b/src/cython/test/test_rips_complex.py index c37b5400..2eb1c61c 100755 --- a/src/cython/test/test_rips_complex.py +++ b/src/cython/test/test_rips_complex.py @@ -30,7 +30,6 @@ __license__ = "GPL v3" def test_empty_rips(): rips_complex = RipsComplex() - assert rips_complex.__is_defined() == True def test_rips_from_points(): point_list = [[0, 0], [1, 0], [0, 1], [1, 1]] -- cgit v1.2.3 From 629a456684e9bbf4c2ef5dbfefebe85e9c04a39d Mon Sep 17 00:00:00 2001 From: glisse Date: Mon, 10 Sep 2018 09:23:07 +0000 Subject: Add minimal testing for sparse rips in python git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3879 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 14cde17f1ef634539937b215e82bcfe3c8c784f0 --- src/cython/test/test_rips_complex.py | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'src') diff --git a/src/cython/test/test_rips_complex.py b/src/cython/test/test_rips_complex.py index 2eb1c61c..73cdac17 100755 --- a/src/cython/test/test_rips_complex.py +++ b/src/cython/test/test_rips_complex.py @@ -67,6 +67,18 @@ def test_filtered_rips_from_points(): assert simplex_tree.num_simplices() == 8 assert simplex_tree.num_vertices() == 4 +def test_sparse_filtered_rips_from_points(): + point_list = [[0, 0], [1, 0], [0, 1], [1, 1]] + filtered_rips = RipsComplex(points=point_list, max_edge_length=1.0, sparse=.001) + + simplex_tree = filtered_rips.create_simplex_tree(max_dimension=1) + + assert simplex_tree.__is_defined() == True + assert simplex_tree.__is_persistence_defined() == False + + assert simplex_tree.num_simplices() == 8 + assert simplex_tree.num_vertices() == 4 + def test_rips_from_distance_matrix(): distance_matrix = [[0], [1, 0], -- cgit v1.2.3 From 4bf56301ea1aa0c43855bea88344c80db237adbb Mon Sep 17 00:00:00 2001 From: glisse Date: Mon, 10 Sep 2018 09:29:57 +0000 Subject: sparse rips example git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3880 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 8dfc1b3218d3ac3e97a04bf25e59e2d48fc8db1d --- .../example/sparse_rips_persistence_diagram.py | 43 ++++++++++++++++++++++ 1 file changed, 43 insertions(+) create mode 100755 src/cython/example/sparse_rips_persistence_diagram.py (limited to 'src') diff --git a/src/cython/example/sparse_rips_persistence_diagram.py b/src/cython/example/sparse_rips_persistence_diagram.py new file mode 100755 index 00000000..3bed87c1 --- /dev/null +++ b/src/cython/example/sparse_rips_persistence_diagram.py @@ -0,0 +1,43 @@ +#!/usr/bin/env python + +import gudhi + +"""This file is part of the Gudhi Library. The Gudhi library + (Geometric Understanding in Higher Dimensions) is a generic C++ + library for computational topology. + + Author(s): Marc Glisse + + Copyright (C) 2016 Inria + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +""" + +__author__ = "Marc Glisse" +__copyright__ = "Copyright (C) 2016 Inria" +__license__ = "GPL v3" + +print("#####################################################################") +print("RipsComplex creation from points") +rips = gudhi.RipsComplex(points=[[0, 0], [0, 0.1], [1, 0], [0, 1], [1, 1]], + max_edge_length=42, sparse=.5) + +simplex_tree = rips.create_simplex_tree(max_dimension=2) + + +diag = simplex_tree.persistence(homology_coeff_field=2, min_persistence=0) +print("diag=", diag) + +pplot = gudhi.plot_persistence_diagram(diag) +pplot.show() -- cgit v1.2.3 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 +- src/Rips_complex/doc/Intro_rips_complex.h | 2 +- src/cython/cython/rips_complex.pyx | 3 +- src/cython/doc/rips_complex_user.rst | 52 ++++++++++++++++++++----------- 4 files changed, 38 insertions(+), 22 deletions(-) (limited to 'src') 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} } diff --git a/src/Rips_complex/doc/Intro_rips_complex.h b/src/Rips_complex/doc/Intro_rips_complex.h index 3db5287e..e54ae57c 100644 --- a/src/Rips_complex/doc/Intro_rips_complex.h +++ b/src/Rips_complex/doc/Intro_rips_complex.h @@ -39,7 +39,7 @@ namespace rips_complex { * (Wikipedia) * is an abstract simplicial complex * defined on a finite metric space, where each simplex corresponds to a subset - * of point whose diameter is smaller that some given threshold. + * of points whose diameter is smaller that some given threshold. * Varying the threshold, we can also see the Rips complex as a filtration of * the \f$(n-1)-\f$dimensional simplex, where the filtration value of each * simplex is the diameter of the corresponding subset of points. diff --git a/src/cython/cython/rips_complex.pyx b/src/cython/cython/rips_complex.pyx index 620130ca..ecf039b6 100644 --- a/src/cython/cython/rips_complex.pyx +++ b/src/cython/cython/rips_complex.pyx @@ -62,8 +62,7 @@ cdef class RipsComplex: Or - :param distance_matrix: A distance matrix (full square or lower - triangular). + :param distance_matrix: A distance matrix (full square or lower triangular). :type points: list of list of double And in both cases 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') 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 c537a466ffdd812d92098bcea04cdf6f0bfc64ec Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 10 Oct 2018 21:17:19 +0000 Subject: Example text and copyright year git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3937 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 6d5bf6a2c55f7c4fd4f3f5159651b3ffa057ffdd --- src/cython/example/sparse_rips_persistence_diagram.py | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src') diff --git a/src/cython/example/sparse_rips_persistence_diagram.py b/src/cython/example/sparse_rips_persistence_diagram.py index 3bed87c1..d58c244c 100755 --- a/src/cython/example/sparse_rips_persistence_diagram.py +++ b/src/cython/example/sparse_rips_persistence_diagram.py @@ -8,7 +8,7 @@ import gudhi Author(s): Marc Glisse - Copyright (C) 2016 Inria + Copyright (C) 2018 Inria This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -25,11 +25,11 @@ import gudhi """ __author__ = "Marc Glisse" -__copyright__ = "Copyright (C) 2016 Inria" +__copyright__ = "Copyright (C) 2018 Inria" __license__ = "GPL v3" print("#####################################################################") -print("RipsComplex creation from points") +print("Sparse RipsComplex creation from points") rips = gudhi.RipsComplex(points=[[0, 0], [0, 0.1], [1, 0], [0, 1], [1, 1]], max_edge_length=42, sparse=.5) -- 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') 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') 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 e9d843d0a5c48315c45e8639e8bf9b79ccf904af Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 10 Oct 2018 21:55:26 +0000 Subject: add example to the list of examples git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3940 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: fe3c41785e3bb72766f7a817851583f82b9f7d15 --- src/cython/doc/examples.rst | 1 + 1 file changed, 1 insertion(+) (limited to 'src') diff --git a/src/cython/doc/examples.rst b/src/cython/doc/examples.rst index 1f02f8a2..edbc2f72 100644 --- a/src/cython/doc/examples.rst +++ b/src/cython/doc/examples.rst @@ -22,6 +22,7 @@ Examples * :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>` -- cgit v1.2.3 From 665ba1dfe82b663ed755267b74c62706ec6eb88a Mon Sep 17 00:00:00 2001 From: glisse Date: Wed, 10 Oct 2018 22:04:13 +0000 Subject: add myself as coauthor git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/sparserips-python@3941 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 61cf8acdce3bc5cb0c8261166e195eccc3f8bb54 --- src/cython/doc/rips_complex_sum.inc | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src') diff --git a/src/cython/doc/rips_complex_sum.inc b/src/cython/doc/rips_complex_sum.inc index 5616bfa9..ea26769a 100644 --- a/src/cython/doc/rips_complex_sum.inc +++ b/src/cython/doc/rips_complex_sum.inc @@ -1,6 +1,6 @@ -================================================================= =================================== =================================== -:Author: Clément Maria, Pawel Dlotko, Vincent Rouvreau :Introduced in: GUDHI 2.0.0 :Copyright: GPL v3 -================================================================= =================================== =================================== +===================================================================== =========================== =================================== +:Author: Clément Maria, Pawel Dlotko, Vincent Rouvreau, Marc Glisse :Introduced in: GUDHI 2.0.0 :Copyright: GPL v3 +===================================================================== =========================== =================================== +----------------------------------------------------------------+------------------------------------------------------------------------+ | .. figure:: | Rips complex is a simplicial complex constructed from a one skeleton | -- 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') 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') 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