diff options
| -rw-r--r-- | biblio/bibliography.bib | 36 | ||||
| -rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 124 | ||||
| -rw-r--r-- | src/python/gudhi/simplex_tree.pxd | 2 | ||||
| -rw-r--r-- | src/python/gudhi/simplex_tree.pyx | 51 | ||||
| -rw-r--r-- | src/python/include/Simplex_tree_interface.h | 40 | ||||
| -rwxr-xr-x | src/python/test/test_simplex_tree.py | 82 |
6 files changed, 325 insertions, 10 deletions
diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 3bbe7960..b017a07e 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -7,11 +7,13 @@ } @article{Carriere17c, - author = {Carri\`ere, Mathieu and Michel, Bertrand and Oudot, Steve}, - title = {{Statistical Analysis and Parameter Selection for Mapper}}, - journal = {CoRR}, - volume = {abs/1706.00204}, - year = {2017} +author = {Carri{\`{e}}re, Mathieu and Michel, Bertrand and Oudot, Steve}, +journal = {Journal of Machine Learning Research}, +pages = {1--39}, +publisher = {JMLR.org}, +title = {{Statistical analysis and parameter selection for Mapper}}, +volume = {19}, +year = {2018} } @inproceedings{Dey13, @@ -23,11 +25,14 @@ } @article{Carriere16, - title={{Structure and Stability of the 1-Dimensional Mapper}}, - author={Carri\`ere, Mathieu and Oudot, Steve}, - journal={CoRR}, - volume= {abs/1511.05823}, - year={2015} +author = {Carri{\`{e}}re, Mathieu and Oudot, Steve}, +journal = {Foundations of Computational Mathematics}, +number = {6}, +pages = {1333--1396}, +publisher = {Springer-Verlag}, +title = {{Structure and stability of the one-dimensional Mapper}}, +volume = {18}, +year = {2017} } @inproceedings{zigzag_reflection, @@ -36,6 +41,17 @@ year = {2014 $\ \ \ \ \ \ \ \ \ \ \ $ \emph{In Preparation}}, } +@article{Cohen-Steiner2009, +author = {Cohen-Steiner, David and Edelsbrunner, Herbert and Harer, John}, +journal = {Foundations of Computational Mathematics}, +number = {1}, +pages = {79--103}, +publisher = {Springer-Verlag}, +title = {{Extending persistence using Poincar{\'{e}} and Lefschetz duality}}, +volume = {9}, +year = {2009} +} + @misc{gudhi_stpcoh, author = {Cl\'ement Maria}, title = "\textsc{Gudhi}, Simplex Tree and Persistent Cohomology Packages", diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 430d1ac4..b455ae31 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -42,6 +42,20 @@ namespace Gudhi { +/** + * \class Extended_simplex_type Simplex_tree.h gudhi/Simplex_tree.h + * \brief Extended simplex type data structure for representing the type of simplices in an extended filtration. + * + * \details The extended simplex type can be either UP (which means + * that the simplex was present originally, and is thus part of the ascending extended filtration), DOWN (which means + * that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or + * EXTRA (which means the simplex is the cone point). + * + * Details may be found in \cite Cohen-Steiner2009 and section 2.2 in \cite Carriere16. + * + */ +enum class Extended_simplex_type {UP, DOWN, EXTRA}; + struct Simplex_tree_options_full_featured; /** @@ -87,6 +101,8 @@ class Simplex_tree { /* \brief Set of nodes sharing a same parent in the simplex tree. */ typedef Simplex_tree_siblings<Simplex_tree, Dictionary> Siblings; + + struct Key_simplex_base_real { Key_simplex_base_real() : key_(-1) {} void assign_key(Simplex_key k) { key_ = k; } @@ -100,6 +116,12 @@ class Simplex_tree { void assign_key(Simplex_key); Simplex_key key() const; }; + struct Extended_filtration_data { + Filtration_value minval; + Filtration_value maxval; + Extended_filtration_data(){} + Extended_filtration_data(Filtration_value vmin, Filtration_value vmax): minval(vmin), maxval(vmax) {} + }; typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type Key_simplex_base; @@ -1471,6 +1493,108 @@ class Simplex_tree { } } + /** \brief Retrieve the original filtration value for a given simplex in the Simplex_tree. Since the + * computation of extended persistence requires modifying the filtration values, this function can be used + * to recover the original values. Moreover, computing extended persistence requires adding new simplices + * in the Simplex_tree. Hence, this function also outputs the type of each simplex. It can be either UP (which means + * that the simplex was present originally, and is thus part of the ascending extended filtration), DOWN (which means + * that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or + * EXTRA (which means the simplex is the cone point). See the definition of Extended_simplex_type. Note that if the simplex type is DOWN, the original filtration value + * is set to be the original filtration value of the corresponding (not coned) original simplex. + * \pre This function should be called only if `extend_filtration()` has been called first! + * \post The output filtration value is supposed to be the same, but might be a little different, than the + * original filtration value, due to the internal transformation (scaling to [-2,-1]) that is + * performed on the original filtration values during the computation of extended persistence. + * @param[in] f Filtration value of the simplex in the extended (i.e., modified) filtration. + * @param[in] efd Structure containing the minimum and maximum values of the original filtration. This the output of `extend_filtration()`. + * @return A pair containing the original filtration value of the simplex as well as the simplex type. + */ + std::pair<Filtration_value, Extended_simplex_type> decode_extended_filtration(Filtration_value f, const Extended_filtration_data& efd){ + std::pair<Filtration_value, Extended_simplex_type> p; + Filtration_value minval = efd.minval; + Filtration_value maxval = efd.maxval; + if (f >= -2 && f <= -1){ + p.first = minval + (maxval-minval)*(f + 2); p.second = Extended_simplex_type::UP; + } + else if (f >= 1 && f <= 2){ + p.first = minval - (maxval-minval)*(f - 2); p.second = Extended_simplex_type::DOWN; + } + else{ + p.first = std::numeric_limits<Filtration_value>::quiet_NaN(); p.second = Extended_simplex_type::EXTRA; + } + return p; + }; + + /** \brief Extend filtration for computing extended persistence. + * This function only uses the filtration values at the 0-dimensional simplices, + * and computes the extended persistence diagram induced by the lower-star filtration + * computed with these values. + * \post Note that after calling this function, the filtration + * values are actually modified. The function `decode_extended_filtration()` + * retrieves the original values and outputs the extended simplex type. + * \pre Note that this code creates an extra vertex internally, so you should make sure that + * the Simplex tree does not contain a vertex with the largest Vertex_handle. + * @return A data structure containing the maximum and minimum values of the original filtration. + * It is meant to be provided as input to `decode_extended_filtration()` in order to retrieve + * the original filtration values for each simplex. + */ + Extended_filtration_data extend_filtration() { + + // Compute maximum and minimum of filtration values + Vertex_handle maxvert = std::numeric_limits<Vertex_handle>::min(); + Filtration_value minval = std::numeric_limits<Filtration_value>::infinity(); + Filtration_value maxval = -std::numeric_limits<Filtration_value>::infinity(); + for (auto sh = root_.members().begin(); sh != root_.members().end(); ++sh){ + Filtration_value f = this->filtration(sh); + minval = std::min(minval, f); + maxval = std::max(maxval, f); + maxvert = std::max(sh->first, maxvert); + } + + GUDHI_CHECK(maxvert < std::numeric_limits<Vertex_handle>::max(), std::invalid_argument("Simplex_tree contains a vertex with the largest Vertex_handle")); + maxvert += 1; + + Simplex_tree st_copy = *this; + + // Add point for coning the simplicial complex + this->insert_simplex({maxvert}, -3); + + // For each simplex + std::vector<Vertex_handle> vr; + for (auto sh_copy : st_copy.complex_simplex_range()){ + + // Locate simplex + vr.clear(); + for (auto vh : st_copy.simplex_vertex_range(sh_copy)){ + vr.push_back(vh); + } + auto sh = this->find(vr); + + // Create cone on simplex + vr.push_back(maxvert); + if (this->dimension(sh) == 0){ + Filtration_value v = this->filtration(sh); + Filtration_value scaled_v = (v-minval)/(maxval-minval); + // Assign ascending value between -2 and -1 to vertex + this->assign_filtration(sh, -2 + scaled_v); + // Assign descending value between 1 and 2 to cone on vertex + this->insert_simplex(vr, 2 - scaled_v); + } + else{ + // Assign value -3 to simplex and cone on simplex + this->assign_filtration(sh, -3); + this->insert_simplex(vr, -3); + } + } + + // Automatically assign good values for simplices + this->make_filtration_non_decreasing(); + + // Return the filtration data + Extended_filtration_data efd(minval, maxval); + return efd; + } + /** \brief Returns a vertex of `sh` that has the same filtration value as `sh` if it exists, and `null_vertex()` otherwise. * * For a lower-star filtration built with `make_filtration_non_decreasing()`, this is a way to invert the process and find out which vertex had its filtration value propagated to `sh`. diff --git a/src/python/gudhi/simplex_tree.pxd b/src/python/gudhi/simplex_tree.pxd index 82f155de..595f22bb 100644 --- a/src/python/gudhi/simplex_tree.pxd +++ b/src/python/gudhi/simplex_tree.pxd @@ -57,6 +57,8 @@ cdef extern from "Simplex_tree_interface.h" namespace "Gudhi": void remove_maximal_simplex(vector[int] simplex) bool prune_above_filtration(double filtration) bool make_filtration_non_decreasing() + void compute_extended_filtration() + vector[vector[pair[int, pair[double, double]]]] compute_extended_persistence_subdiagrams(vector[pair[int, pair[double, double]]] dgm, double min_persistence) # Iterators over Simplex tree pair[vector[int], double] get_simplex_and_filtration(Simplex_tree_simplex_handle f_simplex) Simplex_tree_simplices_iterator get_simplices_iterator_begin() diff --git a/src/python/gudhi/simplex_tree.pyx b/src/python/gudhi/simplex_tree.pyx index c01cc905..cc3753e1 100644 --- a/src/python/gudhi/simplex_tree.pyx +++ b/src/python/gudhi/simplex_tree.pyx @@ -396,6 +396,57 @@ cdef class SimplexTree: """ return self.get_ptr().make_filtration_non_decreasing() + def extend_filtration(self): + """ Extend filtration for computing extended persistence. This function only uses the + filtration values at the 0-dimensional simplices, and computes the extended persistence + diagram induced by the lower-star filtration computed with these values. + + .. note:: + + Note that after calling this function, the filtration + values are actually modified within the Simplex_tree. + The function :func:`extended_persistence()<gudhi.SimplexTree.extended_persistence>` + retrieves the original values. + + .. note:: + + Note that this code creates an extra vertex internally, so you should make sure that + the Simplex_tree does not contain a vertex with the largest possible value (i.e., 4294967295). + """ + return self.get_ptr().compute_extended_filtration() + + def extended_persistence(self, homology_coeff_field=11, min_persistence=0): + """This function retrieves good values for extended persistence, and separate the diagrams + into the Ordinary, Relative, Extended+ and Extended- subdiagrams. + + :param homology_coeff_field: The homology coefficient field. Must be a + prime number. Default value is 11. + :type homology_coeff_field: int. + :param min_persistence: The minimum persistence value (i.e., the absolute value of the difference between the persistence diagram point coordinates) to take into + account (strictly greater than min_persistence). Default value is + 0.0. + Sets min_persistence to -1.0 to see all values. + :type min_persistence: float. + :returns: A list of four persistence diagrams in the format described in :func:`persistence()<gudhi.SimplexTree.persistence>`. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See https://link.springer.com/article/10.1007/s10208-008-9027-z and/or section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes. + + .. note:: + + This function should be called only if :func:`extend_filtration()<gudhi.SimplexTree.extend_filtration>` has been called first! + + .. note:: + + The coordinates of the persistence diagram points might be a little different than the + original filtration values due to the internal transformation (scaling to [-2,-1]) that is + performed on these values during the computation of extended persistence. + """ + cdef vector[pair[int, pair[double, double]]] persistence_result + if self.pcohptr != NULL: + del self.pcohptr + self.pcohptr = new Simplex_tree_persistence_interface(self.get_ptr(), False) + persistence_result = self.pcohptr.get_persistence(homology_coeff_field, -1.) + return self.get_ptr().compute_extended_persistence_subdiagrams(persistence_result, min_persistence) + + def persistence(self, homology_coeff_field=11, min_persistence=0, persistence_dim_max = False): """This function returns the persistence of the simplicial complex. diff --git a/src/python/include/Simplex_tree_interface.h b/src/python/include/Simplex_tree_interface.h index 4a7062d6..1a18aed6 100644 --- a/src/python/include/Simplex_tree_interface.h +++ b/src/python/include/Simplex_tree_interface.h @@ -37,8 +37,12 @@ class Simplex_tree_interface : public Simplex_tree<SimplexTreeOptions> { using Filtered_simplices = std::vector<Simplex_and_filtration>; using Skeleton_simplex_iterator = typename Base::Skeleton_simplex_iterator; using Complex_simplex_iterator = typename Base::Complex_simplex_iterator; + using Extended_filtration_data = typename Base::Extended_filtration_data; public: + + Extended_filtration_data efd; + bool find_simplex(const Simplex& vh) { return (Base::find(vh) != Base::null_simplex()); } @@ -117,6 +121,42 @@ class Simplex_tree_interface : public Simplex_tree<SimplexTreeOptions> { return cofaces; } + void compute_extended_filtration() { + this->efd = this->extend_filtration(); + this->initialize_filtration(); + return; + } + + std::vector<std::vector<std::pair<int, std::pair<Filtration_value, Filtration_value>>>> compute_extended_persistence_subdiagrams(const std::vector<std::pair<int, std::pair<Filtration_value, Filtration_value>>>& dgm, Filtration_value min_persistence){ + std::vector<std::vector<std::pair<int, std::pair<Filtration_value, Filtration_value>>>> new_dgm(4); + for (unsigned int i = 0; i < dgm.size(); i++){ + std::pair<Filtration_value, Extended_simplex_type> px = this->decode_extended_filtration(dgm[i].second.first, this->efd); + std::pair<Filtration_value, Extended_simplex_type> py = this->decode_extended_filtration(dgm[i].second.second, this->efd); + std::pair<int, std::pair<Filtration_value, Filtration_value>> pd_point = std::make_pair(dgm[i].first, std::make_pair(px.first, py.first)); + if(std::abs(px.first - py.first) > min_persistence){ + //Ordinary + if (px.second == Extended_simplex_type::UP && py.second == Extended_simplex_type::UP){ + new_dgm[0].push_back(pd_point); + } + // Relative + else if (px.second == Extended_simplex_type::DOWN && py.second == Extended_simplex_type::DOWN){ + new_dgm[1].push_back(pd_point); + } + else{ + // Extended+ + if (px.first < py.first){ + new_dgm[2].push_back(pd_point); + } + //Extended- + else{ + new_dgm[3].push_back(pd_point); + } + } + } + } + return new_dgm; + } + void create_persistence(Gudhi::Persistent_cohomology_interface<Base>* pcoh) { Base::initialize_filtration(); pcoh = new Gudhi::Persistent_cohomology_interface<Base>(*this); diff --git a/src/python/test/test_simplex_tree.py b/src/python/test/test_simplex_tree.py index f7848379..70b26e97 100755 --- a/src/python/test/test_simplex_tree.py +++ b/src/python/test/test_simplex_tree.py @@ -9,6 +9,7 @@ """ from gudhi import SimplexTree +import pytest __author__ = "Vincent Rouvreau" __copyright__ = "Copyright (C) 2016 Inria" @@ -250,6 +251,87 @@ def test_make_filtration_non_decreasing(): assert st.filtration([3, 4]) == 2.0 assert st.filtration([4, 5]) == 2.0 +def test_extend_filtration(): + + # Inserted simplex: + # 5 4 + # o o + # / \ / + # o o + # /2\ /3 + # o o + # 1 0 + + st = SimplexTree() + st.insert([0,2]) + st.insert([1,2]) + st.insert([0,3]) + st.insert([2,5]) + st.insert([3,4]) + st.insert([3,5]) + st.assign_filtration([0], 1.) + st.assign_filtration([1], 2.) + st.assign_filtration([2], 3.) + st.assign_filtration([3], 4.) + st.assign_filtration([4], 5.) + st.assign_filtration([5], 6.) + + assert list(st.get_filtration()) == [ + ([0, 2], 0.0), + ([1, 2], 0.0), + ([0, 3], 0.0), + ([3, 4], 0.0), + ([2, 5], 0.0), + ([3, 5], 0.0), + ([0], 1.0), + ([1], 2.0), + ([2], 3.0), + ([3], 4.0), + ([4], 5.0), + ([5], 6.0) + ] + + st.extend_filtration() + + assert list(st.get_filtration()) == [ + ([6], -3.0), + ([0], -2.0), + ([1], -1.8), + ([2], -1.6), + ([0, 2], -1.6), + ([1, 2], -1.6), + ([3], -1.4), + ([0, 3], -1.4), + ([4], -1.2), + ([3, 4], -1.2), + ([5], -1.0), + ([2, 5], -1.0), + ([3, 5], -1.0), + ([5, 6], 1.0), + ([4, 6], 1.2), + ([3, 6], 1.4), + ([3, 4, 6], 1.4), + ([3, 5, 6], 1.4), + ([2, 6], 1.6), + ([2, 5, 6], 1.6), + ([1, 6], 1.8), + ([1, 2, 6], 1.8), + ([0, 6], 2.0), + ([0, 2, 6], 2.0), + ([0, 3, 6], 2.0) + ] + + dgms = st.extended_persistence(min_persistence=-1.) + + assert dgms[0][0][1][0] == pytest.approx(2.) + assert dgms[0][0][1][1] == pytest.approx(3.) + assert dgms[1][0][1][0] == pytest.approx(5.) + assert dgms[1][0][1][1] == pytest.approx(4.) + assert dgms[2][0][1][0] == pytest.approx(1.) + assert dgms[2][0][1][1] == pytest.approx(6.) + assert dgms[3][0][1][0] == pytest.approx(6.) + assert dgms[3][0][1][1] == pytest.approx(1.) + def test_simplices_iterator(): st = SimplexTree() |