diff options
author | Vincent Rouvreau <VincentRouvreau@users.noreply.github.com> | 2019-05-06 15:52:00 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2019-05-06 15:52:00 +0200 |
commit | a33d17ebb1a5f7c830ee155ec2733a0f48211010 (patch) | |
tree | b5f5f39488530941444b278be66384139652e6d1 | |
parent | 145f6084b734c24d594ab7dddf5a664953ca4545 (diff) | |
parent | bd8591187090a59c979947825fe9eff2645161ae (diff) |
Merge pull request #51 from VincentRouvreau/toplex_map
Toplex map
-rw-r--r-- | CMakeLists.txt | 1 | ||||
-rw-r--r-- | biblio/bibliography.bib | 34 | ||||
-rw-r--r-- | src/CMakeLists.txt | 1 | ||||
-rw-r--r-- | src/Tangential_complex/example/example_basic.cpp | 5 | ||||
-rw-r--r-- | src/Toplex_map/benchmark/CMakeLists.txt | 3 | ||||
-rw-r--r-- | src/Toplex_map/benchmark/benchmark_tm.cpp | 137 | ||||
-rw-r--r-- | src/Toplex_map/doc/Intro_Toplex_map.h | 61 | ||||
-rw-r--r-- | src/Toplex_map/doc/map.png | bin | 0 -> 71815 bytes | |||
-rw-r--r-- | src/Toplex_map/example/CMakeLists.txt | 4 | ||||
-rw-r--r-- | src/Toplex_map/example/simple_toplex_map.cpp | 165 | ||||
-rw-r--r-- | src/Toplex_map/include/gudhi/Lazy_toplex_map.h | 271 | ||||
-rw-r--r-- | src/Toplex_map/include/gudhi/Toplex_map.h | 338 | ||||
-rw-r--r-- | src/Toplex_map/test/CMakeLists.txt | 11 | ||||
-rw-r--r-- | src/Toplex_map/test/lazy_toplex_map_unit_test.cpp | 170 | ||||
-rw-r--r-- | src/Toplex_map/test/toplex_map_unit_test.cpp | 138 | ||||
-rw-r--r-- | src/common/doc/main_page.h | 17 |
16 files changed, 1355 insertions, 1 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 76e5b528..9b97947f 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -36,6 +36,7 @@ add_gudhi_module(Skeleton_blocker) add_gudhi_module(Spatial_searching) add_gudhi_module(Subsampling) add_gudhi_module(Tangential_complex) +add_gudhi_module(Toplex_map) add_gudhi_module(Witness_complex) add_gudhi_module(Nerve_GIC) diff --git a/biblio/bibliography.bib b/biblio/bibliography.bib index a8c040ed..be4c2db5 100644 --- a/biblio/bibliography.bib +++ b/biblio/bibliography.bib @@ -1106,3 +1106,37 @@ language={English} doi = "10.1007/s00454-013-9513-1", 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/CMakeLists.txt b/src/CMakeLists.txt index b40d506a..40fdcf2b 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -35,6 +35,7 @@ add_gudhi_module(Skeleton_blocker) add_gudhi_module(Spatial_searching) add_gudhi_module(Subsampling) add_gudhi_module(Tangential_complex) +add_gudhi_module(Toplex_map) add_gudhi_module(Witness_complex) add_gudhi_module(Nerve_GIC) diff --git a/src/Tangential_complex/example/example_basic.cpp b/src/Tangential_complex/example/example_basic.cpp index 4f2b859e..ab35edf0 100644 --- a/src/Tangential_complex/example/example_basic.cpp +++ b/src/Tangential_complex/example/example_basic.cpp @@ -1,5 +1,7 @@ #include <gudhi/Tangential_complex.h> #include <gudhi/sparsify_point_set.h> +//#include <gudhi/Fake_simplex_tree.h> + #include <CGAL/Epick_d.h> #include <CGAL/Random.h> @@ -20,7 +22,7 @@ CGAL::Parallel_tag> TC; int main(void) { const int INTRINSIC_DIM = 2; const int AMBIENT_DIM = 3; - const int NUM_POINTS = 1000; + const int NUM_POINTS = 100; Kernel k; @@ -37,6 +39,7 @@ int main(void) { // Export the TC into a Simplex_tree Gudhi::Simplex_tree<> stree; + //Gudhi::Fake_simplex_tree stree; tc.create_complex(stree); // Display stats about inconsistencies diff --git a/src/Toplex_map/benchmark/CMakeLists.txt b/src/Toplex_map/benchmark/CMakeLists.txt new file mode 100644 index 00000000..2d58a156 --- /dev/null +++ b/src/Toplex_map/benchmark/CMakeLists.txt @@ -0,0 +1,3 @@ +project(Toplex_map_benchmark) + +add_executable(Toplex_map_benchmark benchmark_tm.cpp) diff --git a/src/Toplex_map/benchmark/benchmark_tm.cpp b/src/Toplex_map/benchmark/benchmark_tm.cpp new file mode 100644 index 00000000..eedb442b --- /dev/null +++ b/src/Toplex_map/benchmark/benchmark_tm.cpp @@ -0,0 +1,137 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +#include <iostream> +#include <random> +#include <chrono> + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Toplex_map.h> +#include <gudhi/Lazy_toplex_map.h> + +using namespace Gudhi; + +typedef Toplex_map::Simplex Simplex; +typedef Toplex_map::Vertex Vertex; +typedef std::pair<Simplex_tree<>::Simplex_handle, bool> typePairSimplexBool; + +class ST_wrapper { + public: + void insert_simplex(const Simplex& tau) { + /*std::cout << "insert_simplex - " << simplexTree.num_simplices() << " - "; + for (auto v : tau) + std::cout << v << ", "; + std::cout << std::endl; + */ + simplexTree.insert_simplex_and_subfaces(tau); + } + + 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(); } + + 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; +int nb_membership1 = 4000; +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<std::size_t> dis(1, n); + Simplex s; + while (s.size() < d) s.insert(dis(gen)); + return s; +} + +std::vector<Simplex> r_vector_simplices(int n, int max_d, int m) { + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution<std::size_t> dis(1, max_d); + std::vector<Simplex> v; + for (int i = 0; i < m; i++) v.push_back(random_simplex(n, dis(gen))); + return v; +} + +template <typename complex_type> +void chrono(int n, int d) { + complex_type K; + std::vector<Simplex> simplices_insert_simplex1 = r_vector_simplices(n, d, nb_insert_simplex1); + std::vector<Simplex> simplices_membership1 = r_vector_simplices(n, d, nb_membership1); + std::vector<Simplex> simplices_insert_simplex2 = r_vector_simplices(n - 2 * nb_contraction, d, nb_insert_simplex2); + std::vector<Simplex> simplices_membership2 = r_vector_simplices(n - 2 * nb_contraction, d, nb_membership2); + std::chrono::time_point<std::chrono::system_clock> 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<std::chrono::milliseconds>(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<std::chrono::milliseconds>(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<std::chrono::milliseconds>(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<Toplex_map>(n, d); + std::cout << "Lazy \t \t"; + chrono<Lazy_toplex_map>(n, d); + if (d <= 15) { + std::cout << "ST \t \t"; + chrono<ST_wrapper>(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 new file mode 100644 index 00000000..a925dc2b --- /dev/null +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -0,0 +1,61 @@ +/* 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) 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 <http://www.gnu.org/licenses/>. + */ + +#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 { + +/** \defgroup toplex_map Toplex Map + * + * \author François Godi + * @{ + * + * \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. 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 + * 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$. + * + * 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. 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 + * (cf. \cite DBLP:journals/corr/BoissonnatS16 ). + * + */ +/** @} */ // end defgroup toplex_map + +} // namespace Gudhi + +#endif // DOC_TOPLEX_MAP_INTRO_TOPLEX_MAP_H_ diff --git a/src/Toplex_map/doc/map.png b/src/Toplex_map/doc/map.png Binary files differnew file mode 100644 index 00000000..0f9cde2b --- /dev/null +++ b/src/Toplex_map/doc/map.png diff --git a/src/Toplex_map/example/CMakeLists.txt b/src/Toplex_map/example/CMakeLists.txt new file mode 100644 index 00000000..1d54fe87 --- /dev/null +++ b/src/Toplex_map/example/CMakeLists.txt @@ -0,0 +1,4 @@ +project(Toplex_map_examples) + +add_executable(Toplex_map_example_simple_toplex_map simple_toplex_map.cpp) +add_test(NAME Toplex_map_example_simple_toplex_map COMMAND $<TARGET_FILE:Toplex_map_example_simple_toplex_map>) diff --git a/src/Toplex_map/example/simple_toplex_map.cpp b/src/Toplex_map/example/simple_toplex_map.cpp new file mode 100644 index 00000000..e1c12ed6 --- /dev/null +++ b/src/Toplex_map/example/simple_toplex_map.cpp @@ -0,0 +1,165 @@ +/* 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(s): Vincent Rouvreau + * + * Copyright (C) 2018 + * + * 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 <http://www.gnu.org/licenses/>. + */ + +#include <gudhi/Toplex_map.h> + +#include <iostream> +#include <utility> // for pair +#include <vector> +#include <cassert> + +int main(int argc, char* const argv[]) { + using Simplex = Gudhi::Toplex_map::Simplex; + Simplex sigma1 = {1, 2, 3}; + Simplex sigma2 = {2, 3, 4, 5}; + + Gudhi::Toplex_map tm; + tm.insert_simplex(sigma1); + tm.insert_simplex(sigma2); + + /* Simplex is: */ + /* 2 4 */ + /* o---o */ + /* /X\5/ */ + /* o---o */ + /* 1 3 */ + + std::cout << "num max simplices = " << tm.num_maximal_simplices() << " - num vertices = " << tm.num_vertices() + << std::endl; + + // Browse maximal cofaces + Simplex sigma3 = {2, 3}; + std::cout << "Maximal cofaces of {2, 3} are :" << std::endl; + for (auto simplex_ptr : tm.maximal_cofaces(sigma3, 2)) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + } + + // Browse maximal simplices + std::cout << "Maximal simplices are :" << std::endl; + for (auto simplex_ptr : tm.maximal_simplices()) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + } + + Simplex sigma4 = {1, 3}; + assert(tm.membership(sigma4)); + + Gudhi::Toplex_map::Vertex v = tm.contraction(1, 3); + std::cout << "After contraction(1, 3) - " << v << std::endl; + /* Simplex is: */ + /* 2 4 */ + /* o---o */ + /* \5/ */ + /* o */ + /* 3 */ + 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; + for (auto simplex_ptr : tm.maximal_simplices()) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + } + + Simplex sigma5 = {3, 4}; + assert(tm.membership(sigma5)); + + v = tm.contraction(3, 4); + std::cout << "After contraction(3, 4) - " << v << std::endl; + /* Simplex is: */ + /* 2 4 */ + /* o---o */ + /* \X/ */ + /* o */ + /* 5 */ + 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; + for (auto simplex_ptr : tm.maximal_simplices()) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + } + + tm.insert_simplex(sigma1); + tm.insert_simplex(sigma2); + /* Simplex is: */ + /* 2 4 */ + /* o---o */ + /* /X\5/ */ + /* o---o */ + /* 1 3 */ + tm.remove_simplex(sigma1); + + std::cout << "After remove_simplex(1, 2, 3)" << std::endl; + /* Simplex is: */ + /* 2 4 */ + /* o---o */ + /* / \5/ */ + /* o---o */ + /* 1 3 */ + 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; + for (auto simplex_ptr : tm.maximal_simplices()) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + } + + tm.remove_vertex(1); + + std::cout << "After remove_vertex(1)" << std::endl; + /* Simplex is: */ + /* 2 4 */ + /* o---o */ + /* \5/ */ + /* o */ + /* 3 */ + 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; + for (auto simplex_ptr : tm.maximal_simplices()) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + } + + return 0; +} diff --git a/src/Toplex_map/include/gudhi/Lazy_toplex_map.h b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h new file mode 100644 index 00000000..b0b3706e --- /dev/null +++ b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h @@ -0,0 +1,271 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef LAZY_TOPLEX_MAP_H +#define LAZY_TOPLEX_MAP_H + +#include <gudhi/Toplex_map.h> +#include <boost/heap/fibonacci_heap.hpp> + +namespace Gudhi { + +/** + * \brief Lazy toplex map data structure for representing unfiltered simplicial complexes. + * + * \details A Toplex_map is an unordered map from vertices to maximal simplices (aka. toplices). + * The lazy version is not always up to date as it requires clean operation in order to be. + * + * \ingroup toplex_map */ +class Lazy_toplex_map { + public: + /** Vertex is the type of vertices. */ + using Vertex = Toplex_map::Vertex; + + /** Simplex is the type of simplices. */ + using Simplex = Toplex_map::Simplex; + + /** The type of the pointers to maximal simplices. */ + using Simplex_ptr = Toplex_map::Simplex_ptr; + + /** The type of the sets of Simplex_ptr. */ + using Simplex_ptr_set = Toplex_map::Simplex_ptr_set; + + /** Adds the given simplex to the complex. + * The simplex must not be in the complex already, and it must not contain one of the current toplices. */ + template <typename Input_vertex_range> + void insert_independent_simplex(const Input_vertex_range &vertex_range); + + /** \brief Adds the given simplex to the complex. + * Nothing happens if the simplex is already in the complex (i.e. it is a face of one of the toplices). */ + template <typename Input_vertex_range> + bool 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 <typename Input_vertex_range> + void remove_simplex(const Input_vertex_range &vertex_range); + + /** Does a simplex belong to the complex ? */ + template <typename Input_vertex_range> + bool membership(const Input_vertex_range &vertex_range); + + /** Do all the facets of a simplex belong to the complex ? */ + template <typename Input_vertex_range> + bool all_facets_inside(const Input_vertex_range &vertex_range); + + /** Contracts one edge in the complex. + * The edge has to verify the link condition if you want to preserve topology. + * Returns the remaining vertex. */ + Vertex contraction(const Vertex x, const Vertex y); + + /** \brief Number of maximal simplices. */ + std::size_t num_maximal_simplices() const { return size; } + + /** \brief Number of vertices. */ + std::size_t num_vertices() const { return t0.size(); } + + private: + template <typename Input_vertex_range> + void erase_max(const Input_vertex_range &vertex_range); + template <typename Input_vertex_range> + Vertex best_index(const Input_vertex_range &vertex_range); + void clean(const Vertex v); + + std::unordered_map<Vertex, std::size_t> gamma0_lbounds; + + std::unordered_map<Vertex, Simplex_ptr_set> t0; + bool empty_toplex; // Is the empty simplex a toplex ? + + typedef boost::heap::fibonacci_heap<std::pair<std::size_t, Vertex>> PriorityQueue; + PriorityQueue cleaning_priority; + std::unordered_map<Vertex, PriorityQueue::handle_type> cp_handles; + + std::size_t get_gamma0_lbound(const Vertex v) const; + + std::size_t size_lbound = 0; + std::size_t size = 0; + + const double ALPHA = 4; // time + const double BETTA = 8; // memory +}; + +template <typename Input_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 <typename Input_vertex_range> +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<Simplex>(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)); + } + if (inserted) size++; + if (size > (size_lbound + 1) * BETTA) clean(cleaning_priority.top().second); + return inserted; +} + +template <typename Input_vertex_range> +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 <typename Input_vertex_range> +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 <typename Input_vertex_range> +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<Vertex> 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; +} + +/* No facets insert_simplexed */ +template <typename Input_vertex_range> +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<Simplex>(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 <typename Input_vertex_range> +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<size_t>::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; +} + +void Lazy_toplex_map::clean(const Vertex v) { + Toplex_map toplices; + std::unordered_map<int, std::vector<Simplex>> 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<Simplex>()); + max_dim = sptr->size(); + } + 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 + +#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 new file mode 100644 index 00000000..4dc2331f --- /dev/null +++ b/src/Toplex_map/include/gudhi/Toplex_map.h @@ -0,0 +1,338 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +#ifndef TOPLEX_MAP_H +#define TOPLEX_MAP_H + +#include <vector> +#include <set> +#include <unordered_set> +#include <unordered_map> +#include <memory> +#include <limits> + +namespace Gudhi { + +/** + * \brief Toplex map data structure for representing unfiltered simplicial complexes. + * + * \details A Toplex_map is an unordered map from vertices to maximal simplices (aka. toplices). + * + * \ingroup toplex_map */ +class Toplex_map { + public: + /** Vertex is the type of vertices. */ + using Vertex = std::size_t; + + /** Simplex is the type of simplices. */ + using Simplex = std::set<Vertex>; + + /** The type of the pointers to maximal simplices. */ + using Simplex_ptr = std::shared_ptr<Toplex_map::Simplex>; + + struct Sptr_hash { + std::size_t operator()(const Toplex_map::Simplex_ptr& s) const; + }; + + struct Sptr_equal { + std::size_t operator()(const Toplex_map::Simplex_ptr& a, const Toplex_map::Simplex_ptr& b) const; + }; + + /** The type of the sets of Toplex_map::Simplex_ptr. */ + using Simplex_ptr_set = std::unordered_set<Toplex_map::Simplex_ptr, Sptr_hash, Sptr_equal>; + + /** \brief Adds the given simplex to the complex. + * Nothing happens if the simplex is already in the complex (i.e. it is a face of one of the toplices). */ + template <typename Input_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 <typename Input_vertex_range> + void remove_simplex(const Input_vertex_range& vertex_range); + + /** Does a simplex belong to the complex ? */ + template <typename Input_vertex_range> + bool membership(const Input_vertex_range& vertex_range) const; + + /** Does a simplex is a toplex ? */ + template <typename Input_vertex_range> + 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 <typename Input_vertex_range> + 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. */ + Toplex_map::Simplex_ptr_set maximal_simplices(const std::size_t max_number = 0) const { + return maximal_cofaces(Simplex(), max_number); + } + + /** Contracts one edge in the complex. + * The edge has to verify the link condition if you want to preserve topology. + * Returns the remaining vertex. */ + Vertex contraction(const Vertex x, const Vertex y); + + /** Remove the vertex and all its cofaces from the complex. */ + void remove_vertex(const Vertex x); + + /** \brief Number of maximal simplices. */ + 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::set<Vertex> unitary_collapse(const Vertex k, const Vertex d); + + /** Adds the given simplex to the complex. + * The simplex must not be in the complex already, and it must not contain one of the current toplices. */ + template <typename Input_vertex_range> + void insert_independent_simplex(const Input_vertex_range& vertex_range); + + protected: + /** \internal Gives an index in order to look for a simplex quickly. */ + template <typename Input_vertex_range> + Vertex best_index(const Input_vertex_range& vertex_range) const; + + /** \internal The map from vertices to toplices */ + std::unordered_map<Vertex, Toplex_map::Simplex_ptr_set> t0; + + const Vertex VERTEX_UPPER_BOUND = std::numeric_limits<Vertex>::max(); + + /** \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 <typename Input_vertex_range> +Toplex_map::Simplex_ptr get_key(const Input_vertex_range& vertex_range); + +// Is the first simplex a face of the second ? +template <typename Input_vertex_range1, typename Input_vertex_range2> +bool included(const Input_vertex_range1& vertex_range1, const Input_vertex_range2& vertex_range2); + +// All the facets of the given simplex. +template <typename Input_vertex_range> +std::vector<Toplex_map::Simplex> facets(const Input_vertex_range& vertex_range); + +template <typename Input_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 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 <typename Input_vertex_range> +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 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 <typename Input_vertex_range> +bool Toplex_map::membership(const Input_vertex_range& vertex_range) const { + if (t0.size() == 0) return false; + const 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 <typename Input_vertex_range> +bool Toplex_map::maximality(const Input_vertex_range& vertex_range) const { + const Vertex& v = best_index(vertex_range); + if (!t0.count(v)) return false; + return t0.at(v).count(get_key(vertex_range)); +} + +template <typename Input_vertex_range> +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 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; +} + +std::set<Toplex_map::Vertex> Toplex_map::unitary_collapse(const Toplex_map::Vertex k, const Toplex_map::Vertex d) { + Toplex_map::Simplex 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 Vertex v : sigma) r.insert(v); + sigma.insert(k); + insert_simplex(sigma); + } + return r; +} + +template <typename Input_vertex_range> +void Toplex_map::insert_independent_simplex(const Input_vertex_range& vertex_range) { + auto key = get_key(vertex_range); + for (const 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); + } +} + +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 Vertex& v : sigma) { + t0.at(v).erase(sptr); + if (t0.at(v).size() == 0) t0.erase(v); + } +} + +template <typename Input_vertex_range> +Toplex_map::Vertex Toplex_map::best_index(const Input_vertex_range& vertex_range) const { + std::size_t min = std::numeric_limits<size_t>::max(); + Vertex arg_min = VERTEX_UPPER_BOUND; + for (const 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_hash::operator()(const Toplex_map::Simplex_ptr& s) const { + std::hash<double> h_f; + // double hash works better than int hash + size_t h = 0; + for (const Vertex& v : *s) h += h_f(static_cast<double>(v)); + return h; +} + +template <typename Input_vertex_range> +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<Toplex_map::Simplex>(s); +} + +template <typename Input_vertex_range1, typename Input_vertex_range2> +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 <typename Input_vertex_range> +std::vector<Toplex_map::Simplex> facets(const Input_vertex_range& vertex_range) { + std::vector<Toplex_map::Simplex> 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 + +#endif /* TOPLEX_MAP_H */ diff --git a/src/Toplex_map/test/CMakeLists.txt b/src/Toplex_map/test/CMakeLists.txt new file mode 100644 index 00000000..59517db5 --- /dev/null +++ b/src/Toplex_map/test/CMakeLists.txt @@ -0,0 +1,11 @@ +project(Toplex_map_tests) + +include(GUDHI_test_coverage) + +add_executable( Toplex_map_unit_test toplex_map_unit_test.cpp ) +target_link_libraries(Toplex_map_unit_test ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +gudhi_add_coverage_test(Toplex_map_unit_test) + +add_executable( Lazy_toplex_map_unit_test lazy_toplex_map_unit_test.cpp ) +target_link_libraries(Lazy_toplex_map_unit_test ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) +gudhi_add_coverage_test(Lazy_toplex_map_unit_test) diff --git a/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp b/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp new file mode 100644 index 00000000..a050cc92 --- /dev/null +++ b/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp @@ -0,0 +1,170 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +#include <iostream> +#include <vector> +#include <gudhi/Lazy_toplex_map.h> + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "lazy toplex map" +#include <boost/test/unit_test.hpp> + +BOOST_AUTO_TEST_CASE(toplex_map) { + using Vertex = Gudhi::Lazy_toplex_map::Vertex; + + Gudhi::Lazy_toplex_map tm; + std::cout << "insert_simplex {1, 2, 3, 4}" << std::endl; + std::vector<Vertex> sigma1 = {1, 2, 3, 4}; + tm.insert_simplex(sigma1); + std::cout << "insert_simplex {5, 2, 3, 6}" << std::endl; + std::vector<Vertex> sigma2 = {5, 2, 3, 6}; + tm.insert_simplex(sigma2); + std::cout << "insert_simplex {5}" << std::endl; + std::vector<Vertex> sigma3 = {5}; + tm.insert_simplex(sigma3); + std::cout << "insert_simplex {4, 5, 3}" << std::endl; + std::vector<Vertex> sigma6 = {4, 5, 3}; + tm.insert_simplex(sigma6); + std::cout << "insert_simplex {4, 5, 9}" << std::endl; + std::vector<Vertex> sigma7 = {4, 5, 9}; + tm.insert_simplex(sigma7); + + std::cout << "num_maximal_simplices = " << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 5); + + std::vector<Vertex> sigma4 = {5, 2, 3}; + std::vector<Vertex> sigma5 = {5, 2, 7}; + BOOST_CHECK(tm.membership(sigma4)); + BOOST_CHECK(!tm.membership(sigma5)); + std::cout << "insert_simplex {5, 2, 7}" << std::endl; + tm.insert_simplex(sigma5); + + std::cout << "num_maximal_simplices = " << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 6); + + BOOST_CHECK(tm.membership(sigma5)); + + std::cout << "contraction(4,5)" << std::endl; + auto r = tm.contraction(4, 5); + std::cout << "r=" << r << std::endl; + BOOST_CHECK(r == 5); + + std::cout << "num_maximal_simplices = " << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 6); + + std::vector<Vertex> sigma8 = {1, 2, 3}; + std::vector<Vertex> sigma9 = {2, 7}; + + sigma8.emplace_back(r); + sigma9.emplace_back(r); + BOOST_CHECK(!tm.membership(sigma6)); + BOOST_CHECK(tm.membership(sigma8)); + BOOST_CHECK(tm.membership(sigma9)); + + std::cout << "remove_simplex({2, 7, r = 5})" << std::endl; + tm.remove_simplex(sigma9); + BOOST_CHECK(!tm.membership(sigma9)); + + std::cout << "num_maximal_simplices = " << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 8); + + // {2, 7, 5} is removed, but verify its edges are still there + std::vector<Vertex> edge = {2, 7}; + BOOST_CHECK(tm.membership(edge)); + edge = {2, 5}; + BOOST_CHECK(tm.membership(edge)); + edge = {7, 5}; + BOOST_CHECK(tm.membership(edge)); +} + +BOOST_AUTO_TEST_CASE(toplex_map_empty_toplex) { + using Vertex = Gudhi::Lazy_toplex_map::Vertex; + + Gudhi::Lazy_toplex_map tm; + std::cout << "num_maximal_simplices = " << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 0); + std::cout << "num_vertices = " << tm.num_vertices() << std::endl; + BOOST_CHECK(tm.num_vertices() == 0); + + std::cout << "Check an empty simplex is a member." << std::endl; + std::vector<Vertex> empty_sigma = {}; + BOOST_CHECK(tm.membership(empty_sigma)); + + std::cout << "Check the edge 2,7 is not a member." << std::endl; + std::vector<Vertex> edge = {2, 7}; + BOOST_CHECK(!tm.membership(edge)); + + std::cout << "Insert an empty simplex." << std::endl; + tm.insert_simplex(empty_sigma); + + std::cout << "num_maximal_simplices = " << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 0); + std::cout << "num_vertices = " << tm.num_vertices() << std::endl; + BOOST_CHECK(tm.num_vertices() == 0); + + std::cout << "Check an empty simplex is a member." << std::endl; + BOOST_CHECK(tm.membership(empty_sigma)); + std::cout << "Check the edge 2,7 is not a member." << std::endl; + BOOST_CHECK(!tm.membership(edge)); + + std::cout << "Insert edge 2,7." << std::endl; + tm.insert_simplex(edge); + + std::cout << "num_maximal_simplices = " << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 1); + std::cout << "num_vertices = " << tm.num_vertices() << std::endl; + BOOST_CHECK(tm.num_vertices() == 2); + + std::cout << "Check an empty simplex is a member." << std::endl; + BOOST_CHECK(tm.membership(empty_sigma)); + std::cout << "Check the edge 2,7 is a member." << std::endl; + BOOST_CHECK(tm.membership(edge)); + + std::cout << "contraction(2,7)" << std::endl; + auto r = tm.contraction(2, 7); + std::cout << "r=" << r << std::endl; + BOOST_CHECK(r == 7); + + std::cout << "num_maximal_simplices = " << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 1); + std::cout << "num_vertices = " << tm.num_vertices() << std::endl; + BOOST_CHECK(tm.num_vertices() == 1); + + std::cout << "Check an empty simplex is a member." << std::endl; + BOOST_CHECK(tm.membership(empty_sigma)); + std::cout << "Check the edge 2,7 is not a member." << std::endl; + BOOST_CHECK(!tm.membership(edge)); + + std::cout << "Remove the vertex 7." << std::endl; + std::vector<Vertex> vertex = {7}; + tm.remove_simplex(vertex); + + std::cout << "num_maximal_simplices = " << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 0); + std::cout << "num_vertices = " << tm.num_vertices() << std::endl; + BOOST_CHECK(tm.num_vertices() == 0); + + std::cout << "Check an empty simplex is a member." << std::endl; + BOOST_CHECK(tm.membership(empty_sigma)); + std::cout << "Check the edge 2,7 is not a member." << std::endl; + 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 new file mode 100644 index 00000000..2bd27936 --- /dev/null +++ b/src/Toplex_map/test/toplex_map_unit_test.cpp @@ -0,0 +1,138 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +#include <iostream> +#include <vector> +#include <gudhi/Toplex_map.h> + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "toplex map" +#include <boost/test/unit_test.hpp> + +BOOST_AUTO_TEST_CASE(toplex_map) { + using Vertex = Gudhi::Toplex_map::Vertex; + + Gudhi::Toplex_map tm; + std::cout << "insert_simplex {1, 2, 3, 4}" << std::endl; + std::vector<Vertex> sigma1 = {1, 2, 3, 4}; + tm.insert_simplex(sigma1); + std::cout << "insert_simplex {5, 2, 3, 6}" << std::endl; + std::vector<Vertex> sigma2 = {5, 2, 3, 6}; + tm.insert_simplex(sigma2); + std::cout << "insert_simplex {5}" << std::endl; + std::vector<Vertex> sigma3 = {5}; + tm.insert_simplex(sigma3); + std::cout << "insert_simplex {4, 5, 3}" << std::endl; + std::vector<Vertex> sigma6 = {4, 5, 3}; + tm.insert_simplex(sigma6); + std::cout << "insert_simplex {4, 5, 9}" << std::endl; + std::vector<Vertex> sigma7 = {4, 5, 9}; + tm.insert_simplex(sigma7); + + std::cout << "num_maximal_simplices" << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 4); + // Browse maximal simplices + std::cout << "Maximal simplices are :" << std::endl; + for (auto simplex_ptr : tm.maximal_simplices()) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + BOOST_CHECK(tm.maximality(*simplex_ptr)); + } + + BOOST_CHECK(tm.maximality(sigma1)); + BOOST_CHECK(tm.maximality(sigma2)); + BOOST_CHECK(!tm.maximality(sigma3)); + BOOST_CHECK(tm.maximality(sigma6)); + BOOST_CHECK(tm.maximality(sigma7)); + + std::vector<Vertex> sigma4 = {5, 2, 3}; + std::vector<Vertex> sigma5 = {5, 2, 7}; + BOOST_CHECK(tm.membership(sigma4)); + BOOST_CHECK(!tm.membership(sigma5)); + std::cout << "insert_simplex {5, 2, 7}" << std::endl; + tm.insert_simplex(sigma5); + + std::cout << "num_maximal_simplices" << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 5); + // Browse maximal simplices + std::cout << "Maximal simplices are :" << std::endl; + for (auto simplex_ptr : tm.maximal_simplices()) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + BOOST_CHECK(tm.maximality(*simplex_ptr)); + } + + BOOST_CHECK(tm.membership(sigma5)); + + std::cout << "contraction(4,5)" << std::endl; + auto r = tm.contraction(4, 5); + std::cout << "r=" << r << std::endl; + BOOST_CHECK(r == 5); + + std::cout << "num_maximal_simplices" << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 4); + // Browse maximal simplices + std::cout << "Maximal simplices are :" << std::endl; + for (auto simplex_ptr : tm.maximal_simplices()) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + BOOST_CHECK(tm.maximality(*simplex_ptr)); + } + + std::vector<Vertex> sigma8 = {1, 2, 3}; + std::vector<Vertex> sigma9 = {2, 7}; + + sigma8.emplace_back(r); + sigma9.emplace_back(r); + BOOST_CHECK(!tm.membership(sigma6)); + BOOST_CHECK(tm.membership(sigma8)); + BOOST_CHECK(tm.membership(sigma9)); + + std::cout << "remove_simplex({2, 7, r = 5})" << std::endl; + tm.remove_simplex(sigma9); + BOOST_CHECK(!tm.membership(sigma9)); + + std::cout << "num_maximal_simplices" << tm.num_maximal_simplices() << std::endl; + BOOST_CHECK(tm.num_maximal_simplices() == 5); + // Browse maximal simplices + std::cout << "Maximal simplices are :" << std::endl; + for (auto simplex_ptr : tm.maximal_simplices()) { + for (auto v : *simplex_ptr) { + std::cout << v << ", "; + } + std::cout << std::endl; + BOOST_CHECK(tm.maximality(*simplex_ptr)); + } + // {2, 7, 5} is removed, but verify its edges are still there + std::vector<Vertex> edge = {2, 7}; + BOOST_CHECK(tm.membership(edge)); + edge = {2, 5}; + BOOST_CHECK(tm.membership(edge)); + edge = {7, 5}; + BOOST_CHECK(tm.membership(edge)); +} diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index b33a95a1..afe9b68c 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -171,6 +171,23 @@ </td> </tr> </table> + \subsection ToplexMapDataStructure Toplex Map + \image html "map.png" "Toplex map representation" +<table border="0"> + <tr> + <td width="25%"> + <b>Author:</b> François Godi<br> + <b>Introduced in:</b> GUDHI 2.1.0<br> + <b>Copyright:</b> GPL v3<br> + </td> + <td width="75%"> + The Toplex map data structure is composed firstly of a raw storage of toplices (the maximal simplices) + and secondly of a map which associate any vertex to a set of pointers toward all toplices + containing this vertex. + <b>User manual:</b> \ref toplex_map - <b>Reference manual:</b> Gudhi::Toplex_map + </td> + </tr> + \subsection WitnessComplexDataStructure Witness complex \image html "Witness_complex_representation.png" "Witness complex representation" <table border="0"> |