From 418180d74ea25cfc70a272ab7e883d93ecb31e93 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 16 Oct 2018 14:06:53 +0000 Subject: Rename Lazy_Toplex_map accordingly to code conventions git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@3957 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 7e73d088dbc458f42219e6f7a50baf98d8db65ed --- src/Toplex_map/benchmark/CMakeLists.txt | 2 +- src/Toplex_map/benchmark/benchmark_tm.cpp | 129 +++++++++++ src/Toplex_map/benchmark/chrono.cpp | 129 ----------- src/Toplex_map/example/simple_toplex_map.cpp | 4 +- src/Toplex_map/include/gudhi/Lazy_Toplex_map.h | 256 ---------------------- src/Toplex_map/include/gudhi/Lazy_toplex_map.h | 256 ++++++++++++++++++++++ src/Toplex_map/test/lazy_toplex_map_unit_test.cpp | 6 +- 7 files changed, 391 insertions(+), 391 deletions(-) create mode 100644 src/Toplex_map/benchmark/benchmark_tm.cpp delete mode 100644 src/Toplex_map/benchmark/chrono.cpp delete mode 100644 src/Toplex_map/include/gudhi/Lazy_Toplex_map.h create mode 100644 src/Toplex_map/include/gudhi/Lazy_toplex_map.h (limited to 'src/Toplex_map') diff --git a/src/Toplex_map/benchmark/CMakeLists.txt b/src/Toplex_map/benchmark/CMakeLists.txt index c2f216bc..2d58a156 100644 --- a/src/Toplex_map/benchmark/CMakeLists.txt +++ b/src/Toplex_map/benchmark/CMakeLists.txt @@ -1,3 +1,3 @@ project(Toplex_map_benchmark) -add_executable(toplex_map_chrono chrono.cpp) +add_executable(Toplex_map_benchmark benchmark_tm.cpp) diff --git a/src/Toplex_map/benchmark/benchmark_tm.cpp b/src/Toplex_map/benchmark/benchmark_tm.cpp new file mode 100644 index 00000000..5f13288c --- /dev/null +++ b/src/Toplex_map/benchmark/benchmark_tm.cpp @@ -0,0 +1,129 @@ +#include +#include +#include + +#include +#include +#include + +using namespace Gudhi; + +typedef Toplex_map::Simplex Simplex; +typedef Toplex_map::Vertex Vertex; +typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool; + +class ST_wrapper { + +public: + void insert_simplex(const Simplex& tau) { + /*std::cout << "insert_simplex - " << simplexTree.num_simplices() << " - "; + for (auto v : tau) + std::cout << v << ", "; + std::cout << std::endl; + */ + simplexTree.insert_simplex_and_subfaces(tau); + } + + bool membership(const Simplex& tau) { + return simplexTree.find(tau) != simplexTree.null_simplex(); + } + + Vertex contraction(const Vertex x, const Vertex y) { + // TODO (VR): edge contraction is not yet available for Simplex_tree + return y; + } + + std::size_t num_maximal_simplices() { + return simplexTree.num_simplices(); + } + +private: + Simplex_tree<> simplexTree; + void erase_max(const Simplex& sigma) { + if(membership(sigma)) + simplexTree.remove_maximal_simplex(simplexTree.find(sigma)); + } +}; + + +int n = 300; + +int nb_insert_simplex1 = 3000; +int nb_membership1 = 4000; +int nb_contraction = 300; +int nb_insert_simplex2 = 3000; +int nb_membership2 = 400000; + +Simplex random_simplex(int n, std::size_t d){ + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution dis(1, n); + Simplex s; + while(s.size() < d) + s.insert(dis(gen)); + return s; +} + +std::vector r_vector_simplices(int n, int max_d, int m){ + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution dis(1, max_d); + std::vector v; + for(int i=0; i +void chrono(int n, int d){ + complex_type K; + std::vector simplices_insert_simplex1 = r_vector_simplices(n,d,nb_insert_simplex1); + std::vector simplices_membership1 = r_vector_simplices(n,d,nb_membership1); + std::vector simplices_insert_simplex2 = r_vector_simplices(n - 2*nb_contraction,d,nb_insert_simplex2); + std::vector simplices_membership2 = r_vector_simplices(n - 2*nb_contraction,d,nb_membership2); + std::chrono::time_point start, end; + + for(const Simplex& s : simplices_insert_simplex1) + K.insert_simplex(s); + + for(const Simplex& s : simplices_membership1) + K.membership(s); + + start = std::chrono::system_clock::now(); + for(int i = 1; i<=nb_contraction; i++) + K.contraction(n-2*i,n-2*i-1); + end = std::chrono::system_clock::now(); + auto c3 = std::chrono::duration_cast(end-start).count(); + + start = std::chrono::system_clock::now(); + for(const Simplex& s : simplices_insert_simplex2) + K.insert_simplex(s); + end = std::chrono::system_clock::now(); + auto c1 = std::chrono::duration_cast(end-start).count(); + + start = std::chrono::system_clock::now(); + for(const Simplex& s : simplices_membership2) + K.membership(s); + end = std::chrono::system_clock::now(); + auto c2 = std::chrono::duration_cast(end-start).count(); + + if (c3 > 0) + std::cout << c1 << "\t \t" << c2 << "\t \t" << c3 << "\t \t" << K.num_maximal_simplices() << std::endl; + else + std::cout << c1 << "\t \t" << c2 << "\t \tN/A\t \t" << K.num_maximal_simplices() << std::endl; +} + +int main(){ + for(int d=5;d<=40;d+=5){ + std::cout << "d=" << d << " \t Insertions \t Membership \t Contractions \t Size" << std::endl; + std::cout << "T Map \t \t"; + chrono(n,d); + std::cout << "Lazy \t \t"; + chrono(n,d); + if(d<=15){ + std::cout << "ST \t \t"; + chrono(n,d); + } + std::cout << std::endl; + } +} diff --git a/src/Toplex_map/benchmark/chrono.cpp b/src/Toplex_map/benchmark/chrono.cpp deleted file mode 100644 index e6172c61..00000000 --- a/src/Toplex_map/benchmark/chrono.cpp +++ /dev/null @@ -1,129 +0,0 @@ -#include -#include -#include - -#include -#include -#include - -using namespace Gudhi; - -typedef Toplex_map::Simplex Simplex; -typedef Toplex_map::Vertex Vertex; -typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool; - -class ST_wrapper { - -public: - void insert_simplex(const Simplex& tau) { - /*std::cout << "insert_simplex - " << simplexTree.num_simplices() << " - "; - for (auto v : tau) - std::cout << v << ", "; - std::cout << std::endl; - */ - simplexTree.insert_simplex_and_subfaces(tau); - } - - bool membership(const Simplex& tau) { - return simplexTree.find(tau) != simplexTree.null_simplex(); - } - - Vertex contraction(const Vertex x, const Vertex y) { - // TODO (VR): edge contraction is not yet available for Simplex_tree - return y; - } - - std::size_t num_maximal_simplices() { - return simplexTree.num_simplices(); - } - -private: - Simplex_tree<> simplexTree; - void erase_max(const Simplex& sigma) { - if(membership(sigma)) - simplexTree.remove_maximal_simplex(simplexTree.find(sigma)); - } -}; - - -int n = 300; - -int nb_insert_simplex1 = 3000; -int nb_membership1 = 4000; -int nb_contraction = 300; -int nb_insert_simplex2 = 3000; -int nb_membership2 = 400000; - -Simplex random_simplex(int n, std::size_t d){ - std::random_device rd; - std::mt19937 gen(rd()); - std::uniform_int_distribution dis(1, n); - Simplex s; - while(s.size() < d) - s.insert(dis(gen)); - return s; -} - -std::vector r_vector_simplices(int n, int max_d, int m){ - std::random_device rd; - std::mt19937 gen(rd()); - std::uniform_int_distribution dis(1, max_d); - std::vector v; - for(int i=0; i -void chrono(int n, int d){ - complex_type K; - std::vector simplices_insert_simplex1 = r_vector_simplices(n,d,nb_insert_simplex1); - std::vector simplices_membership1 = r_vector_simplices(n,d,nb_membership1); - std::vector simplices_insert_simplex2 = r_vector_simplices(n - 2*nb_contraction,d,nb_insert_simplex2); - std::vector simplices_membership2 = r_vector_simplices(n - 2*nb_contraction,d,nb_membership2); - std::chrono::time_point start, end; - - for(const Simplex& s : simplices_insert_simplex1) - K.insert_simplex(s); - - for(const Simplex& s : simplices_membership1) - K.membership(s); - - start = std::chrono::system_clock::now(); - for(int i = 1; i<=nb_contraction; i++) - K.contraction(n-2*i,n-2*i-1); - end = std::chrono::system_clock::now(); - auto c3 = std::chrono::duration_cast(end-start).count(); - - start = std::chrono::system_clock::now(); - for(const Simplex& s : simplices_insert_simplex2) - K.insert_simplex(s); - end = std::chrono::system_clock::now(); - auto c1 = std::chrono::duration_cast(end-start).count(); - - start = std::chrono::system_clock::now(); - for(const Simplex& s : simplices_membership2) - K.membership(s); - end = std::chrono::system_clock::now(); - auto c2 = std::chrono::duration_cast(end-start).count(); - - if (c3 > 0) - std::cout << c1 << "\t \t" << c2 << "\t \t" << c3 << "\t \t" << K.num_maximal_simplices() << std::endl; - else - std::cout << c1 << "\t \t" << c2 << "\t \tN/A\t \t" << K.num_maximal_simplices() << std::endl; -} - -int main(){ - for(int d=5;d<=40;d+=5){ - std::cout << "d=" << d << " \t Insertions \t Membership \t Contractions \t Size" << std::endl; - std::cout << "T Map \t \t"; - chrono(n,d); - std::cout << "Lazy \t \t"; - chrono(n,d); - if(d<=15){ - std::cout << "ST \t \t"; - chrono(n,d); - } - std::cout << std::endl; - } -} diff --git a/src/Toplex_map/example/simple_toplex_map.cpp b/src/Toplex_map/example/simple_toplex_map.cpp index 0d80f94e..912d79a0 100644 --- a/src/Toplex_map/example/simple_toplex_map.cpp +++ b/src/Toplex_map/example/simple_toplex_map.cpp @@ -4,7 +4,7 @@ * * Author(s): Vincent Rouvreau * - * Copyright (C) 2017 + * Copyright (C) 2018 * * 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 @@ -20,12 +20,12 @@ * along with this program. If not, see . */ -#include #include #include #include // for pair #include +#include int main(int argc, char * const argv[]) { using Simplex = Gudhi::Toplex_map::Simplex; diff --git a/src/Toplex_map/include/gudhi/Lazy_Toplex_map.h b/src/Toplex_map/include/gudhi/Lazy_Toplex_map.h deleted file mode 100644 index 5461c0a3..00000000 --- a/src/Toplex_map/include/gudhi/Lazy_Toplex_map.h +++ /dev/null @@ -1,256 +0,0 @@ -#ifndef LAZY_TOPLEX_MAP_H -#define LAZY_TOPLEX_MAP_H - -#include -#include - -namespace Gudhi { - -/** - * \brief Lazy toplex map data structure for representing unfiltered simplicial complexes. - * - * \details A Toplex_map is an unordered map from vertices to maximal simplices (aka. toplices). - * The lazy version is not always up to date as it requires clean operation in order to be. - * - * \ingroup toplex_map */ -class Lazy_Toplex_map { - -public: - /** Vertex is the type of vertices. */ - using Vertex = Toplex_map::Vertex; - - /** Simplex is the type of simplices. */ - using Simplex = Toplex_map::Simplex; - - /** The type of the pointers to maximal simplices. */ - using Simplex_ptr = Toplex_map::Simplex_ptr; - - /** The type of the sets of Simplex_ptr. */ - using Simplex_ptr_set = Toplex_map::Simplex_ptr_set; - - /** Adds the given simplex to the complex. - * The simplex must not have maximal coface in the complex. */ - template - void insert_independent_simplex(const Input_vertex_range &vertex_range); - - /** \brief Adds the given simplex to the complex. - * Nothing happens if the simplex has a coface in the complex. */ - template - bool insert_simplex(const Input_vertex_range &vertex_range); - - /** \brief Removes the given simplex and its cofaces from the complex. - * Its faces are kept inside. */ - template - void remove_simplex(const Input_vertex_range &vertex_range); - - /** Does a simplex belong to the complex ? */ - template - bool membership(const Input_vertex_range &vertex_range); - - - /** Do all the facets of a simplex belong to the complex ? */ - template - bool all_facets_inside(const Input_vertex_range &vertex_range); - - /** Contracts one edge in the complex. - * The edge has to verify the link condition if you want to preserve topology. - * Returns the remaining vertex. */ - Vertex contraction(const Vertex x, const Vertex y); - - /** \brief Number of maximal simplices. */ - std::size_t num_maximal_simplices() const { - return size; - } - - /** \brief Number of vertices. */ - std::size_t num_vertices() const{ - return t0.size(); - } - -private: - template - void erase_max(const Input_vertex_range &vertex_range); - template - Vertex best_index(const Input_vertex_range &vertex_range); - void clean(const Vertex v); - - std::unordered_map gamma0_lbounds; - - std::unordered_map t0; - bool empty_toplex; // Is the empty simplex a toplex ? - - typedef boost::heap::fibonacci_heap> PriorityQueue; - PriorityQueue cleaning_priority; - std::unordered_map cp_handles; - - std::size_t get_gamma0_lbound(const Vertex v) const; - - std::size_t size_lbound = 0; - std::size_t size = 0; - - const double ALPHA = 4; //time - const double BETTA = 8; //memory -}; - -template -void Lazy_Toplex_map::insert_independent_simplex(const Input_vertex_range &vertex_range){ - for(const Vertex& v : vertex_range) - if(!gamma0_lbounds.count(v)) gamma0_lbounds.emplace(v,1); - else gamma0_lbounds[v]++; - size_lbound++; - insert_simplex(vertex_range); -} - -template -bool Lazy_Toplex_map::insert_simplex(const Input_vertex_range &vertex_range){ - Simplex sigma(vertex_range.begin(),vertex_range.end()); - empty_toplex = (sigma.size()==0); //vérifier la gestion de empty face - Simplex_ptr sptr = std::make_shared(sigma); - bool inserted = false; - for(const Vertex& v : sigma){ - if(!t0.count(v)){ - t0.emplace(v, Simplex_ptr_set()); - auto v_handle = cleaning_priority.push(std::make_pair(0, v)); - cp_handles.emplace(v, v_handle); - } - inserted = t0.at(v).emplace(sptr).second; - cleaning_priority.update(cp_handles.at(v), std::make_pair(t0.at(v).size() - get_gamma0_lbound(v),v)); - } - if(inserted) - size++; - if(size > (size_lbound+1) * BETTA) - clean(cleaning_priority.top().second); - return inserted; -} - -template -void Lazy_Toplex_map::remove_simplex(const Input_vertex_range &vertex_range){ - if(vertex_range.begin()==vertex_range.end()){ - t0.clear(); - gamma0_lbounds.clear(); - cleaning_priority.clear(); - size_lbound = 0; - size = 0; - empty_toplex = false; - } - else { - const Vertex& v = best_index(vertex_range); - //Copy constructor needed because the set is modified - if(t0.count(v)) for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))) - if(included(vertex_range, *sptr)){ - erase_max(*sptr); - for(const Simplex& f : facets(vertex_range)) - insert_independent_simplex(f); - } - } -} - -template -bool Lazy_Toplex_map::membership(const Input_vertex_range &vertex_range){ - if(t0.size()==0 && !empty_toplex) return false; //empty complex - if(vertex_range.begin()==vertex_range.end()) return true; //empty query simplex - Vertex v = best_index(vertex_range); - if(!t0.count(v)) return false; - for(const Simplex_ptr& sptr : t0.at(v)) - if(included(vertex_range, *sptr)) return true; - return false; -} - -template -bool Lazy_Toplex_map::all_facets_inside(const Input_vertex_range &vertex_range){ - Simplex sigma(vertex_range.begin(),vertex_range.end()); - Vertex v = best_index(sigma); - if(!t0.count(v)) return false; - Simplex f = sigma; f.erase(v); - if(!membership(f)) return false; - std::unordered_set facets_inside; - for(const Simplex_ptr& sptr : t0.at(v)) - for(const Vertex& w : sigma){ - f = sigma; f.erase(w); - if(included(f, *sptr)) facets_inside.insert(w); - } - return facets_inside.size() == sigma.size() - 1; -} - -/* Returns the remaining vertex */ -Lazy_Toplex_map::Vertex Lazy_Toplex_map::contraction(const Vertex x, const Vertex y){ - if(!t0.count(x)) return y; - if(!t0.count(y)) return x; - Vertex k, d; - if(t0.at(x).size() > t0.at(y).size()) - k=x, d=y; - else - k=y, d=x; - //Copy constructor needed because the set is modified - for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))){ - Simplex sigma(*sptr); - erase_max(sigma); - sigma.erase(d); - sigma.insert(k); - insert_simplex(sigma); - } - t0.erase(d); - return k; -} - -/* No facets insert_simplexed */ -template -inline void Lazy_Toplex_map::erase_max(const Input_vertex_range &vertex_range){ - Simplex sigma(vertex_range.begin(),vertex_range.end()); - empty_toplex = false; - Simplex_ptr sptr = std::make_shared(sigma); - bool erased=false; - for(const Vertex& v : sigma){ - erased = t0.at(v).erase(sptr) > 0; - if(t0.at(v).size()==0) - t0.erase(v); - } - if (erased) - size--; -} - -template -Lazy_Toplex_map::Vertex Lazy_Toplex_map::best_index(const Input_vertex_range &vertex_range) { - Simplex tau(vertex_range.begin(),vertex_range.end()); - std::size_t min = std::numeric_limits::max(); Vertex arg_min = -1; - for(const Vertex& v : tau) - if(!t0.count(v)) return v; - else if(t0.at(v).size() < min) - min = t0.at(v).size(), arg_min = v; - if(min > ALPHA * get_gamma0_lbound(arg_min)) - clean(arg_min); - return arg_min; -} - -std::size_t Lazy_Toplex_map::get_gamma0_lbound(const Vertex v) const{ - return gamma0_lbounds.count(v) ? gamma0_lbounds.at(v) : 0; -} - -void Lazy_Toplex_map::clean(const Vertex v){ - Toplex_map toplices; - std::unordered_map> dsorted_simplices; - std::size_t max_dim = 0; - for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))){ - if(sptr->size() > max_dim){ - for(std::size_t d = max_dim+1; d<=sptr->size(); d++) - dsorted_simplices.emplace(d, std::vector()); - max_dim = sptr->size(); - } - dsorted_simplices[sptr->size()].emplace_back(*sptr); - erase_max(*sptr); - } - for(std::size_t d = max_dim; d>=1; d--) - for(const Simplex &s : dsorted_simplices.at(d)) - if(!toplices.membership(s)) - toplices.insert_independent_simplex(s); - Simplex sv; sv.insert(v); - auto clean_cofaces = toplices.maximal_cofaces(sv); - size_lbound = size_lbound - get_gamma0_lbound(v) + clean_cofaces.size(); - gamma0_lbounds[v] = clean_cofaces.size(); - for(const Simplex_ptr& sptr : clean_cofaces) - insert_simplex(*sptr); -} - -} //namespace Gudhi - -#endif /* LAZY_TOPLEX_MAP_H */ diff --git a/src/Toplex_map/include/gudhi/Lazy_toplex_map.h b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h new file mode 100644 index 00000000..8cc5610a --- /dev/null +++ b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h @@ -0,0 +1,256 @@ +#ifndef LAZY_TOPLEX_MAP_H +#define LAZY_TOPLEX_MAP_H + +#include +#include + +namespace Gudhi { + +/** + * \brief Lazy toplex map data structure for representing unfiltered simplicial complexes. + * + * \details A Toplex_map is an unordered map from vertices to maximal simplices (aka. toplices). + * The lazy version is not always up to date as it requires clean operation in order to be. + * + * \ingroup toplex_map */ +class Lazy_toplex_map { + +public: + /** Vertex is the type of vertices. */ + using Vertex = Toplex_map::Vertex; + + /** Simplex is the type of simplices. */ + using Simplex = Toplex_map::Simplex; + + /** The type of the pointers to maximal simplices. */ + using Simplex_ptr = Toplex_map::Simplex_ptr; + + /** The type of the sets of Simplex_ptr. */ + using Simplex_ptr_set = Toplex_map::Simplex_ptr_set; + + /** Adds the given simplex to the complex. + * The simplex must not have maximal coface in the complex. */ + template + void insert_independent_simplex(const Input_vertex_range &vertex_range); + + /** \brief Adds the given simplex to the complex. + * Nothing happens if the simplex has a coface in the complex. */ + template + bool insert_simplex(const Input_vertex_range &vertex_range); + + /** \brief Removes the given simplex and its cofaces from the complex. + * Its faces are kept inside. */ + template + void remove_simplex(const Input_vertex_range &vertex_range); + + /** Does a simplex belong to the complex ? */ + template + bool membership(const Input_vertex_range &vertex_range); + + + /** Do all the facets of a simplex belong to the complex ? */ + template + bool all_facets_inside(const Input_vertex_range &vertex_range); + + /** Contracts one edge in the complex. + * The edge has to verify the link condition if you want to preserve topology. + * Returns the remaining vertex. */ + Vertex contraction(const Vertex x, const Vertex y); + + /** \brief Number of maximal simplices. */ + std::size_t num_maximal_simplices() const { + return size; + } + + /** \brief Number of vertices. */ + std::size_t num_vertices() const{ + return t0.size(); + } + +private: + template + void erase_max(const Input_vertex_range &vertex_range); + template + Vertex best_index(const Input_vertex_range &vertex_range); + void clean(const Vertex v); + + std::unordered_map gamma0_lbounds; + + std::unordered_map t0; + bool empty_toplex; // Is the empty simplex a toplex ? + + typedef boost::heap::fibonacci_heap> PriorityQueue; + PriorityQueue cleaning_priority; + std::unordered_map cp_handles; + + std::size_t get_gamma0_lbound(const Vertex v) const; + + std::size_t size_lbound = 0; + std::size_t size = 0; + + const double ALPHA = 4; //time + const double BETTA = 8; //memory +}; + +template +void Lazy_toplex_map::insert_independent_simplex(const Input_vertex_range &vertex_range){ + for(const Vertex& v : vertex_range) + if(!gamma0_lbounds.count(v)) gamma0_lbounds.emplace(v,1); + else gamma0_lbounds[v]++; + size_lbound++; + insert_simplex(vertex_range); +} + +template +bool Lazy_toplex_map::insert_simplex(const Input_vertex_range &vertex_range){ + Simplex sigma(vertex_range.begin(),vertex_range.end()); + empty_toplex = (sigma.size()==0); //vérifier la gestion de empty face + Simplex_ptr sptr = std::make_shared(sigma); + bool inserted = false; + for(const Vertex& v : sigma){ + if(!t0.count(v)){ + t0.emplace(v, Simplex_ptr_set()); + auto v_handle = cleaning_priority.push(std::make_pair(0, v)); + cp_handles.emplace(v, v_handle); + } + inserted = t0.at(v).emplace(sptr).second; + cleaning_priority.update(cp_handles.at(v), std::make_pair(t0.at(v).size() - get_gamma0_lbound(v),v)); + } + if(inserted) + size++; + if(size > (size_lbound+1) * BETTA) + clean(cleaning_priority.top().second); + return inserted; +} + +template +void Lazy_toplex_map::remove_simplex(const Input_vertex_range &vertex_range){ + if(vertex_range.begin()==vertex_range.end()){ + t0.clear(); + gamma0_lbounds.clear(); + cleaning_priority.clear(); + size_lbound = 0; + size = 0; + empty_toplex = false; + } + else { + const Vertex& v = best_index(vertex_range); + //Copy constructor needed because the set is modified + if(t0.count(v)) for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))) + if(included(vertex_range, *sptr)){ + erase_max(*sptr); + for(const Simplex& f : facets(vertex_range)) + insert_independent_simplex(f); + } + } +} + +template +bool Lazy_toplex_map::membership(const Input_vertex_range &vertex_range){ + if(t0.size()==0 && !empty_toplex) return false; //empty complex + if(vertex_range.begin()==vertex_range.end()) return true; //empty query simplex + Vertex v = best_index(vertex_range); + if(!t0.count(v)) return false; + for(const Simplex_ptr& sptr : t0.at(v)) + if(included(vertex_range, *sptr)) return true; + return false; +} + +template +bool Lazy_toplex_map::all_facets_inside(const Input_vertex_range &vertex_range){ + Simplex sigma(vertex_range.begin(),vertex_range.end()); + Vertex v = best_index(sigma); + if(!t0.count(v)) return false; + Simplex f = sigma; f.erase(v); + if(!membership(f)) return false; + std::unordered_set facets_inside; + for(const Simplex_ptr& sptr : t0.at(v)) + for(const Vertex& w : sigma){ + f = sigma; f.erase(w); + if(included(f, *sptr)) facets_inside.insert(w); + } + return facets_inside.size() == sigma.size() - 1; +} + +/* Returns the remaining vertex */ +Lazy_toplex_map::Vertex Lazy_toplex_map::contraction(const Vertex x, const Vertex y){ + if(!t0.count(x)) return y; + if(!t0.count(y)) return x; + Vertex k, d; + if(t0.at(x).size() > t0.at(y).size()) + k=x, d=y; + else + k=y, d=x; + //Copy constructor needed because the set is modified + for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))){ + Simplex sigma(*sptr); + erase_max(sigma); + sigma.erase(d); + sigma.insert(k); + insert_simplex(sigma); + } + t0.erase(d); + return k; +} + +/* No facets insert_simplexed */ +template +inline void Lazy_toplex_map::erase_max(const Input_vertex_range &vertex_range){ + Simplex sigma(vertex_range.begin(),vertex_range.end()); + empty_toplex = false; + Simplex_ptr sptr = std::make_shared(sigma); + bool erased=false; + for(const Vertex& v : sigma){ + erased = t0.at(v).erase(sptr) > 0; + if(t0.at(v).size()==0) + t0.erase(v); + } + if (erased) + size--; +} + +template +Lazy_toplex_map::Vertex Lazy_toplex_map::best_index(const Input_vertex_range &vertex_range) { + Simplex tau(vertex_range.begin(),vertex_range.end()); + std::size_t min = std::numeric_limits::max(); Vertex arg_min = -1; + for(const Vertex& v : tau) + if(!t0.count(v)) return v; + else if(t0.at(v).size() < min) + min = t0.at(v).size(), arg_min = v; + if(min > ALPHA * get_gamma0_lbound(arg_min)) + clean(arg_min); + return arg_min; +} + +std::size_t Lazy_toplex_map::get_gamma0_lbound(const Vertex v) const{ + return gamma0_lbounds.count(v) ? gamma0_lbounds.at(v) : 0; +} + +void Lazy_toplex_map::clean(const Vertex v){ + Toplex_map toplices; + std::unordered_map> dsorted_simplices; + std::size_t max_dim = 0; + for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))){ + if(sptr->size() > max_dim){ + for(std::size_t d = max_dim+1; d<=sptr->size(); d++) + dsorted_simplices.emplace(d, std::vector()); + max_dim = sptr->size(); + } + dsorted_simplices[sptr->size()].emplace_back(*sptr); + erase_max(*sptr); + } + for(std::size_t d = max_dim; d>=1; d--) + for(const Simplex &s : dsorted_simplices.at(d)) + if(!toplices.membership(s)) + toplices.insert_independent_simplex(s); + Simplex sv; sv.insert(v); + auto clean_cofaces = toplices.maximal_cofaces(sv); + size_lbound = size_lbound - get_gamma0_lbound(v) + clean_cofaces.size(); + gamma0_lbounds[v] = clean_cofaces.size(); + for(const Simplex_ptr& sptr : clean_cofaces) + insert_simplex(*sptr); +} + +} //namespace Gudhi + +#endif /* LAZY_TOPLEX_MAP_H */ diff --git a/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp b/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp index 77d464ae..5d71c295 100644 --- a/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp +++ b/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp @@ -1,6 +1,6 @@ #include #include -#include +#include #define BOOST_TEST_DYN_LINK @@ -8,9 +8,9 @@ #include BOOST_AUTO_TEST_CASE(toplex_map) { - using Vertex = Gudhi::Lazy_Toplex_map::Vertex; + using Vertex = Gudhi::Lazy_toplex_map::Vertex; - Gudhi::Lazy_Toplex_map tm; + Gudhi::Lazy_toplex_map tm; std::cout << "insert_simplex {1, 2, 3, 4}" << std::endl; std::vector sigma1 = {1, 2, 3, 4}; tm.insert_simplex(sigma1); -- cgit v1.2.3