|
|
|
Simplex Tree data structure for representing simplicial complexes. More...
#include <gudhi/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 Simplex_tree_siblings< Simplex_tree, Dictionary > | Siblings |
| Set of nodes sharing a same parent in the simplex tree. | |
| typedef Dictionary::iterator | Simplex_handle |
| Handle type to a simplex contained in the simplicial complex represented by the simplex tree. More... | |
Public Member Functions | |
| template<class OtherSimplexTreeOptions > | |
| bool | operator== (Simplex_tree< OtherSimplexTreeOptions > &st2) |
| Checks if two simplex trees are equal. | |
| template<class OtherSimplexTreeOptions > | |
| bool | operator!= (Simplex_tree< OtherSimplexTreeOptions > &st2) |
| Checks if two simplex trees are different. | |
| Simplex_handle | simplex (Simplex_key idx) const |
| Returns the simplex that has index idx in the filtration. More... | |
| void | assign_filtration (Simplex_handle sh, Filtration_value fv) |
| Sets the filtration value of a simplex. More... | |
| 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. | |
| bool | is_empty () const |
| Returns whether the complex is empty. | |
| size_t | num_simplices () |
| Returns the number of simplices in the simplex_tree. More... | |
| std::vector< size_t > | num_simplices_by_dimension () |
| Returns the number of simplices of each dimension in the simplex tree. | |
| int | dimension (Simplex_handle sh) |
| Returns the dimension of a simplex. More... | |
| int | upper_bound_dimension () const |
| Returns an upper bound on the dimension of the simplicial complex. | |
| int | dimension () |
| Returns the dimension of the simplicial complex. More... | |
| template<class SimplexHandle > | |
| bool | has_children (SimplexHandle sh) const |
| Returns true if the node in the simplex tree pointed by the given simplex handle has children. | |
| template<class InputVertexRange = std::initializer_list<Vertex_handle>> | |
| 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::initializer_list<Vertex_handle>> | |
| 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::initializer_list<Vertex_handle>> | |
| 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 * | root () |
| void | set_dimension (int dimension, bool exact=true) |
| Set a dimension for the simplicial complex. More... | |
| void | initialize_filtration (bool ignore_infinite_values=false) |
| Initializes the filtration cache, i.e. sorts the simplices according to their order in the filtration. More... | |
| void | maybe_initialize_filtration () |
| Initializes the filtration cache if it isn't initialized yet. More... | |
| void | clear_filtration () |
| Clears the filtration cache produced by initialize_filtration(). 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... | |
| template<class VertexRange > | |
| void | insert_batch_vertices (VertexRange const &vertices, Filtration_value filt=0) |
| Inserts several vertices. More... | |
| void | expansion (int max_dim) |
| Expands the Simplex_tree containing only its one skeleton until dimension max_dim. More... | |
| 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, defined to maintain the property of the complex to be a flag complex, truncated at dimension dim_max. To insert a new edge, the two given vertex handles have to correspond to the two end points of the edge. To insert a new vertex, the handles have to be twice the same and correspond to the number you want assigned to it. I.e., to insert vertex \(i\), give \(u = v = i\). The method assumes that the given edge was not already contained in the simplex tree, so the behaviour is undefined if called on an existing edge. Also, the vertices of an edge have to be inserted before the edge. More... | |
| template<typename Blocker > | |
| 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 added incrementally, faces before cofaces, unless the simplex has dimension larger than max_dim or block_simplex returns true for this simplex. More... | |
| void | print_hasse (std::ostream &os) |
| Write the hasse diagram of the simplicial complex in os. More... | |
| template<class Fun > | |
| void | for_each_simplex (Fun &&fun) |
| bool | make_filtration_non_decreasing () |
| This function ensures that each simplex has a higher filtration value than its faces by increasing the filtration values. More... | |
| void | clear () |
| Remove all the simplices, leaving an empty complex. | |
| bool | prune_above_filtration (Filtration_value filtration) |
| Prune above filtration value given as parameter. More... | |
| bool | prune_above_dimension (int dimension) |
| Remove all simplices of dimension greater than a given value. More... | |
| void | remove_maximal_simplex (Simplex_handle sh) |
| Remove a maximal simplex. More... | |
| std::pair< Filtration_value, Extended_simplex_type > | decode_extended_filtration (Filtration_value f, const Extended_filtration_data &efd) |
| Retrieve the original filtration value for a given simplex in the Simplex_tree. Since the computation of extended persistence requires modifying the filtration values, this function can be used to recover the original values. Moreover, computing extended persistence requires adding new simplices in the Simplex_tree. Hence, this function also outputs the type of each simplex. It can be either UP (which means that the simplex was present originally, and is thus part of the ascending extended filtration), DOWN (which means that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or EXTRA (which means the simplex is the cone point). See the definition of Extended_simplex_type. Note that if the simplex type is DOWN, the original filtration value is set to be the original filtration value of the corresponding (not coned) original simplex. More... | |
| Extended_filtration_data | extend_filtration () |
| Extend filtration for computing extended persistence. This function only uses the filtration values at the 0-dimensional simplices, and computes the extended persistence diagram induced by the lower-star filtration computed with these values. More... | |
| Vertex_handle | vertex_with_same_filtration (Simplex_handle sh) |
Returns a vertex of sh that has the same filtration value as sh if it exists, and null_vertex() otherwise. More... | |
| Simplex_handle | edge_with_same_filtration (Simplex_handle sh) |
Returns an edge of sh that has the same filtration value as sh if it exists, and null_simplex() otherwise. More... | |
| Simplex_handle | minimal_simplex_with_same_filtration (Simplex_handle sh) |
Returns a minimal face of sh that has the same filtration value as sh. More... | |
| 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. Resets all the Simplex_tree when min_dim = 0. reset_filtration may break the filtration property with min_dim > 0, and it is the user's responsibility to make it a valid filtration (using a large enough filt_value, or calling make_filtration_non_decreasing afterwards for instance). 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) const |
| Returns a range over the vertices of a simplex. More... | |
| template<class SimplexHandle > | |
| Boundary_simplex_range | boundary_simplex_range (SimplexHandle sh) |
| Returns a range over the simplices of the boundary of a simplex. More... | |
| template<class SimplexHandle > | |
| Boundary_opposite_vertex_simplex_range | boundary_opposite_vertex_simplex_range (SimplexHandle sh) |
| Given a simplex, returns a range over the simplices of its boundary and their opposite vertices. More... | |
Constructor/Destructor | |
| Simplex_tree () | |
| Constructs an empty simplex tree. | |
| Simplex_tree (const Simplex_tree &complex_source) | |
| User-defined copy constructor reproduces the whole tree structure. | |
| Simplex_tree (Simplex_tree &&complex_source) | |
| User-defined move constructor relocates the whole tree structure. More... | |
| ~Simplex_tree () | |
| Destructor; deallocates the whole tree structure. | |
| Simplex_tree & | operator= (const Simplex_tree &complex_source) |
| User-defined copy assignment reproduces the whole tree structure. | |
| Simplex_tree & | operator= (Simplex_tree &&complex_source) |
| User-defined move assignment relocates the whole tree structure. 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 fixed number not in the interval [0, num_simplices()). | |
| template<class SimplexHandle > | |
| static Siblings * | self_siblings (SimplexHandle sh) |
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::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. | |
| 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_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. More... | |
| typedef 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. | |
| 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... | |
Simplex Tree data structure for representing simplicial complexes.
Every simplex \([v_0, \cdots ,v_d]\) admits a canonical orientation induced by the order relation on vertices \( v_0 < \cdots < v_d \).
Details may be found in [7].
| typedef Simplex_tree_boundary_opposite_vertex_simplex_iterator<Simplex_tree> Gudhi::Simplex_tree< SimplexTreeOptions >::Boundary_opposite_vertex_simplex_iterator |
Iterator over the simplices of the boundary of a simplex and their opposite vertices.
'value_type' is std::pair<Simplex_handle, Vertex_handle>.
| 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 Dictionary::iterator Gudhi::Simplex_tree< SimplexTreeOptions >::Simplex_handle |
Handle type to a simplex contained in the simplicial complex represented by the simplex tree.
They are essentially pointers into internal vectors, and any insertion or removal of a simplex may invalidate any other Simplex_handle in the complex, unless Options::stable_simplex_handles == true.
| typedef Options::Simplex_key Gudhi::Simplex_tree< SimplexTreeOptions >::Simplex_key |
Key associated to each simplex.
Must be an 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 |
User-defined move constructor relocates the whole tree structure.
| std::invalid_argument | In debug mode, if the complex_source is invalid. |
|
inline |
Sets the filtration value of a simplex.
| std::invalid_argument | In debug mode, if sh is a null_simplex. |
|
inline |
Given a simplex, returns a range over the simplices of its boundary and their opposite vertices.
The boundary of a simplex is the set of codimension \(1\) subsimplices of the simplex. If the simplex is \([v_0, \cdots ,v_d]\), with canonical orientation induced by \( v_0 < \cdots < v_d \), the iterator enumerates the simplices of the boundary in the order: \([v_0,\cdots,\widehat{v_i},\cdots,v_d]\) for \(i\) from \(d\) to \(0\), where \(\widehat{v_i}\) means that the vertex \(v_i\), known as the opposite vertex, is omitted from boundary, but returned as the second element of a pair.
| [in] | sh | Simplex for which the boundary is computed. |
|
inline |
Returns a range over the simplices of the boundary of a simplex.
The boundary of a simplex is the set of codimension \(1\) subsimplices of the simplex. If the simplex is \([v_0, \cdots ,v_d]\), with canonical orientation induced by \( v_0 < \cdots < v_d \), the iterator enumerates the simplices of the boundary in the order: \([v_0,\cdots,\widehat{v_i},\cdots,v_d]\) for \(i\) from \(0\) to \(d\), where \(\widehat{v_i}\) means that the vertex \(v_i\) is omitted.
We note that the alternate sum of the simplices given by the iterator gives \((-1)^{\text{dim} \sigma}\) the chains corresponding to the boundary of the simplex.
| [in] | sh | Simplex for which the boundary is computed. |
|
inline |
Clears the filtration cache produced by initialize_filtration().
Useful when initialize_filtration() has already been called and we perform an operation (say an insertion) that invalidates the cache.
|
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) |
Simplex_tree::Simplex_handle range for an optimized search for the coface of a simplex when SimplexTreeOptions::link_nodes_by_label is true.
|
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 |
Retrieve the original filtration value for a given simplex in the Simplex_tree. Since the computation of extended persistence requires modifying the filtration values, this function can be used to recover the original values. Moreover, computing extended persistence requires adding new simplices in the Simplex_tree. Hence, this function also outputs the type of each simplex. It can be either UP (which means that the simplex was present originally, and is thus part of the ascending extended filtration), DOWN (which means that the simplex is the cone of an original simplex, and is thus part of the descending extended filtration) or EXTRA (which means the simplex is the cone point). See the definition of Extended_simplex_type. Note that if the simplex type is DOWN, the original filtration value is set to be the original filtration value of the corresponding (not coned) original simplex.
extend_filtration() has been called first! | [in] | f | Filtration value of the simplex in the extended (i.e., modified) filtration. |
| [in] | efd | Structure containing the minimum and maximum values of the original filtration. This the output of extend_filtration(). |
|
inline |
Returns the dimension of the simplicial complex.
This function is not constant time because it can recompute dimension if required (can be triggered by remove_maximal_simplex() or prune_above_filtration()).
|
inline |
Returns the dimension of a simplex.
Must be different from null_simplex().
|
inline |
Returns an edge of sh that has the same filtration value as sh if it exists, and null_simplex() otherwise.
For a flag-complex built with expansion(), this is a way to invert the process and find out which edge had its filtration value propagated to sh. If several edges have the same filtration value, the one it returns is arbitrary.
sh must have dimension at least 1.
|
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 \(d\) attached to a graph \(G\) is the maximal simplicial complex of dimension at most \(d\) admitting the graph \(G\) as \(1\)-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.
|
inline |
Expands a simplex tree containing only a graph. Simplices corresponding to cliques in the graph are added incrementally, faces before cofaces, unless the simplex has dimension larger than max_dim or block_simplex returns true for this simplex.
| [in] | max_dim | Expansion maximal dimension value. |
| [in] | block_simplex | Blocker oracle. Its concept is bool block_simplex(Simplex_handle sh) |
The function identifies a candidate simplex whose faces are all already in the complex, inserts it with a filtration value corresponding to the maximum of the filtration values of the faces, then calls block_simplex on a Simplex_handle for this new simplex. If block_simplex returns true, the simplex is removed, otherwise it is kept. Note that the evaluation of block_simplex is a good time to update the filtration value of the simplex if you want a customized value. The algorithm then proceeds with the next candidate.
block_simplex, so if you examine the complex in block_simplex, you may hit a few simplices of the same dimension that have not been vetted by block_simplex yet, or have already been rejected but not yet removed.
|
inline |
Extend filtration for computing extended persistence. This function only uses the filtration values at the 0-dimensional simplices, and computes the extended persistence diagram induced by the lower-star filtration computed with these values.
decode_extended_filtration() retrieves the original values and outputs the extended simplex type. | std::invalid_argument | In debug mode if the Simplex tree contains a vertex with the largest Vertex_handle, as this method requires to create an extra vertex internally. |
decode_extended_filtration() in order to retrieve the original filtration values for each simplex.
|
inlinestatic |
Returns the filtration value of a simplex.
Called on the null_simplex, it 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 \( f: \mathbf{K} \rightarrow \mathbb{R} \), i.e. if two simplices \(\tau\) and \(\sigma\) satisfy \(\tau \subseteq \sigma\) then \(f(\tau) \leq f(\sigma)\).
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 clear_filtration() or 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 |
Calls a function on each simplex. The order ensures that faces are visited before cofaces. While it is fine to modify the data of a simplex (filtration, key) in the function, modifying the structure itself (insertion, removal) is not supported.
| [in] | fun | Function that takes as argument a Simplex_handle and an int (representing the dimension of this simplex). It may return void or bool, and in the second case returning true means that the iteration will skip the children of this simplex (a subset of the cofaces). |
|
inline |
Initializes the filtration cache, i.e. sorts the simplices according to their order in the filtration.
It always recomputes the cache, even if one already exists.
Any insertion, deletion or change of filtration value invalidates this cache, which can be cleared with clear_filtration().
|
inline |
Inserts several vertices.
| [in] | vertices | A range of Vertex_handle |
| [in] | filt | filtration value of the new vertices (the same for all) |
This may be faster than inserting the vertices one by one, especially in a random order. The complex does not need to be empty before calling this function. However, if a vertex is already present, its filtration value is not modified, unlike with other insertion functions.
|
inline |
Adds a new vertex or a new edge in a flag complex, as well as all simplices of its star, defined to maintain the property of the complex to be a flag complex, truncated at dimension dim_max. To insert a new edge, the two given vertex handles have to correspond to the two end points of the edge. To insert a new vertex, the handles have to be twice the same and correspond to the number you want assigned to it. I.e., to insert vertex \(i\), give \(u = v = i\). The method assumes that the given edge was not already contained in the simplex tree, so the behaviour is undefined if called on an existing edge. Also, the vertices of an edge have to be inserted before the edge.
| [in] | u,v | Vertex_handle representing the new edge (v != u) or the new vertex (v == u). |
| [in] | fil | Filtration value of the edge. |
| [in] | dim_max | Maximal dimension of the expansion. If set to -1, the expansion goes as far as possible. |
| [out] | added_simplices | Contains at the end all new simplices induced by the insertion of the edge. The container is not emptied and new simplices are appended at the end. |
SimplexTreeOptions::link_nodes_by_label must be true. [u,v], the vertices u and v have to be already inserted in the simplex tree.make_filtration_non_decreasing() has to be called at the end of the insertions to restore the intended filtration. Note that even then, an edge has to be inserted after its vertices. In term of edges in the graph, inserting edge [u,v] only affects the subtree rooted at u.
For a new node with label v, we first do a local expansion for computing the children of this new node, and then a standard expansion for its children. Nodes with label v (and their subtrees) already in the tree do not get affected.
Nodes with label u get affected only if a Node with label v is in their same siblings set. We then try to insert "ponctually" v all over the subtree rooted at Node(u). Each insertion of a Node with v label induces a local expansion at this Node (as explained above) and a sequence of "ponctual" insertion of Node(v) in the subtree rooted at sibling nodes of the new node, on its left.
|
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::VertexAndEdgeListGraph 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 can be directed_tag (the fastest, the least RAM use), undirected_tag or even bidirected_tag.
If an edge appears with multiplicity, the function will arbitrarily pick one representative to read the filtration value.
|
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. |
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. |
|
inlinestatic |
Returns the key associated to a simplex.
If no key has been assigned, returns null_key().
|
inline |
This function ensures that each simplex has a higher filtration value than its faces by increasing the filtration values.
If a simplex has a NaN filtration value, it is considered lower than any other defined filtration value.
|
inline |
Initializes the filtration cache if it isn't initialized yet.
Automatically called by filtration_simplex_range().
|
inline |
Returns a minimal face of sh that has the same filtration value as sh.
For a filtration built with make_filtration_non_decreasing(), this is a way to invert the process and find out which simplex had its filtration value propagated to sh. If several minimal (for inclusion) simplices have the same filtration value, the one it returns is arbitrary, and it is not guaranteed to be the one with smallest dimension.
|
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 |
Returns the number of simplices in the simplex_tree.
This function takes time linear in the number of simplices.
|
inline |
User-defined move assignment relocates the whole tree structure.
| std::invalid_argument | In debug mode, if the complex_source is invalid. |
|
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 |
Remove all simplices of dimension greater than a given value.
| [in] | dimension | Maximum dimension value. |
|
inline |
Prune above filtration value given as parameter.
| [in] | filtration | Maximum threshold value. |
prune_above_filtration() than it was before. However, upper_bound_dimension() will return the old value, which remains a valid upper bound. If you care, you can call dimension() to recompute the exact dimension.
|
inline |
Remove a maximal simplex.
| [in] | sh | Simplex handle on the maximal simplex to remove. |
| std::invalid_argument | In debug mode, if sh has children. |
remove_maximal_simplex() than it was before. However, upper_bound_dimension() will return the old value, which remains a valid upper bound. If you care, you can call dimension() to recompute the exact dimension.
|
inline |
This function resets the filtration value of all the simplices of dimension at least min_dim. Resets all the Simplex_tree when min_dim = 0. reset_filtration may break the filtration property with min_dim > 0, and it is the user's responsibility to make it a valid filtration (using a large enough filt_value, or calling make_filtration_non_decreasing afterwards for instance).
| [in] | filt_value | The new filtration value. |
| [in] | min_dim | The minimal dimension. Default value is 0. |
|
inline |
Returns a pointer to the root nodes of the simplex tree.
|
inlinestatic |
Returns the Siblings containing a simplex.
|
inline |
Set a dimension for the simplicial complex.
If exact is false, dimension is only an upper bound on the dimension of the complex. This function must be used with caution because it disables or limits the on-demand recomputation of the dimension (the need for recomputation can be caused by remove_maximal_simplex() or prune_above_filtration()).
|
inline |
Returns the simplex that has index idx in the filtration.
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 \((-1)^{\text{dim} \sigma}\) the canonical orientation on the simplex.
|
inline |
Returns a range over the simplices of the dim-skeleton of the simplicial complex.
The \(d\)-skeleton of a simplicial complex \(\mathbf{K}\) is the simplicial complex containing the simplices of \(\mathbf{K}\) of dimension at most \(d\).
| [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 |
Simplex_tree::Simplex_handle range for an optimized search for the star of a simplex when SimplexTreeOptions::link_nodes_by_label is true.
|
inline |
Returns a vertex of sh that has the same filtration value as sh if it exists, and null_vertex() otherwise.
For a lower-star filtration built with make_filtration_non_decreasing(), this is a way to invert the process and find out which vertex had its filtration value propagated to sh. If several vertices have the same filtration value, the one it returns is arbitrary.