diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/Simplex_tree/concept/IndexingTag.h | 2 | ||||
| -rw-r--r-- | src/Simplex_tree/concept/SimplexKey.h | 4 | ||||
| -rw-r--r-- | src/Simplex_tree/concept/SimplexTreeOptions.h | 41 | ||||
| -rw-r--r-- | src/Simplex_tree/concept/VertexHandle.h | 3 | ||||
| -rw-r--r-- | src/Simplex_tree/example/CMakeLists.txt | 9 | ||||
| -rw-r--r-- | src/Simplex_tree/example/mini_simplex_tree.cpp | 71 | ||||
| -rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree.h | 82 | ||||
| -rw-r--r-- | src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h | 43 |
8 files changed, 193 insertions, 62 deletions
diff --git a/src/Simplex_tree/concept/IndexingTag.h b/src/Simplex_tree/concept/IndexingTag.h index d690da11..1dcdd756 100644 --- a/src/Simplex_tree/concept/IndexingTag.h +++ b/src/Simplex_tree/concept/IndexingTag.h @@ -25,6 +25,6 @@ * continuous maps to a cell complex, and compute its persistent * homology. * - * Must be linear_indexing_tag. + * Must be `Gudhi::linear_indexing_tag`. */ struct IndexingTag {}; diff --git a/src/Simplex_tree/concept/SimplexKey.h b/src/Simplex_tree/concept/SimplexKey.h index ce5b2382..7fdbdd84 100644 --- a/src/Simplex_tree/concept/SimplexKey.h +++ b/src/Simplex_tree/concept/SimplexKey.h @@ -22,7 +22,7 @@ /** \brief Key type used as simplex identifier. * - * Must be <CODE>int</CODE> + * Must be a signed integer type. */ struct SimplexKey {}; -
\ No newline at end of file + diff --git a/src/Simplex_tree/concept/SimplexTreeOptions.h b/src/Simplex_tree/concept/SimplexTreeOptions.h new file mode 100644 index 00000000..a50a2bf1 --- /dev/null +++ b/src/Simplex_tree/concept/SimplexTreeOptions.h @@ -0,0 +1,41 @@ + /* 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): Marc Glisse + * + * Copyright (C) 2015 INRIA Saclay - Ile-de-France (France) + * + * 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/>. + */ + +/** \brief Concept of the template parameter for the class `Gudhi::Simplex_tree<SimplexTreeOptions>`. + * + * One model for this is `Gudhi::Simplex_tree_options_full_featured`. If you want to provide your own, it is recommended that you derive from it and override some parts instead of writing a class from scratch. + */ +struct SimplexTreeOptions { + /// Forced for now. + typedef IndexingTag Indexing_tag; + /// Must be a signed integer type. It admits a total order <. + typedef VertexHandle Vertex_handle; + /// Must be comparable with operator<. + typedef FiltrationValue Filtration_value; + /// Must be a signed integer type. + typedef SimplexKey Simplex_key; + /// If true, each simplex has extra storage for one `Simplex_key`. Necessary for `Persistent_cohomology`. + static constexpr bool store_key; + /// If true, each simplex has extra storage for one `Filtration_value`, and this value is propagated by operations like `Gudhi::Simplex_tree<SimplexTreeOptions>::expansion`. Without it, `Persistent_cohomology` degenerates to computing usual (non-persistent) cohomology. + static constexpr bool store_filtration; +}; + diff --git a/src/Simplex_tree/concept/VertexHandle.h b/src/Simplex_tree/concept/VertexHandle.h index 491f0f56..3efbba61 100644 --- a/src/Simplex_tree/concept/VertexHandle.h +++ b/src/Simplex_tree/concept/VertexHandle.h @@ -22,5 +22,6 @@ /** \brief Handle type for the vertices of a cell complex. * - * Must be int.*/ + * Must be a signed integer type. <code>operator<</code> defines a total order on it. + */ struct VertexHandle {}; diff --git a/src/Simplex_tree/example/CMakeLists.txt b/src/Simplex_tree/example/CMakeLists.txt index 1a3cdfbf..2f924490 100644 --- a/src/Simplex_tree/example/CMakeLists.txt +++ b/src/Simplex_tree/example/CMakeLists.txt @@ -7,15 +7,18 @@ add_test(simplex_tree_from_file_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_ add_executable ( simple_simplex_tree simple_simplex_tree.cpp ) add_test(simple_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/simple_simplex_tree) - + +add_executable ( mini_simplex_tree mini_simplex_tree.cpp ) +add_test(mini_simplex_tree ${CMAKE_CURRENT_BINARY_DIR}/mini_simplex_tree) + # An example with Simplex-tree using CGAL alpha_shapes_3 if(GMP_FOUND AND CGAL_FOUND) message("CGAL_lib = ${CGAL_LIBRARIES_DIR}") - message("GMP_LIBRARIES = ${GMP_LIBRARIES}") + message("GMP_LIBRARIES = ${GMP_LIBRARIES}") INCLUDE_DIRECTORIES(${GMP_INCLUDE_DIR}) INCLUDE_DIRECTORIES(${CGAL_INCLUDE_DIRS}) add_executable ( simplex_tree_from_alpha_shapes_3 simplex_tree_from_alpha_shapes_3.cpp ) target_link_libraries(simplex_tree_from_alpha_shapes_3 ${GMP_LIBRARIES} ${CGAL_LIBRARY}) add_test(simplex_tree_from_alpha_shapes_3 ${CMAKE_CURRENT_BINARY_DIR}/simplex_tree_from_alpha_shapes_3 ${CMAKE_SOURCE_DIR}/data/points/bunny_5000) -endif() +endif() diff --git a/src/Simplex_tree/example/mini_simplex_tree.cpp b/src/Simplex_tree/example/mini_simplex_tree.cpp new file mode 100644 index 00000000..9c07f15f --- /dev/null +++ b/src/Simplex_tree/example/mini_simplex_tree.cpp @@ -0,0 +1,71 @@ +/* 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): Marc Glisse + * + * Copyright (C) 2015 INRIA Saclay - Ile-de-France (France) + * + * 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/>. + */ + +// FIXME: remove the first include +#include <gudhi/graph_simplicial_complex.h> +#include <gudhi/Simplex_tree.h> +#include <iostream> +#include <initializer_list> + +using namespace Gudhi; + +struct MyOptions : Simplex_tree_options_full_featured { + // Not doing persistence, so we don't need those + static const bool store_key = false; + static const bool store_filtration = false; + // I have few vertices + typedef short Vertex_handle; +}; +typedef Simplex_tree<MyOptions> ST; + +// Dictionary should be private, but for now this is the easiest way. +static_assert(sizeof(ST::Dictionary::value_type) < sizeof(Simplex_tree<>::Dictionary::value_type), + "Not storing the filtration and key should save some space"); + +int main() { + ST st; + + /* Complex to build. */ + /* 1 */ + /* o */ + /* /X\ */ + /* o---o---o */ + /* 2 0 3 */ + + // FIXME: Replace std::vector<short> with auto + std::vector<short> triangle012 = {0, 1, 2}; + std::vector<short> edge03 = {0, 3}; + st.insert_simplex_and_subfaces(triangle012); + st.insert_simplex_and_subfaces(edge03); + // FIXME: Remove this line + st.set_dimension(2); + + std::vector<short> edge02 = {0, 2}; + ST::Simplex_handle e = st.find(edge02); + assert(st.filtration(e) == 0); // We are not using filtrations so everything has value 0 + for(ST::Simplex_handle t : st.cofaces_simplex_range(e, 1)) // Only coface is 012 + { + for(ST::Vertex_handle v : st.simplex_vertex_range(t)) // v in { 0, 1, 2 } + std::cout << v; + std::cout << '\n'; + } +} diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree.h b/src/Simplex_tree/include/gudhi/Simplex_tree.h index 9989e850..b911552d 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree.h @@ -77,6 +77,16 @@ namespace Gudhi { * @{ */ +/// Model of SimplexTreeOptions. +struct Simplex_tree_options_full_featured { + typedef linear_indexing_tag Indexing_tag; + typedef int Vertex_handle; + typedef double Filtration_value; + typedef int Simplex_key; + static const bool store_key = true; + static const bool store_filtration = true; +}; + /** * \brief Simplex Tree data structure for representing simplicial complexes. * @@ -88,35 +98,63 @@ namespace Gudhi { * \implements FilteredComplex * */ -template<typename IndexingTag = linear_indexing_tag, -typename FiltrationValue = double, typename SimplexKey = int // must be a signed integer type -, typename VertexHandle = int // must be a signed integer type, int convertible to it -> + +template<typename SimplexTreeOptions = Simplex_tree_options_full_featured> class Simplex_tree { public: - typedef IndexingTag Indexing_tag; + typedef SimplexTreeOptions Options; + typedef typename Options::Indexing_tag Indexing_tag; /** \brief Type for the value of the filtration function. * * Must be comparable with <. */ - typedef FiltrationValue Filtration_value; + typedef typename Options::Filtration_value Filtration_value; /** \brief Key associated to each simplex. * * Must be a signed integer type. */ - typedef SimplexKey Simplex_key; + typedef typename Options::Simplex_key Simplex_key; /** \brief Type for the vertex handle. * * Must be a signed integer type. It admits a total order <. */ - typedef VertexHandle Vertex_handle; + typedef typename Options::Vertex_handle Vertex_handle; /* Type of node in the simplex tree. */ typedef Simplex_tree_node_explicit_storage<Simplex_tree> Node; /* Type of dictionary Vertex_handle -> Node for traversing the simplex tree. */ + // Note: this wastes space when Vertex_handle is 32 bits and Node is aligned on 64 bits. It would be better to use a flat_set (with our own comparator) where we can control the layout of the struct (put Vertex_handle and Simplex_key next to each other). typedef typename boost::container::flat_map<Vertex_handle, Node> Dictionary; /* \brief Set of nodes sharing a same parent in the simplex tree. */ /* \brief Set of nodes sharing a same parent in the simplex tree. */ typedef Simplex_tree_siblings<Simplex_tree, Dictionary> Siblings; + struct Key_simplex_base_real { + Key_simplex_base_real() : key_(-1) {} + void assign_key(Simplex_key k) { key_ = k; } + Simplex_key key() const { return key_; } + private: + Simplex_key key_; + }; + struct Key_simplex_base_dummy { + Key_simplex_base_dummy() {} + void assign_key(Simplex_key) { } + Simplex_key key() const { assert(false); return -1; } + }; + typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type Key_simplex_base; + + struct Filtration_simplex_base_real { + Filtration_simplex_base_real() : filt_(0) {} + void assign_filtration(Filtration_value f) { filt_ = f; } + Filtration_value filtration() const { return filt_; } + private: + Filtration_value filt_; + }; + struct Filtration_simplex_base_dummy { + Filtration_simplex_base_dummy() {} + void assign_filtration(Filtration_value f) { assert(f == 0); } + Filtration_value filtration() const { return 0; } + }; + typedef typename std::conditional<Options::store_filtration, Filtration_simplex_base_real, Filtration_simplex_base_dummy>::type Filtration_simplex_base; + public: /** \brief Handle type to a simplex contained in the simplicial complex represented * by the simplex tree. */ @@ -231,12 +269,14 @@ class Simplex_tree { * order is used. * * The filtration must be valid. If the filtration has not been initialized yet, the - * method initializes it (i.e. order the simplices). */ + * method initializes it (i.e. order the simplices). If the complex has changed since the last time the filtration + * was initialized, please call `initialize_filtration()` to recompute it. */ Filtration_simplex_range filtration_simplex_range(Indexing_tag) { if (filtration_vect_.empty()) { initialize_filtration(); } - return Filtration_simplex_range(filtration_vect_.begin(), filtration_vect_.end()); + return Filtration_simplex_range(filtration_vect_.begin(), + filtration_vect_.end()); } Filtration_simplex_range filtration_simplex_range() { @@ -382,21 +422,27 @@ class Simplex_tree { public: /** \brief Returns the key associated to a simplex. * - * The filtration must be initialized. */ + * The filtration must be initialized. + * \pre SimplexTreeOptions::store_key + */ static Simplex_key key(Simplex_handle sh) { return sh->second.key(); } /** \brief Returns the simplex associated to a key. * - * The filtration must be initialized. */ + * The filtration must be initialized. + * \pre SimplexTreeOptions::store_key + */ Simplex_handle simplex(Simplex_key key) const { return filtration_vect_[key]; } /** \brief Returns the filtration value of a simplex. * - * Called on the null_simplex, returns INFINITY. */ + * Called on the null_simplex, returns INFINITY. + * If SimplexTreeOptions::store_filtration is false, returns 0. + */ static Filtration_value filtration(Simplex_handle sh) { if (sh != null_simplex()) { return sh->second.filtration(); @@ -583,7 +629,7 @@ class Simplex_tree { * .end() return input iterators, with 'value_type' Vertex_handle. */ template<class InputVertexRange> std::pair<Simplex_handle, bool> insert_simplex(const InputVertexRange & simplex, - Filtration_value filtration) { + Filtration_value filtration = 0) { auto first = std::begin(simplex); auto last = std::end(simplex); @@ -612,7 +658,7 @@ class Simplex_tree { */ template<class InputVertexRange> std::pair<Simplex_handle, bool> insert_simplex_and_subfaces(const InputVertexRange& Nsimplex, - Filtration_value filtration = 0.0) { + Filtration_value filtration = 0) { auto first = std::begin(Nsimplex); auto last = std::end(Nsimplex); @@ -822,13 +868,13 @@ class Simplex_tree { assert(codimension >= 0); Simplex_vertex_range rg = simplex_vertex_range(simplex); std::vector<Vertex_handle> copy(rg.begin(), rg.end()); - if (codimension + static_cast<int> (copy.size()) > dimension_ + 1 || - (codimension == 0 && static_cast<int> (copy.size()) > dimension_)) // n+codimension greater than dimension_ + if (codimension + static_cast<int>(copy.size()) > dimension_ + 1 || + (codimension == 0 && static_cast<int>(copy.size()) > dimension_)) // n+codimension greater than dimension_ return cofaces; // must be sorted in decreasing order assert(std::is_sorted(copy.begin(), copy.end(), std::greater<Vertex_handle>())); bool star = codimension == 0; - rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast<int> (copy.size())); + rec_coface(copy, &root_, 1, cofaces, star, codimension + static_cast<int>(copy.size())); return cofaces; } diff --git a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h index 1f1a34cc..c49e30b9 100644 --- a/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h +++ b/src/Simplex_tree/include/gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h @@ -39,62 +39,31 @@ namespace Gudhi { * It stores explicitely its own filtration value and its own Simplex_key. */ template<class SimplexTree> -class Simplex_tree_node_explicit_storage { - public: +struct Simplex_tree_node_explicit_storage : SimplexTree::Filtration_simplex_base, SimplexTree::Key_simplex_base { typedef typename SimplexTree::Siblings Siblings; typedef typename SimplexTree::Filtration_value Filtration_value; typedef typename SimplexTree::Simplex_key Simplex_key; - // Default constructor. - Simplex_tree_node_explicit_storage() - : children_(NULL), - simplex_key_(-1), - filtration_(0) { - } - - Simplex_tree_node_explicit_storage(Siblings * sib, - Filtration_value filtration) - : children_(sib), - simplex_key_(-1), - filtration_(filtration) { - } - - void assign_key(Simplex_key key) { - simplex_key_ = key; + Simplex_tree_node_explicit_storage(Siblings * sib = nullptr, + Filtration_value filtration = 0) + : children_(sib) { + this->assign_filtration(filtration); } /* - * Assign a children to the node + * Assign children to the node */ void assign_children(Siblings * children) { children_ = children; } - /* - * - */ - void assign_filtration(double filtration_value) { - filtration_ = filtration_value; - } - - Filtration_value filtration() { - return filtration_; - } /* Careful -> children_ can be NULL*/ Siblings * children() { return children_; } - Simplex_key key() { - return simplex_key_; - } - private: Siblings * children_; - - // Data attached to simplex, explicit storage - Simplex_key simplex_key_; - Filtration_value filtration_; // value in the filtration }; /* @} */ // end addtogroup simplex_tree |