From 5207236bc6cfacf1789b3eac99360a272a008678 Mon Sep 17 00:00:00 2001 From: fgodi Date: Mon, 23 Apr 2018 16:17:49 +0000 Subject: Lazy ré-ajouté MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@3390 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: f4b2cbaf62e0c43d29f8d52b7df45e62b52f067f --- src/Toplex_map/include/gudhi/Lazy_Toplex_map.h | 236 +++++++++++++++++++++++++ 1 file changed, 236 insertions(+) create mode 100644 src/Toplex_map/include/gudhi/Lazy_Toplex_map.h (limited to 'src/Toplex_map/include/gudhi') 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..481d33a1 --- /dev/null +++ b/src/Toplex_map/include/gudhi/Lazy_Toplex_map.h @@ -0,0 +1,236 @@ +#ifndef LAZY_TOPLEX_MAP_H +#define LAZY_TOPLEX_MAP_H + +#include +#include + +namespace Gudhi { + +class Lazy_Toplex_map { + +public: + + /** Vertex is the type of vertices. + * \ingroup toplex_map */ + typedef Toplex_map::Vertex Vertex; + + /** Simplex is the type of simplices. + * \ingroup toplex_map */ + typedef Toplex_map::Simplex Simplex; + + /** The type of the pointers to maximal simplices. + * \ingroup toplex_map */ + typedef Toplex_map::Simplex_ptr Simplex_ptr; + + /** The type of the sets of Simplex_ptr. + * \ingroup toplex_map */ + typedef Toplex_map::Simplex_ptr_set Simplex_ptr_set; + + template + void insert_max_simplex(const Input_vertex_range &vertex_range); + template + bool insert_simplex(const Input_vertex_range &vertex_range); + template + void remove_simplex(const Input_vertex_range &vertex_range); + + template + bool membership(const Input_vertex_range &vertex_range); + template + bool all_facets_inside(const Input_vertex_range &vertex_range); + + Vertex contraction(const Vertex x, const Vertex y); + + std::size_t num_simplices() const; + + std::unordered_map gamma0_lbounds; + +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 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 = 2; //time + const double betta = 4; //memory +}; + +template +void Lazy_Toplex_map::insert_max_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_max_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 */ +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; + 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 +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; + int max_dim = 0; + for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))){ + if(sptr->size() > max_dim){ + for(int 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(int 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); +} + +std::size_t Lazy_Toplex_map::num_simplices() const{ + return size; +} + +} //namespace Gudhi + +#endif /* LAZY_TOPLEX_MAP_H */ -- cgit v1.2.3