19#ifndef SIMPLEX_TREE_H_
20#define SIMPLEX_TREE_H_
22#include <gudhi/Simplex_tree/simplex_tree_options.h>
23#include <gudhi/Simplex_tree/Simplex_tree_node_explicit_storage.h>
24#include <gudhi/Simplex_tree/Simplex_tree_siblings.h>
25#include <gudhi/Simplex_tree/Simplex_tree_iterators.h>
26#include <gudhi/Simplex_tree/Simplex_tree_star_simplex_iterators.h>
27#include <gudhi/Simplex_tree/serialization_utils.h>
28#include <gudhi/Simplex_tree/hooks_simplex_base.h>
32#include <gudhi/Debug_utils.h>
34#include <boost/container/map.hpp>
35#include <boost/container/flat_map.hpp>
36#include <boost/iterator/transform_iterator.hpp>
37#include <boost/graph/adjacency_list.hpp>
38#include <boost/range/adaptor/reversed.hpp>
39#include <boost/range/adaptor/transformed.hpp>
40#include <boost/range/size.hpp>
41#include <boost/container/static_vector.hpp>
42#include <boost/range/adaptors.hpp>
44#include <boost/intrusive/list.hpp>
45#include <boost/intrusive/parent_from_member.hpp>
49#include <tbb/parallel_sort.h>
57#include <initializer_list>
61#include <unordered_map>
97template<
typename SimplexTreeOptions = Simplex_tree_options_default>
127 typedef typename boost::container::flat_map<Vertex_handle, Node> flat_map;
130 typedef typename boost::container::map<Vertex_handle, Node> map;
133 flat_map>::type Dictionary;
140 struct Key_simplex_base_real {
141 Key_simplex_base_real() : key_(-1) {}
148 struct Key_simplex_base_dummy {
149 Key_simplex_base_dummy() {}
151 void assign_key(Simplex_key);
152 Simplex_key key()
const;
155 struct Extended_filtration_data {
158 Extended_filtration_data(){}
161 typedef typename std::conditional<Options::store_key, Key_simplex_base_real, Key_simplex_base_dummy>::type
164 struct Filtration_simplex_base_real {
165 Filtration_simplex_base_real() : filt_(0) {}
172 struct Filtration_simplex_base_dummy {
173 Filtration_simplex_base_dummy() {}
175 GUDHI_CHECK(f == 0,
"filtration value specified for a complex that does not store them");
178 GUDHI_CHECK(f == 0,
"filtration value specified for a complex that does not store them");
183 Filtration_simplex_base_dummy>::type Filtration_simplex_base;
195 typedef typename Dictionary::iterator Dictionary_it;
196 typedef typename Dictionary::const_iterator Dictionary_const_it;
197 typedef typename Dictionary_it::value_type Dit_value_t;
199 struct return_first {
214 using Optimized_star_simplex_range = boost::iterator_range<Optimized_star_simplex_iterator>;
216 class Fast_cofaces_predicate {
221 Fast_cofaces_predicate(
Simplex_tree const* st,
int codim,
int dim)
222 : st_(st), codim_(codim), dim_(codim + dim) {}
223 bool operator()(
const Simplex_handle iter )
const {
228 return dim_ == st_->dimension(iter);
234 using Optimized_cofaces_simplex_filtered_range = boost::filtered_range<Fast_cofaces_predicate,
235 Optimized_star_simplex_range>;
240 static constexpr int max_dimension() {
return 40; }
264 Optimized_cofaces_simplex_filtered_range,
270 using Static_vertex_vector = boost::container::static_vector<
Vertex_handle, max_dimension()>;
312 return Complex_vertex_range(boost::make_transform_iterator(root_.members_.begin(), return_first()),
313 boost::make_transform_iterator(root_.members_.end(), return_first()));
360 return filtration_vect_;
389 template<
class SimplexHandle>
406 template<
class SimplexHandle>
2734template<
typename...T>
2736 for (
auto sh : st.filtration_simplex_range()) {
2737 os << st.dimension(sh) <<
" ";
2738 for (
auto v : st.simplex_vertex_range(sh)) {
2746template<
typename...T>
2749 std::vector<typename ST::Vertex_handle> simplex;
2755 int dim =
static_cast<int> (simplex.size() - 1);
2756 if (max_dim < dim) {
Extended simplex type data structure for representing the type of simplices in an extended filtration...
Iterator over the simplices of the boundary of a simplex and their opposite vertices.
Definition Simplex_tree_iterators.h:193
Iterator over the simplices of the boundary of a simplex.
Definition Simplex_tree_iterators.h:81
Iterator over the simplices of a simplicial complex.
Definition Simplex_tree_iterators.h:308
Iterator over the simplices of the star of a simplex.
Definition Simplex_tree_star_simplex_iterators.h:162
Data structure to store a set of nodes in a SimplexTree sharing the same parent node.
Definition Simplex_tree_siblings.h:28
Iterator over the vertices of a simplex in a SimplexTree.
Definition Simplex_tree_iterators.h:36
Iterator over the simplices of the skeleton of a given dimension of the simplicial complex.
Definition Simplex_tree_iterators.h:382
Simplex Tree data structure for representing simplicial complexes.
Definition Simplex_tree.h:98
Simplex_tree(Simplex_tree &&complex_source)
User-defined move constructor relocates the whole tree structure including extra data (Simplex_data) ...
Definition Simplex_tree.h:460
std::vector< size_t > num_simplices_by_dimension() const
Returns the number of simplices of each dimension in the simplex tree.
Definition Simplex_tree.h:826
void for_each_simplex(Fun &&fun) const
Definition Simplex_tree.h:2015
void insert_edge_as_flag(Vertex_handle u, Vertex_handle v, Filtration_value fil, int dim_max, std::vector< Simplex_handle > &added_simplices)
Adds a new vertex or a new edge in a flag complex, as well as all simplices of its star,...
Definition Simplex_tree.h:1559
Options::Filtration_value Filtration_value
Type for the value of the filtration function.
Definition Simplex_tree.h:105
Simplex_tree_boundary_opposite_vertex_simplex_iterator< Simplex_tree > Boundary_opposite_vertex_simplex_iterator
Iterator over the simplices of the boundary of a simplex and their opposite vertices.
Definition Simplex_tree.h:281
void reset_filtration(Filtration_value filt_value, int min_dim=0)
This function resets the filtration value of all the simplices of dimension at least min_dim....
Definition Simplex_tree.h:2548
int dimension(Simplex_handle sh) const
Returns the dimension of a simplex.
Definition Simplex_tree.h:847
void assign_filtration(Simplex_handle sh, Filtration_value fv)
Sets the filtration value of a simplex.
Definition Simplex_tree.h:738
Siblings const * self_siblings(SimplexHandle sh) const
Definition Simplex_tree.h:1154
std::conditional< Options::link_nodes_by_label, Optimized_cofaces_simplex_filtered_range, std::vector< Simplex_handle > >::type Cofaces_simplex_range
Range over the cofaces of a simplex.
Definition Simplex_tree.h:265
void initialize_filtration(bool ignore_infinite_values=false) const
Initializes the filtration cache, i.e. sorts the simplices according to their order in the filtration...
Definition Simplex_tree.h:1200
Complex_simplex_range complex_simplex_range() const
Returns a range over the simplices of the simplicial complex.
Definition Simplex_tree.h:321
bool make_filtration_non_decreasing()
This function ensures that each simplex has a higher filtration value than its faces by increasing th...
Definition Simplex_tree.h:2051
bool operator==(const Simplex_tree< OtherSimplexTreeOptions > &st2) const
Checks if two simplex trees are equal. Any extra data (Simplex_data) stored in the simplices are igno...
Definition Simplex_tree.h:653
Vertex_handle vertex_with_same_filtration(Simplex_handle sh) const
Returns a vertex of sh that has the same filtration value as sh if it exists, and null_vertex() other...
Definition Simplex_tree.h:2370
bool operator!=(const Simplex_tree< OtherSimplexTreeOptions > &st2) const
Checks if two simplex trees are different.
Definition Simplex_tree.h:662
bool prune_above_dimension(int dimension)
Remove all simplices of dimension greater than a given value.
Definition Simplex_tree.h:2162
std::pair< Simplex_handle, bool > insert_simplex(const InputVertexRange &simplex, Filtration_value filtration=0)
Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex.
Definition Simplex_tree.h:1045
Vertex_handle null_vertex() const
Returns a Vertex_handle different from all Vertex_handles associated to the vertices of the simplicia...
Definition Simplex_tree.h:773
Simplex_handle edge_with_same_filtration(Simplex_handle sh) const
Returns an edge of sh that has the same filtration value as sh if it exists, and null_simplex() other...
Definition Simplex_tree.h:2384
boost::iterator_range< Boundary_simplex_iterator > Boundary_simplex_range
Range over the simplices of the boundary of a simplex.
Definition Simplex_tree.h:277
Simplex_vertex_range simplex_vertex_range(Simplex_handle sh) const
Returns a range over the vertices of a simplex.
Definition Simplex_tree.h:369
Boundary_opposite_vertex_simplex_range boundary_opposite_vertex_simplex_range(SimplexHandle sh) const
Given a simplex, returns a range over the simplices of its boundary and their opposite vertices.
Definition Simplex_tree.h:407
Simplex_tree_simplex_vertex_iterator< Simplex_tree > Simplex_vertex_iterator
Iterator over the vertices of a simplex.
Definition Simplex_tree.h:259
void clear()
Remove all the simplices, leaving an empty complex.
Definition Simplex_tree.h:2081
static Simplex_key key(Simplex_handle sh)
Returns the key associated to a simplex.
Definition Simplex_tree.h:708
static Filtration_value filtration(Simplex_handle sh)
Returns the filtration value of a simplex.
Definition Simplex_tree.h:727
Simplex_tree(const Simplex_tree< OtherSimplexTreeOptions > &complex_source, F &&translate_filtration_value)
Construct the simplex tree as the copy of a given simplex tree with eventually different template par...
Definition Simplex_tree.h:439
Cofaces_simplex_range star_simplex_range(const Simplex_handle simplex) const
Compute the star of a n simplex.
Definition Simplex_tree.h:1310
boost::transform_iterator< return_first, Dictionary_const_it > Complex_vertex_iterator
Iterator over the vertices of the simplicial complex.
Definition Simplex_tree.h:253
bool has_children(SimplexHandle sh) const
Returns true if the node in the simplex tree pointed by the given simplex handle has children.
Definition Simplex_tree.h:874
void expansion_with_blockers(int max_dim, Blocker block_simplex)
Expands a simplex tree containing only a graph. Simplices corresponding to cliques in the graph are a...
Definition Simplex_tree.h:1884
boost::iterator_range< Simplex_vertex_iterator > Simplex_vertex_range
Range over the vertices of a simplex.
Definition Simplex_tree.h:261
void remove_maximal_simplex(Simplex_handle sh)
Remove a maximal simplex.
Definition Simplex_tree.h:2243
void assign_key(Simplex_handle sh, Simplex_key key)
Assign a value 'key' to the key of the simplex represented by the Simplex_handle 'sh'.
Definition Simplex_tree.h:1140
Options::Simplex_key Simplex_key
Key associated to each simplex.
Definition Simplex_tree.h:109
Simplex_tree()
Constructs an empty simplex tree.
Definition Simplex_tree.h:417
boost::iterator_range< Complex_simplex_iterator > Complex_simplex_range
Range over the simplices of the simplicial complex.
Definition Simplex_tree.h:289
Dictionary::const_iterator Simplex_handle
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
Definition Simplex_tree.h:192
Simplex_tree_boundary_simplex_iterator< Simplex_tree > Boundary_simplex_iterator
Iterator over the simplices of the boundary of a simplex.
Definition Simplex_tree.h:275
const Simplex_data & simplex_data(Simplex_handle sh) const
Returns the extra data stored in a simplex.
Definition Simplex_tree.h:765
Simplex_tree_siblings< Simplex_tree, Dictionary > Siblings
Set of nodes sharing a same parent in the simplex tree.
Definition Simplex_tree.h:136
Siblings * self_siblings(SimplexHandle sh)
Definition Simplex_tree.h:1163
std::pair< Simplex_handle, Simplex_handle > endpoints(Simplex_handle sh) const
Definition Simplex_tree.h:1147
bool is_empty() const
Returns whether the complex is empty.
Definition Simplex_tree.h:783
Simplex_tree_complex_simplex_iterator< Simplex_tree > Complex_simplex_iterator
Iterator over the simplices of the simplicial complex.
Definition Simplex_tree.h:287
Simplex_handle simplex(Simplex_key idx) const
Returns the simplex that has index idx in the filtration.
Definition Simplex_tree.h:718
void print_hasse(std::ostream &os) const
Write the hasse diagram of the simplicial complex in os.
Definition Simplex_tree.h:1993
Simplex_data & simplex_data(Simplex_handle sh)
Returns the extra data stored in a simplex.
Definition Simplex_tree.h:758
void insert_batch_vertices(VertexRange const &vertices, Filtration_value filt=0)
Inserts several vertices.
Definition Simplex_tree.h:1487
std::vector< Simplex_handle > Filtration_simplex_range
Range over the simplices of the simplicial complex, ordered by the filtration.
Definition Simplex_tree.h:299
Filtration_simplex_range::const_iterator Filtration_simplex_iterator
Iterator over the simplices of the simplicial complex, ordered by the filtration.
Definition Simplex_tree.h:303
int dimension() const
Returns the dimension of the simplicial complex.
Definition Simplex_tree.h:865
Extended_filtration_data extend_filtration()
Extend filtration for computing extended persistence. This function only uses the filtration values a...
Definition Simplex_tree.h:2310
std::pair< Filtration_value, Extended_simplex_type > decode_extended_filtration(Filtration_value f, const Extended_filtration_data &efd) const
Retrieve the original filtration value for a given simplex in the Simplex_tree. Since the computation...
Definition Simplex_tree.h:2283
void maybe_initialize_filtration() const
Initializes the filtration cache if it isn't initialized yet.
Definition Simplex_tree.h:1231
Options::Vertex_handle Vertex_handle
Type for the vertex handle.
Definition Simplex_tree.h:119
Skeleton_simplex_range skeleton_simplex_range(int dim) const
Returns a range over the simplices of the dim-skeleton of the simplicial complex.
Definition Simplex_tree.h:335
Filtration_simplex_range const & filtration_simplex_range(Indexing_tag=Indexing_tag()) const
Returns a range over the simplices of the simplicial complex, in the order of the filtration.
Definition Simplex_tree.h:358
size_t num_vertices() const
Returns the number of vertices in the complex.
Definition Simplex_tree.h:778
Cofaces_simplex_range cofaces_simplex_range(const Simplex_handle simplex, int codimension) const
Compute the cofaces of a n simplex.
Definition Simplex_tree.h:1324
void clear_filtration() const
Clears the filtration cache produced by initialize_filtration().
Definition Simplex_tree.h:1243
void expansion(int max_dim)
Expands the Simplex_tree containing only its one skeleton until dimension max_dim.
Definition Simplex_tree.h:1512
Simplex_tree(const Simplex_tree &complex_source)
User-defined copy constructor reproduces the whole tree structure including extra data (Simplex_data)...
Definition Simplex_tree.h:449
size_t num_simplices() const
Returns the number of simplices in the simplex_tree.
Definition Simplex_tree.h:791
boost::iterator_range< Complex_vertex_iterator > Complex_vertex_range
Range over the vertices of the simplicial complex.
Definition Simplex_tree.h:255
static Simplex_key null_key()
Returns a fixed number not in the interval [0, num_simplices()).
Definition Simplex_tree.h:753
Simplex_handle minimal_simplex_with_same_filtration(Simplex_handle sh) const
Returns a minimal face of sh that has the same filtration value as sh.
Definition Simplex_tree.h:2417
bool prune_above_filtration(Filtration_value filtration)
Prune above filtration value given as parameter.
Definition Simplex_tree.h:2097
int upper_bound_dimension() const
Returns an upper bound on the dimension of the simplicial complex.
Definition Simplex_tree.h:855
Siblings * root()
Definition Simplex_tree.h:1171
std::pair< Simplex_handle, bool > insert_simplex_and_subfaces(const InputVertexRange &Nsimplex, Filtration_value filtration=0)
Insert a N-simplex and all his subfaces, from a N-simplex represented by a range of Vertex_handles,...
Definition Simplex_tree.h:1074
Simplex_tree_skeleton_simplex_iterator< Simplex_tree > Skeleton_simplex_iterator
Iterator over the simplices of the skeleton of the simplicial complex, for a given dimension.
Definition Simplex_tree.h:294
Simplex_tree & operator=(Simplex_tree &&complex_source)
User-defined move assignment relocates the whole tree structure including extra data (Simplex_data) s...
Definition Simplex_tree.h:497
const Siblings * root() const
Definition Simplex_tree.h:1174
boost::iterator_range< Boundary_opposite_vertex_simplex_iterator > Boundary_opposite_vertex_simplex_range
Range over the simplices of the boundary of a simplex and their opposite vertices.
Definition Simplex_tree.h:283
Simplex_tree & operator=(const Simplex_tree &complex_source)
User-defined copy assignment reproduces the whole tree structure including extra data (Simplex_data) ...
Definition Simplex_tree.h:479
Complex_vertex_range complex_vertex_range() const
Returns a range over the vertices of the simplicial complex. The order is increasing according to < o...
Definition Simplex_tree.h:311
void insert_graph(const OneSkeletonGraph &skel_graph)
Inserts a 1-skeleton in an empty Simplex_tree.
Definition Simplex_tree.h:1424
Get_simplex_data_type< Options >::type Simplex_data
Extra data stored in each simplex.
Definition Simplex_tree.h:115
Simplex_handle find(const InputVertexRange &s) const
Given a range of Vertex_handles, returns the Simplex_handle of the simplex in the simplicial complex ...
Definition Simplex_tree.h:899
boost::iterator_range< Skeleton_simplex_iterator > Skeleton_simplex_range
Range over the simplices of the skeleton of the simplicial complex, for a given dimension.
Definition Simplex_tree.h:297
~Simplex_tree()
Destructor; deallocates the whole tree structure.
Definition Simplex_tree.h:472
static Simplex_handle null_simplex()
Returns a Simplex_handle different from all Simplex_handles associated to the simplices in the simpli...
Definition Simplex_tree.h:748
Boundary_simplex_range boundary_simplex_range(SimplexHandle sh) const
Returns a range over the simplices of the boundary of a simplex.
Definition Simplex_tree.h:390
void set_dimension(int dimension, bool exact=true)
Set a dimension for the simplicial complex.
Definition Simplex_tree.h:1184
Graph simplicial complex methods.
std::ostream & operator<<(std::ostream &os, const Permutahedral_representation< Vertex, OrderedSetPartition > &simplex)
Print a permutahedral representation to a stream.
Definition Permutahedral_representation.h:173
Gudhi namespace.
Definition SimplicialComplexForAlpha.h:14
bool read_simplex(std::istream &in_, std::vector< Vertex_handle > &simplex, Filtration_value &fil)
Read a face from a file.
Definition reader_utils.h:158
This file includes common file reader for GUDHI.
Value type for a filtration function on a cell complex.
Definition FiltrationValue.h:20
No hook when SimplexTreeOptions::link_nodes_by_label is false.
Definition hooks_simplex_base.h:20
Data structure to put all simplex tree nodes with same label into a list.
Definition hooks_simplex_base.h:29
Node of a simplex tree with filtration value and simplex key.
Definition Simplex_tree_node_explicit_storage.h:40
Concept describing an indexing scheme (see FilteredComplex) for applying continuous maps to a cell co...
Definition IndexingTag.h:18
Key type used as simplex identifier.
Definition SimplexKey.h:15
Concept of the template parameter for the class Gudhi::Simplex_tree<SimplexTreeOptions>.
Definition SimplexTreeOptions.h:17
static const bool store_key
If true, each simplex has extra storage for one Simplex_key. Necessary for Persistent_cohomology.
Definition SimplexTreeOptions.h:29
static const bool store_filtration
If true, each simplex has extra storage for one Filtration_value, and this value is propagated by ope...
Definition SimplexTreeOptions.h:34
static const bool link_nodes_by_label
If true, the lists of Node with same label are stored to enhance cofaces and stars access.
Definition SimplexTreeOptions.h:39
static const bool stable_simplex_handles
If true, Simplex_handle will not be invalidated after insertions or removals.
Definition SimplexTreeOptions.h:41
static constexpr bool contiguous_vertices
If true, the list of vertices present in the complex must always be 0, ..., num_vertices-1,...
Definition SimplexTreeOptions.h:37
Handle type for the vertices of a cell complex.
Definition VertexHandle.h:15