diff options
| -rw-r--r-- | CMakeLists.txt | 1 | ||||
| -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 | 4 | ||||
| -rw-r--r-- | src/Toplex_map/benchmark/chrono.cpp | 139 | ||||
| -rw-r--r-- | src/Toplex_map/doc/Intro_Toplex_map.h | 62 | ||||
| -rw-r--r-- | src/Toplex_map/doc/map.png | bin | 0 -> 278692 bytes | |||
| -rw-r--r-- | src/Toplex_map/example/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | src/Toplex_map/example/Fake_simplex_tree.h | 188 | ||||
| -rw-r--r-- | src/Toplex_map/example/Simple_toplex_map.cpp | 218 | ||||
| -rw-r--r-- | src/Toplex_map/example/Toplex_map_from_cliques_of_graph.cpp | 93 | ||||
| -rw-r--r-- | src/Toplex_map/include/gudhi/Filtered_toplex_map.h | 84 | ||||
| -rw-r--r-- | src/Toplex_map/include/gudhi/Lazy_Toplex_map.h | 263 | ||||
| -rw-r--r-- | src/Toplex_map/include/gudhi/Toplex_map.h | 322 | ||||
| -rw-r--r-- | src/Toplex_map/test/CMakeLists.txt | 14 | ||||
| -rw-r--r-- | src/Toplex_map/test/toplex_map_unit_test.cpp | 54 | ||||
| -rw-r--r-- | src/common/doc/main_page.h | 17 |
17 files changed, 1469 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/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..2c67892c --- /dev/null +++ b/src/Toplex_map/benchmark/CMakeLists.txt @@ -0,0 +1,4 @@ +cmake_minimum_required(VERSION 2.6) +project(Toplex_map_benchmark) + +add_executable(toplex_map_chrono chrono.cpp) diff --git a/src/Toplex_map/benchmark/chrono.cpp b/src/Toplex_map/benchmark/chrono.cpp new file mode 100644 index 00000000..a745f099 --- /dev/null +++ b/src/Toplex_map/benchmark/chrono.cpp @@ -0,0 +1,139 @@ +#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); + 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, 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 = 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<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(); + + 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<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..e3f18b32 --- /dev/null +++ b/src/Toplex_map/doc/Intro_Toplex_map.h @@ -0,0 +1,62 @@ +/* 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 <http://www.gnu.org/licenses/>. + */ + +#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 \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$. + * + * 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 + * + * 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 + +} // namespace Gudhi + +#endif // DOC_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..d1987043 --- /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..051d7bcd --- /dev/null +++ b/src/Toplex_map/example/CMakeLists.txt @@ -0,0 +1,5 @@ +cmake_minimum_required(VERSION 2.6) +project(Toplex_map_examples) + +add_executable(Toplex_map_example_simple Simple_toplex_map.cpp) +add_executable(Toplex_map_example_from_cliques_of_graph Toplex_map_from_cliques_of_graph.cpp) diff --git a/src/Toplex_map/example/Fake_simplex_tree.h b/src/Toplex_map/example/Fake_simplex_tree.h new file mode 100644 index 00000000..6a7e7bdc --- /dev/null +++ b/src/Toplex_map/example/Fake_simplex_tree.h @@ -0,0 +1,188 @@ +#ifndef FAKE_SIMPLEX_TREE_H +#define FAKE_SIMPLEX_TREE_H + +#include <cmath> + +#include <gudhi/Simplex_tree.h> +#include <gudhi/Filtered_toplex_map.h> + +#include <boost/graph/adjacency_list.hpp> +#include <boost/graph/bron_kerbosch_all_cliques.hpp> + +namespace Gudhi { + +struct Visitor { + Toplex_map* tm; + + Visitor(Toplex_map* tm) + :tm(tm) + {} + + template <typename Clique, typename Graph> + void clique(const Clique& c, const Graph& g) + { + tm->insert_simplex(c); + } +}; + +/** Fake_simplex_tree is a wrapper for Filtered_toplex_map which has the interface of the Simplex_tree. + * Mostly for retro-compatibility purpose. If you use a function that output non maximal simplices, it will be non efficient. + * \ingroup toplex_map */ +class Fake_simplex_tree : public Filtered_toplex_map { + +public: + + /** Handle type to a vertex contained in the simplicial complex. + * \ingroup toplex_map */ + typedef Toplex_map::Vertex Vertex_handle; + + /** Handle type to a simplex contained in the simplicial complex. + * \ingroup toplex_map */ + typedef Toplex_map::Simplex Simplex_handle; + + typedef void Insertion_result_type; + + /** Inserts the flag complex of a given range `Gudhi::rips_complex::Rips_complex::OneSkeletonGraph` + * in the simplicial complex. + * \ingroup toplex_map */ + template<class OneSkeletonGraph> + void insert_graph(const OneSkeletonGraph& skel_graph); + + /** Do actually nothing. + * \ingroup toplex_map */ + void expansion(int max_dim); + + /** Returns the number of vertices stored i.e. the number of max simplices + * \ingroup toplex_map */ + std::size_t num_vertices() const; + + /** Returns the dimension of the complex. + * \ingroup toplex_map */ + std::size_t dimension() const; + + /** Returns the dimension of a given simplex in the complex. + * \ingroup toplex_map */ + std::size_t dimension(Simplex_ptr& sptr) const; + + /** Returns the number of simplices stored i.e. the number of maximal simplices. + * \ingroup toplex_map */ + std::size_t num_simplices() const; + + /** Returns a range over the vertices of a simplex. + * \ingroup toplex_map */ + Toplex_map::Simplex simplex_vertex_range(const Simplex& s) const; + + /** Returns a set of all maximal (critical if there is filtration values) simplices. + * \ingroup toplex_map */ + std::vector<Toplex_map::Simplex> max_simplices() const; + + /** Returns all the simplices, of max dimension d if a parameter d is given. + * \ingroup toplex_map */ + std::vector<Toplex_map::Simplex> filtration_simplex_range(int d=std::numeric_limits<int>::max()) const; + + /** Returns all the simplices of max dimension d + * \ingroup toplex_map */ + std::vector<Toplex_map::Simplex> skeleton_simplex_range(int d) const; + + Toplex_map::Vertex contraction(const Toplex_map::Vertex x, const Toplex_map::Vertex y); + + +protected: + + /** \internal Does all the facets of the given simplex belong to the complex ? + * \ingroup toplex_map */ + template <typename Input_vertex_range> + bool all_facets_inside(const Input_vertex_range &vertex_range) const; + +}; + +template<class OneSkeletonGraph> +void Fake_simplex_tree::insert_graph(const OneSkeletonGraph& skel_graph){ + toplex_maps.emplace(nan(""), new Toplex_map()); + using vertex_iterator = typename boost::graph_traits<OneSkeletonGraph>::vertex_iterator; + vertex_iterator vi, vi_end; + for (std::tie(vi, vi_end) = boost::vertices(skel_graph); vi != vi_end; ++vi) { + Simplex s; s.insert(*vi); + insert_simplex_and_subfaces(s); + } + bron_kerbosch_all_cliques(skel_graph, Visitor(this->toplex_maps.at(nan("")))); +} + +void Fake_simplex_tree::expansion(int max_dim){} + +template <typename Input_vertex_range> +bool Fake_simplex_tree::all_facets_inside(const Input_vertex_range &vertex_range) const{ + Simplex sigma(vertex_range); + for(const Simplex& s : facets(sigma)) + if(!membership(s)) return false; + return true; +} + +std::size_t Fake_simplex_tree::dimension() const { + std::size_t max = 0; + for(const Simplex& s : max_simplices()) + max = std::max(max, s.size()); + 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 max_simplices().size(); +} + +std::size_t Fake_simplex_tree::num_vertices() const { + std::unordered_set<Toplex_map::Vertex> vertices; + for(const Toplex_map::Simplex& s : max_simplices()) + for (Toplex_map::Vertex v : s) + vertices.emplace(v); + return vertices.size(); +} + +Toplex_map::Simplex Fake_simplex_tree::simplex_vertex_range(const Simplex& s) const { + return s; +} + +std::vector<Toplex_map::Simplex> Fake_simplex_tree::max_simplices() const{ + std::vector<Toplex_map::Simplex> max_s; + for(auto kv : toplex_maps) + for(const Toplex_map::Simplex_ptr& sptr : kv.second->maximal_cofaces(Simplex())) + max_s.emplace_back(*sptr); + return max_s; +} + +std::vector<Toplex_map::Simplex> Fake_simplex_tree::filtration_simplex_range(int d) const{ + std::vector<Toplex_map::Simplex> m = max_simplices(); + std::vector<Toplex_map::Simplex> range; + Toplex_map::Simplex_ptr_set seen; + while(m.begin()!=m.end()){ + Toplex_map::Simplex s(m.back()); + m.pop_back(); + if(seen.find(get_key(s))==seen.end()){ + if((int) 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 range; +} + +std::vector<Toplex_map::Simplex> Fake_simplex_tree::skeleton_simplex_range(int d) const{ + return filtration_simplex_range(d); +} + +Toplex_map::Vertex Fake_simplex_tree::contraction(const Toplex_map::Vertex x, const Toplex_map::Vertex y){ + for(auto kv : toplex_maps) + kv.second->contraction(x,y); + return y; +} + +} //namespace Gudhi + +#endif /* FAKE_SIMPLEX_TREE_H */ + 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..d383e84b --- /dev/null +++ b/src/Toplex_map/example/Simple_toplex_map.cpp @@ -0,0 +1,218 @@ +/* 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) 2017 + * + * 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/graph_simplicial_complex.h> +#include "Fake_simplex_tree.h" + +#include <iostream> +#include <utility> // for pair +#include <vector> + +using Toplex_map = Gudhi::Fake_simplex_tree; +using typeVectorVertex = std::vector< Toplex_map::Vertex_handle >; +using typePairSimplexBool = std::pair< Toplex_map::Simplex_handle, bool >; + +int main(int argc, char * const argv[]) { + + // TEST OF INSERTION + std::cout << "********************************************************************" << std::endl; + std::cout << "EXAMPLE OF SIMPLE INSERTION" << std::endl; + // Construct the Toplex_map + Toplex_map t_map; + + /* Simplex to be inserted: */ + /* 1 */ + /* o */ + /* /X\ */ + /* o---o---o */ + /* 2 0 3 */ + + // ++ FIRST + std::cout << " * INSERT 0" << std::endl; + typeVectorVertex firstSimplexVector = { 0 }; + typePairSimplexBool returnValue = t_map.insert_simplex_and_subfaces(firstSimplexVector, 0.1); + + if (returnValue.second == true) { + std::cout << " + 0 INSERTED" << std::endl; + } else { + std::cout << " - 0 NOT INSERTED" << std::endl; + } + + // ++ SECOND + std::cout << " * INSERT 1" << std::endl; + typeVectorVertex secondSimplexVector = { 1 }; + returnValue = t_map.insert_simplex_and_subfaces(secondSimplexVector, 0.1); + + if (returnValue.second == true) { + std::cout << " + 1 INSERTED" << std::endl; + } else { + std::cout << " - 1 NOT INSERTED" << std::endl; + } + + // ++ THIRD + std::cout << " * INSERT (0,1)" << std::endl; + typeVectorVertex thirdSimplexVector = { 0, 1 }; + returnValue = + t_map.insert_simplex_and_subfaces(thirdSimplexVector, 0.2); + + if (returnValue.second == true) { + std::cout << " + (0,1) INSERTED" << std::endl; + } else { + std::cout << " - (0,1) NOT INSERTED" << std::endl; + } + + // ++ FOURTH + std::cout << " * INSERT 2" << std::endl; + typeVectorVertex fourthSimplexVector = { 2 }; + returnValue = + t_map.insert_simplex_and_subfaces(fourthSimplexVector, 0.1); + + if (returnValue.second == true) { + std::cout << " + 2 INSERTED" << std::endl; + } else { + std::cout << " - 2 NOT INSERTED" << std::endl; + } + + // ++ FIFTH + std::cout << " * INSERT (2,0)" << std::endl; + typeVectorVertex fifthSimplexVector = { 2, 0 }; + returnValue = + t_map.insert_simplex_and_subfaces(fifthSimplexVector, 0.2); + + if (returnValue.second == true) { + std::cout << " + (2,0) INSERTED" << std::endl; + } else { + std::cout << " - (2,0) NOT INSERTED" << std::endl; + } + + // ++ SIXTH + std::cout << " * INSERT (2,1)" << std::endl; + typeVectorVertex sixthSimplexVector = { 2, 1 }; + returnValue = + t_map.insert_simplex_and_subfaces(sixthSimplexVector, 0.2); + + if (returnValue.second == true) { + std::cout << " + (2,1) INSERTED" << std::endl; + } else { + std::cout << " - (2,1) NOT INSERTED" << std::endl; + } + + // ++ SEVENTH + std::cout << " * INSERT (2,1,0)" << std::endl; + typeVectorVertex seventhSimplexVector = { 2, 1, 0 }; + returnValue = + t_map.insert_simplex_and_subfaces(seventhSimplexVector, 0.3); + + if (returnValue.second == true) { + std::cout << " + (2,1,0) INSERTED" << std::endl; + } else { + std::cout << " - (2,1,0) NOT INSERTED" << std::endl; + } + + // ++ EIGHTH + std::cout << " * INSERT 3" << std::endl; + typeVectorVertex eighthSimplexVector = { 3 }; + returnValue = + t_map.insert_simplex_and_subfaces(eighthSimplexVector, 0.1); + + if (returnValue.second == true) { + std::cout << " + 3 INSERTED" << std::endl; + } else { + std::cout << " - 3 NOT INSERTED" << std::endl; + } + + // ++ NINETH + std::cout << " * INSERT (3,0)" << std::endl; + typeVectorVertex ninethSimplexVector = { 3, 0 }; + returnValue = + t_map.insert_simplex_and_subfaces(ninethSimplexVector, 0.2); + + if (returnValue.second == true) { + std::cout << " + (3,0) INSERTED" << std::endl; + } else { + std::cout << " - (3,0) NOT INSERTED" << std::endl; + } + + // ++ TENTH + std::cout << " * INSERT 0 (already inserted)" << std::endl; + typeVectorVertex tenthSimplexVector = { 0 }; + // With a different filtration value + returnValue = t_map.insert_simplex_and_subfaces(tenthSimplexVector, 0.4); + + if (returnValue.second == true) { + std::cout << " + 0 INSERTED" << std::endl; + } else { + std::cout << " - 0 NOT INSERTED" << std::endl; + } + + // ++ ELEVENTH + std::cout << " * INSERT (2,1,0) (already inserted)" << std::endl; + typeVectorVertex eleventhSimplexVector = { 2, 1, 0 }; + returnValue = + t_map.insert_simplex_and_subfaces(eleventhSimplexVector, 0.4); + + if (returnValue.second == true) { + std::cout << " + (2,1,0) INSERTED" << std::endl; + } else { + std::cout << " - (2,1,0) NOT INSERTED" << std::endl; + } + + // ++ GENERAL VARIABLE SET + + std::cout << "********************************************************************\n"; + // Display the Simplex_tree - Can not be done in the middle of 2 inserts + std::cout << "* The complex contains " << t_map.num_vertices() << " vertices and " << t_map.num_simplices() + << " simplices - dimension is " << t_map.dimension() << "\n"; + std::cout << "* Iterator on Simplices in the filtration, with [filtration value]:\n"; + for (auto f_simplex : t_map.filtration_simplex_range()) { + if (f_simplex.size() > 0) { + std::cout << " " << "[" << t_map.filtration(f_simplex) << "] "; + for (auto vertex : t_map.simplex_vertex_range(f_simplex)) + std::cout << "(" << vertex << ")"; + std::cout << std::endl; + } + } + // [0.1] 0 + // [0.1] 1 + // [0.1] 2 + // [0.1] 3 + // [0.2] 1 0 + // [0.2] 2 0 + // [0.2] 2 1 + // [0.2] 3 0 + // [0.3] 2 1 0 + + std::cout << std::endl << std::endl; + + std::cout << "Iterator on skeleton[1]:" << std::endl; + for (auto f_simplex : t_map.skeleton_simplex_range(1)) { + if (f_simplex.size() > 0) { + std::cout << " " << "[" << t_map.filtration(f_simplex) << "] "; + for (auto vertex : t_map.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } + } + + return 0; +} diff --git a/src/Toplex_map/example/Toplex_map_from_cliques_of_graph.cpp b/src/Toplex_map/example/Toplex_map_from_cliques_of_graph.cpp new file mode 100644 index 00000000..c43f1b69 --- /dev/null +++ b/src/Toplex_map/example/Toplex_map_from_cliques_of_graph.cpp @@ -0,0 +1,93 @@ +/* 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) 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/>. + */ + +#include <gudhi/reader_utils.h> +#include "Fake_simplex_tree.h" + +#include <iostream> +#include <ctime> +#include <string> +#include <utility> // for std::pair + +using Toplex_map = Gudhi::Fake_simplex_tree; +using Vertex_handle = Toplex_map::Vertex_handle; +using Filtration_value = Toplex_map::Filtration_value; + +typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS, + boost::property < vertex_filtration_t, Filtration_value >, + boost::property < edge_filtration_t, Filtration_value > > Graph_t; + +int main(int argc, char * const argv[]) { + if (argc != 3) { + std::cerr << "Usage: " << argv[0] + << " path_to_file_graph max_dim \n"; + return 0; + } + std::string filegraph = argv[1]; + int max_dim = atoi(argv[2]); + + clock_t start, end; + // Construct the Toplex Map + Toplex_map t_map; + + start = clock(); + auto g = Gudhi::read_graph<Graph_t, Filtration_value, Vertex_handle>(filegraph); + // insert the graph in the toplex map as 1-skeleton + t_map.insert_graph(g); + end = clock(); + std::cout << "Insert the 1-skeleton in the toplex map in " + << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + + start = clock(); + // expand the 1-skeleton until dimension max_dim + t_map.expansion(max_dim); + end = clock(); + std::cout << "max_dim = " << max_dim << "\n"; + std::cout << "Expand the toplex map in " + << static_cast<double>(end - start) / CLOCKS_PER_SEC << " s. \n"; + + std::cout << "Information of the toplex map: " << std::endl; + std::cout << " Number of vertices = " << t_map.num_vertices() << " "; + std::cout << " Number of simplices = " << t_map.num_simplices() << std::endl; + std::cout << std::endl << std::endl; + + std::cout << "Iterator on Simplices in the filtration:" << std::endl; + for (auto f_simplex : t_map.filtration_simplex_range()) { + std::cout << " " << "[" << t_map.filtration(f_simplex) << "] "; + for (auto vertex : t_map.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } + + std::cout << std::endl << std::endl; + + std::cout << "Iterator on skeleton:" << std::endl; + for (auto f_simplex : t_map.skeleton_simplex_range(max_dim)) { + std::cout << " " << "[" << t_map.filtration(f_simplex) << "] "; + for (auto vertex : t_map.simplex_vertex_range(f_simplex)) { + std::cout << vertex << " "; + } + std::cout << std::endl; + } + return 0; +} diff --git a/src/Toplex_map/include/gudhi/Filtered_toplex_map.h b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h new file mode 100644 index 00000000..ed65e36f --- /dev/null +++ b/src/Toplex_map/include/gudhi/Filtered_toplex_map.h @@ -0,0 +1,84 @@ + #ifndef FILTERED_TOPLEX_MAP_H +#define FILTERED_TOPLEX_MAP_H + +#include <gudhi/Toplex_map.h> +#include <map> +#include <limits> + +namespace Gudhi { + +/** A Filtered_toplex_map represents the simplicial complex with a filtration. + * A "toplex" is a critical simplex. + * \ingroup toplex_map */ +class 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; + + /** The type of the filtration values. + * \ingroup toplex_map */ + typedef double Filtration_value; + + /** Add a simplex and its subfaces with the given filtration value + * in the Filtered_toplex_map. + * \ingroup toplex_map */ + template <typename Input_vertex_range> + std::pair<Simplex, bool> insert_simplex_and_subfaces(const Input_vertex_range &vertex_range, Filtration_value f = std::numeric_limits<double>::quiet_NaN()); + + /** Gives the filtration of the input simplex. + * \ingroup toplex_map */ + template <typename Input_vertex_range> + Filtration_value filtration(const Input_vertex_range &vertex_range) const; + + /** Is the input simplex member of the complex ? + * \ingroup toplex_map */ + template <typename Input_vertex_range> + bool membership(const Input_vertex_range &vertex_range) const; + +protected: + std::map<Filtration_value, Toplex_map*> toplex_maps; +}; + +template <typename Input_vertex_range> +std::pair<Toplex_map::Simplex, bool> Filtered_toplex_map::insert_simplex_and_subfaces(const Input_vertex_range &vertex_range, Filtration_value f){ + Simplex s(vertex_range.begin(),vertex_range.end()); + if(membership(s)) return make_pair(s,false); + if(!toplex_maps.count(f)) toplex_maps.emplace(f,new Toplex_map()); + toplex_maps.at(f)->insert_simplex(vertex_range); + return make_pair(s,true); +} + + +template <typename Input_vertex_range> +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; //min only because a map is ordered + return std::numeric_limits<double>::quiet_NaN() ; +} + +template <typename Input_vertex_range> +bool Filtered_toplex_map::membership(const Input_vertex_range &vertex_range) const{ + for(auto kv : toplex_maps) + if(kv.second->membership(vertex_range)) + return true; + return false; +} + +} //namespace Gudhi + +#endif /* FILTERED_TOPLEX_MAP_H */ 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..25281998 --- /dev/null +++ b/src/Toplex_map/include/gudhi/Lazy_Toplex_map.h @@ -0,0 +1,263 @@ +#ifndef LAZY_TOPLEX_MAP_H +#define LAZY_TOPLEX_MAP_H + +#include <gudhi/Toplex_map.h> +#include <boost/heap/fibonacci_heap.hpp> +#include <cmath> + +namespace Gudhi { + +/** A Lazy_Toplex_map represents the simplicial complex. + * A "toplex" is a maximal simplex but not all simplices in a LTM are toplices. + * \ingroup toplex_map */ +class Lazy_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; + + /** Adds the given simplex to the complex. + * The simplex must not have maximal coface in the complex. + * \ingroup toplex_map */ + 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 has a coface in the complex. + * \ingroup toplex_map */ + 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. + * \ingroup toplex_map */ + template <typename Input_vertex_range> + void remove_simplex(const Input_vertex_range &vertex_range); + + /** Does a simplex belong to the complex ? + * \ingroup toplex_map */ + template <typename Input_vertex_range> + bool membership(const Input_vertex_range &vertex_range); + + + /** Do all the facets of a simplex belong to the complex ? + * \ingroup toplex_map */ + 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. + * \ingroup toplex_map */ + Vertex contraction(const Vertex x, const Vertex y); + + /** \brief Number of simplices stored. + * \ingroup toplex_map */ + std::size_t num_simplices() const; + + std::unordered_map<Vertex, std::size_t> gamma0_lbounds; + +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, 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()); + empty_toplex = (sigma.size()==0); //vérifier la gestion de empty face + 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 */ +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> +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); +} + +std::size_t Lazy_Toplex_map::num_simplices() const{ + return size; +} + +} //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..73d2c63d --- /dev/null +++ b/src/Toplex_map/include/gudhi/Toplex_map.h @@ -0,0 +1,322 @@ +#ifndef TOPLEX_MAP_H +#define TOPLEX_MAP_H + +#include <vector> +#include <set> +#include <unordered_set> +#include <unordered_map> +#include <memory> +#include <limits> + +#define vertex_upper_bound std::numeric_limits<Toplex_map::Vertex>::max() + +namespace Gudhi { + +/** A Toplex_map represents the simplicial complex. + * A "toplex" is a maximal simplex. + * \ingroup toplex_map */ +class Toplex_map { + +public: + + /** Vertex is the type of vertices. + * \ingroup toplex_map */ + typedef std::size_t Vertex; + + /** Simplex is the type of simplices. + * \ingroup toplex_map */ + typedef std::set<Toplex_map::Vertex> Simplex; + + /** The type of the pointers to maximal simplices. + * \ingroup toplex_map */ + typedef std::shared_ptr<Toplex_map::Simplex> Simplex_ptr; + + 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. + * \ingroup toplex_map */ + typedef std::unordered_set<Toplex_map::Simplex_ptr, Sptr_hash, Sptr_equal> Simplex_ptr_set; + + /** \brief Adds the given simplex to the complex. + * Nothing happens if the simplex has a coface in the complex. + * \ingroup toplex_map */ + 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. + * \ingroup toplex_map */ + template <typename Input_vertex_range> + void remove_simplex(const Input_vertex_range &vertex_range); + + /** Does a simplex belong to the complex ? + * \ingroup toplex_map */ + template <typename Input_vertex_range> + bool membership(const Input_vertex_range &vertex_range) const; + + /** Does a simplex is a toplex ? + * \ingroup toplex_map */ + 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. + * \ingroup toplex_map */ + 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; + + /** Contracts one edge in the complex. + * The edge has to verify the link condition if you want to preserve topology. + * Returns the remaining vertex. + * \ingroup toplex_map */ + Toplex_map::Vertex contraction(const Toplex_map::Vertex x, const Toplex_map::Vertex y); + + /** Adds the given simplex to the complex. + * The simplex must not have neither maximal face nor coface in the complex. + * \ingroup toplex_map */ + template <typename Input_vertex_range> + void insert_independent_simplex(const Input_vertex_range &vertex_range); + + /** \internal Removes a toplex without adding facets after. + * \ingroup toplex_map */ + void erase_maximal(const Toplex_map::Simplex_ptr& sptr); + + /** Removes a vertex from any simplex containing it. + * \ingroup toplex_map */ + void remove_vertex(const Toplex_map::Vertex x); + + /** \brief Number of maximal simplices. + * \ingroup toplex_map */ + std::size_t num_simplices() const; + + std::set<Toplex_map::Vertex> unitary_collapse(const Toplex_map::Vertex k, const Toplex_map::Vertex d); + +protected: + /** \internal Gives an index in order to look for a simplex quickly. + * \ingroup toplex_map */ + template <typename Input_vertex_range> + Toplex_map::Vertex best_index(const Input_vertex_range &vertex_range) const; + + /** \internal The map from vertices to toplices + * \ingroup toplex_map */ + std::unordered_map<Toplex_map::Vertex, Toplex_map::Simplex_ptr_set> t0; +}; + +// 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 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 <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 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 <typename Input_vertex_range> +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 <typename Input_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 <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 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; +} + +std::set<Toplex_map::Vertex> Toplex_map::unitary_collapse(const Toplex_map::Vertex k, const Toplex_map::Vertex d){ + std::set<Toplex_map::Vertex> 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 <typename Input_vertex_range> +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); + } +} + +std::size_t Toplex_map::num_simplices() const{ + return maximal_cofaces(Simplex()).size(); +} + +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 <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 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_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 Toplex_map::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..5ed55e97 --- /dev/null +++ b/src/Toplex_map/test/CMakeLists.txt @@ -0,0 +1,14 @@ +cmake_minimum_required(VERSION 2.6) +project(Toplex_map_tests) + +add_executable ( ToplexMapUT toplex_map_unit_test.cpp ) +target_link_libraries(ToplexMapUT ${Boost_SYSTEM_LIBRARY} ${Boost_UNIT_TEST_FRAMEWORK_LIBRARY}) + + +# Unitary tests +add_test(NAME ToplexMapUT + COMMAND ${CMAKE_CURRENT_BINARY_DIR}/ToplexMapUT + ${CMAKE_SOURCE_DIR}/src/Toplex_map/test/test.txt + # XML format for Jenkins xUnit plugin + --log_format=XML --log_sink=${CMAKE_SOURCE_DIR}/ToplexMapUT.xml --log_level=test_suite --report_level=no) + 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..c12ad094 --- /dev/null +++ b/src/Toplex_map/test/toplex_map_unit_test.cpp @@ -0,0 +1,54 @@ +#include <iostream> +#include <gudhi/Filtered_toplex_map.h> + + +#define BOOST_TEST_DYN_LINK +#define BOOST_TEST_MODULE "toplex map" +#include <boost/test/unit_test.hpp> + +using namespace Gudhi; + +typedef Toplex_map::Vertex Vertex; + +std::vector<Vertex> sigma1 = {1, 2, 3, 4}; +std::vector<Vertex> sigma2 = {5, 2, 3, 6}; +std::vector<Vertex> sigma3 = {5}; +std::vector<Vertex> sigma4 = {5, 2, 3}; +std::vector<Vertex> sigma5 = {5, 2, 7}; +std::vector<Vertex> sigma6 = {4, 5, 3}; +std::vector<Vertex> sigma7 = {4, 5, 9}; +std::vector<Vertex> sigma8 = {1, 2, 3, 6}; + + +BOOST_AUTO_TEST_CASE(toplexmap) { + 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.maximality(sigma3)); + BOOST_CHECK(!K.membership(sigma5)); + K.insert_simplex(sigma5); + std::vector<Vertex> sigma9 = {1, 2, 3}; + std::vector<Vertex> sigma10 = {2, 7}; + auto r = K.contraction(4,5); + sigma9.emplace_back(r); + sigma10.emplace_back(r); + BOOST_CHECK(!K.membership(sigma6)); + BOOST_CHECK(K.membership(sigma9)); + BOOST_CHECK(K.membership(sigma10)); +} + + +BOOST_AUTO_TEST_CASE(ftoplexmap) { + Filtered_toplex_map K; + K.insert_simplex_and_subfaces(sigma1, 2.); + K.insert_simplex_and_subfaces(sigma2, 2.); + K.insert_simplex_and_subfaces(sigma6, 1.); + K.insert_simplex_and_subfaces(sigma7, 1.); + BOOST_CHECK(K.filtration(sigma4)==2.); + BOOST_CHECK(K.filtration(sigma3)==1.); +} + diff --git a/src/common/doc/main_page.h b/src/common/doc/main_page.h index db1e80ce..5ccb648f 100644 --- a/src/common/doc/main_page.h +++ b/src/common/doc/main_page.h @@ -168,6 +168,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"> |
