Simplex tree reference manual#
- class gudhi.SimplexTree#
Bases:
object
The simplex tree is an efficient and flexible data structure for representing general (filtered) simplicial complexes. The data structure is described in Jean-Daniel Boissonnat and Clément Maria. The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes. Algorithmica, pages 1–22, 2014.
This class is a filtered, with keys, and non contiguous vertices version of the simplex tree.
- __eq__()#
- Returns:
True if the 2 complexes have the same simplices with the same filtration values, False otherwise.
- Return type:
bool
- __getstate__()#
- Returns:
Serialized (or flattened) SimplexTree data structure in order to pickle SimplexTree.
- Return type:
numpy.array of shape (n,)
- __init__()#
SimplexTree constructor.
- Parameters:
other¶ (SimplexTree (Optional)) – If other is None (default value), an empty SimplexTree is created. If other is a SimplexTree, the SimplexTree is constructed from a deep copy of other.
- Returns:
An empty or a copy simplex tree.
- Return type:
- Raises:
TypeError – In case other is neither None, nor a SimplexTree.
- Note:
If the SimplexTree is a copy, the persistence information is not copied. If you need it in the clone, you have to call
compute_persistence()
on it even if you had already computed it in the original.
- __new__(**kwargs)#
- __setstate__()#
Construct the SimplexTree data structure from a Numpy Array (cf.
__getstate__()
) in order to unpickle a SimplexTree.- Parameters:
state¶ (numpy.array of shape (n,)) – Serialized SimplexTree data structure
- assign_filtration()#
This function assigns a new filtration value to a given N-simplex.
- Parameters:
Note
Beware that after this operation, the structure may not be a valid filtration anymore, a simplex could have a lower filtration value than one of its faces. Callers are responsible for fixing this (with more
assign_filtration()
ormake_filtration_non_decreasing()
for instance) before calling any function that relies on the filtration property, likepersistence()
.
- betti_numbers()#
This function returns the Betti numbers of the simplicial complex.
- Returns:
The Betti numbers ([B0, B1, …, Bn]).
- Return type:
list of int
- Note:
betti_numbers function requires
compute_persistence()
function to be launched first.
- collapse_edges()#
Assuming the complex is a graph (simplices of higher dimension are ignored), this method implicitly interprets it as the 1-skeleton of a flag complex, and replaces it with another (smaller) graph whose expansion has the same persistent homology, using a technique known as edge collapses (see [21]).
A natural application is to get a simplex tree of dimension 1 from
RipsComplex
, then collapse edges, performexpansion()
and finally compute persistence (cf.rips_complex_edge_collapse_example.py
).- Parameters:
nb_iterations¶ (int) – The number of edge collapse iterations to perform. Default is 1.
- compute_persistence()#
This function computes the persistence of the simplicial complex, so it can be accessed through
persistent_betti_numbers()
,persistence_pairs()
, etc. This function is equivalent topersistence()
when you do not want the listpersistence()
returns.- Parameters:
homology_coeff_field¶ (int) – The homology coefficient field. Must be a prime number. Default value is 11. Max is 46337.
min_persistence¶ (float) – The minimum persistence value to take into account (strictly greater than min_persistence). Default value is 0.0. Sets min_persistence to -1.0 to see all values.
persistence_dim_max¶ (bool) – If true, the persistent homology for the maximal dimension in the complex is computed. If false, it is ignored. Default is false.
- Returns:
Nothing.
- copy()#
- Returns:
A simplex tree that is a deep copy of itself.
- Return type:
- Note:
The persistence information is not copied. If you need it in the clone, you have to call
compute_persistence()
on it even if you had already computed it in the original.
- static create_from_array()#
Creates a new, empty complex and inserts vertices and edges. The vertices are numbered from 0 to n-1, and the filtration values are encoded in the array, with the diagonal representing the vertices. It is the caller’s responsibility to ensure that this defines a filtration, which can be achieved with either:
filtrations[np.diag_indices_from(filtrations)] = filtrations.min(axis=1)
or:
diag = filtrations.diagonal() filtrations = np.fmax(np.fmax(filtrations, diag[:, None]), diag[None, :])
- Parameters:
- Returns:
the new complex
- Return type:
- dimension()#
This function returns the dimension of the simplicial complex.
- Returns:
the simplicial complex dimension.
- Return type:
int
Note
This function is not constant time because it can recompute dimension if required (can be triggered by
remove_maximal_simplex()
orprune_above_filtration()
methods).
- expansion()#
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.
- Parameters:
max_dimension¶ (int) – The maximal dimension.
- expansion_with_blocker()#
Expands the 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 blocker_func returns True for this simplex.
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 blocker_func with this new simplex (represented as a list of int). If blocker_func returns True, the simplex is removed, otherwise it is kept. The algorithm then proceeds with the next candidate.
Warning
Several candidates of the same dimension may be inserted simultaneously before calling blocker_func, so if you examine the complex in blocker_func, you may hit a few simplices of the same dimension that have not been vetted by blocker_func yet, or have already been rejected but not yet removed.
- 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.
Note
Note that after calling this function, the filtration values are actually modified within the simplex tree. The function
extended_persistence()
retrieves the original values.Note
Note that this code creates an extra vertex internally, so you should make sure that the simplex tree does not contain a vertex with the largest possible value (i.e., 4294967295).
This notebook explains how to compute an extension of persistence called extended persistence.
- extended_persistence()#
This function retrieves good values for extended persistence, and separate the diagrams into the Ordinary, Relative, Extended+ and Extended- subdiagrams.
- Parameters:
homology_coeff_field¶ (int) – The homology coefficient field. Must be a prime number. Default value is 11. Max is 46337.
min_persistence¶ (float) – The minimum persistence value (i.e., the absolute value of the difference between the persistence diagram point coordinates) to take into account (strictly greater than min_persistence). Default value is 0.0. Sets min_persistence to -1.0 to see all values.
- Returns:
A list of four persistence diagrams in the format described in
persistence()
. The first one is Ordinary, the second one is Relative, the third one is Extended+ and the fourth one is Extended-. See https://link.springer.com/article/10.1007/s10208-008-9027-z and/or section 2.2 in https://link.springer.com/article/10.1007/s10208-017-9370-z for a description of these subtypes.
Note
This function should be called only if
extend_filtration()
has been called first!Note
The coordinates of the persistence diagram points might be a little different than the original filtration values due to the internal transformation (scaling to [-2,-1]) that is performed on these values during the computation of extended persistence.
This notebook explains how to compute an extension of persistence called extended persistence.
- filtration()#
This function returns the filtration value for a given N-simplex in this simplicial complex, or +infinity if it is not in the complex.
- Parameters:
simplex¶ (list of int) – The N-simplex, represented by a list of vertex.
- Returns:
The simplicial complex filtration value.
- Return type:
float
- find()#
This function returns if the N-simplex was found in the simplicial complex or not.
- Parameters:
simplex¶ (list of int) – The N-simplex to find, represented by a list of vertex.
- Returns:
true if the simplex was found, false otherwise.
- Return type:
bool
- flag_persistence_generators()#
Assuming this is a flag complex, this function returns the persistence pairs, where each simplex is replaced with the vertices of the edges that gave it its filtration value.
- Returns:
First the regular persistence pairs of dimension 0, with one vertex for birth and two for death; then the other regular persistence pairs, grouped by dimension, with 2 vertices per extremity; then the connected components, with one vertex each; finally the other essential features, grouped by dimension, with 2 vertices for birth.
- Return type:
Tuple[numpy.array[int] of shape (n,3), List[numpy.array[int] of shape (m,4)], numpy.array[int] of shape (l,), List[numpy.array[int] of shape (k,2)]]
- Note:
flag_persistence_generators requires that persistence() be called first.
- get_boundaries()#
This function returns a generator with the boundaries of a given N-simplex. If you do not need the filtration values, the boundary can also be obtained as
itertools.combinations(simplex,len(simplex)-1)
.- Parameters:
simplex¶ (list of int.) – The N-simplex, represented by a list of vertex.
- Returns:
The (simplices of the) boundary of a simplex
- Return type:
generator with tuples(simplex, filtration)
- get_cofaces()#
This function returns the cofaces of a given N-simplex with a given codimension.
- Parameters:
- Returns:
The (simplices of the) cofaces of a simplex
- Return type:
list of tuples(simplex, filtration)
- get_filtration()#
This function returns a generator with simplices and their given filtration values sorted by increasing filtration values.
- Returns:
The simplices sorted by increasing filtration values.
- Return type:
generator with tuples(simplex, filtration)
- get_simplices()#
This function returns a generator with simplices and their given filtration values.
- Returns:
The simplices.
- Return type:
generator with tuples(simplex, filtration)
- get_skeleton()#
This function returns a generator with the (simplices of the) skeleton of a maximum given dimension.
- Parameters:
dimension¶ (int) – The skeleton dimension value.
- Returns:
The (simplices of the) skeleton of a maximum dimension.
- Return type:
generator with tuples(simplex, filtration)
- get_star()#
This function returns the star of a given N-simplex.
- Parameters:
simplex¶ (list of int) – The N-simplex, represented by a list of vertex.
- Returns:
The (simplices of the) star of a simplex.
- Return type:
list of tuples(simplex, filtration)
- initialize_filtration()#
This function initializes and sorts the simplicial complex filtration vector.
Deprecated since version 3.2.0.
- insert()#
This function inserts the given N-simplex and its subfaces with the given filtration value (default value is ‘0.0’). If some of those simplices are already present with a higher filtration value, their filtration value is lowered.
- insert_batch#
Inserts k-simplices given by a sparse array in a format similar to torch.sparse. The n-th simplex has vertices vertex_array[0,n], …, vertex_array[k,n] and filtration value filtrations[n]. If a simplex is repeated, the smallest filtration value is used. Simplices with a repeated vertex are currently interpreted as lower dimensional simplices, but we do not guarantee this behavior in the future. Any time a simplex is inserted, its faces are inserted as well if needed to preserve a simplicial complex.
- Parameters:
vertex_array (numpy.array of shape (k+1,n)) – the k-simplices to insert.
filtrations (numpy.array of shape (n,)) – the filtration values.
- insert_edges_from_coo_matrix()#
Inserts edges given by a sparse matrix in COOrdinate format. If an edge is repeated, the smallest filtration value is used. Missing entries are not inserted. Diagonal entries are currently interpreted as vertices, although we do not guarantee this behavior in the future, and this is only useful if you want to insert vertices with a smaller filtration value than the smallest edge containing it, since vertices are implicitly inserted together with the edges.
- Parameters:
edges¶ (scipy.sparse.coo_matrix of shape (n,n)) – the edges to insert and their filtration values.
See also
- is_empty()#
This function returns whether the simplicial complex is empty.
- Returns:
True if the simplicial complex is empty.
- Return type:
bool
- lower_star_persistence_generators()#
Assuming this is a lower-star filtration, this function returns the persistence pairs, where each simplex is replaced with the vertex that gave it its filtration value.
- Returns:
First the regular persistence pairs, grouped by dimension, with one vertex per extremity, and second the essential features, grouped by dimension, with one vertex each
- Return type:
Tuple[List[numpy.array[int] of shape (n,2)], List[numpy.array[int] of shape (m,)]]
- Note:
lower_star_persistence_generators requires that persistence() be called first.
- make_filtration_non_decreasing()#
This function ensures that each simplex has a higher filtration value than its faces by increasing the filtration values.
- Returns:
True if any filtration value was modified, False if the filtration was already non-decreasing.
- Return type:
bool
- num_simplices()#
This function returns the number of simplices of the simplicial complex.
- Returns:
the simplicial complex number of simplices.
- Return type:
int
- num_vertices()#
This function returns the number of vertices of the simplicial complex.
- Returns:
The simplicial complex number of vertices.
- Return type:
int
- persistence()#
This function computes and returns the persistence of the simplicial complex.
- Parameters:
homology_coeff_field¶ (int) – The homology coefficient field. Must be a prime number. Default value is 11. Max is 46337.
min_persistence¶ (float) – The minimum persistence value to take into account (strictly greater than min_persistence). Default value is 0.0. Set min_persistence to -1.0 to see all values.
persistence_dim_max¶ (bool) – If true, the persistent homology for the maximal dimension in the complex is computed. If false, it is ignored. Default is false.
- Returns:
The persistence of the simplicial complex.
- Return type:
list of pairs(dimension, pair(birth, death))
- persistence_intervals_in_dimension()#
This function returns the persistence intervals of the simplicial complex in a specific dimension.
- Parameters:
dimension¶ (int) – The specific dimension.
- Returns:
The persistence intervals.
- Return type:
numpy array of dimension 2
- Note:
intervals_in_dim function requires
compute_persistence()
function to be launched first.
- persistence_pairs()#
This function returns a list of persistence birth and death simplices pairs.
- Returns:
A list of persistence simplices intervals.
- Return type:
list of pair of list of int
- Note:
persistence_pairs function requires
compute_persistence()
function to be launched first.
- persistent_betti_numbers()#
This function returns the persistent Betti numbers of the simplicial complex.
- Parameters:
- Returns:
The persistent Betti numbers ([B0, B1, …, Bn]).
- Return type:
list of int
- Note:
persistent_betti_numbers function requires
compute_persistence()
function to be launched first.
- prune_above_dimension()#
Remove all simplices of dimension greater than a given value.
- Parameters:
dimension¶ (int) – Maximum dimension value.
- Returns:
The modification information.
- Return type:
bool
- prune_above_filtration()#
Prune above filtration value given as parameter.
- Parameters:
filtration¶ (float) – Maximum threshold value.
- Returns:
The filtration modification information.
- Return type:
bool
Note
Note that the dimension of the simplicial complex may be lower after calling
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 calldimension()
method to recompute the exact dimension.
- remove_maximal_simplex()#
This function removes a given maximal N-simplex from the simplicial complex.
- Parameters:
simplex¶ (list of int) – The N-simplex, represented by a list of vertex.
Note
The dimension of the simplicial complex may be lower after calling remove_maximal_simplex than it was before. However,
upper_bound_dimension()
method will return the old value, which remains a valid upper bound. If you care, you can calldimension()
to recompute the exact dimension.
- reset_filtration()#
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).
- set_dimension()#
This function sets the dimension of the simplicial complex.
- Parameters:
dimension¶ (int) – The new dimension value.
Note
This function must be used with caution because it disables dimension recomputation when required (this recomputation can be triggered by
remove_maximal_simplex()
orprune_above_filtration()
).
- upper_bound_dimension()#
This function returns a valid dimension upper bound of the simplicial complex.
- Returns:
an upper bound on the dimension of the simplicial complex.
- Return type:
int
- write_persistence_diagram()#
This function writes the persistence intervals of the simplicial complex in a user given file name.
- Parameters:
persistence_file¶ (string) – Name of the file.
- Note:
intervals_in_dim function requires
compute_persistence()
function to be launched first.