summaryrefslogtreecommitdiff
path: root/src/Toplex_map
diff options
context:
space:
mode:
Diffstat (limited to 'src/Toplex_map')
-rw-r--r--src/Toplex_map/benchmark/CMakeLists.txt3
-rw-r--r--src/Toplex_map/benchmark/benchmark_tm.cpp125
-rw-r--r--src/Toplex_map/doc/Intro_Toplex_map.h49
-rw-r--r--src/Toplex_map/doc/map.pngbin0 -> 71815 bytes
-rw-r--r--src/Toplex_map/example/CMakeLists.txt4
-rw-r--r--src/Toplex_map/example/simple_toplex_map.cpp153
-rw-r--r--src/Toplex_map/include/gudhi/Lazy_toplex_map.h259
-rw-r--r--src/Toplex_map/include/gudhi/Toplex_map.h326
-rw-r--r--src/Toplex_map/test/CMakeLists.txt11
-rw-r--r--src/Toplex_map/test/lazy_toplex_map_unit_test.cpp158
-rw-r--r--src/Toplex_map/test/toplex_map_unit_test.cpp126
11 files changed, 1214 insertions, 0 deletions
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..feb5d01c
--- /dev/null
+++ b/src/Toplex_map/benchmark/benchmark_tm.cpp
@@ -0,0 +1,125 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#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..cd7705b6
--- /dev/null
+++ b/src/Toplex_map/doc/Intro_Toplex_map.h
@@ -0,0 +1,49 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2017 INRIA
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#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&ccedil;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
new file mode 100644
index 00000000..0f9cde2b
--- /dev/null
+++ b/src/Toplex_map/doc/map.png
Binary files differ
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..7538c989
--- /dev/null
+++ b/src/Toplex_map/example/simple_toplex_map.cpp
@@ -0,0 +1,153 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author(s): Vincent Rouvreau
+ *
+ * Copyright (C) 2018
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#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..dcc128fa
--- /dev/null
+++ b/src/Toplex_map/include/gudhi/Lazy_toplex_map.h
@@ -0,0 +1,259 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#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 = true; // 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..95e94938
--- /dev/null
+++ b/src/Toplex_map/include/gudhi/Toplex_map.h
@@ -0,0 +1,326 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#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..639bf35a
--- /dev/null
+++ b/src/Toplex_map/test/lazy_toplex_map_unit_test.cpp
@@ -0,0 +1,158 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#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..24ec679b
--- /dev/null
+++ b/src/Toplex_map/test/toplex_map_unit_test.cpp
@@ -0,0 +1,126 @@
+/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
+ * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
+ * Author: François Godi, Vincent Rouvreau
+ *
+ * Copyright (C) 2018 INRIA
+ *
+ * Modification(s):
+ * - YYYY/MM Author: Description of the modification
+ */
+
+#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));
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-11 12:38:47 +0000