From 23e265d8c48d921a51eb0265afa6d8af27b27559 Mon Sep 17 00:00:00 2001 From: fgodi Date: Wed, 25 Oct 2017 11:19:00 +0000 Subject: 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 --- src/Rips_complex/example/CMakeLists.txt | 2 + .../example/example_rips_complex_from_fvecs.cpp | 67 ++++++++++ src/Toplex_map/include/gudhi/Fake_simplex_tree.h | 142 +++++++++------------ src/Toplex_map/include/gudhi/Filtered_toplex_map.h | 8 +- src/Toplex_map/include/gudhi/Toplex_map.h | 30 ++--- src/Witness_complex/example/CMakeLists.txt | 2 + .../example/example_strong_witness_complex_off.cpp | 4 +- 7 files changed, 153 insertions(+), 102 deletions(-) create mode 100644 src/Rips_complex/example/example_rips_complex_from_fvecs.cpp (limited to 'src') diff --git a/src/Rips_complex/example/CMakeLists.txt b/src/Rips_complex/example/CMakeLists.txt index 2940f164..b854b1c9 100644 --- a/src/Rips_complex/example/CMakeLists.txt +++ b/src/Rips_complex/example/CMakeLists.txt @@ -4,6 +4,8 @@ project(Rips_complex_examples) # Point cloud add_executable ( Rips_complex_example_from_off example_rips_complex_from_off_file.cpp ) +add_executable ( Rips_complex_example_from_fvecs example_rips_complex_from_fvecs.cpp ) + add_executable ( Rips_complex_example_one_skeleton_from_points example_one_skeleton_rips_from_points.cpp ) # Distance matrix diff --git a/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp b/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp new file mode 100644 index 00000000..c05d038a --- /dev/null +++ b/src/Rips_complex/example/example_rips_complex_from_fvecs.cpp @@ -0,0 +1,67 @@ +#include +// to construct Rips_complex from a fvecs file of points +#include +#include +#include +#include + +#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); // ----- >> +} + +int main(int argc, char **argv) { + if ((argc != 4) && (argc != 5)) usage(argc, (argv[0] - 1)); + + 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; + + // ---------------------------------------------------------------------------- + // 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()); + + 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; + rips_complex_from_file.create_complex(stree, dim_max); + std::ostream output_stream(streambufffer); + + // ---------------------------------------------------------------------------- + // Display information about the Rips complex + // ---------------------------------------------------------------------------- + output_stream << "Rips complex is of dimension " << stree.dimension() << + " - " << stree.num_simplices() << " simplices." << std::endl; + + ouput_file_stream.close(); + 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 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 #include + #include + 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 max_simplices() const; + std::vector max_simplices() const; - std::unordered_set filtration_simplex_range() const; + std::vector filtration_simplex_range() const; - std::unordered_set skeleton_simplex_range(int d=std::numeric_limits::max()) const; + std::vector skeleton_simplex_range(int d=std::numeric_limits::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 void Fake_simplex_tree::insert_graph(const OneSkeletonGraph& skel_graph){ - typename boost::graph_traits::edge_iterator e_it, - e_it_end; + 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) { - auto u = source(*e_it, skel_graph); - auto v = target(*e_it, skel_graph); - if(u, Toplex_map::Sptr_hash, Toplex_map::Sptr_equal> facets_to_max; + std::unordered_map, 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()); - 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()); + 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()); @@ -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 Fake_simplex_tree::filtration_simplex_range() const{ - std::vector m = max_simplices(); - std::cout << m.size()<< std::endl; - std::cout << m.size()<< std::endl; - - std::cout << m.size()<< std::endl; - - std::unordered_set seen; +std::vector Fake_simplex_tree::filtration_simplex_range() const{ + std::vector m = max_simplices(); + std::vector 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 Fake_simplex_tree::skeleton_simplex_range(int d) const{ - std::unordered_set simplices; - for(auto sptr: filtration_simplex_range()) - if(sptr->size()<=d) - simplices.emplace(sptr); +std::vector Fake_simplex_tree::skeleton_simplex_range(int d) const{ + std::vector simplices; + for(auto s: filtration_simplex_range()) + if(s.size()<=d) + simplices.emplace_back(s); return simplices; } -std::vector Fake_simplex_tree::max_simplices() const{ - std::vector s; +std::vector Fake_simplex_tree::max_simplices() const{ + std::vector 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 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 toplex_maps; - std::unordered_map filtrations; + std::unordered_map filtrations; }; @@ -33,7 +33,7 @@ void Filtered_toplex_map::insert_simplex_and_subfaces(const Input_vertex_range & } template -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 #include #include +#include #define vertex_upper_bound std::numeric_limits::max() @@ -18,22 +19,22 @@ typedef std::size_t Vertex; * \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: - /** 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 */ @@ -75,7 +76,6 @@ public: template 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 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 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 h_f; //double hash works better than int hash size_t h = 0; diff --git a/src/Witness_complex/example/CMakeLists.txt b/src/Witness_complex/example/CMakeLists.txt index cbc53902..0f709409 100644 --- a/src/Witness_complex/example/CMakeLists.txt +++ b/src/Witness_complex/example/CMakeLists.txt @@ -14,6 +14,7 @@ install(TARGETS Witness_complex_example_nearest_landmark_table DESTINATION bin) if (NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.6.0) add_executable( Witness_complex_example_off example_witness_complex_off.cpp ) add_executable( Witness_complex_example_strong_off example_strong_witness_complex_off.cpp ) +add_executable( Witness_complex_example_strong_fvecs example_strong_witness_complex_fvecs.cpp ) add_executable ( Witness_complex_example_sphere example_witness_complex_sphere.cpp ) add_executable ( Witness_complex_example_witness_persistence example_witness_complex_persistence.cpp ) @@ -44,6 +45,7 @@ if (NOT CGAL_WITH_EIGEN3_VERSION VERSION_LESS 4.6.0) install(TARGETS Witness_complex_example_off DESTINATION bin) install(TARGETS Witness_complex_example_strong_off DESTINATION bin) + install(TARGETS Witness_complex_example_strong_fvecs DESTINATION bin) install(TARGETS Witness_complex_example_sphere DESTINATION bin) install(TARGETS Witness_complex_example_witness_persistence DESTINATION bin) install(TARGETS Witness_complex_example_strong_witness_persistence DESTINATION bin) diff --git a/src/Witness_complex/example/example_strong_witness_complex_off.cpp b/src/Witness_complex/example/example_strong_witness_complex_off.cpp index 4a232481..6292e248 100644 --- a/src/Witness_complex/example/example_strong_witness_complex_off.cpp +++ b/src/Witness_complex/example/example_strong_witness_complex_off.cpp @@ -50,8 +50,8 @@ int main(int argc, char * const argv[]) { int nbL = atoi(argv[2]), lim_dim = atoi(argv[4]); double alpha2 = atof(argv[3]); clock_t start, end; - //Gudhi::Simplex_tree<> simplex_tree; - Gudhi::Fake_simplex_tree simplex_tree; + Gudhi::Simplex_tree<> simplex_tree; + //Gudhi::Fake_simplex_tree simplex_tree; // Read the point file Point_vector point_vector, landmarks; -- cgit v1.2.3