From 03566e8a3a7f52f180bfa643b801f302c033f3fa Mon Sep 17 00:00:00 2001 From: fgodi Date: Thu, 26 Oct 2017 15:20:03 +0000 Subject: boost clique algorithm for ribs git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@2808 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 99ab7e5ce4cf1de7c710333ca1328c552499a446 --- src/Toplex_map/include/gudhi/Fake_simplex_tree.h | 108 ++++++--------------- src/Toplex_map/include/gudhi/Filtered_toplex_map.h | 15 ++- 2 files changed, 43 insertions(+), 80 deletions(-) (limited to 'src/Toplex_map/include') diff --git a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h index b318acb4..6a0782ea 100644 --- a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h +++ b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h @@ -5,10 +5,26 @@ #include #include +#include +#define filtration_upper_bound std::numeric_limits::max() namespace Gudhi { +struct Visitor { + Toplex_map* tm; + + Visitor(Toplex_map* tm) + :tm(tm) + {} + + template + void clique(const Clique& c, const Graph& g) + { + tm->insert_simplex(c); + } +}; + class Fake_simplex_tree : public Filtered_toplex_map { public: @@ -31,14 +47,12 @@ public: /** \brief Returns the number of vertices in the simplicial complex. */ std::size_t num_vertices() const; - Simplex_ptr_set candidates() const; + Simplex_ptr_set candidates(int min_dim=-1) const; std::size_t dimension() const; std::size_t num_simplices() const; - void set_dimension(int d); - Simplex simplex_vertex_range(const Simplex& s) const; std::vector max_simplices() const; @@ -58,87 +72,26 @@ protected: }; -void Fake_simplex_tree::set_dimension(int d){ - -} - template void Fake_simplex_tree::insert_graph(const OneSkeletonGraph& skel_graph){ - if (boost::num_vertices(skel_graph) == 0) return; - typename boost::graph_traits::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::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) { - Vertex u = source(*e_it, skel_graph); - Vertex v = target(*e_it, skel_graph); - if (u < v) { - Simplex s; - s.insert(u); - s.insert(v); - insert_simplex_and_subfaces(s, boost::get(edge_filtration_t(), skel_graph, *e_it)); - } - } + toplex_maps.emplace(filtration_upper_bound,Toplex_map()); + bron_kerbosch_all_cliques(skel_graph, Visitor(&(this->toplex_maps.at(filtration_upper_bound)))); } -void Fake_simplex_tree::expansion(int max_dim){ - 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) - insert_simplex_and_subfaces(*sptr); //filtration ? - } -} +void Fake_simplex_tree::expansion(int max_dim){} template bool Fake_simplex_tree::all_facets_inside(const Input_vertex_range &vertex_range) const{ Simplex sigma(vertex_range); for(const Simplex& s : facets(sigma)) - if(!filtrations.count(get_key(s))) return false; + if(!membership(s)) return false; return true; } -Simplex_ptr_set Fake_simplex_tree::candidates() const{ - Simplex_ptr_set c; - std::unordered_map, Sptr_hash, Sptr_equal> facets_to_max; - for(const auto& kv : filtrations){ - Simplex sigma (*(kv.first)); - 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()); - facets_to_max.at(sptr).emplace_back(v); - sigma.insert(v); - } - } - for(const auto& kv : facets_to_max){ - std::unordered_set facets(kv.second.begin(), kv.second.end()); - for(Vertex v : kv.second){ - facets.erase(v); - for(Vertex w : facets){ - Simplex sigma(*(kv.first)); - sigma.insert(v); - sigma.insert(w); - if(all_facets_inside(sigma)) - c.emplace(get_key(sigma)); - } - facets.emplace(v); - } - } - return c; -} - std::size_t Fake_simplex_tree::dimension() const { std::size_t max = 0; - for(auto kv : filtrations) - max = std::max(max, kv.first->size()); + for(const Simplex& s : max_simplices()) + max = std::max(max, s.size()); return max-1; } @@ -149,8 +102,8 @@ std::size_t Fake_simplex_tree::num_simplices() const { std::size_t Fake_simplex_tree::num_vertices() const { std::unordered_set vertices; - for(auto kv : filtrations) - for (Vertex v : *(kv.first)) + for(const Simplex& s : max_simplices()) + for (Vertex v : s) vertices.emplace(v); return vertices.size(); } @@ -179,17 +132,18 @@ std::vector Fake_simplex_tree::filtration_simplex_range() const{ std::vector Fake_simplex_tree::skeleton_simplex_range(int d) const{ std::vector simplices; - for(auto s: filtration_simplex_range()) + for(const Simplex& s : max_simplices()) if(s.size()<=d) simplices.emplace_back(s); return simplices; } std::vector Fake_simplex_tree::max_simplices() const{ - std::vector s; - for(auto kv : filtrations) - s.emplace_back(*(kv.first)); - return s; + std::vector max_s; + for(auto kv : toplex_maps) + for(const Simplex_ptr& sptr : kv.second.maximal_cofaces(Simplex())) + max_s.emplace_back(*sptr); + return max_s; } std::size_t Fake_simplex_tree::dimension(Simplex_ptr& sptr) const{ diff --git a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h index 6d89c062..5bf50fc5 100644 --- a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h +++ b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h @@ -19,19 +19,20 @@ public: template Filtration_value filtration(const Input_vertex_range &vertex_range) const; + template + bool membership(const Input_vertex_range &vertex_range) const; + protected: std::unordered_map toplex_maps; - std::unordered_map filtrations; - }; template void Filtered_toplex_map::insert_simplex_and_subfaces(const Input_vertex_range &vertex_range, Filtration_value f){ if(!toplex_maps.count(f)) toplex_maps.emplace(f,Toplex_map()); toplex_maps.at(f).insert_simplex(vertex_range); - filtrations.emplace(get_key(vertex_range),f); } + template Filtered_toplex_map::Filtration_value Filtered_toplex_map::filtration(const Input_vertex_range &vertex_range) const{ for(auto kv : toplex_maps) @@ -40,6 +41,14 @@ Filtered_toplex_map::Filtration_value Filtered_toplex_map::filtration(const Inpu return filtration_upper_bound; } +template +bool Filtered_toplex_map::membership(const Input_vertex_range &vertex_range) const{ + for(auto kv : toplex_maps) + if(kv.second.membership(vertex_range)) + return true; + return false; +} + } //namespace Gudhi #endif /* FILTERED_TOPLEX_MAP_H */ -- cgit v1.2.3