diff options
author | Ulrich Bauer <ulrich.bauer@tum.de> | 2016-05-24 17:17:34 +0200 |
---|---|---|
committer | Ulrich Bauer <ulrich.bauer@tum.de> | 2016-05-24 17:17:34 +0200 |
commit | c3afc0b529554cf737aeb41df86629d23280ba37 (patch) | |
tree | c95ca4731f6c1efa1e808b8681685e33a9b69eb8 /ripser.cpp | |
parent | 05747807349f86b372f746edc384d7a26770d6f1 (diff) | |
parent | bb8a173be181d3035e6523cb38a4eec526c4bd71 (diff) |
updated Google hash map support
Diffstat (limited to 'ripser.cpp')
-rw-r--r-- | ripser.cpp | 101 |
1 files changed, 49 insertions, 52 deletions
@@ -1,20 +1,32 @@ +#define USE_BINARY_SEARCH +//#define USE_EXPONENTIAL_SEARCH + +//#define ASSEMBLE_REDUCTION_MATRIX +//#define USE_COEFFICIENTS + +//#define INDICATE_PROGRESS +//#define PRINT_PERSISTENCE_PAIRS + +//#define FILE_FORMAT_DIPHA +//#define FILE_FORMAT_UPPER_TRIANGULAR_CSV +//#define FILE_FORMAT_LOWER_TRIANGULAR_CSV + +//#define USE_GOOGLE_HASHMAP + #include <iostream> #include <fstream> #include <cassert> #include <queue> -#include <cmath> +#include <unordered_map> #ifdef USE_GOOGLE_HASHMAP - #include <sparsehash/sparse_hash_map> template <class Key, class T> class hash_map : public google::sparse_hash_map<Key, T> { - public: inline void reserve(size_t hint) { this->resize(hint); } }; - +public: + inline void reserve(size_t hint) { this->resize(hint); } +}; #else - -#include <unordered_map> template <class Key, class T> class hash_map : public std::unordered_map<Key, T> {}; - #endif typedef float value_t; @@ -23,19 +35,6 @@ typedef float value_t; typedef long index_t; typedef long coefficient_t; -#define USE_BINARY_SEARCH -//#define USE_EXPONENTIAL_SEARCH - -//#define ASSEMBLE_REDUCTION_MATRIX -//#define USE_COEFFICIENTS - -//#define INDICATE_PROGRESS -//#define PRINT_PERSISTENCE_PAIRS - -//#define FILE_FORMAT_DIPHA -//#define FILE_FORMAT_UPPER_TRIANGULAR_CSV -//#define FILE_FORMAT_LOWER_TRIANGULAR_CSV - class binomial_coeff_table { std::vector<std::vector<index_t>> B; index_t n_max, k_max; @@ -271,7 +270,7 @@ public: idx -= binomial_coeff(v, k); modified_idx += binomial_coeff(v, k + 1) - binomial_coeff(v, k); --v; - --k; + --k; assert(k != -1); } return v != -1; @@ -371,13 +370,12 @@ typedef compressed_distance_matrix_adapter<LOWER_TRIANGULAR> typedef compressed_distance_matrix_adapter<UPPER_TRIANGULAR> compressed_upper_distance_matrix_adapter; - template <typename Heap> inline diameter_entry_t pop_pivot(Heap& column, coefficient_t modulus) { if (column.empty()) return diameter_entry_t(-1); else { auto pivot = column.top(); - + #ifdef USE_COEFFICIENTS coefficient_t coefficient = 0; do { @@ -409,7 +407,6 @@ template <typename Heap> inline diameter_entry_t pop_pivot(Heap& column, coeffic } } - template <typename Heap> inline diameter_entry_t get_pivot(Heap& column, coefficient_t modulus) { diameter_entry_t result = pop_pivot(column, modulus); if (get_index(result) != -1) { column.push(result); } @@ -428,8 +425,7 @@ void assemble_columns_to_reduce(std::vector<diameter_index_t>& columns_to_reduce for (index_t index = 0; index < num_simplices; ++index) { if (pivot_column_index.find(index) == pivot_column_index.end()) { value_t diameter = comp.diameter(index); - if (diameter <= threshold) - columns_to_reduce.push_back(std::make_pair(diameter, index)); + if (diameter <= threshold) columns_to_reduce.push_back(std::make_pair(diameter, index)); } } @@ -486,10 +482,10 @@ inline void push_entry(Heap& column, index_t i, coefficient_t c, value_t diamete template <typename DistanceMatrix, typename ComparatorCofaces, typename Comparator> void compute_pairs(std::vector<diameter_index_t>& columns_to_reduce, - hash_map<index_t, index_t>& pivot_column_index, - const DistanceMatrix& dist, const ComparatorCofaces& comp, - const Comparator& comp_prev, index_t dim, index_t n, value_t threshold, - coefficient_t modulus, const std::vector<coefficient_t>& multiplicative_inverse, + hash_map<index_t, index_t>& pivot_column_index, const DistanceMatrix& dist, + const ComparatorCofaces& comp, const Comparator& comp_prev, index_t dim, + index_t n, value_t threshold, coefficient_t modulus, + const std::vector<coefficient_t>& multiplicative_inverse, const binomial_coeff_table& binomial_coeff) { #ifdef PRINT_PERSISTENCE_PAIRS @@ -504,8 +500,8 @@ void compute_pairs(std::vector<diameter_index_t>& columns_to_reduce, #endif #endif - std::vector<diameter_entry_t> coface_entries; - std::vector<index_t> vertices; + std::vector<diameter_entry_t> coface_entries; + std::vector<index_t> vertices; for (index_t i = 0; i < columns_to_reduce.size(); ++i) { auto column_to_reduce = columns_to_reduce[i]; @@ -547,7 +543,7 @@ void compute_pairs(std::vector<diameter_index_t>& columns_to_reduce, #endif bool might_be_apparent_pair = true; - + do { const coefficient_t factor = modulus - get_coefficient(pivot); @@ -575,10 +571,11 @@ void compute_pairs(std::vector<diameter_index_t>& columns_to_reduce, make_diameter_entry(simplex_diameter, get_index(simplex), simplex_coefficient)); #endif - vertices.clear(); - get_simplex_vertices(get_index(simplex), dim, n, binomial_coeff, std::back_inserter(vertices)); - - coface_entries.clear(); + vertices.clear(); + get_simplex_vertices(get_index(simplex), dim, n, binomial_coeff, + std::back_inserter(vertices)); + + coface_entries.clear(); simplex_coboundary_enumerator cofaces(get_index(simplex), dim, n, binomial_coeff); while (cofaces.has_next()) { auto coface_descriptor = cofaces.next(); @@ -597,26 +594,26 @@ void compute_pairs(std::vector<diameter_index_t>& columns_to_reduce, coface_coefficient %= modulus; if (coface_coefficient < 0) coface_coefficient += modulus; assert(coface_coefficient >= 0); - - diameter_entry_t coface_entry = make_diameter_entry(coface_diameter, coface_index, coface_coefficient); - coface_entries.push_back(coface_entry); - - if (might_be_apparent_pair && (simplex_diameter == coface_diameter)) { - if (pivot_column_index.find(coface_index) == pivot_column_index.end()) - { - pivot = coface_entry; - goto found_pivot; - } - might_be_apparent_pair = false; - } + + diameter_entry_t coface_entry = + make_diameter_entry(coface_diameter, coface_index, coface_coefficient); + coface_entries.push_back(coface_entry); + + if (might_be_apparent_pair && (simplex_diameter == coface_diameter)) { + if (pivot_column_index.find(coface_index) == pivot_column_index.end()) { + pivot = coface_entry; + goto found_pivot; + } + might_be_apparent_pair = false; + } } } - for (auto e: coface_entries) working_coboundary.push(e); + for (auto e : coface_entries) working_coboundary.push(e); } - + pivot = get_pivot(working_coboundary, modulus); - found_pivot: + found_pivot: if (get_index(pivot) != -1) { auto pair = pivot_column_index.find(get_index(pivot)); |