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 --- .../example/example_rips_complex_from_fvecs.cpp | 71 ++++++-------- src/Toplex_map/include/gudhi/Fake_simplex_tree.h | 108 ++++++--------------- src/Toplex_map/include/gudhi/Filtered_toplex_map.h | 15 ++- 3 files changed, 74 insertions(+), 120 deletions(-) (limited to 'src') diff --git a/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp b/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp index c05d038a..5e7667bd 100644 --- a/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp +++ b/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp @@ -10,58 +10,49 @@ #include #include #include +#include void usage(int nbArgs, char * const progName) { - std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n"; - std::cerr << "Usage: " << progName << " filename.fvecs threshold dim_max [ouput_file.txt]\n"; - std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.fvecs 60.0\n"; - exit(-1); // ----- >> + std::cerr << "Error: Number of arguments (" << nbArgs << ") is not correct\n"; + std::cerr << "Usage: " << progName << " filename.fvecs threshold dim_max [ouput_file.txt]\n"; + std::cerr << " i.e.: " << progName << " ../../data/points/alphacomplexdoc.fvecs 60.0\n"; + exit(-1); // ----- >> } int main(int argc, char **argv) { - if ((argc != 4) && (argc != 5)) usage(argc, (argv[0] - 1)); + if (argc != 4) usage(argc, (argv[0] - 1)); - std::string file_name(argv[1]); - double threshold = atof(argv[2]); - int dim_max = atoi(argv[3]); + std::string file_name(argv[1]); + double threshold = atof(argv[2]); + int dim_max = atoi(argv[3]); - // Type definitions - using K = CGAL::Epick_d; - using Point = typename K::Point_d; - //using Simplex_tree = Gudhi::Simplex_tree<>; - using Simplex_tree = Gudhi::Fake_simplex_tree; - using Filtration_value = Simplex_tree::Filtration_value; - using Rips_complex = Gudhi::rips_complex::Rips_complex; - using Point_vector = std::vector; + // Type definitions + using K = CGAL::Epick_d; + using Point = typename K::Point_d; + //using Simplex_tree = Gudhi::Simplex_tree<>; + using Simplex_tree = Gudhi::Fake_simplex_tree; + using Filtration_value = Simplex_tree::Filtration_value; + using Rips_complex = Gudhi::rips_complex::Rips_complex; + using Point_vector = std::vector; - // ---------------------------------------------------------------------------- - // Init of a Rips complex from an fvecs file - // ---------------------------------------------------------------------------- - Point_vector point_vector; - Gudhi::load_points_from_fvecs_file(file_name, std::back_insert_iterator< Point_vector >(point_vector)); + // ---------------------------------------------------------------------------- + // Init of a Rips complex from an fvecs file + // ---------------------------------------------------------------------------- + Point_vector point_vector; + Gudhi::load_points_from_fvecs_file(file_name, std::back_insert_iterator< Point_vector >(point_vector)); - Rips_complex rips_complex_from_file(point_vector, threshold, Gudhi::Euclidean_distance()); + Rips_complex rips_complex_from_file(point_vector, threshold, Gudhi::Euclidean_distance()); - std::streambuf* streambufffer; - std::ofstream ouput_file_stream; - if (argc == 5) { - ouput_file_stream.open(std::string(argv[4])); - streambufffer = ouput_file_stream.rdbuf(); - } else { - streambufffer = std::cout.rdbuf(); - } + Simplex_tree stree; - Simplex_tree stree; - rips_complex_from_file.create_complex(stree, dim_max); - std::ostream output_stream(streambufffer); + clock_t start, end; + start = clock(); + rips_complex_from_file.create_complex(stree, dim_max); + end = clock(); - // ---------------------------------------------------------------------------- - // Display information about the Rips complex - // ---------------------------------------------------------------------------- - output_stream << "Rips complex is of dimension " << stree.dimension() << - " - " << stree.num_simplices() << " simplices." << std::endl; + std::cout << "Strong witness complex took "<< static_cast(end - start) / CLOCKS_PER_SEC << " s." << std::endl; + std::cout << "Rips complex is of dimension " << stree.dimension() << " - " << stree.num_simplices() << " simplices." << std::endl; - ouput_file_stream.close(); - return 0; + return 0; } 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