diff options
Diffstat (limited to 'src/Persistent_cohomology')
3 files changed, 56 insertions, 56 deletions
diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h index f638a0fb..27d64b8a 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology.h @@ -42,15 +42,22 @@ namespace Gudhi { namespace persistent_cohomology { -/** \defgroup persistent_cohomology Persistent Cohomology Package - * - * Computation of persistent cohomology using the algorithm of - * \cite DBLP:journals/dcg/SilvaMV11 and \cite DBLP:journals/corr/abs-1208-5018 - * and the Compressed Annotation Matrix - * implementation of \cite DBLP:conf/esa/BoissonnatDM13 - * - * - * +/** \defgroup persistent_cohomology Persistent Cohomology + * + + Computation of persistent cohomology using the algorithm of + \cite DBLP:journals/dcg/SilvaMV11 and \cite DBLP:journals/corr/abs-1208-5018 + and the Compressed Annotation Matrix + implementation of \cite DBLP:conf/esa/BoissonnatDM13 + + The theory of homology consists in attaching to a topological space a sequence of + (homology) groups, + capturing global topological features + like connected components, holes, cavities, etc. Persistent homology studies the evolution + -- birth, life and death -- of + these features when the topological space is changing. Consequently, the theory is essentially + composed of three elements: + topological spaces, their homology groups and an evolution scheme. The theory of homology consists in attaching to a topological space a sequence of (homology) groups, @@ -154,18 +161,19 @@ namespace persistent_cohomology { by increasing filtration values (breaking ties so as a simplex appears after its subsimplices of same filtration value) provides an indexing scheme. +\section Examples + We provide several example files: run these examples with -h for details on their use, and read the README file. + +\li <CODE>rips_persistence.cpp</CODE> computes the Rips complex of a point cloud and its persistence diagram. +\li <CODE>rips_multifield_persistence.cpp</CODE> computes the Rips complex of a point cloud and its persistence diagram +with a family of field coefficients. - <DT>Implementations:</DT> - We use the <EM>Compressed Annotation Matrix</EM> of \cite DBLP:conf/esa/BoissonnatDM13 to - implement the - persistent cohomology algorithm of \cite DBLP:journals/dcg/SilvaMV11 - and \cite DBLP:conf/compgeom/DeyFW14 for persistence in the class Persistent_cohomology. +\li <CODE>performance_rips_persistence.cpp</CODE> provides timings for the construction of the Rips complex on a set of +points sampling a Klein bottle in \f$\mathbb{R}^5\f$ with a simplex tree, its conversion to a +Hasse diagram and the computation of persistent homology and multi-field persistent homology for the +different representations. - The coefficient fields available as models of CoefficientField are Field_Zp - for \f$\mathbb{Z}_p\f$ (for any prime p) and Multi_field for the multi-field persistence algorithm - -- computing persistence simultaneously in various coefficient fields -- described - in \cite boissonnat:hal-00922572. \author Clément Maria @@ -294,11 +302,11 @@ class Persistent_cohomology { public: /** \brief Initializes the coefficient field.*/ - void init_coefficients(uint8_t charac) { + void init_coefficients(uint16_t charac) { coeff_field_.init(charac); } /** \brief Initializes the coefficient field for multi-field persistent homology.*/ - void init_coefficients(uint8_t charac_min, uint8_t charac_max) { + void init_coefficients(uint16_t charac_min, uint16_t charac_max) { coeff_field_.init(charac_min, charac_max); } @@ -460,7 +468,7 @@ class Persistent_cohomology { if (w_y != coeff_field_.additive_identity()) { // if != 0 result_insert_a_ds = map_a_ds.insert(std::pair<Simplex_key, Arith_element>(cell_ref.key_, w_y)); if (!(result_insert_a_ds.second)) { // if cell_ref.key_ already a Key in map_a_ds - coeff_field_.plus_equal(result_insert_a_ds.first->second, w_y); + result_insert_a_ds.first->second = coeff_field_.plus_equal(result_insert_a_ds.first->second, w_y); if (result_insert_a_ds.first->second == coeff_field_.additive_identity()) { map_a_ds.erase(result_insert_a_ds.first); } @@ -632,16 +640,14 @@ class Persistent_cohomology { Cell * cell_tmp = cell_pool_->construct(Cell(other_it->first // key , coeff_field_.additive_identity(), &target)); - coeff_field_.plus_times_equal(cell_tmp->coefficient_, - other_it->second, w); + cell_tmp->coefficient_ = coeff_field_.plus_times_equal(cell_tmp->coefficient_, other_it->second, w); target.col_.insert(target_it, *cell_tmp); ++other_it; } else { // it1->key == it2->key // target_it->coefficient_ <- target_it->coefficient_ + other_it->second * w - coeff_field_.plus_times_equal(target_it->coefficient_, - other_it->second, w); + target_it->coefficient_ = coeff_field_.plus_times_equal(target_it->coefficient_, other_it->second, w); if (target_it->coefficient_ == coeff_field_.additive_identity()) { auto tmp_it = target_it; ++target_it; @@ -660,7 +666,7 @@ class Persistent_cohomology { } while (other_it != other.end()) { Cell * cell_tmp = cell_pool_->construct(Cell(other_it->first, coeff_field_.additive_identity(), &target)); - coeff_field_.plus_times_equal(cell_tmp->coefficient_, other_it->second, w); + cell_tmp->coefficient_ = coeff_field_.plus_times_equal(cell_tmp->coefficient_, other_it->second, w); target.col_.insert(target.col_.end(), *cell_tmp); ++other_it; diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Field_Zp.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Field_Zp.h index 49883a4a..419bd2eb 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Field_Zp.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Field_Zp.h @@ -46,7 +46,7 @@ class Field_Zp { add_id_all(0) { } - void init(uint8_t charac) { + void init(uint16_t charac) { assert(charac != 0); // division by zero Prime = charac; inverse_.clear(); @@ -61,29 +61,26 @@ class Field_Zp { } /** Set x <- x + w * y*/ - void plus_times_equal(Element & x, Element y, Element w) { + Element plus_times_equal(const Element& x, const Element& y, const Element& w) { assert(Prime != 0); // division by zero - x = (x + w * y) % Prime; + Element result = (x + w * y) % Prime; + if (result < 0) + result += Prime; + return result; } // operator= defined on Element /** Returns y * w */ - Element times(Element y, int w) { - assert(Prime != 0); // division by zero - Element res = (y * w) % Prime; - if (res < 0) - return res + Prime; - else - return res; + Element times(const Element& y, const Element& w) { + return plus_times_equal(0, y, (Element)w); } void clear_coefficient(Element x) { } - void plus_equal(Element & x, Element y) { - assert(Prime != 0); // division by zero - x = ((x + y) % Prime); + Element plus_equal(const Element& x, const Element& y) { + return plus_times_equal(x, y, (Element)1); } /** \brief Returns the additive idendity \f$0_{\Bbbk}\f$ of the field.*/ @@ -107,12 +104,12 @@ class Field_Zp { } /** \brief Returns the characteristic \f$p\f$ of the field.*/ - const uint8_t& characteristic() const { + const uint16_t& characteristic() const { return Prime; } private: - uint8_t Prime; + uint16_t Prime; /** Property map Element -> Element, which associate to an element its inverse in the field.*/ std::vector<Element> inverse_; const Element mult_id_all; diff --git a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h index 306877e7..91937c65 100644 --- a/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h +++ b/src/Persistent_cohomology/include/gudhi/Persistent_cohomology/Multi_field.h @@ -52,7 +52,7 @@ class Multi_field { /* Initialize the multi-field. The generation of prime numbers might fail with * a very small probability.*/ - void init(uint8_t min_prime, uint8_t max_prime) { + void init(uint16_t min_prime, uint16_t max_prime) { if (max_prime < 2) { std::cerr << "There is no prime less than " << max_prime << std::endl; } @@ -61,7 +61,7 @@ class Multi_field { << std::endl; } // fill the list of prime numbers - uint8_t curr_prime = min_prime; + uint16_t curr_prime = min_prime; mpz_t tmp_prime; mpz_init_set_ui(tmp_prime, min_prime); // test if min_prime is prime @@ -132,18 +132,12 @@ class Multi_field { } /** Returns y * w */ - Element times(const Element& y, int w) { - assert(prod_characteristics_ != 0); // division by zero - Element tmp = (y * w) % prod_characteristics_; - if (tmp < 0) - return prod_characteristics_ + tmp; - return tmp; + Element times(const Element& y, const Element& w) { + return plus_times_equal(0, y, w); } - void plus_equal(Element & x, const Element& y) { - assert(prod_characteristics_ != 0); // division by zero - x += y; - x %= prod_characteristics_; + Element plus_equal(const Element& x, const Element& y) { + return plus_times_equal(x, y, (Element)1); } /** \brief Returns the characteristic \f$p\f$ of the field.*/ @@ -172,14 +166,17 @@ class Multi_field { } /** Set x <- x + w * y*/ - void plus_times_equal(Element & x, const Element& y, const Element& w) { + Element plus_times_equal(const Element& x, const Element& y, const Element& w) { assert(prod_characteristics_ != 0); // division by zero - x = (x + w * y) % prod_characteristics_; + Element result = (x + w * y) % prod_characteristics_; + if (result < 0) + result += prod_characteristics_; + return result; } Element prod_characteristics_; // product of characteristics of the fields // represented by the multi-field class - std::vector<uint8_t> primes_; // all the characteristics of the fields + std::vector<uint16_t> primes_; // all the characteristics of the fields std::vector<Element> Uvect_; Element mult_id_all; const Element add_id_all; |