diff options
author | fgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-10-25 11:19:00 +0000 |
---|---|---|
committer | fgodi <fgodi@636b058d-ea47-450e-bf9e-a15bfbe3eedb> | 2017-10-25 11:19:00 +0000 |
commit | 23e265d8c48d921a51eb0265afa6d8af27b27559 (patch) | |
tree | f008c1dc24209204ede4b69386f6bf56513a72c2 /src/Toplex_map | |
parent | 8fd07bda067d82fd0d345c3bde0dce7de18a6722 (diff) |
include limits in toplex_map
git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@2804 636b058d-ea47-450e-bf9e-a15bfbe3eedb
Former-commit-id: a42cc7c557c193c57e3696eb0b877f6196841aaf
Diffstat (limited to 'src/Toplex_map')
-rw-r--r-- | src/Toplex_map/include/gudhi/Fake_simplex_tree.h | 142 | ||||
-rw-r--r-- | src/Toplex_map/include/gudhi/Filtered_toplex_map.h | 8 | ||||
-rw-r--r-- | src/Toplex_map/include/gudhi/Toplex_map.h | 30 |
3 files changed, 80 insertions, 100 deletions
diff --git a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h index 10ef39d7..b318acb4 100644 --- a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h +++ b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h @@ -1,9 +1,12 @@ #ifndef FAKE_SIMPLEX_TREE_H #define FAKE_SIMPLEX_TREE_H +#include <gudhi/Simplex_tree.h> #include <gudhi/Filtered_toplex_map.h> + #include <boost/graph/adjacency_list.hpp> + namespace Gudhi { class Fake_simplex_tree : public Filtered_toplex_map { @@ -12,7 +15,7 @@ public: typedef Vertex Vertex_handle; - typedef Simplex_ptr Simplex_handle; + typedef Simplex Simplex_handle; typedef void Insertion_result_type; @@ -36,20 +39,16 @@ public: void set_dimension(int d); - Simplex simplex_vertex_range(Simplex_ptr &sptr) const; + Simplex simplex_vertex_range(const Simplex& s) const; - std::vector<Simplex_ptr> max_simplices() const; + std::vector<Simplex> max_simplices() const; - std::unordered_set<Simplex_ptr> filtration_simplex_range() const; + std::vector<Simplex> filtration_simplex_range() const; - std::unordered_set<Simplex_ptr> skeleton_simplex_range(int d=std::numeric_limits<int>::max()) const; + std::vector<Simplex> skeleton_simplex_range(int d=std::numeric_limits<int>::max()) const; std::size_t dimension(Simplex_ptr& sptr) const; - void assign_filtration(Simplex_ptr& f_simplex, Filtration_value alpha_complex_filtration); - - void make_filtration_non_decreasing(); - protected: /** \internal Does all the facets of the given simplex belong to the complex ? @@ -65,28 +64,34 @@ void Fake_simplex_tree::set_dimension(int d){ template<class OneSkeletonGraph> void Fake_simplex_tree::insert_graph(const OneSkeletonGraph& skel_graph){ - typename boost::graph_traits<OneSkeletonGraph>::edge_iterator e_it, - e_it_end; + if (boost::num_vertices(skel_graph) == 0) return; + typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator v_it, v_it_end; + for (std::tie(v_it, v_it_end) = boost::vertices(skel_graph); v_it != v_it_end; ++v_it){ + Simplex s; + s.insert(*v_it); + insert_simplex_and_subfaces(s, boost::get(vertex_filtration_t(), skel_graph, *v_it)); + } + + typename boost::graph_traits<OneSkeletonGraph>::edge_iterator e_it, e_it_end; for (std::tie(e_it, e_it_end) = boost::edges(skel_graph); e_it != e_it_end; ++e_it) { - auto u = source(*e_it, skel_graph); - auto v = target(*e_it, skel_graph); - if(u<v){ + Vertex u = source(*e_it, skel_graph); + Vertex v = target(*e_it, skel_graph); + if (u < v) { Simplex s; - s.emplace(u); - s.emplace(v); - insert_simplex_and_subfaces(s); + s.insert(u); + s.insert(v); + insert_simplex_and_subfaces(s, boost::get(edge_filtration_t(), skel_graph, *e_it)); } } } void Fake_simplex_tree::expansion(int max_dim){ - for(int d=3; d <= max_dim; d++){ - auto cs = candidates(); + for(int d=2; d <= max_dim; d++){ + Simplex_ptr_set cs = candidates(); //dimension ? + if(cs.empty()) std::cout << d << std::endl; if(cs.empty()) return; - for(const Simplex_ptr& sptr: cs){ - Simplex sigma = *sptr; - insert_simplex_and_subfaces(sigma); - } + for(const Simplex_ptr& sptr: cs) + insert_simplex_and_subfaces(*sptr); //filtration ? } } @@ -100,16 +105,18 @@ bool Fake_simplex_tree::all_facets_inside(const Input_vertex_range &vertex_range Simplex_ptr_set Fake_simplex_tree::candidates() const{ Simplex_ptr_set c; - std::unordered_map<Simplex_ptr, std::vector<Vertex>, Toplex_map::Sptr_hash, Toplex_map::Sptr_equal> facets_to_max; + std::unordered_map<Simplex_ptr, std::vector<Vertex>, Sptr_hash, Sptr_equal> facets_to_max; for(const auto& kv : filtrations){ Simplex sigma (*(kv.first)); - for(Vertex v : sigma){ - sigma.erase(v); - auto sptr = get_key(sigma); - if(!facets_to_max.count(sptr)) facets_to_max.emplace(sptr, std::vector<Vertex>()); - facets_to_max.at(sptr).emplace_back(v); - sigma.insert(v); - } + if(sigma.size()>1) + for(Vertex v : *(kv.first)){ + sigma.erase(v); + auto sptr = get_key(sigma); + if(!facets_to_max.count(sptr)) + facets_to_max.emplace(sptr, std::vector<Vertex>()); + facets_to_max.at(sptr).emplace_back(v); + sigma.insert(v); + } } for(const auto& kv : facets_to_max){ std::unordered_set<Vertex> facets(kv.second.begin(), kv.second.end()); @@ -132,11 +139,12 @@ std::size_t Fake_simplex_tree::dimension() const { std::size_t max = 0; for(auto kv : filtrations) max = std::max(max, kv.first->size()); - return max; + return max-1; } std::size_t Fake_simplex_tree::num_simplices() const { - return filtration_simplex_range().size(); + //return filtration_simplex_range().size(); + return max_simplices().size(); } std::size_t Fake_simplex_tree::num_vertices() const { @@ -147,42 +155,40 @@ std::size_t Fake_simplex_tree::num_vertices() const { return vertices.size(); } -Simplex Fake_simplex_tree::simplex_vertex_range(Simplex_ptr& sptr) const { - return *sptr; +Simplex Fake_simplex_tree::simplex_vertex_range(const Simplex& s) const { + return s; } -std::unordered_set<Simplex_ptr> Fake_simplex_tree::filtration_simplex_range() const{ - std::vector<Simplex_ptr> m = max_simplices(); - std::cout << m.size()<< std::endl; - std::cout << m.size()<< std::endl; - - std::cout << m.size()<< std::endl; - - std::unordered_set<Simplex_ptr> seen; +std::vector<Simplex> Fake_simplex_tree::filtration_simplex_range() const{ + std::vector<Simplex> m = max_simplices(); + std::vector<Simplex> seen1; + Simplex_ptr_set seen2; while(m.begin()!=m.end()){ - Simplex_ptr& sptr = m.back(); + Simplex s(m.back()); m.pop_back(); - if(seen.find(sptr)!=seen.end()){ - seen.emplace(sptr); - for(Simplex& sigma : facets(*sptr)) - m.emplace_back(get_key(sigma)); + if(seen2.find(get_key(s))==seen2.end()){ + seen1.emplace_back(s); + seen2.emplace(get_key(s)); + if(s.size()>0) + for(Simplex& sigma : facets(s)) + m.emplace_back(sigma); } } - return seen; + return seen1; } -std::unordered_set<Simplex_ptr> Fake_simplex_tree::skeleton_simplex_range(int d) const{ - std::unordered_set<Simplex_ptr> simplices; - for(auto sptr: filtration_simplex_range()) - if(sptr->size()<=d) - simplices.emplace(sptr); +std::vector<Simplex> Fake_simplex_tree::skeleton_simplex_range(int d) const{ + std::vector<Simplex> simplices; + for(auto s: filtration_simplex_range()) + if(s.size()<=d) + simplices.emplace_back(s); return simplices; } -std::vector<Simplex_ptr> Fake_simplex_tree::max_simplices() const{ - std::vector<Simplex_ptr> s; +std::vector<Simplex> Fake_simplex_tree::max_simplices() const{ + std::vector<Simplex> s; for(auto kv : filtrations) - s.emplace_back(kv.first); + s.emplace_back(*(kv.first)); return s; } @@ -190,28 +196,6 @@ std::size_t Fake_simplex_tree::dimension(Simplex_ptr& sptr) const{ return sptr->size(); } - -void Fake_simplex_tree::assign_filtration(Simplex_ptr& f_simplex, Filtration_value alpha_complex_filtration){ - filtrations.emplace(f_simplex,alpha_complex_filtration); -} - -void Fake_simplex_tree::make_filtration_non_decreasing(){ - for(auto yt = filtrations.begin(); yt != filtrations.end(); ++yt) - for (auto it = toplex_maps.begin(); it != toplex_maps.end(); ++it){ - if(it->first == yt -> second) - break; - if(it->second.membership(*(yt->first))) - for(const Simplex_ptr& sptr : it->second.maximal_cofaces(*(yt->first))){ - it->second.erase_maximal(sptr); - toplex_maps.at(yt->second).insert_simplex(*sptr); - filtrations.emplace(sptr,yt->second); - } - } - -} - - - } //namespace Gudhi #endif /* FAKE_SIMPLEX_TREE_H */ diff --git a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h index 4b626f11..6d89c062 100644 --- a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h +++ b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h @@ -8,11 +8,11 @@ namespace Gudhi { -typedef double Filtration_value; - class Filtered_toplex_map { public: + typedef double Filtration_value; + template <typename Input_vertex_range> void insert_simplex_and_subfaces(const Input_vertex_range &vertex_range, Filtration_value f = filtration_upper_bound); @@ -21,7 +21,7 @@ public: protected: std::unordered_map<Filtration_value, Toplex_map> toplex_maps; - std::unordered_map<Simplex_ptr, Filtration_value> filtrations; + std::unordered_map<Simplex_ptr, Filtration_value, Sptr_hash, Sptr_equal> filtrations; }; @@ -33,7 +33,7 @@ void Filtered_toplex_map::insert_simplex_and_subfaces(const Input_vertex_range & } template <typename Input_vertex_range> -Filtration_value Filtered_toplex_map::filtration(const Input_vertex_range &vertex_range) const{ +Filtered_toplex_map::Filtration_value Filtered_toplex_map::filtration(const Input_vertex_range &vertex_range) const{ for(auto kv : toplex_maps) if(kv.second.membership(vertex_range)) return kv.first; diff --git a/src/Toplex_map/include/gudhi/Toplex_map.h b/src/Toplex_map/include/gudhi/Toplex_map.h index 0b6cad37..9de3a6be 100644 --- a/src/Toplex_map/include/gudhi/Toplex_map.h +++ b/src/Toplex_map/include/gudhi/Toplex_map.h @@ -5,6 +5,7 @@ #include <unordered_set> #include <unordered_map> #include <memory> +#include <limits> #define vertex_upper_bound std::numeric_limits<Vertex>::max() @@ -18,22 +19,22 @@ typedef std::size_t Vertex; * \ingroup toplex_map */ typedef std::unordered_set<Vertex> Simplex; +/** The type of the pointers to maximal simplices. + * \ingroup toplex_map */ +typedef std::shared_ptr<Simplex> 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, Sptr_hash, Sptr_equal> Simplex_ptr_set; + /** A Toplex_map represents the simplicial complex. * A "toplex" is a maximal simplex. * \ingroup toplex_map */ class Toplex_map { public: - /** The type of the pointers to maximal simplices. - * \ingroup toplex_map */ - typedef std::shared_ptr<Simplex> 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, Sptr_hash, Sptr_equal> 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 */ @@ -75,7 +76,6 @@ public: template <typename Input_vertex_range> void insert_independent_simplex(const Input_vertex_range &vertex_range); - /** \internal Removes a toplex without adding facets after. * \ingroup toplex_map */ void erase_maximal(const Simplex_ptr& sptr); @@ -98,12 +98,8 @@ protected: /** \internal The map from vertices to toplices * \ingroup toplex_map */ std::unordered_map<Vertex, Simplex_ptr_set> t0; - }; -typedef Toplex_map::Simplex_ptr Simplex_ptr; -typedef Toplex_map::Simplex_ptr_set Simplex_ptr_set; - // Pointers are also used as key in the hash sets. template <typename Input_vertex_range> Simplex_ptr get_key(const Input_vertex_range &vertex_range); @@ -261,13 +257,13 @@ Vertex Toplex_map::best_index(const Input_vertex_range &vertex_range) const{ return arg_min; } -std::size_t Toplex_map::Sptr_equal::operator()(const Simplex_ptr& s1, const Simplex_ptr& s2) const { +std::size_t Sptr_equal::operator()(const Simplex_ptr& s1, const Simplex_ptr& s2) const { if (s1->size() != s2->size()) return false; return included(*s1,*s2); // inclusion tests equality for same size simplices } -std::size_t Toplex_map::Sptr_hash::operator()(const Simplex_ptr& s) const { +std::size_t Sptr_hash::operator()(const Simplex_ptr& s) const { std::hash<double> h_f; //double hash works better than int hash size_t h = 0; |