diff options
author | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2018-10-16 13:57:50 +0000 |
---|---|---|
committer | vrouvrea <vrouvrea@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2018-10-16 13:57:50 +0000 |
commit | c71dce7fe646cd4ca4da5f385cb0d97535e4d941 (patch) | |
tree | 237d99233a51b3707d5880a9e81e07280442c31a /src/Toplex_map/include | |
parent | c882b0478d4b0899005bf6c0e9528a1fc8785cf9 (diff) |
Add lazy_toplex_map_unit_test
Class documentation rewrite
Fix conventions in code
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@3956 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: 65f79ee3c0f22157b2cedfc498e5d9c97dd055f6
Diffstat (limited to 'src/Toplex_map/include')
-rw-r--r-- | src/Toplex_map/include/gudhi/Lazy_Toplex_map.h | 123 | ||||
-rw-r--r-- | src/Toplex_map/include/gudhi/Toplex_map.h | 13 |
2 files changed, 70 insertions, 66 deletions
diff --git a/src/Toplex_map/include/gudhi/Lazy_Toplex_map.h b/src/Toplex_map/include/gudhi/Lazy_Toplex_map.h index 434fea47..5461c0a3 100644 --- a/src/Toplex_map/include/gudhi/Lazy_Toplex_map.h +++ b/src/Toplex_map/include/gudhi/Lazy_Toplex_map.h @@ -6,84 +6,90 @@ namespace Gudhi { -/** A Lazy_Toplex_map represents the simplicial complex. - * A "toplex" is a maximal simplex but not all simplices in a LTM are toplices. - * \ingroup toplex_map */ +/** + * \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; - /** Vertex is the type of vertices. */ - typedef Toplex_map::Vertex Vertex; + /** Simplex is the type of simplices. */ + using Simplex = Toplex_map::Simplex; - /** Simplex is the type of simplices. */ - typedef Toplex_map::Simplex Simplex; + /** The type of the pointers to maximal simplices. */ + using Simplex_ptr = Toplex_map::Simplex_ptr; - /** The type of the pointers to maximal simplices. */ - typedef Toplex_map::Simplex_ptr Simplex_ptr; + /** The type of the sets of Simplex_ptr. */ + using Simplex_ptr_set = Toplex_map::Simplex_ptr_set; - /** The type of the sets of Simplex_ptr. */ - typedef Toplex_map::Simplex_ptr_set Simplex_ptr_set; + /** Adds the given simplex to the complex. + * The simplex must not have maximal coface in the complex. */ + template <typename Input_vertex_range> + void insert_independent_simplex(const Input_vertex_range &vertex_range); - /** Adds the given simplex to the complex. - * The simplex must not have maximal coface in the complex. */ - template <typename Input_vertex_range> - 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 <typename Input_vertex_range> + bool insert_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 <typename Input_vertex_range> - 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 <typename Input_vertex_range> + void remove_simplex(const Input_vertex_range &vertex_range); - /** \brief Removes the given simplex and its cofaces from the complex. - * Its faces are kept inside. */ - template <typename Input_vertex_range> - void remove_simplex(const Input_vertex_range &vertex_range); + /** Does a simplex belong to the complex ? */ + template <typename Input_vertex_range> + bool membership(const Input_vertex_range &vertex_range); - /** Does a simplex belong to the complex ? */ - template <typename Input_vertex_range> - bool membership(const Input_vertex_range &vertex_range); + /** Do all the facets of a simplex belong to the complex ? */ + template <typename Input_vertex_range> + bool all_facets_inside(const Input_vertex_range &vertex_range); - /** Do all the facets of a simplex belong to the complex ? */ - template <typename Input_vertex_range> - 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); - /** 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; + /** \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(); } - std::unordered_map<Vertex, std::size_t> gamma0_lbounds; private: - template <typename Input_vertex_range> - void erase_max(const Input_vertex_range &vertex_range); - template <typename Input_vertex_range> - Vertex best_index(const Input_vertex_range &vertex_range); - void clean(const Vertex v); + template <typename Input_vertex_range> + void erase_max(const Input_vertex_range &vertex_range); + template <typename Input_vertex_range> + Vertex best_index(const Input_vertex_range &vertex_range); + void clean(const Vertex v); + + std::unordered_map<Vertex, std::size_t> gamma0_lbounds; - std::unordered_map<Vertex, Simplex_ptr_set> t0; - bool empty_toplex; // Is the empty simplex a toplex ? + std::unordered_map<Vertex, Simplex_ptr_set> t0; + bool empty_toplex; // Is the empty simplex a toplex ? - typedef boost::heap::fibonacci_heap<std::pair<std::size_t,Vertex>> PriorityQueue; - PriorityQueue cleaning_priority; - std::unordered_map<Vertex, PriorityQueue::handle_type> cp_handles; + typedef boost::heap::fibonacci_heap<std::pair<std::size_t,Vertex>> PriorityQueue; + PriorityQueue cleaning_priority; + std::unordered_map<Vertex, PriorityQueue::handle_type> cp_handles; - std::size_t get_gamma0_lbound(const Vertex v) const; + std::size_t get_gamma0_lbound(const Vertex v) const; - std::size_t size_lbound = 0; - std::size_t size = 0; + std::size_t size_lbound = 0; + std::size_t size = 0; - const double alpha = 4; //time - const double betta = 8; //memory + const double ALPHA = 4; //time + const double BETTA = 8; //memory }; template <typename Input_vertex_range> @@ -112,7 +118,7 @@ bool Lazy_Toplex_map::insert_simplex(const Input_vertex_range &vertex_range){ } if(inserted) size++; - if(size > (size_lbound+1) * betta) + if(size > (size_lbound+1) * BETTA) clean(cleaning_priority.top().second); return inserted; } @@ -167,7 +173,7 @@ bool Lazy_Toplex_map::all_facets_inside(const Input_vertex_range &vertex_range){ } /* Returns the remaining vertex */ -Toplex_map::Vertex Lazy_Toplex_map::contraction(const Vertex x, const Vertex y){ +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; @@ -204,14 +210,14 @@ inline void Lazy_Toplex_map::erase_max(const Input_vertex_range &vertex_range){ } template <typename Input_vertex_range> -Toplex_map::Vertex Lazy_Toplex_map::best_index(const Input_vertex_range &vertex_range){ +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<size_t>::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)) + if(min > ALPHA * get_gamma0_lbound(arg_min)) clean(arg_min); return arg_min; } @@ -220,7 +226,6 @@ 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<int, std::vector<Simplex>> dsorted_simplices; @@ -246,10 +251,6 @@ void Lazy_Toplex_map::clean(const Vertex v){ insert_simplex(*sptr); } -std::size_t Lazy_Toplex_map::num_maximal_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 7cde8ea1..b7a5db41 100644 --- a/src/Toplex_map/include/gudhi/Toplex_map.h +++ b/src/Toplex_map/include/gudhi/Toplex_map.h @@ -10,8 +10,11 @@ namespace Gudhi { -/** A Toplex_map represents the simplicial complex. - * A "toplex" is a maximal simplex. +/** + * \brief Toplex map data structure for representing unfiltered simplicial complexes. + * + * \details A Toplex_map is an unordered map from vertices to maximal simplices (aka. toplices). + * * \ingroup toplex_map */ class Toplex_map { @@ -100,7 +103,7 @@ protected: /** \internal The map from vertices to toplices */ std::unordered_map<Toplex_map::Vertex, Toplex_map::Simplex_ptr_set> t0; - const Toplex_map::Vertex vertex_upper_bound = std::numeric_limits<Toplex_map::Vertex>::max(); + const Toplex_map::Vertex VERTEX_UPPER_BOUND = std::numeric_limits<Toplex_map::Vertex>::max(); /** \internal Removes a toplex without adding facets after. */ void erase_maximal(const Toplex_map::Simplex_ptr& sptr); @@ -258,7 +261,7 @@ void Toplex_map::remove_vertex(const Toplex_map::Vertex x){ inline void Toplex_map::erase_maximal(const Toplex_map::Simplex_ptr& sptr){ Simplex sigma(*sptr); if (sptr->size()==0) - sigma.insert(vertex_upper_bound); + sigma.insert(VERTEX_UPPER_BOUND); for(const Toplex_map::Vertex& v : sigma){ t0.at(v).erase(sptr); if(t0.at(v).size()==0) t0.erase(v); @@ -268,7 +271,7 @@ inline void Toplex_map::erase_maximal(const Toplex_map::Simplex_ptr& sptr){ template <typename Input_vertex_range> Toplex_map::Vertex Toplex_map::best_index(const Input_vertex_range &vertex_range) const{ std::size_t min = std::numeric_limits<size_t>::max(); - Vertex arg_min = vertex_upper_bound; + Vertex arg_min = VERTEX_UPPER_BOUND; for(const Toplex_map::Vertex& v : vertex_range) if(!t0.count(v)) return v; else if(t0.at(v).size() < min) |