From d8e1da2f6465e3d6baa0c6e921a3cc0b9ce3f2c7 Mon Sep 17 00:00:00 2001 From: fgodi Date: Fri, 13 Oct 2017 09:33:33 +0000 Subject: module toplex_map added git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@2784 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 61f8f8a2d3920dbc30b86dd808a0e316383af137 --- src/Toplex_map/doc/Intro_Toplex_map.h | 57 +++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) create mode 100644 src/Toplex_map/doc/Intro_Toplex_map.h (limited to 'src/Toplex_map/doc/Intro_Toplex_map.h') diff --git a/src/Toplex_map/doc/Intro_Toplex_map.h b/src/Toplex_map/doc/Intro_Toplex_map.h new file mode 100644 index 00000000..da9562ec --- /dev/null +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -0,0 +1,57 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author: François Godi + * + * Copyright (C) 2017 INRIA + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef DOC_TOPLEX_MAP_H_ +#define DOC_TOPLEX_MAP_H_ + +// needs namespace for Doxygen to link on classes +namespace Gudhi { + +/** \defgroup toplex_map Toplex Map + * + * \author François Godi + * @{ + * + * \section toplexmapdefinition Definition + * + * Let's consider a simplicial complex, denote by $d$ its dimension + * and by $k$ its number of maximal simplices. + * Furthermore, denote by $\gamma_0$ the maximal number of toplices, i.e. maximal simplices, + * that contain a same vertex. + * + * The goal of the Toplex Map is both to represent the complex in optimal + * O(kd) space and to provide fast standard operations such as : insertion, removal + * and membership of a simplex, contraction of an edge, collapses. The time needed + * for these operation is linear or quadratic in $\gamma_0$ and $d$. + * + * Toplex map is composed firstly of a raw storage of toplices and secondly of a + * map which associate any vertex to a set of pointers toward all toplices + * containing this vertex. + * + * \image html map.png + * + */ +/** @} */ // end defgroup toplex_map + +} // namespace Gudhi + +#endif // DOC_TOPLEX_MAP_H_ -- cgit v1.2.3 From bf84494b3e7f3d2a36661b66defb131e515cdc5b Mon Sep 17 00:00:00 2001 From: fgodi Date: Tue, 21 Nov 2017 18:38:25 +0000 Subject: ... git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@2926 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: d872eef9342046002b81f55cc12760e799df0c1d --- src/Toplex_map/benchmarks/CMakeLists.txt | 4 + src/Toplex_map/benchmarks/chrono.cpp | 137 +++++++++++++++++++++ src/Toplex_map/doc/Intro_Toplex_map.h | 8 +- src/Toplex_map/include/gudhi/Fake_simplex_tree.h | 69 +++++------ src/Toplex_map/include/gudhi/Filtered_toplex_map.h | 11 +- 5 files changed, 182 insertions(+), 47 deletions(-) create mode 100644 src/Toplex_map/benchmarks/CMakeLists.txt create mode 100644 src/Toplex_map/benchmarks/chrono.cpp (limited to 'src/Toplex_map/doc/Intro_Toplex_map.h') diff --git a/src/Toplex_map/benchmarks/CMakeLists.txt b/src/Toplex_map/benchmarks/CMakeLists.txt new file mode 100644 index 00000000..2341fe06 --- /dev/null +++ b/src/Toplex_map/benchmarks/CMakeLists.txt @@ -0,0 +1,4 @@ +cmake_minimum_required(VERSION 2.6) +project(Toplex_map_examples) + +add_executable(chrono chrono.cpp) diff --git a/src/Toplex_map/benchmarks/chrono.cpp b/src/Toplex_map/benchmarks/chrono.cpp new file mode 100644 index 00000000..d93d1e1f --- /dev/null +++ b/src/Toplex_map/benchmarks/chrono.cpp @@ -0,0 +1,137 @@ +#include +#include +#include + +#include +#include + +using namespace Gudhi; + +typedef Simplex typeVectorVertex; +typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool; + +class ST_wrapper { + +public: + void insert_simplex(const Simplex& tau); + bool membership(const Simplex& tau); + Vertex contraction(const Vertex x, const Vertex y); + std::size_t num_simplices(); + +private: + Simplex_tree<> simplexTree; + void erase_max(const Simplex& sigma); +}; + +void ST_wrapper::insert_simplex(const Simplex& tau){ + simplexTree.insert_simplex_and_subfaces(tau); +} + +bool ST_wrapper::membership(const Simplex& tau) { + return simplexTree.find(tau) != simplexTree.null_simplex(); +} + +void ST_wrapper::erase_max(const Simplex& sigma){ + if(membership(sigma)) + simplexTree.remove_maximal_simplex(simplexTree.find(sigma)); +} + +Vertex ST_wrapper::contraction(const Vertex x, const Vertex y){ + Simplex sx; sx.insert(x); + auto hx = simplexTree.find(sx); + if(hx != simplexTree.null_simplex()) + for(auto h : simplexTree.cofaces_simplex_range(hx,0)){ + auto sr = simplexTree.simplex_vertex_range(h); + Simplex sigma(sr.begin(),sr.end()); + erase_max(sigma); + sigma.erase(x); + sigma.insert(y); + insert_simplex(sigma); + } + return y; +} + +std::size_t ST_wrapper::num_simplices(){ + return simplexTree.num_simplices(); +} + + + +int n = 300; + +int nb_insert_simplex1 = 3000; +int nb_membership1 = 4000; +int nb_contraction = 300; +int nb_insert_simplex2 = 3000; +int nb_membership2 = 400000; + +Simplex random_simplex(int n, int d){ + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution<> dis(1, n); + Simplex s; + while(s.size()!=d) + s.insert(dis(gen)); + return s; +} + +std::vector r_vector_simplices(int n, int max_d, int m){ + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution<> dis(1, max_d); + std::vector v; + for(int i=0; i +void chrono(int n, int d){ + complex_type K; + std::vector simplices_insert_simplex1 = r_vector_simplices(n,d,nb_insert_simplex1); + std::vector simplices_membership1 = r_vector_simplices(n,d,nb_membership1); + std::vector simplices_insert_simplex2 = r_vector_simplices(n - 2*nb_contraction,d,nb_insert_simplex2); + std::vector simplices_membership2 = r_vector_simplices(n - 2*nb_contraction,d,nb_membership2); + std::chrono::time_point start, end; + + for(const Simplex& s : simplices_insert_simplex1) + K.insert_simplex(s); + + for(const Simplex& s : simplices_membership1) + K.membership(s); + + start = std::chrono::system_clock::now(); + for(int i = 0; i<=nb_contraction; i++) + K.contraction(n-2*i,n-2*i-1); + end = std::chrono::system_clock::now(); + auto c3 = std::chrono::duration_cast(end-start).count(); + + start = std::chrono::system_clock::now(); + for(const Simplex& s : simplices_insert_simplex2) + K.insert_simplex(s); + end = std::chrono::system_clock::now(); + auto c1 = std::chrono::duration_cast(end-start).count(); + + start = std::chrono::system_clock::now(); + for(const Simplex& s : simplices_membership2) + K.membership(s); + end = std::chrono::system_clock::now(); + auto c2 = std::chrono::duration_cast(end-start).count(); + + std::cout << c1 << "\t \t" << c2 << "\t \t" << c3 << "\t \t" << K.num_simplices() << std::endl; +} + +int main(){ + for(int d=5;d<=40;d+=5){ + std::cout << "d=" << d << " \t Insertions \t Membership \t Contractions \t Size" << std::endl; + std::cout << "T Map \t \t"; + chrono(n,d); + std::cout << "Lazy \t \t"; + chrono(n,d); + if(d<=15){ + std::cout << "ST \t \t"; + chrono(n,d); + } + std::cout << std::endl; + } +} diff --git a/src/Toplex_map/doc/Intro_Toplex_map.h b/src/Toplex_map/doc/Intro_Toplex_map.h index da9562ec..6f4c1a1b 100644 --- a/src/Toplex_map/doc/Intro_Toplex_map.h +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -33,15 +33,15 @@ namespace Gudhi { * * \section toplexmapdefinition Definition * - * Let's consider a simplicial complex, denote by $d$ its dimension - * and by $k$ its number of maximal simplices. - * Furthermore, denote by $\gamma_0$ the maximal number of toplices, i.e. maximal simplices, + * Let's consider a simplicial complex, denote by \f$d\f$ its dimension + * and by \f$k\f$ its number of maximal simplices. + * Furthermore, denote by \f$\gamma_0\f$ the maximal number of toplices, i.e. maximal simplices, * that contain a same vertex. * * The goal of the Toplex Map is both to represent the complex in optimal * O(kd) space and to provide fast standard operations such as : insertion, removal * and membership of a simplex, contraction of an edge, collapses. The time needed - * for these operation is linear or quadratic in $\gamma_0$ and $d$. + * for these operation is linear or quadratic in \f$\gamma_0\f$ and \f$d\f$. * * Toplex map is composed firstly of a raw storage of toplices and secondly of a * map which associate any vertex to a set of pointers toward all toplices diff --git a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h index 6a0782ea..3de962af 100644 --- a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h +++ b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h @@ -1,14 +1,14 @@ #ifndef FAKE_SIMPLEX_TREE_H #define FAKE_SIMPLEX_TREE_H +#include + #include #include #include #include -#define filtration_upper_bound std::numeric_limits::max() - namespace Gudhi { struct Visitor { @@ -35,33 +35,31 @@ public: typedef void Insertion_result_type; - /** \brief Inserts a given range `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph` in the simplicial + /** \brief Inserts the flag complex of a given range `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph` in the simplicial * complex. */ template void insert_graph(const OneSkeletonGraph& skel_graph); - /** \brief Expands the simplicial complex containing only its one skeleton until a given maximal dimension as - * explained in \ref ripsdefinition. */ + /** \brief Do nothing */ void expansion(int max_dim); - /** \brief Returns the number of vertices in the simplicial complex. */ + /** \brief Returns the number of vertices stored i.e. the number of max simplices */ std::size_t num_vertices() const; - Simplex_ptr_set candidates(int min_dim=-1) const; - std::size_t dimension() const; + std::size_t dimension(Simplex_ptr& sptr) const; + std::size_t num_simplices() const; Simplex simplex_vertex_range(const Simplex& s) const; std::vector max_simplices() const; - std::vector filtration_simplex_range() const; + std::vector filtration_simplex_range(int d=std::numeric_limits::max()) const; - std::vector skeleton_simplex_range(int d=std::numeric_limits::max()) const; + std::vector skeleton_simplex_range(int d) const; - std::size_t dimension(Simplex_ptr& sptr) const; protected: @@ -74,8 +72,8 @@ protected: template void Fake_simplex_tree::insert_graph(const OneSkeletonGraph& skel_graph){ - toplex_maps.emplace(filtration_upper_bound,Toplex_map()); - bron_kerbosch_all_cliques(skel_graph, Visitor(&(this->toplex_maps.at(filtration_upper_bound)))); + toplex_maps.emplace(nan(""),Toplex_map()); + bron_kerbosch_all_cliques(skel_graph, Visitor(&(this->toplex_maps.at(nan(""))))); } void Fake_simplex_tree::expansion(int max_dim){} @@ -95,6 +93,10 @@ std::size_t Fake_simplex_tree::dimension() const { return max-1; } +std::size_t Fake_simplex_tree::dimension(Simplex_ptr& sptr) const{ + return sptr->size(); +} + std::size_t Fake_simplex_tree::num_simplices() const { //return filtration_simplex_range().size(); return max_simplices().size(); @@ -112,42 +114,35 @@ Simplex Fake_simplex_tree::simplex_vertex_range(const Simplex& s) const { return s; } -std::vector Fake_simplex_tree::filtration_simplex_range() const{ +std::vector Fake_simplex_tree::max_simplices() const{ + 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::vector Fake_simplex_tree::filtration_simplex_range(int d) const{ std::vector m = max_simplices(); - std::vector seen1; - Simplex_ptr_set seen2; + std::vector range; + Simplex_ptr_set seen; while(m.begin()!=m.end()){ Simplex s(m.back()); m.pop_back(); - if(seen2.find(get_key(s))==seen2.end()){ - seen1.emplace_back(s); - seen2.emplace(get_key(s)); + if(seen.find(get_key(s))==seen.end()){ + if(s.size()-1<=d) + range.emplace_back(s); + seen.emplace(get_key(s)); if(s.size()>0) for(Simplex& sigma : facets(s)) m.emplace_back(sigma); } } - return seen1; + return range; } std::vector Fake_simplex_tree::skeleton_simplex_range(int d) const{ - std::vector simplices; - 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 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{ - return sptr->size(); + return filtration_simplex_range(d); } } //namespace Gudhi diff --git a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h index 3a0064dc..a0c24304 100644 --- a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h +++ b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h @@ -2,10 +2,9 @@ #define FILTERED_TOPLEX_MAP_H #include +#include #include -#define filtration_upper_bound std::numeric_limits::max() - namespace Gudhi { class Filtered_toplex_map { @@ -14,7 +13,7 @@ public: typedef double Filtration_value; template - std::pair insert_simplex_and_subfaces(const Input_vertex_range &vertex_range, Filtration_value f = filtration_upper_bound); + std::pair insert_simplex_and_subfaces(const Input_vertex_range &vertex_range, Filtration_value f = nan("")); template Filtration_value filtration(const Input_vertex_range &vertex_range) const; @@ -23,7 +22,7 @@ public: bool membership(const Input_vertex_range &vertex_range) const; protected: - std::unordered_map toplex_maps; + std::map toplex_maps; }; template @@ -40,8 +39,8 @@ template 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; - return filtration_upper_bound; + return kv.first; //min only because a map is ordered + return nan(""); } template -- cgit v1.2.3 From 6485e6957ef3c9310f618db6caaf2858cc56db66 Mon Sep 17 00:00:00 2001 From: fgodi Date: Mon, 8 Jan 2018 10:57:04 +0000 Subject: test name git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@3115 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 4d65b9218d81a3f7e32dd873ba8eb0d5e6524095 --- src/Toplex_map/doc/Intro_Toplex_map.h | 5 +++++ src/Toplex_map/include/gudhi/Fake_simplex_tree.h | 12 ---------- src/Toplex_map/test/CMakeLists.txt | 2 +- src/Toplex_map/test/toplex_map_unit_test.cpp | 28 ++---------------------- 4 files changed, 8 insertions(+), 39 deletions(-) (limited to 'src/Toplex_map/doc/Intro_Toplex_map.h') diff --git a/src/Toplex_map/doc/Intro_Toplex_map.h b/src/Toplex_map/doc/Intro_Toplex_map.h index 6f4c1a1b..e3f18b32 100644 --- a/src/Toplex_map/doc/Intro_Toplex_map.h +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -49,6 +49,11 @@ namespace Gudhi { * * \image html map.png * + * The performances are a lot better than in simplex tree as soon you use maximal simplices and not simplices, + * here the construction of a strong witness complex of a point set with growing parameter : + * + * \image html graph.png + * */ /** @} */ // end defgroup toplex_map diff --git a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h index ea5ac618..abd815f9 100644 --- a/src/Toplex_map/include/gudhi/Fake_simplex_tree.h +++ b/src/Toplex_map/include/gudhi/Fake_simplex_tree.h @@ -31,18 +31,6 @@ struct Visitor { class Fake_simplex_tree : public Filtered_toplex_map { public: - /** Vertex is the type of vertices. - * \ingroup toplex_map */ - typedef Toplex_map::Vertex Vertex; - - /** Simplex is the type of simplices. - * \ingroup toplex_map */ - typedef Toplex_map::Simplex Simplex; - - /** The type of the pointers to maximal simplices. - * \ingroup toplex_map */ - typedef Toplex_map::Simplex_ptr Simplex_ptr; - /** The type of the sets of Simplex_ptr. * \ingroup toplex_map */ typedef Toplex_map::Simplex_ptr_set Simplex_ptr_set; diff --git a/src/Toplex_map/test/CMakeLists.txt b/src/Toplex_map/test/CMakeLists.txt index 25fcabac..5ed55e97 100644 --- a/src/Toplex_map/test/CMakeLists.txt +++ b/src/Toplex_map/test/CMakeLists.txt @@ -1,7 +1,7 @@ cmake_minimum_required(VERSION 2.6) project(Toplex_map_tests) -add_executable ( ToplexMapUT test.cpp ) +add_executable ( ToplexMapUT toplex_map_unit_test.cpp ) target_link_libraries(ToplexMapUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) diff --git a/src/Toplex_map/test/toplex_map_unit_test.cpp b/src/Toplex_map/test/toplex_map_unit_test.cpp index 3f4d96c2..b7a9251c 100644 --- a/src/Toplex_map/test/toplex_map_unit_test.cpp +++ b/src/Toplex_map/test/toplex_map_unit_test.cpp @@ -1,5 +1,4 @@ #include -#include #include #include @@ -9,6 +8,8 @@ using namespace Gudhi; +typedef Toplex_map::Vertex Vertex; + std::vector sigma1 = {1, 2, 3, 4}; std::vector sigma2 = {5, 2, 3, 6}; std::vector sigma3 = {5}; @@ -33,18 +34,6 @@ BOOST_AUTO_TEST_CASE(toplexmap) { BOOST_CHECK(!K.membership(sigma6)); } -BOOST_AUTO_TEST_CASE(ltoplexmap) { - Lazy_Toplex_map K; - K.insert_simplex(sigma1); - K.insert_simplex(sigma2); - K.insert_simplex(sigma3); - K.insert_simplex(sigma6); - K.insert_simplex(sigma7); - BOOST_CHECK(K.membership(sigma4)); - BOOST_CHECK(!K.membership(sigma5)); - K.contraction(4,5); - BOOST_CHECK(!K.membership(sigma6)); -} BOOST_AUTO_TEST_CASE(ftoplexmap) { Filtered_toplex_map K; @@ -56,16 +45,3 @@ BOOST_AUTO_TEST_CASE(ftoplexmap) { BOOST_CHECK(K.filtration(sigma3)==1.); } -/* -BOOST_AUTO_TEST_CASE(toplexmap_candidates) { - Toplex_map K; - K.insert_simplex(sigma1); - K.insert_simplex(sigma2); - K.remove_simplex(sigma1); - K.remove_simplex(sigma2); - auto c = K.candidates(); - BOOST_CHECK(c.count(get_key(sigma1))); - BOOST_CHECK(c.count(get_key(sigma2))); - BOOST_CHECK(c.size()==2); -} -*/ -- cgit v1.2.3 From c882b0478d4b0899005bf6c0e9528a1fc8785cf9 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 16 Oct 2018 08:35:12 +0000 Subject: Toplex definition Remove witness complex graph to compare Toplex_map vs Simplex_tree git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@3955 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 5a1fc1be157b74963faa98b7844b8b47e54a82b6 --- src/Toplex_map/doc/Intro_Toplex_map.h | 31 ++++++++++++++----------------- 1 file changed, 14 insertions(+), 17 deletions(-) (limited to 'src/Toplex_map/doc/Intro_Toplex_map.h') diff --git a/src/Toplex_map/doc/Intro_Toplex_map.h b/src/Toplex_map/doc/Intro_Toplex_map.h index e3f18b32..93534e0e 100644 --- a/src/Toplex_map/doc/Intro_Toplex_map.h +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -2,7 +2,7 @@ * (Geometric Understanding in Higher Dimensions) is a generic C++ * library for computational topology. * - * Author: François Godi + * Author: François Godi, Vincent Rouvreau * * Copyright (C) 2017 INRIA * @@ -32,27 +32,24 @@ namespace Gudhi { * @{ * * \section toplexmapdefinition Definition - * - * Let's consider a simplicial complex, denote by \f$d\f$ its dimension - * and by \f$k\f$ its number of maximal simplices. - * Furthermore, denote by \f$\gamma_0\f$ the maximal number of toplices, i.e. maximal simplices, - * that contain a same vertex. * - * The goal of the Toplex Map is both to represent the complex in optimal - * O(kd) space and to provide fast standard operations such as : insertion, removal - * and membership of a simplex, contraction of an edge, collapses. The time needed - * for these operation is linear or quadratic in \f$\gamma_0\f$ and \f$d\f$. + * A Toplex_map is a data structure to represent and store a simplicial complex. A "toplex" is the contraction of + * "top-simplex", also known as a maximal simplex. We will call "toplices" a set of "toplex". * - * Toplex map is composed firstly of a raw storage of toplices and secondly of a - * map which associate any vertex to a set of pointers toward all toplices - * containing this vertex. + * Let's consider a simplicial complex, denote by \f$d\f$ its dimension and by \f$k\f$ its number of maximal simplices. + * Furthermore, denote by \f$\gamma_0\f$ the maximal number of toplices, i.e. maximal simplices, that contain a same + * vertex. * - * \image html map.png + * The goal of the Toplex Map is both to represent the complex in optimal O(kd) space and to provide fast standard + * operations such as : insertion, removal, contraction of an edge, collapses and membership of a simplex. The time + * needed for these operation is linear or quadratic in \f$\gamma_0\f$ and \f$d\f$. * - * The performances are a lot better than in simplex tree as soon you use maximal simplices and not simplices, - * here the construction of a strong witness complex of a point set with growing parameter : + * Toplex map is composed firstly of a raw storage of toplices and secondly of a map which associate any vertex to a + * set of pointers toward all toplices containing this vertex. + * + * \image html map.png * - * \image html graph.png + * The performances are a lot better than the `Simplex_tree` as soon you use maximal simplices and not simplices. * */ /** @} */ // end defgroup toplex_map -- cgit v1.2.3 From dda6af124625a4fbcd2524d623ef904b394af001 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Tue, 16 Oct 2018 14:33:27 +0000 Subject: Add copyrights Fix cpplint git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@3959 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 02c873347468e28d50f0c8ac385be988c07c96df --- src/Toplex_map/benchmark/benchmark_tm.cpp | 170 +++++----- src/Toplex_map/doc/Intro_Toplex_map.h | 6 +- src/Toplex_map/example/simple_toplex_map.cpp | 17 +- src/Toplex_map/include/gudhi/Lazy_toplex_map.h | 299 +++++++++--------- src/Toplex_map/include/gudhi/Toplex_map.h | 369 +++++++++++----------- src/Toplex_map/test/lazy_toplex_map_unit_test.cpp | 27 +- src/Toplex_map/test/toplex_map_unit_test.cpp | 27 +- 7 files changed, 497 insertions(+), 418 deletions(-) (limited to 'src/Toplex_map/doc/Intro_Toplex_map.h') diff --git a/src/Toplex_map/benchmark/benchmark_tm.cpp b/src/Toplex_map/benchmark/benchmark_tm.cpp index 5f13288c..eedb442b 100644 --- a/src/Toplex_map/benchmark/benchmark_tm.cpp +++ b/src/Toplex_map/benchmark/benchmark_tm.cpp @@ -1,3 +1,25 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author: François Godi, Vincent Rouvreau + * + * Copyright (C) 2018 INRIA + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + #include #include #include @@ -10,11 +32,10 @@ using namespace Gudhi; typedef Toplex_map::Simplex Simplex; typedef Toplex_map::Vertex Vertex; -typedef std::pair< Simplex_tree<>::Simplex_handle, bool > typePairSimplexBool; +typedef std::pair::Simplex_handle, bool> typePairSimplexBool; class ST_wrapper { - -public: + public: void insert_simplex(const Simplex& tau) { /*std::cout << "insert_simplex - " << simplexTree.num_simplices() << " - "; for (auto v : tau) @@ -24,28 +45,22 @@ public: simplexTree.insert_simplex_and_subfaces(tau); } - bool membership(const Simplex& tau) { - return simplexTree.find(tau) != simplexTree.null_simplex(); - } + bool membership(const Simplex& tau) { return simplexTree.find(tau) != simplexTree.null_simplex(); } Vertex contraction(const Vertex x, const Vertex y) { // TODO (VR): edge contraction is not yet available for Simplex_tree return y; } - std::size_t num_maximal_simplices() { - return simplexTree.num_simplices(); - } + std::size_t num_maximal_simplices() { return simplexTree.num_simplices(); } -private: - Simplex_tree<> simplexTree; - void erase_max(const Simplex& sigma) { - if(membership(sigma)) - simplexTree.remove_maximal_simplex(simplexTree.find(sigma)); - } + private: + Simplex_tree<> simplexTree; + void erase_max(const Simplex& sigma) { + if (membership(sigma)) simplexTree.remove_maximal_simplex(simplexTree.find(sigma)); + } }; - int n = 300; int nb_insert_simplex1 = 3000; @@ -54,76 +69,69 @@ int nb_contraction = 300; int nb_insert_simplex2 = 3000; int nb_membership2 = 400000; -Simplex random_simplex(int n, std::size_t d){ - std::random_device rd; - std::mt19937 gen(rd()); - std::uniform_int_distribution dis(1, n); - Simplex s; - while(s.size() < d) - s.insert(dis(gen)); - return s; +Simplex random_simplex(int n, std::size_t d) { + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution dis(1, n); + Simplex s; + while (s.size() < d) s.insert(dis(gen)); + return s; } -std::vector r_vector_simplices(int n, int max_d, int m){ - std::random_device rd; - std::mt19937 gen(rd()); - std::uniform_int_distribution dis(1, max_d); - std::vector v; - for(int i=0; i r_vector_simplices(int n, int max_d, int m) { + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution dis(1, max_d); + std::vector v; + for (int i = 0; i < m; i++) v.push_back(random_simplex(n, dis(gen))); + return v; } -template -void chrono(int n, int d){ - complex_type K; - std::vector simplices_insert_simplex1 = r_vector_simplices(n,d,nb_insert_simplex1); - std::vector simplices_membership1 = r_vector_simplices(n,d,nb_membership1); - std::vector simplices_insert_simplex2 = r_vector_simplices(n - 2*nb_contraction,d,nb_insert_simplex2); - std::vector simplices_membership2 = r_vector_simplices(n - 2*nb_contraction,d,nb_membership2); - std::chrono::time_point start, end; - - for(const Simplex& s : simplices_insert_simplex1) - K.insert_simplex(s); - - for(const Simplex& s : simplices_membership1) - K.membership(s); - - start = std::chrono::system_clock::now(); - for(int i = 1; i<=nb_contraction; i++) - K.contraction(n-2*i,n-2*i-1); - end = std::chrono::system_clock::now(); - auto c3 = std::chrono::duration_cast(end-start).count(); - - start = std::chrono::system_clock::now(); - for(const Simplex& s : simplices_insert_simplex2) - K.insert_simplex(s); - end = std::chrono::system_clock::now(); - auto c1 = std::chrono::duration_cast(end-start).count(); - - start = std::chrono::system_clock::now(); - for(const Simplex& s : simplices_membership2) - K.membership(s); - end = std::chrono::system_clock::now(); - auto c2 = std::chrono::duration_cast(end-start).count(); - - if (c3 > 0) - std::cout << c1 << "\t \t" << c2 << "\t \t" << c3 << "\t \t" << K.num_maximal_simplices() << std::endl; - else - std::cout << c1 << "\t \t" << c2 << "\t \tN/A\t \t" << K.num_maximal_simplices() << std::endl; +template +void chrono(int n, int d) { + complex_type K; + std::vector simplices_insert_simplex1 = r_vector_simplices(n, d, nb_insert_simplex1); + std::vector simplices_membership1 = r_vector_simplices(n, d, nb_membership1); + std::vector simplices_insert_simplex2 = r_vector_simplices(n - 2 * nb_contraction, d, nb_insert_simplex2); + std::vector simplices_membership2 = r_vector_simplices(n - 2 * nb_contraction, d, nb_membership2); + std::chrono::time_point start, end; + + for (const Simplex& s : simplices_insert_simplex1) K.insert_simplex(s); + + for (const Simplex& s : simplices_membership1) K.membership(s); + + start = std::chrono::system_clock::now(); + for (int i = 1; i <= nb_contraction; i++) K.contraction(n - 2 * i, n - 2 * i - 1); + end = std::chrono::system_clock::now(); + auto c3 = std::chrono::duration_cast(end - start).count(); + + start = std::chrono::system_clock::now(); + for (const Simplex& s : simplices_insert_simplex2) K.insert_simplex(s); + end = std::chrono::system_clock::now(); + auto c1 = std::chrono::duration_cast(end - start).count(); + + start = std::chrono::system_clock::now(); + for (const Simplex& s : simplices_membership2) K.membership(s); + end = std::chrono::system_clock::now(); + auto c2 = std::chrono::duration_cast(end - start).count(); + + if (c3 > 0) + std::cout << c1 << "\t \t" << c2 << "\t \t" << c3 << "\t \t" << K.num_maximal_simplices() << std::endl; + else + std::cout << c1 << "\t \t" << c2 << "\t \tN/A\t \t" << K.num_maximal_simplices() << std::endl; } -int main(){ - for(int d=5;d<=40;d+=5){ - std::cout << "d=" << d << " \t Insertions \t Membership \t Contractions \t Size" << std::endl; - std::cout << "T Map \t \t"; - chrono(n,d); - std::cout << "Lazy \t \t"; - chrono(n,d); - if(d<=15){ - std::cout << "ST \t \t"; - chrono(n,d); - } - std::cout << std::endl; +int main() { + for (int d = 5; d <= 40; d += 5) { + std::cout << "d=" << d << " \t Insertions \t Membership \t Contractions \t Size" << std::endl; + std::cout << "T Map \t \t"; + chrono(n, d); + std::cout << "Lazy \t \t"; + chrono(n, d); + if (d <= 15) { + std::cout << "ST \t \t"; + chrono(n, d); } + std::cout << std::endl; + } } diff --git a/src/Toplex_map/doc/Intro_Toplex_map.h b/src/Toplex_map/doc/Intro_Toplex_map.h index 93534e0e..649c27f9 100644 --- a/src/Toplex_map/doc/Intro_Toplex_map.h +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -20,8 +20,8 @@ * along with this program. If not, see . */ -#ifndef DOC_TOPLEX_MAP_H_ -#define DOC_TOPLEX_MAP_H_ +#ifndef DOC_TOPLEX_MAP_INTRO_TOPLEX_MAP_H_ +#define DOC_TOPLEX_MAP_INTRO_TOPLEX_MAP_H_ // needs namespace for Doxygen to link on classes namespace Gudhi { @@ -56,4 +56,4 @@ namespace Gudhi { } // namespace Gudhi -#endif // DOC_TOPLEX_MAP_H_ +#endif // DOC_TOPLEX_MAP_INTRO_TOPLEX_MAP_H_ diff --git a/src/Toplex_map/example/simple_toplex_map.cpp b/src/Toplex_map/example/simple_toplex_map.cpp index 912d79a0..e1c12ed6 100644 --- a/src/Toplex_map/example/simple_toplex_map.cpp +++ b/src/Toplex_map/example/simple_toplex_map.cpp @@ -27,7 +27,7 @@ #include #include -int main(int argc, char * const argv[]) { +int main(int argc, char* const argv[]) { using Simplex = Gudhi::Toplex_map::Simplex; Simplex sigma1 = {1, 2, 3}; Simplex sigma2 = {2, 3, 4, 5}; @@ -43,7 +43,8 @@ int main(int argc, char * const argv[]) { /* o---o */ /* 1 3 */ - std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl; + std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() + << std::endl; // Browse maximal cofaces Simplex sigma3 = {2, 3}; @@ -75,7 +76,8 @@ int main(int argc, char * const argv[]) { /* \5/ */ /* o */ /* 3 */ - std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl; + std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() + << std::endl; // Browse maximal simplices std::cout << "Maximal simplices are :" << std::endl; @@ -97,7 +99,8 @@ int main(int argc, char * const argv[]) { /* \X/ */ /* o */ /* 5 */ - std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl; + std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() + << std::endl; // Browse maximal simplices std::cout << "Maximal simplices are :" << std::endl; @@ -125,7 +128,8 @@ int main(int argc, char * const argv[]) { /* / \5/ */ /* o---o */ /* 1 3 */ - std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl; + std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() + << std::endl; // Browse maximal simplices std::cout << "Maximal simplices are :" << std::endl; @@ -145,7 +149,8 @@ int main(int argc, char * const argv[]) { /* \5/ */ /* o */ /* 3 */ - std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() << std::endl; + std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() + << std::endl; // Browse maximal simplices std::cout << "Maximal simplices are :" << std::endl; diff --git a/src/Toplex_map/include/gudhi/Lazy_toplex_map.h b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h index 8cc5610a..63c933d9 100644 --- a/src/Toplex_map/include/gudhi/Lazy_toplex_map.h +++ b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h @@ -1,3 +1,25 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author: François Godi, Vincent Rouvreau + * + * Copyright (C) 2018 INRIA + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + #ifndef LAZY_TOPLEX_MAP_H #define LAZY_TOPLEX_MAP_H @@ -14,8 +36,7 @@ namespace Gudhi { * * \ingroup toplex_map */ class Lazy_toplex_map { - -public: + public: /** Vertex is the type of vertices. */ using Vertex = Toplex_map::Vertex; @@ -47,7 +68,6 @@ public: template bool membership(const Input_vertex_range &vertex_range); - /** Do all the facets of a simplex belong to the complex ? */ template bool all_facets_inside(const Input_vertex_range &vertex_range); @@ -58,16 +78,12 @@ public: Vertex contraction(const Vertex x, const Vertex y); /** \brief Number of maximal simplices. */ - std::size_t num_maximal_simplices() const { - return size; - } + std::size_t num_maximal_simplices() const { return size; } /** \brief Number of vertices. */ - std::size_t num_vertices() const{ - return t0.size(); - } + std::size_t num_vertices() const { return t0.size(); } -private: + private: template void erase_max(const Input_vertex_range &vertex_range); template @@ -77,9 +93,9 @@ private: std::unordered_map gamma0_lbounds; std::unordered_map t0; - bool empty_toplex; // Is the empty simplex a toplex ? + bool empty_toplex; // Is the empty simplex a toplex ? - typedef boost::heap::fibonacci_heap> PriorityQueue; + typedef boost::heap::fibonacci_heap> PriorityQueue; PriorityQueue cleaning_priority; std::unordered_map cp_handles; @@ -88,169 +104,168 @@ private: 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 -void Lazy_toplex_map::insert_independent_simplex(const Input_vertex_range &vertex_range){ - for(const Vertex& v : vertex_range) - if(!gamma0_lbounds.count(v)) gamma0_lbounds.emplace(v,1); - else gamma0_lbounds[v]++; - size_lbound++; - insert_simplex(vertex_range); +void Lazy_toplex_map::insert_independent_simplex(const Input_vertex_range &vertex_range) { + for (const Vertex &v : vertex_range) + if (!gamma0_lbounds.count(v)) + gamma0_lbounds.emplace(v, 1); + else + gamma0_lbounds[v]++; + size_lbound++; + insert_simplex(vertex_range); } template -bool Lazy_toplex_map::insert_simplex(const Input_vertex_range &vertex_range){ - Simplex sigma(vertex_range.begin(),vertex_range.end()); - empty_toplex = (sigma.size()==0); //vérifier la gestion de empty face - Simplex_ptr sptr = std::make_shared(sigma); - bool inserted = false; - for(const Vertex& v : sigma){ - if(!t0.count(v)){ - t0.emplace(v, Simplex_ptr_set()); - auto v_handle = cleaning_priority.push(std::make_pair(0, v)); - cp_handles.emplace(v, v_handle); - } - inserted = t0.at(v).emplace(sptr).second; - cleaning_priority.update(cp_handles.at(v), std::make_pair(t0.at(v).size() - get_gamma0_lbound(v),v)); +bool Lazy_toplex_map::insert_simplex(const Input_vertex_range &vertex_range) { + Simplex sigma(vertex_range.begin(), vertex_range.end()); + // Check empty face management + empty_toplex = (sigma.size() == 0); + Simplex_ptr sptr = std::make_shared(sigma); + bool inserted = false; + for (const Vertex &v : sigma) { + if (!t0.count(v)) { + t0.emplace(v, Simplex_ptr_set()); + auto v_handle = cleaning_priority.push(std::make_pair(0, v)); + cp_handles.emplace(v, v_handle); } - if(inserted) - size++; - if(size > (size_lbound+1) * BETTA) - clean(cleaning_priority.top().second); - return inserted; + inserted = t0.at(v).emplace(sptr).second; + cleaning_priority.update(cp_handles.at(v), std::make_pair(t0.at(v).size() - get_gamma0_lbound(v), v)); + } + if (inserted) size++; + if (size > (size_lbound + 1) * BETTA) clean(cleaning_priority.top().second); + return inserted; } template -void Lazy_toplex_map::remove_simplex(const Input_vertex_range &vertex_range){ - if(vertex_range.begin()==vertex_range.end()){ - t0.clear(); - gamma0_lbounds.clear(); - cleaning_priority.clear(); - size_lbound = 0; - size = 0; - empty_toplex = false; - } - else { - const Vertex& v = best_index(vertex_range); - //Copy constructor needed because the set is modified - if(t0.count(v)) for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))) - if(included(vertex_range, *sptr)){ - erase_max(*sptr); - for(const Simplex& f : facets(vertex_range)) - insert_independent_simplex(f); - } - } +void Lazy_toplex_map::remove_simplex(const Input_vertex_range &vertex_range) { + if (vertex_range.begin() == vertex_range.end()) { + t0.clear(); + gamma0_lbounds.clear(); + cleaning_priority.clear(); + size_lbound = 0; + size = 0; + empty_toplex = false; + } else { + const Vertex &v = best_index(vertex_range); + // Copy constructor needed because the set is modified + if (t0.count(v)) + for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(v))) + if (included(vertex_range, *sptr)) { + erase_max(*sptr); + for (const Simplex &f : facets(vertex_range)) insert_independent_simplex(f); + } + } } template -bool Lazy_toplex_map::membership(const Input_vertex_range &vertex_range){ - if(t0.size()==0 && !empty_toplex) return false; //empty complex - if(vertex_range.begin()==vertex_range.end()) return true; //empty query simplex - Vertex v = best_index(vertex_range); - if(!t0.count(v)) return false; - for(const Simplex_ptr& sptr : t0.at(v)) - if(included(vertex_range, *sptr)) return true; - return false; +bool Lazy_toplex_map::membership(const Input_vertex_range &vertex_range) { + if (t0.size() == 0 && !empty_toplex) return false; // empty complex + if (vertex_range.begin() == vertex_range.end()) return true; // empty query simplex + Vertex v = best_index(vertex_range); + if (!t0.count(v)) return false; + for (const Simplex_ptr &sptr : t0.at(v)) + if (included(vertex_range, *sptr)) return true; + return false; } template -bool Lazy_toplex_map::all_facets_inside(const Input_vertex_range &vertex_range){ - Simplex sigma(vertex_range.begin(),vertex_range.end()); - Vertex v = best_index(sigma); - if(!t0.count(v)) return false; - Simplex f = sigma; f.erase(v); - if(!membership(f)) return false; - std::unordered_set facets_inside; - for(const Simplex_ptr& sptr : t0.at(v)) - for(const Vertex& w : sigma){ - f = sigma; f.erase(w); - if(included(f, *sptr)) facets_inside.insert(w); - } - return facets_inside.size() == sigma.size() - 1; +bool Lazy_toplex_map::all_facets_inside(const Input_vertex_range &vertex_range) { + Simplex sigma(vertex_range.begin(), vertex_range.end()); + Vertex v = best_index(sigma); + if (!t0.count(v)) return false; + Simplex f = sigma; + f.erase(v); + if (!membership(f)) return false; + std::unordered_set facets_inside; + for (const Simplex_ptr &sptr : t0.at(v)) + for (const Vertex &w : sigma) { + f = sigma; + f.erase(w); + if (included(f, *sptr)) facets_inside.insert(w); + } + return facets_inside.size() == sigma.size() - 1; } /* Returns the remaining vertex */ -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; - if(t0.at(x).size() > t0.at(y).size()) - k=x, d=y; - else - k=y, d=x; - //Copy constructor needed because the set is modified - for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))){ - Simplex sigma(*sptr); - erase_max(sigma); - sigma.erase(d); - sigma.insert(k); - insert_simplex(sigma); - } - t0.erase(d); - return k; +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; + if (t0.at(x).size() > t0.at(y).size()) + k = x, d = y; + else + k = y, d = x; + // Copy constructor needed because the set is modified + for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(d))) { + Simplex sigma(*sptr); + erase_max(sigma); + sigma.erase(d); + sigma.insert(k); + insert_simplex(sigma); + } + t0.erase(d); + return k; } /* No facets insert_simplexed */ template -inline void Lazy_toplex_map::erase_max(const Input_vertex_range &vertex_range){ - Simplex sigma(vertex_range.begin(),vertex_range.end()); - empty_toplex = false; - Simplex_ptr sptr = std::make_shared(sigma); - bool erased=false; - for(const Vertex& v : sigma){ - erased = t0.at(v).erase(sptr) > 0; - if(t0.at(v).size()==0) - t0.erase(v); - } - if (erased) - size--; +inline void Lazy_toplex_map::erase_max(const Input_vertex_range &vertex_range) { + Simplex sigma(vertex_range.begin(), vertex_range.end()); + empty_toplex = false; + Simplex_ptr sptr = std::make_shared(sigma); + bool erased = false; + for (const Vertex &v : sigma) { + erased = t0.at(v).erase(sptr) > 0; + if (t0.at(v).size() == 0) t0.erase(v); + } + if (erased) size--; } template 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::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)) - clean(arg_min); - return arg_min; + Simplex tau(vertex_range.begin(), vertex_range.end()); + std::size_t min = std::numeric_limits::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)) clean(arg_min); + return arg_min; } -std::size_t Lazy_toplex_map::get_gamma0_lbound(const Vertex v) const{ - return gamma0_lbounds.count(v) ? gamma0_lbounds.at(v) : 0; +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> dsorted_simplices; - std::size_t max_dim = 0; - for(const Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))){ - if(sptr->size() > max_dim){ - for(std::size_t d = max_dim+1; d<=sptr->size(); d++) - dsorted_simplices.emplace(d, std::vector()); - max_dim = sptr->size(); - } - dsorted_simplices[sptr->size()].emplace_back(*sptr); - erase_max(*sptr); +void Lazy_toplex_map::clean(const Vertex v) { + Toplex_map toplices; + std::unordered_map> dsorted_simplices; + std::size_t max_dim = 0; + for (const Simplex_ptr &sptr : Simplex_ptr_set(t0.at(v))) { + if (sptr->size() > max_dim) { + for (std::size_t d = max_dim + 1; d <= sptr->size(); d++) dsorted_simplices.emplace(d, std::vector()); + max_dim = sptr->size(); } - for(std::size_t d = max_dim; d>=1; d--) - for(const Simplex &s : dsorted_simplices.at(d)) - if(!toplices.membership(s)) - toplices.insert_independent_simplex(s); - Simplex sv; sv.insert(v); - auto clean_cofaces = toplices.maximal_cofaces(sv); - size_lbound = size_lbound - get_gamma0_lbound(v) + clean_cofaces.size(); - gamma0_lbounds[v] = clean_cofaces.size(); - for(const Simplex_ptr& sptr : clean_cofaces) - insert_simplex(*sptr); + dsorted_simplices[sptr->size()].emplace_back(*sptr); + erase_max(*sptr); + } + for (std::size_t d = max_dim; d >= 1; d--) + for (const Simplex &s : dsorted_simplices.at(d)) + if (!toplices.membership(s)) toplices.insert_independent_simplex(s); + Simplex sv; + sv.insert(v); + auto clean_cofaces = toplices.maximal_cofaces(sv); + size_lbound = size_lbound - get_gamma0_lbound(v) + clean_cofaces.size(); + gamma0_lbounds[v] = clean_cofaces.size(); + for (const Simplex_ptr &sptr : clean_cofaces) insert_simplex(*sptr); } -} //namespace Gudhi +} // 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 b7a5db41..3da505f8 100644 --- a/src/Toplex_map/include/gudhi/Toplex_map.h +++ b/src/Toplex_map/include/gudhi/Toplex_map.h @@ -1,3 +1,25 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author: François Godi, Vincent Rouvreau + * + * Copyright (C) 2018 INRIA + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + #ifndef TOPLEX_MAP_H #define TOPLEX_MAP_H @@ -17,9 +39,7 @@ namespace Gudhi { * * \ingroup toplex_map */ class Toplex_map { - -public: - + public: /** Vertex is the type of vertices. */ using Vertex = std::size_t; @@ -33,7 +53,7 @@ public: std::size_t operator()(const Toplex_map::Simplex_ptr& s) const; }; - struct Sptr_equal{ + struct Sptr_equal { std::size_t operator()(const Toplex_map::Simplex_ptr& a, const Toplex_map::Simplex_ptr& b) const; }; @@ -43,26 +63,27 @@ public: /** \brief Adds the given simplex to the complex. * Nothing happens if the simplex has a coface in the complex. */ template - void insert_simplex(const Input_vertex_range &vertex_range); + void 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 - void remove_simplex(const Input_vertex_range &vertex_range); + void remove_simplex(const Input_vertex_range& vertex_range); /** Does a simplex belong to the complex ? */ template - bool membership(const Input_vertex_range &vertex_range) const; + bool membership(const Input_vertex_range& vertex_range) const; /** Does a simplex is a toplex ? */ template - bool maximality(const Input_vertex_range &vertex_range) const; + bool maximality(const Input_vertex_range& vertex_range) const; /** Gives a set of pointers to the maximal cofaces of a simplex. * Gives all the toplices if given the empty simplex. * Gives not more than max_number maximal cofaces if max_number is strictly positive. */ template - Toplex_map::Simplex_ptr_set maximal_cofaces(const Input_vertex_range &vertex_range, const std::size_t max_number = 0) const; + Toplex_map::Simplex_ptr_set maximal_cofaces(const Input_vertex_range& vertex_range, + const std::size_t max_number = 0) const; /** Gives a set of pointers to the maximal simplices. * Gives not more than max_number maximal cofaces if max_number is strictly positive. */ @@ -79,26 +100,22 @@ public: void remove_vertex(const Toplex_map::Vertex x); /** \brief Number of maximal simplices. */ - std::size_t num_maximal_simplices() const { - return maximal_simplices().size(); - } + std::size_t num_maximal_simplices() const { return maximal_simplices().size(); } /** \brief Number of vertices. */ - std::size_t num_vertices() const { - return t0.size(); - } + std::size_t num_vertices() const { return t0.size(); } std::set unitary_collapse(const Toplex_map::Vertex k, const Toplex_map::Vertex d); /** Adds the given simplex to the complex. * The simplex must not have neither maximal face nor coface in the complex. */ template - void insert_independent_simplex(const Input_vertex_range &vertex_range); + void insert_independent_simplex(const Input_vertex_range& vertex_range); -protected: + protected: /** \internal Gives an index in order to look for a simplex quickly. */ template - Toplex_map::Vertex best_index(const Input_vertex_range &vertex_range) const; + Toplex_map::Vertex best_index(const Input_vertex_range& vertex_range) const; /** \internal The map from vertices to toplices */ std::unordered_map t0; @@ -107,219 +124,215 @@ protected: /** \internal Removes a toplex without adding facets after. */ void erase_maximal(const Toplex_map::Simplex_ptr& sptr); - }; // Pointers are also used as key in the hash sets. template -Toplex_map::Simplex_ptr get_key(const Input_vertex_range &vertex_range); +Toplex_map::Simplex_ptr get_key(const Input_vertex_range& vertex_range); // Is the first simplex a face of the second ? template -bool included(const Input_vertex_range1 &vertex_range1, const Input_vertex_range2 &vertex_range2); +bool included(const Input_vertex_range1& vertex_range1, const Input_vertex_range2& vertex_range2); // All the facets of the given simplex. template -std::vector facets(const Input_vertex_range &vertex_range); +std::vector facets(const Input_vertex_range& vertex_range); template -void Toplex_map::insert_simplex(const Input_vertex_range &vertex_range){ - if(membership(vertex_range)) return; - bool replace_facets = true; - for(const Toplex_map::Simplex& facet : facets(vertex_range)) - if(!maximality(facet)) - { - replace_facets=false; - break; - } - if(replace_facets) - for(const Toplex_map::Simplex& facet : facets(vertex_range)) - erase_maximal(get_key(facet)); - else - for(const Toplex_map::Vertex& v : vertex_range) - if(t0.count(v)) for(const Toplex_map::Simplex_ptr& fptr : Simplex_ptr_set(t0.at(v))) - //Copy constructor needed because the set is modified - if(included(*fptr,vertex_range)) erase_maximal(fptr); - // We erase all the maximal faces of the simplex - insert_independent_simplex(vertex_range); +void Toplex_map::insert_simplex(const Input_vertex_range& vertex_range) { + if (membership(vertex_range)) return; + bool replace_facets = true; + for (const Toplex_map::Simplex& facet : facets(vertex_range)) + if (!maximality(facet)) { + replace_facets = false; + break; + } + if (replace_facets) + for (const Toplex_map::Simplex& facet : facets(vertex_range)) erase_maximal(get_key(facet)); + else + for (const Toplex_map::Vertex& v : vertex_range) + if (t0.count(v)) + for (const Toplex_map::Simplex_ptr& fptr : Simplex_ptr_set(t0.at(v))) + // Copy constructor needed because the set is modified + if (included(*fptr, vertex_range)) erase_maximal(fptr); + // We erase all the maximal faces of the simplex + insert_independent_simplex(vertex_range); } template -void Toplex_map::remove_simplex(const Input_vertex_range &vertex_range){ - if(vertex_range.begin()==vertex_range.end()) - t0.clear(); - // Removal of the empty simplex means cleaning everything - else { - const Toplex_map::Vertex& v = best_index(vertex_range); - if(t0.count(v)) for(const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))) - //Copy constructor needed because the set is modified - if(included(vertex_range, *sptr)){ - erase_maximal(sptr); - for(const Toplex_map::Simplex& f : facets(vertex_range)) - if(!membership(f)) insert_independent_simplex(f); - // We add the facets which are new maximal simplices - } - } +void Toplex_map::remove_simplex(const Input_vertex_range& vertex_range) { + if (vertex_range.begin() == vertex_range.end()) t0.clear(); + // Removal of the empty simplex means cleaning everything + else { + const Toplex_map::Vertex& v = best_index(vertex_range); + if (t0.count(v)) + for (const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(v))) + // Copy constructor needed because the set is modified + if (included(vertex_range, *sptr)) { + erase_maximal(sptr); + for (const Toplex_map::Simplex& f : facets(vertex_range)) + if (!membership(f)) insert_independent_simplex(f); + // We add the facets which are new maximal simplices + } + } } template -bool Toplex_map::membership(const Input_vertex_range &vertex_range) const{ - if(t0.size()==0) return false; - const Toplex_map::Vertex& v = best_index(vertex_range); - if(!t0.count(v)) return false; - if(maximality(vertex_range)) return true; - for(const Toplex_map::Simplex_ptr& sptr : t0.at(v)) - if(included(vertex_range, *sptr)) - return true; - return false; +bool Toplex_map::membership(const Input_vertex_range& vertex_range) const { + if (t0.size() == 0) return false; + const Toplex_map::Vertex& v = best_index(vertex_range); + if (!t0.count(v)) return false; + if (maximality(vertex_range)) return true; + for (const Toplex_map::Simplex_ptr& sptr : t0.at(v)) + if (included(vertex_range, *sptr)) return true; + return false; } template -bool Toplex_map::maximality(const Input_vertex_range &vertex_range) const{ - const Toplex_map::Vertex& v = best_index(vertex_range); - if(!t0.count(v)) return false; - return t0.at(v).count(get_key(vertex_range)); +bool Toplex_map::maximality(const Input_vertex_range& vertex_range) const { + const Toplex_map::Vertex& v = best_index(vertex_range); + if (!t0.count(v)) return false; + return t0.at(v).count(get_key(vertex_range)); } template -Toplex_map::Simplex_ptr_set Toplex_map::maximal_cofaces(const Input_vertex_range &vertex_range, const std::size_t max_number) const{ - Simplex_ptr_set cofaces; - if(maximality(vertex_range)) - cofaces.emplace(get_key(vertex_range)); - else if(vertex_range.begin()==vertex_range.end()) - for(const auto& kv : t0) - for(const Toplex_map::Simplex_ptr& sptr : kv.second){ - //kv.second is a Simplex_ptr_set - cofaces.emplace(sptr); - if(cofaces.size()==max_number) - return cofaces; - } - else { - const Toplex_map::Vertex& v = best_index(vertex_range); - if(t0.count(v)) for(const Toplex_map::Simplex_ptr& sptr : t0.at(v)) - if(included(vertex_range, *sptr)){ - cofaces.emplace(sptr); - if(cofaces.size()==max_number) - return cofaces; - } - } - return cofaces; +Toplex_map::Simplex_ptr_set Toplex_map::maximal_cofaces(const Input_vertex_range& vertex_range, + const std::size_t max_number) const { + Simplex_ptr_set cofaces; + if (maximality(vertex_range)) + cofaces.emplace(get_key(vertex_range)); + else if (vertex_range.begin() == vertex_range.end()) + for (const auto& kv : t0) + for (const Toplex_map::Simplex_ptr& sptr : kv.second) { + // kv.second is a Simplex_ptr_set + cofaces.emplace(sptr); + if (cofaces.size() == max_number) return cofaces; + } + else { + const Toplex_map::Vertex& v = best_index(vertex_range); + if (t0.count(v)) + for (const Toplex_map::Simplex_ptr& sptr : t0.at(v)) + if (included(vertex_range, *sptr)) { + cofaces.emplace(sptr); + if (cofaces.size() == max_number) return cofaces; + } + } + return cofaces; } -Toplex_map::Vertex Toplex_map::contraction(const Toplex_map::Vertex x, const Toplex_map::Vertex y){ - if(!t0.count(x)) return y; - if(!t0.count(y)) return x; - int k, d; - if(t0.at(x).size() > t0.at(y).size()) - k=x, d=y; - else - k=y, d=x; - for(const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))){ - //Copy constructor needed because the set is modified - Simplex sigma(*sptr); - erase_maximal(sptr); - sigma.erase(d); - sigma.insert(k); - insert_simplex(sigma); - } - return k; +Toplex_map::Vertex Toplex_map::contraction(const Toplex_map::Vertex x, const Toplex_map::Vertex y) { + if (!t0.count(x)) return y; + if (!t0.count(y)) return x; + int k, d; + if (t0.at(x).size() > t0.at(y).size()) + k = x, d = y; + else + k = y, d = x; + for (const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))) { + // Copy constructor needed because the set is modified + Simplex sigma(*sptr); + erase_maximal(sptr); + sigma.erase(d); + sigma.insert(k); + insert_simplex(sigma); + } + return k; } -std::set Toplex_map::unitary_collapse(const Toplex_map::Vertex k, const Toplex_map::Vertex d){ - std::set r; - for(const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))){ - //Copy constructor needed because the set is modified - Simplex sigma(*sptr); - erase_maximal(sptr); - sigma.erase(d); - for(const Toplex_map::Vertex v : sigma) - r.insert(v); - sigma.insert(k); - insert_simplex(sigma); - } - return r; +std::set Toplex_map::unitary_collapse(const Toplex_map::Vertex k, const Toplex_map::Vertex d) { + std::set r; + for (const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(d))) { + // Copy constructor needed because the set is modified + Simplex sigma(*sptr); + erase_maximal(sptr); + sigma.erase(d); + for (const Toplex_map::Vertex v : sigma) r.insert(v); + sigma.insert(k); + insert_simplex(sigma); + } + return r; } template -void Toplex_map::insert_independent_simplex(const Input_vertex_range &vertex_range){ - auto key = get_key(vertex_range); - for(const Toplex_map::Vertex& v : vertex_range){ - if(!t0.count(v)) t0.emplace(v, Simplex_ptr_set()); - t0.at(v).emplace(key); - } +void Toplex_map::insert_independent_simplex(const Input_vertex_range& vertex_range) { + auto key = get_key(vertex_range); + for (const Toplex_map::Vertex& v : vertex_range) { + if (!t0.count(v)) t0.emplace(v, Simplex_ptr_set()); + t0.at(v).emplace(key); + } } -void Toplex_map::remove_vertex(const Toplex_map::Vertex x){ - for(const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(x))){ - Simplex sigma(*sptr); - erase_maximal(sptr); - sigma.erase(x); - insert_simplex(sigma); - } +void Toplex_map::remove_vertex(const Toplex_map::Vertex x) { + for (const Toplex_map::Simplex_ptr& sptr : Simplex_ptr_set(t0.at(x))) { + Simplex sigma(*sptr); + erase_maximal(sptr); + sigma.erase(x); + insert_simplex(sigma); + } } -inline void Toplex_map::erase_maximal(const Toplex_map::Simplex_ptr& sptr){ - Simplex sigma(*sptr); - if (sptr->size()==0) - 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); - } +inline void Toplex_map::erase_maximal(const Toplex_map::Simplex_ptr& sptr) { + Simplex sigma(*sptr); + if (sptr->size() == 0) 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); + } } template -Toplex_map::Vertex Toplex_map::best_index(const Input_vertex_range &vertex_range) const{ - std::size_t min = std::numeric_limits::max(); - 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) - min = t0.at(v).size(), arg_min = v; - return arg_min; +Toplex_map::Vertex Toplex_map::best_index(const Input_vertex_range& vertex_range) const { + std::size_t min = std::numeric_limits::max(); + 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) + min = t0.at(v).size(), arg_min = v; + return arg_min; } -std::size_t Toplex_map::Sptr_equal::operator()(const Toplex_map::Simplex_ptr& s1, const Toplex_map::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_equal::operator()(const Toplex_map::Simplex_ptr& s1, + const Toplex_map::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 Toplex_map::Simplex_ptr& s) const { - std::hash h_f; - //double hash works better than int hash - size_t h = 0; - for(const Toplex_map::Vertex& v : *s) - h += h_f(static_cast(v)); - return h; + std::hash h_f; + // double hash works better than int hash + size_t h = 0; + for (const Toplex_map::Vertex& v : *s) h += h_f(static_cast(v)); + return h; } template -Toplex_map::Simplex_ptr get_key(const Input_vertex_range &vertex_range){ - Toplex_map::Simplex s(vertex_range.begin(), vertex_range.end()); - return std::make_shared(s); +Toplex_map::Simplex_ptr get_key(const Input_vertex_range& vertex_range) { + Toplex_map::Simplex s(vertex_range.begin(), vertex_range.end()); + return std::make_shared(s); } template -bool included(const Input_vertex_range1 &vertex_range1, const Input_vertex_range2 &vertex_range2){ - Toplex_map::Simplex s2(vertex_range2.begin(), vertex_range2.end()); - for(const Toplex_map::Vertex& v : vertex_range1) - if(!s2.count(v)) return false; - return true; +bool included(const Input_vertex_range1& vertex_range1, const Input_vertex_range2& vertex_range2) { + Toplex_map::Simplex s2(vertex_range2.begin(), vertex_range2.end()); + for (const Toplex_map::Vertex& v : vertex_range1) + if (!s2.count(v)) return false; + return true; } template -std::vector facets(const Input_vertex_range &vertex_range){ - std::vector facets; - Toplex_map::Simplex f(vertex_range.begin(), vertex_range.end()); - for(const Toplex_map::Vertex& v : vertex_range){ - f.erase(v); - facets.emplace_back(f); - f.insert(v); - } - return facets; +std::vector facets(const Input_vertex_range& vertex_range) { + std::vector facets; + Toplex_map::Simplex f(vertex_range.begin(), vertex_range.end()); + for (const Toplex_map::Vertex& v : vertex_range) { + f.erase(v); + facets.emplace_back(f); + f.insert(v); + } + return facets; } -} //namespace Gudhi +} // namespace Gudhi #endif /* TOPLEX_MAP_H */ diff --git a/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp b/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp index 5d71c295..eb1aa0b5 100644 --- a/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp +++ b/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp @@ -1,8 +1,29 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author: François Godi, Vincent Rouvreau + * + * Copyright (C) 2018 INRIA + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + #include #include #include - #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MODULE "lazy toplex map" #include @@ -43,7 +64,7 @@ BOOST_AUTO_TEST_CASE(toplex_map) { BOOST_CHECK(tm.membership(sigma5)); std::cout << "contraction(4,5)" << std::endl; - auto r = tm.contraction(4,5); + auto r = tm.contraction(4, 5); std::cout << "r=" << r << std::endl; BOOST_CHECK(r == 5); @@ -73,6 +94,4 @@ BOOST_AUTO_TEST_CASE(toplex_map) { BOOST_CHECK(tm.membership(edge)); edge = {7, 5}; BOOST_CHECK(tm.membership(edge)); - } - diff --git a/src/Toplex_map/test/toplex_map_unit_test.cpp b/src/Toplex_map/test/toplex_map_unit_test.cpp index 59c104ce..2bd27936 100644 --- a/src/Toplex_map/test/toplex_map_unit_test.cpp +++ b/src/Toplex_map/test/toplex_map_unit_test.cpp @@ -1,8 +1,29 @@ +/* This file is part of the Gudhi Library. The Gudhi library + * (Geometric Understanding in Higher Dimensions) is a generic C++ + * library for computational topology. + * + * Author: François Godi, Vincent Rouvreau + * + * Copyright (C) 2018 INRIA + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + #include #include #include - #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MODULE "toplex map" #include @@ -67,7 +88,7 @@ BOOST_AUTO_TEST_CASE(toplex_map) { BOOST_CHECK(tm.membership(sigma5)); std::cout << "contraction(4,5)" << std::endl; - auto r = tm.contraction(4,5); + auto r = tm.contraction(4, 5); std::cout << "r=" << r << std::endl; BOOST_CHECK(r == 5); @@ -114,6 +135,4 @@ BOOST_AUTO_TEST_CASE(toplex_map) { BOOST_CHECK(tm.membership(edge)); edge = {7, 5}; BOOST_CHECK(tm.membership(edge)); - } - -- cgit v1.2.3 From 11b1de2771b060fb286bf428ac081c07ff73e8ec Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Fri, 16 Nov 2018 08:20:00 +0000 Subject: Doc review : Gamma_0 instead of gamma_0 to be like in the paper toplices is the plural form of toplex (not a set of toplex) git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@3984 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 4cfeebffcbf9006fd98bbf32a8dbd9eb683c9bf5 --- src/Toplex_map/doc/Intro_Toplex_map.h | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/Toplex_map/doc/Intro_Toplex_map.h') diff --git a/src/Toplex_map/doc/Intro_Toplex_map.h b/src/Toplex_map/doc/Intro_Toplex_map.h index 649c27f9..0cfbae03 100644 --- a/src/Toplex_map/doc/Intro_Toplex_map.h +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -34,15 +34,15 @@ namespace Gudhi { * \section toplexmapdefinition Definition * * A Toplex_map is a data structure to represent and store a simplicial complex. A "toplex" is the contraction of - * "top-simplex", also known as a maximal simplex. We will call "toplices" a set of "toplex". + * "top-simplex", also known as a maximal simplex. The plural form of "toplex" will be called "toplices". * * Let's consider a simplicial complex, denote by \f$d\f$ its dimension and by \f$k\f$ its number of maximal simplices. - * Furthermore, denote by \f$\gamma_0\f$ the maximal number of toplices, i.e. maximal simplices, that contain a same + * Furthermore, denote by \f$\Gamma_0\f$ the maximal number of toplices, i.e. maximal simplices, that contain a same * vertex. * * The goal of the Toplex Map is both to represent the complex in optimal O(kd) space and to provide fast standard * operations such as : insertion, removal, contraction of an edge, collapses and membership of a simplex. The time - * needed for these operation is linear or quadratic in \f$\gamma_0\f$ and \f$d\f$. + * needed for these operation is linear or quadratic in \f$\Gamma_0\f$ and \f$d\f$. * * Toplex map is composed firstly of a raw storage of toplices and secondly of a map which associate any vertex to a * set of pointers toward all toplices containing this vertex. -- cgit v1.2.3 From 6f9bbc57d9abb1bd395b7c4d58184ee53656fc72 Mon Sep 17 00:00:00 2001 From: vrouvrea Date: Mon, 18 Feb 2019 17:15:41 +0000 Subject: Add biblio and doc references git-svn-id: svn+ssh://scm.gforge.inria.fr/svnroot/gudhi/branches/toplex_map@4111 636b058d-ea47-450e-bf9e-a15bfbe3eedb Former-commit-id: 42a6e48271d333d604cb5cb0c9c9f1e56b8f1965 --- biblio/bibliography.bib | 34 ++++++++++++++++++++++++++++++++++ src/Toplex_map/doc/Intro_Toplex_map.h | 6 ++++-- 2 files changed, 38 insertions(+), 2 deletions(-) (limited to 'src/Toplex_map/doc/Intro_Toplex_map.h') diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index 16f43d6f..47c6b35b 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -1103,3 +1103,37 @@ language={English} pages = {778--796}, year = {2013} } + +@InProceedings{boissonnat_et_al:LIPIcs:2015:5098, + author = {Jean-Daniel Boissonnat and Karthik C. S. and S{\'e}bastien Tavenas}, + title = {{Building Efficient and Compact Data Structures for Simplicial Complexes}}, + booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, + pages = {642--656}, + series = {Leibniz International Proceedings in Informatics (LIPIcs)}, + ISBN = {978-3-939897-83-5}, + ISSN = {1868-8969}, + year = {2015}, + volume = {34}, + editor = {Lars Arge and J{\'a}nos Pach}, + publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, + address = {Dagstuhl, Germany}, + URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5098}, + URN = {urn:nbn:de:0030-drops-50981}, + doi = {10.4230/LIPIcs.SOCG.2015.642}, + annote = {Keywords: Simplicial complex, Compact data structures, Automaton, NP-hard} +} + +@article{DBLP:journals/corr/BoissonnatS16, + author = {Jean{-}Daniel Boissonnat and + {Karthik {C. S.}}}, + title = {An Efficient Representation for Filtrations of Simplicial Complexes}, + journal = {CoRR}, + volume = {abs/1607.08449}, + year = {2016}, + url = {http://arxiv.org/abs/1607.08449}, + archivePrefix = {arXiv}, + eprint = {1607.08449}, + timestamp = {Mon, 13 Aug 2018 16:46:26 +0200}, + biburl = {https://dblp.org/rec/bib/journals/corr/BoissonnatS16}, + bibsource = {dblp computer science bibliography, https://dblp.org} +} \ No newline at end of file diff --git a/src/Toplex_map/doc/Intro_Toplex_map.h b/src/Toplex_map/doc/Intro_Toplex_map.h index 0cfbae03..a925dc2b 100644 --- a/src/Toplex_map/doc/Intro_Toplex_map.h +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -45,11 +45,13 @@ namespace Gudhi { * needed for these operation is linear or quadratic in \f$\Gamma_0\f$ and \f$d\f$. * * Toplex map is composed firstly of a raw storage of toplices and secondly of a map which associate any vertex to a - * set of pointers toward all toplices containing this vertex. + * set of pointers toward all toplices containing this vertex. The data structure is described in + * \cite boissonnat_et_al:LIPIcs:2015:5098 (aka. Simplex Array List or SAL). * * \image html map.png * - * The performances are a lot better than the `Simplex_tree` as soon you use maximal simplices and not simplices. + * The performances are a lot better than the `Simplex_tree` as soon you use maximal simplices and not simplices + * (cf. \cite DBLP:journals/corr/BoissonnatS16 ). * */ /** @} */ // end defgroup toplex_map -- cgit v1.2.3