Simplex Tree data structure for representing simplicial complexes. More...
#include <Simplex_tree.h>
Public Types | |
typedef Options::Filtration_value | Filtration_value |
Type for the value of the filtration function. More... | |
typedef Options::Simplex_key | Simplex_key |
Key associated to each simplex. More... | |
typedef Options::Vertex_handle | Vertex_handle |
Type for the vertex handle. More... | |
typedef Dictionary::iterator | Simplex_handle |
Handle type to a simplex contained in the simplicial complex represented by the simplex tree. | |
Range and iterator types | |
The naming convention is Container_content_(iterator/range). A Container_content_range is essentially an object on which the methods begin() and end() can be called. They both return an object of type Container_content_iterator, and allow the traversal of the range [ begin();end() ). | |
typedef boost::transform_iterator < return_first, Dictionary_it > | Complex_vertex_iterator |
Iterator over the vertices of the simplicial complex. More... | |
typedef boost::iterator_range < Complex_vertex_iterator > | Complex_vertex_range |
Range over the vertices of the simplicial complex. | |
typedef Simplex_tree_simplex_vertex_iterator < Simplex_tree > | Simplex_vertex_iterator |
Iterator over the vertices of a simplex. More... | |
typedef boost::iterator_range < Simplex_vertex_iterator > | Simplex_vertex_range |
Range over the vertices of a simplex. | |
typedef std::vector < Simplex_handle > | Cofaces_simplex_range |
Range over the cofaces of a simplex. | |
typedef Simplex_tree_boundary_simplex_iterator < Simplex_tree > | Boundary_simplex_iterator |
Iterator over the simplices of the boundary of a simplex. More... | |
typedef boost::iterator_range < Boundary_simplex_iterator > | Boundary_simplex_range |
Range over the simplices of the boundary of a simplex. | |
typedef Simplex_tree_complex_simplex_iterator < Simplex_tree > | Complex_simplex_iterator |
Iterator over the simplices of the simplicial complex. More... | |
typedef boost::iterator_range < Complex_simplex_iterator > | Complex_simplex_range |
Range over the simplices of the simplicial complex. | |
typedef 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. More... | |
typedef boost::iterator_range < Skeleton_simplex_iterator > | Skeleton_simplex_range |
Range over the simplices of the skeleton of the simplicial complex, for a given dimension. | |
typedef std::vector < Simplex_handle > | Filtration_simplex_range |
Range over the simplices of the simplicial complex, ordered by the filtration. | |
typedef Filtration_simplex_range::const_iterator | Filtration_simplex_iterator |
Iterator over the simplices of the simplicial complex, ordered by the filtration. More... | |
![]() | |
typedef unspecified | Simplex_handle |
typedef unspecified | Simplex_key |
Key associated to each simplex. More... | |
typedef unspecified | Filtration_value |
Type for the value of the filtration function. More... | |
typedef unspecified | Indexing_tag |
Specifies the nature of the indexing scheme. More... | |
typedef unspecified | Boundary_simplex_iterator |
Iterator on the simplices belonging to the boundary of a simplex. More... | |
typedef unspecified | Boundary_simplex_range |
Range giving access to the simplices in the boundary of a simplex. More... | |
typedef unspecified | Filtration_simplex_iterator |
Iterator over all simplices of the complex in the order of the indexing scheme. More... | |
typedef unspecified | Filtration_simplex_range |
Range over the simplices of the complex in the order of the filtration. More... | |
Public Member Functions | |
bool | operator== (Simplex_tree &st2) |
Checks if two simplex trees are equal. | |
bool | operator!= (Simplex_tree &st2) |
Checks if two simplex trees are different. | |
Simplex_handle | simplex (Simplex_key key) const |
Returns the simplex associated to a key. More... | |
Filtration_value | filtration () const |
Returns an upper bound of the filtration values of the simplices. | |
Vertex_handle | null_vertex () const |
Returns a Vertex_handle different from all Vertex_handles associated to the vertices of the simplicial complex. | |
size_t | num_vertices () const |
Returns the number of vertices in the complex. | |
size_t | num_simplices () |
returns the number of simplices in the simplex_tree. | |
int | dimension (Simplex_handle sh) |
Returns the dimension of a simplex. More... | |
int | dimension () const |
Returns an upper bound on the dimension of the simplicial complex. | |
bool | has_children (Simplex_handle sh) const |
Returns true iff the node in the simplex tree pointed by sh has children. | |
template<class InputVertexRange > | |
Simplex_handle | find (const InputVertexRange &s) |
Given a range of Vertex_handles, returns the Simplex_handle of the simplex in the simplicial complex containing the corresponding vertices. Return null_simplex() if the simplex is not in the complex. More... | |
template<class InputVertexRange > | |
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. More... | |
template<class InputVertexRange > | |
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, in the simplicial complex. More... | |
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'. | |
std::pair< Simplex_handle, Simplex_handle > | endpoints (Simplex_handle sh) |
Siblings * | self_siblings (Simplex_handle sh) |
Siblings * | root () |
void | set_filtration (Filtration_value fil) |
void | set_dimension (int dimension) |
void | initialize_filtration () |
Initializes the filtrations, i.e. sort the simplices according to their order in the filtration and initializes all Simplex_keys. More... | |
Cofaces_simplex_range | star_simplex_range (const Simplex_handle simplex) |
Compute the star of a n simplex. More... | |
Cofaces_simplex_range | cofaces_simplex_range (const Simplex_handle simplex, int codimension) |
Compute the cofaces of a n simplex. More... | |
template<class OneSkeletonGraph > | |
void | insert_graph (const OneSkeletonGraph &skel_graph) |
Inserts a 1-skeleton in an empty Simplex_tree. More... | |
void | expansion (int max_dim) |
Expands the Simplex_tree containing only its one skeleton until dimension max_dim. More... | |
void | print_hasse (std::ostream &os) |
Write the hasse diagram of the simplicial complex in os. More... | |
Range and iterator methods | |
Complex_vertex_range | complex_vertex_range () |
Returns a range over the vertices of the simplicial complex. The order is increasing according to < on Vertex_handles. | |
Complex_simplex_range | complex_simplex_range () |
Returns a range over the simplices of the simplicial complex. More... | |
Skeleton_simplex_range | skeleton_simplex_range (int dim) |
Returns a range over the simplices of the dim-skeleton of the simplicial complex. More... | |
Filtration_simplex_range const & | filtration_simplex_range (Indexing_tag=Indexing_tag()) |
Returns a range over the simplices of the simplicial complex, in the order of the filtration. More... | |
Simplex_vertex_range | simplex_vertex_range (Simplex_handle sh) |
Returns a range over the vertices of a simplex. More... | |
Boundary_simplex_range | boundary_simplex_range (Simplex_handle sh) |
Returns a range over the simplices of the boundary of a simplex. More... | |
Constructor/Destructor | |
Simplex_tree () | |
Constructs an empty simplex tree. | |
Simplex_tree (const Simplex_tree &simplex_source) | |
User-defined copy constructor reproduces the whole tree structure. | |
void | rec_copy (Siblings *sib, Siblings *sib_source) |
depth first search, inserts simplices when reaching a leaf. | |
Simplex_tree (Simplex_tree &&old) | |
User-defined move constructor moves the whole tree structure. | |
~Simplex_tree () | |
Destructor; deallocates the whole tree structure. | |
![]() | |
Simplex_handle | null_simplex () |
size_t | num_simplices () |
Returns the number of simplices in the complex. More... | |
int | dimension (Simplex_handle sh) |
Returns the dimension of a simplex. | |
Filtration_value | filtration (Simplex_handle sh) |
Returns the filtration value of a simplex. More... | |
Simplex_key | null_key () |
Returns a key that is different from the keys associated to the simplices. | |
Simplex_key | key (Simplex_handle sh) |
Returns the key associated to a simplex. | |
Simplex_handle | simplex (Simplex_key key) |
Returns the simplex associated to a key. More... | |
void | assign_key (Simplex_handle sh, Simplex_key key) |
Assign a key to a simplex. | |
Boundary_simplex_range | boundary_simplex_range (Simplex_handle sh) |
Returns a range giving access to all simplices of the boundary of a simplex, i.e. the set of codimension 1 subsimplices of the Simplex. More... | |
Filtration_simplex_range | filtration_simplex_range () |
Returns a range over the simplices of the complex in the order of the filtration. More... | |
Static Public Member Functions | |
static Simplex_key | key (Simplex_handle sh) |
Returns the key associated to a simplex. More... | |
static Filtration_value | filtration (Simplex_handle sh) |
Returns the filtration value of a simplex. More... | |
static Simplex_handle | null_simplex () |
Returns a Simplex_handle different from all Simplex_handles associated to the simplices in the simplicial complex. More... | |
static Simplex_key | null_key () |
Returns a key different for all keys associated to the simplices of the simplicial complex. | |
Simplex Tree data structure for representing simplicial complexes.
Every simplex admits a canonical orientation induced by the order relation on vertices
.
Details may be found in [4].
typedef Simplex_tree_boundary_simplex_iterator<Simplex_tree> Gudhi::Simplex_tree< SimplexTreeOptions >::Boundary_simplex_iterator |
Iterator over the simplices of the boundary of a simplex.
'value_type' is Simplex_handle.
typedef Simplex_tree_complex_simplex_iterator<Simplex_tree> Gudhi::Simplex_tree< SimplexTreeOptions >::Complex_simplex_iterator |
Iterator over the simplices of the simplicial complex.
'value_type' is Simplex_handle.
typedef boost::transform_iterator<return_first, Dictionary_it> Gudhi::Simplex_tree< SimplexTreeOptions >::Complex_vertex_iterator |
Iterator over the vertices of the simplicial complex.
'value_type' is Vertex_handle.
typedef Filtration_simplex_range::const_iterator Gudhi::Simplex_tree< SimplexTreeOptions >::Filtration_simplex_iterator |
Iterator over the simplices of the simplicial complex, ordered by the filtration.
'value_type' is Simplex_handle.
typedef Options::Filtration_value Gudhi::Simplex_tree< SimplexTreeOptions >::Filtration_value |
Type for the value of the filtration function.
Must be comparable with <.
typedef Options::Simplex_key Gudhi::Simplex_tree< SimplexTreeOptions >::Simplex_key |
Key associated to each simplex.
Must be a signed integer type.
typedef Simplex_tree_simplex_vertex_iterator<Simplex_tree> Gudhi::Simplex_tree< SimplexTreeOptions >::Simplex_vertex_iterator |
Iterator over the vertices of a simplex.
'value_type' is Vertex_handle.
typedef Simplex_tree_skeleton_simplex_iterator<Simplex_tree> Gudhi::Simplex_tree< SimplexTreeOptions >::Skeleton_simplex_iterator |
Iterator over the simplices of the skeleton of the simplicial complex, for a given dimension.
'value_type' is Simplex_handle.
typedef Options::Vertex_handle Gudhi::Simplex_tree< SimplexTreeOptions >::Vertex_handle |
Type for the vertex handle.
Must be a signed integer type. It admits a total order <.
|
inline |
Returns a range over the simplices of the boundary of a simplex.
The boundary of a simplex is the set of codimension subsimplices of the simplex. If the simplex is
, with canonical orientation induced by
, the iterator enumerates the simplices of the boundary in the order:
for
from
to
, where
means that the vertex
is omitted.
We note that the alternate sum of the simplices given by the iterator gives the chains corresponding to the boundary of the simplex.
[in] | sh | Simplex for which the boundary is computed. |
|
inline |
Compute the cofaces of a n simplex.
simplex | represent the n-simplex of which we search the n+codimension cofaces |
codimension | The function returns the n+codimension-cofaces of the n-simplex. If codimension = 0, return all cofaces (equivalent of star function) |
|
inline |
Returns a range over the simplices of the simplicial complex.
In the Simplex_tree, the tree is traverse in a depth-first fashion. Consequently, simplices are ordered according to lexicographic order on the list of Vertex_handles of a simplex, read in increasing < order for Vertex_handles.
|
inline |
Returns the dimension of a simplex.
Must be different from null_simplex().
|
inline |
Returns the two Simplex_handle corresponding to the endpoints of and edge. sh must point to a 1-dimensional simplex. This is an optimized version of the boundary computation.
|
inline |
Expands the Simplex_tree containing only its one skeleton until dimension max_dim.
The expanded simplicial complex until dimension attached to a graph
is the maximal simplicial complex of dimension at most
admitting the graph
as
-skeleton. The filtration value assigned to a simplex is the maximal filtration value of one of its edges.
The Simplex_tree must contain no simplex of dimension bigger than 1 when calling the method.
|
inlinestatic |
Returns the filtration value of a simplex.
Called on the null_simplex, returns INFINITY. If SimplexTreeOptions::store_filtration is false, returns 0.
|
inline |
Returns a range over the simplices of the simplicial complex, in the order of the filtration.
The filtration is a monotonic function , i.e. if two simplices
and
satisfy
then
.
The method returns simplices ordered according to increasing filtration values. Ties are resolved by considering inclusion relation (subsimplices appear before their cofaces). If two simplices have same filtration value but are not comparable w.r.t. inclusion, lexicographic 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). If the complex has changed since the last time the filtration was initialized, please call initialize_filtration()
to recompute it.
|
inline |
Given a range of Vertex_handles, returns the Simplex_handle of the simplex in the simplicial complex containing the corresponding vertices. Return null_simplex() if the simplex is not in the complex.
The type InputVertexRange must be a range of Vertex_handle
on which we can call std::begin() function
|
inline |
Initializes the filtrations, i.e. sort the simplices according to their order in the filtration and initializes all Simplex_keys.
After calling this method, filtration_simplex_range() becomes valid, and each simplex is assigned a Simplex_key corresponding to its order in the filtration (from 0 to m-1 for a simplicial complex with m simplices).
Will be automatically called when calling filtration_simplex_range() if the filtration has never been initialized yet.
|
inline |
Inserts a 1-skeleton in an empty Simplex_tree.
The Simplex_tree must contain no simplex when the method is called.
Inserts all vertices and edges given by a OneSkeletonGraph. OneSkeletonGraph must be a model of boost::AdjacencyGraph, boost::EdgeListGraph and boost::PropertyGraph.
The vertex filtration value is accessible through the property tag vertex_filtration_t. The edge filtration value is accessible through the property tag edge_filtration_t.
boost::graph_traits<OneSkeletonGraph>::vertex_descriptor must be Vertex_handle. boost::graph_traits<OneSkeletonGraph>::directed_category must be undirected_tag.
|
inline |
Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex.
[in] | simplex | range of Vertex_handles, representing the vertices of the new simplex |
[in] | filtration | the filtration value assigned to the new simplex. The return type is a pair. If the new simplex is inserted successfully (i.e. it was not in the simplicial complex yet) the bool is set to true and the Simplex_handle is the handle assigned to the new simplex. If the insertion fails (the simplex is already there), the bool is set to false. If the insertion fails and the simplex already in the complex has a filtration value strictly bigger than 'filtration', we assign this simplex with the new value 'filtration', and set the Simplex_handle field of the output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to null_simplex. |
All subsimplices do not necessary need to be already in the simplex tree to proceed to an insertion. However, the property of being a simplicial complex will be violated. This allows us to insert a stream of simplices contained in a simplicial complex without considering any order on them.
The filtration value assigned to the new simplex must preserve the monotonicity of the filtration.
The type InputVertexRange must be a range for which .begin() and .end() return input iterators, with 'value_type' Vertex_handle.
|
inline |
Insert a N-simplex and all his subfaces, from a N-simplex represented by a range of Vertex_handles, in the simplicial complex.
[in] | Nsimplex | range of Vertex_handles, representing the vertices of the new N-simplex |
[in] | filtration | the filtration value assigned to the new N-simplex. The return type is a pair. If the new simplex is inserted successfully (i.e. it was not in the simplicial complex yet) the bool is set to true and the Simplex_handle is the handle assigned to the new simplex. If the insertion fails (the simplex is already there), the bool is set to false. If the insertion fails and the simplex already in the complex has a filtration value strictly bigger than 'filtration', we assign this simplex with the new value 'filtration', and set the Simplex_handle field of the output pair to the Simplex_handle of the simplex. Otherwise, we set the Simplex_handle part to null_simplex. |
|
inlinestatic |
Returns the key associated to a simplex.
The filtration must be initialized.
|
inlinestatic |
Returns a Simplex_handle different from all Simplex_handles associated to the simplices in the simplicial complex.
One can call filtration(null_simplex()).
|
inline |
Write the hasse diagram of the simplicial complex in os.
Each row in the file correspond to a simplex. A line is written: dim idx_1 ... idx_k fil where dim is the dimension of the simplex, idx_1 ... idx_k are the row index (starting from 0) of the simplices of the boundary of the simplex, and fil is its filtration value.
|
inline |
Returns a pointer to the root nodes of the simplex tree.
|
inline |
Returns the Siblings containing a simplex.
|
inline |
Set a dimension for the simplicial complex.
|
inline |
Set an upper bound for the filtration values.
|
inline |
Returns the simplex associated to a key.
The filtration must be initialized.
|
inline |
Returns a range over the vertices of a simplex.
The order in which the vertices are visited is the decreasing order for < on Vertex_handles, which is consequenlty equal to the canonical orientation on the simplex.
|
inline |
Returns a range over the simplices of the dim-skeleton of the simplicial complex.
The -skeleton of a simplicial complex
is the simplicial complex containing the simplices of
of dimension at most
.
[in] | dim | The maximal dimension of the simplices in the skeleton. |
The simplices are ordered according to lexicographic order on the list of Vertex_handles of a simplex, read in increasing < order for Vertex_handles.
|
inline |
Compute the star of a n simplex.
simplex | represent the simplex of which we search the star |