From 6f4c7c0177b6ccf88b61056ea9d2ae2b066e056a Mon Sep 17 00:00:00 2001 From: fgodi Date: Thu, 23 Nov 2017 17:18:13 +0000 Subject: 3 files - 3 docs git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@2945 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: ce6663f33da653f2ac520b4d0f3684b4776aec94 --- src/Toplex_map/include/gudhi/Fake_simplex_tree.h | 53 ++++- src/Toplex_map/include/gudhi/Filtered_toplex_map.h | 28 +++ src/Toplex_map/include/gudhi/Lazy_toplex_map.h | 218 --------------------- src/Toplex_map/include/gudhi/Toplex_map.h | 42 ++-- 4 files changed, 98 insertions(+), 243 deletions(-) delete mode 100644 src/Toplex_map/include/gudhi/Lazy_toplex_map.h (limited to 'src/Toplex_map') diff --git a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h index 3de962af..8876b56d 100644 --- a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h +++ b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h @@ -25,39 +25,78 @@ struct Visitor { } }; +/** Fake_simplex_tree is a wrapper for Filtered_toplex_map which has the interface of the Simplex_tree. + * Mostly for retro-compatibility purpose. If you use a function that output non maximal simplices, it will be non efficient. + * \ingroup toplex_map */ class Fake_simplex_tree : public Filtered_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; + /** Handle type to a vertex contained in the simplicial complex. + * \ingroup toplex_map */ typedef Vertex Vertex_handle; + /** Handle type to a simplex contained in the simplicial complex. + * \ingroup toplex_map */ typedef Simplex Simplex_handle; typedef void Insertion_result_type; - /** \brief Inserts the flag complex of a given range `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph` in the simplicial - * complex. */ + /** Inserts the flag complex of a given range `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph` + * in the simplicial complex. + * \ingroup toplex_map */ template void insert_graph(const OneSkeletonGraph& skel_graph); - /** \brief Do nothing */ + /** Do actually nothing. + * \ingroup toplex_map */ void expansion(int max_dim); - /** \brief Returns the number of vertices stored i.e. the number of max simplices */ + /** Returns the number of vertices stored i.e. the number of max simplices + * \ingroup toplex_map */ std::size_t num_vertices() const; + /** Returns the dimension of the complex. + * \ingroup toplex_map */ std::size_t dimension() const; + /** Returns the dimension of a given simplex in the complex. + * \ingroup toplex_map */ std::size_t dimension(Simplex_ptr& sptr) const; + /** Returns the number of simplices stored i.e. the number of maximal simplices. + * \ingroup toplex_map */ std::size_t num_simplices() const; + /** Returns a range over the vertices of a simplex. + * \ingroup toplex_map */ Simplex simplex_vertex_range(const Simplex& s) const; + /** Returns a set of all maximal (critical if there is filtration values) simplices. + * \ingroup toplex_map */ std::vector max_simplices() const; + /** Returns all the simplices, of max dimension d if a parameter d is given. + * \ingroup toplex_map */ std::vector filtration_simplex_range(int d=std::numeric_limits::max()) const; + /** Returns all the simplices of max dimension d + * \ingroup toplex_map */ std::vector skeleton_simplex_range(int d) const; @@ -73,6 +112,12 @@ protected: template void Fake_simplex_tree::insert_graph(const OneSkeletonGraph& skel_graph){ toplex_maps.emplace(nan(""),Toplex_map()); + using vertex_iterator = typename boost::graph_traits::vertex_iterator; + vertex_iterator vi, vi_end; + for (std::tie(vi, vi_end) = boost::vertices(skel_graph); vi != vi_end; ++vi) { + Simplex s; s.insert(*vi); + insert_simplex_and_subfaces(s); + } bron_kerbosch_all_cliques(skel_graph, Visitor(&(this->toplex_maps.at(nan(""))))); } diff --git a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h index a0c24304..28814d15 100644 --- a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h +++ b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h @@ -7,17 +7,45 @@ namespace Gudhi { +/** A Filtered_toplex_map represents the simplicial complex with a filtration. + * A "toplex" is a critical simplex. + * \ingroup toplex_map */ class Filtered_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; + + /** The type of the filtration values. + * \ingroup toplex_map */ typedef double Filtration_value; + /** Add a simplex and its subfaces with the given filtration value + * in the Filtered_toplex_map. + * \ingroup toplex_map */ template std::pair insert_simplex_and_subfaces(const Input_vertex_range &vertex_range, Filtration_value f = nan("")); + /** Gives the filtration of the input simplex. + * \ingroup toplex_map */ template Filtration_value filtration(const Input_vertex_range &vertex_range) const; + /** Is the input simplex member of the complex ? + * \ingroup toplex_map */ template bool membership(const Input_vertex_range &vertex_range) const; 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 3ffe8214..00000000 --- a/src/Toplex_map/include/gudhi/Lazy_toplex_map.h +++ /dev/null @@ -1,218 +0,0 @@ -#ifndef LAZY_TOPLEX_MAP_H -#define LAZY_TOPLEX_MAP_H - -#include -#include - -namespace Gudhi { - -class Lazy_Toplex_map { - -public: - 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; - -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::unordered_map gamma0_lbounds; - 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 = 3; //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 * 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 */ -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 -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 */ diff --git a/src/Toplex_map/include/gudhi/Toplex_map.h b/src/Toplex_map/include/gudhi/Toplex_map.h index 9de3a6be..b433f3de 100644 --- a/src/Toplex_map/include/gudhi/Toplex_map.h +++ b/src/Toplex_map/include/gudhi/Toplex_map.h @@ -11,30 +11,31 @@ namespace Gudhi { -/** Vertex is the type of vertices. - * \ingroup toplex_map */ -typedef std::size_t Vertex; - -/** Simplex is the type of simplices. - * \ingroup toplex_map */ -typedef std::unordered_set Simplex; - -/** The type of the pointers to maximal simplices. - * \ingroup toplex_map */ -typedef std::shared_ptr Simplex_ptr; - -struct Sptr_hash{ std::size_t operator()(const Simplex_ptr& s) const; }; -struct Sptr_equal{ std::size_t operator()(const Simplex_ptr& a, const Simplex_ptr& b) const; }; -/** The type of the sets of Simplex_ptr. - * \ingroup toplex_map */ -typedef std::unordered_set Simplex_ptr_set; - /** A Toplex_map represents the simplicial complex. * A "toplex" is a maximal simplex. * \ingroup toplex_map */ class Toplex_map { public: + + /** Vertex is the type of vertices. + * \ingroup toplex_map */ + typedef std::size_t Vertex; + + /** Simplex is the type of simplices. + * \ingroup toplex_map */ + typedef std::unordered_set Simplex; + + /** The type of the pointers to maximal simplices. + * \ingroup toplex_map */ + typedef std::shared_ptr Simplex_ptr; + + struct Sptr_hash{ std::size_t operator()(const Simplex_ptr& s) const; }; + struct Sptr_equal{ std::size_t operator()(const Simplex_ptr& a, const Simplex_ptr& b) const; }; + /** The type of the sets of Simplex_ptr. + * \ingroup toplex_map */ + typedef std::unordered_set Simplex_ptr_set; + /** \brief Adds the given simplex to the complex. * Nothing happens if the simplex has a coface in the complex. * \ingroup toplex_map */ @@ -58,7 +59,7 @@ public: bool maximality(const Input_vertex_range &vertex_range) const; /** Gives a set of pointers to the maximal cofaces of a simplex. - * Gives the toplices if given the empty simplex. + * Gives all the toplices if given the empty simplex. * Gives not more than max_number maximal cofaces if max_number is strictly positive. * \ingroup toplex_map */ template @@ -85,8 +86,7 @@ public: void remove_vertex(const Vertex x); /** \brief Number of maximal simplices. - * /!\ Not efficient ! - * \ingroup toplex_map */ + * \ingroup toplex_map */ std::size_t num_simplices() const; protected: -- cgit v1.2.3