From cc57969ebd89dc9f0eff78f5f48d1fffb3233899 Mon Sep 17 00:00:00 2001 From: Ulrich Bauer Date: Thu, 17 Dec 2020 17:41:12 +0100 Subject: enclosing radius output when no threshold is specified --- ripser.cpp | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/ripser.cpp b/ripser.cpp index bdcd249..a4145c5 100644 --- a/ripser.cpp +++ b/ripser.cpp @@ -1090,14 +1090,13 @@ int main(int argc, char** argv) { max = -std::numeric_limits::infinity(), max_finite = max; int num_edges = 0; + value_t enclosing_radius = std::numeric_limits::infinity(); if (threshold == std::numeric_limits::max()) { - value_t enclosing_radius = std::numeric_limits::infinity(); for (size_t i = 0; i < dist.size(); ++i) { value_t r_i = -std::numeric_limits::infinity(); for (size_t j = 0; j < dist.size(); ++j) r_i = std::max(r_i, dist(i, j)); enclosing_radius = std::min(enclosing_radius, r_i); } - threshold = enclosing_radius; } for (auto d : dist.distances) { @@ -1109,10 +1108,12 @@ int main(int argc, char** argv) { } std::cout << "value range: [" << min << "," << max_finite << "]" << std::endl; - if (threshold >= max) { - std::cout << "distance matrix with " << dist.size() << " points" << std::endl; - ripser(std::move(dist), dim_max, threshold, ratio, - modulus) + if (threshold == std::numeric_limits::max()) { + std::cout << "distance matrix with " << dist.size() + << " points, using threshold at enclosing radius " << enclosing_radius + << std::endl; + ripser(std::move(dist), dim_max, enclosing_radius, + ratio, modulus) .compute_barcodes(); } else { std::cout << "sparse distance matrix with " << dist.size() << " points and " @@ -1124,5 +1125,6 @@ int main(int argc, char** argv) { .compute_barcodes(); } exit(0); + } } -- cgit v1.2.3 From 9b7f0a3803ed59a3e804011d6bae2c407c1758cd Mon Sep 17 00:00:00 2001 From: Ulrich Bauer Date: Thu, 31 Dec 2020 17:11:18 +0100 Subject: some cleanup --- .gitmodules | 3 ++ ripser.cpp | 90 ++++++++++++++++++++++++++++++++++++++---------------- robin-hood-hashing | 1 + 3 files changed, 67 insertions(+), 27 deletions(-) create mode 100644 .gitmodules create mode 160000 robin-hood-hashing diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..b85c2fb --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "robin-hood-hashing"] + path = robin-hood-hashing + url = https://github.com/martinus/robin-hood-hashing.git diff --git a/ripser.cpp b/ripser.cpp index a4145c5..b377d49 100644 --- a/ripser.cpp +++ b/ripser.cpp @@ -41,7 +41,7 @@ //#define INDICATE_PROGRESS #define PRINT_PERSISTENCE_PAIRS -//#define USE_GOOGLE_HASHMAP +//#define USE_ROBINHOOD_HASHMAP #include #include @@ -54,17 +54,19 @@ #include #include -#ifdef USE_GOOGLE_HASHMAP -#include +#ifdef USE_ROBINHOOD_HASHMAP + +#include "robin-hood-hashing/src/include/robin_hood.h" + template -class hash_map : public google::dense_hash_map { -public: - explicit hash_map() : google::dense_hash_map() { this->set_empty_key(-1); } - inline void reserve(size_t hint) { this->resize(hint); } -}; +using hash_map = robin_hood::unordered_map; +template using hash = robin_hood::hash; + #else -template -class hash_map : public std::unordered_map {}; + +template using hash_map = std::unordered_map; +template using hash = std::hash; + #endif typedef float value_t; @@ -385,9 +387,7 @@ template class ripser { mutable std::vector cofacet_entries; struct entry_hash { - std::size_t operator()(const entry_t& e) const { - return std::hash()(::get_index(e)); - } + std::size_t operator()(const entry_t& e) const { return hash()(::get_index(e)); } }; struct equal_index { @@ -428,6 +428,43 @@ public: class simplex_coboundary_enumerator; + class simplex_boundary_enumerator { + private: + index_t idx_below, idx_above, j, k; + const diameter_entry_t simplex; + const coefficient_t modulus; + const binomial_coeff_table& binomial_coeff; + const index_t dim; + const ripser& parent; + + public: + simplex_boundary_enumerator(const diameter_entry_t _simplex, const index_t _dim, + const ripser& _parent) + : idx_below(get_index(_simplex)), idx_above(0), j(_parent.n - 1), k(_dim), + simplex(_simplex), modulus(_parent.modulus), binomial_coeff(_parent.binomial_coeff), + dim(_dim), parent(_parent) {} + + bool has_next() { return (k >= 0); } + + diameter_entry_t next() { + j = parent.get_max_vertex(idx_below, k + 1, j); + + index_t face_index = idx_above - binomial_coeff(j, k + 1) + idx_below; + + value_t face_diameter = parent.compute_diameter(face_index, dim - 1); + + coefficient_t face_coefficient = + (k & 1 ? -1 + modulus : 1) * get_coefficient(simplex) % modulus; + + idx_below -= binomial_coeff(j, k + 1); + idx_above += binomial_coeff(j, k); + + --k; + + return diameter_entry_t(face_diameter, face_index, face_coefficient); + } + }; + void assemble_columns_to_reduce(std::vector& simplices, std::vector& columns_to_reduce, entry_hash_map& pivot_column_index, index_t dim) { @@ -697,7 +734,7 @@ public: }; template <> class ripser::simplex_coboundary_enumerator { - index_t idx_below, idx_above, v, k; + index_t idx_below, idx_above, j, k; std::vector vertices; const diameter_entry_t simplex; const coefficient_t modulus; @@ -706,28 +743,28 @@ template <> class ripser::simplex_coboundary_e public: simplex_coboundary_enumerator(const diameter_entry_t _simplex, const index_t _dim, - const ripser& _parent) - : idx_below(get_index(_simplex)), idx_above(0), v(_parent.n - 1), k(_dim + 1), - vertices(_dim + 1), simplex(_simplex), modulus(_parent.modulus), dist(_parent.dist), - binomial_coeff(_parent.binomial_coeff) { - _parent.get_simplex_vertices(get_index(_simplex), _dim, _parent.n, vertices.rbegin()); + const ripser& parent) + : idx_below(get_index(_simplex)), idx_above(0), j(parent.n - 1), k(_dim + 1), + vertices(_dim + 1), simplex(_simplex), modulus(parent.modulus), dist(parent.dist), + binomial_coeff(parent.binomial_coeff) { + parent.get_simplex_vertices(get_index(_simplex), _dim, parent.n, vertices.rbegin()); } bool has_next(bool all_cofacets = true) { - return (v >= k && (all_cofacets || binomial_coeff(v, k) > idx_below)); + return (j >= k && (all_cofacets || binomial_coeff(j, k) > idx_below)); } diameter_entry_t next() { - while ((binomial_coeff(v, k) <= idx_below)) { - idx_below -= binomial_coeff(v, k); - idx_above += binomial_coeff(v, k + 1); - --v; + while ((binomial_coeff(j, k) <= idx_below)) { + idx_below -= binomial_coeff(j, k); + idx_above += binomial_coeff(j, k + 1); + --j; --k; assert(k != -1); } value_t cofacet_diameter = get_diameter(simplex); - for (index_t w : vertices) cofacet_diameter = std::max(cofacet_diameter, dist(v, w)); - index_t cofacet_index = idx_above + binomial_coeff(v--, k + 1) + idx_below; + for (index_t i : vertices) cofacet_diameter = std::max(cofacet_diameter, dist(j, i)); + index_t cofacet_index = idx_above + binomial_coeff(j--, k + 1) + idx_below; coefficient_t cofacet_coefficient = (k & 1 ? modulus - 1 : 1) * get_coefficient(simplex) % modulus; return diameter_entry_t(cofacet_diameter, cofacet_index, cofacet_coefficient); @@ -1125,6 +1162,5 @@ int main(int argc, char** argv) { .compute_barcodes(); } exit(0); - } } diff --git a/robin-hood-hashing b/robin-hood-hashing new file mode 160000 index 0000000..4869243 --- /dev/null +++ b/robin-hood-hashing @@ -0,0 +1 @@ +Subproject commit 4869243035a2732fdb96407db234bdc7a3a985cc -- cgit v1.2.3