The simplex tree is an efficient and flexible data structure for representing general (filtered) simplicial complexes. The data structure is described in Boissonnat and Maria (2014) .
Details
This class is a filtered, with keys, and non contiguous vertices version of the simplex tree.
See also
Other data structures for cell complexes:
CubicalComplex,
PeriodicCubicalComplex
Methods
Method new()
The SimplexTree class constructor.
Usage
SimplexTree$new(py_class = NULL)Method set_is_flag()
This function sets the internal field m_IsFlag which
records whether the simplex tree is a flag complex (i.e. has been
generated by a Rips complex).
Method assign_filtration()
This function assigns a new filtration value to a given N-simplex.
Arguments
simplexAn integer vector representing the N-simplex in the form of a list of vertices.
filtrationA numeric value specifying the new filtration value.
Details
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 calls to the $assign_filtration() method or a call to the
$make_filtration_non_decreasing() method for instance) before calling
any function that relies on the filtration property, such as
persistence().
Method collapse_edges()
Assuming the simplex tree is a 1-skeleton graph, this method
collapse edges (simplices of higher dimension are ignored) and resets
the simplex tree from the remaining edges. A good candidate is to build
a simplex tree on top of a RipsComplex of dimension 1 before
collapsing edges as done in this Python example.
For implementation details, please refer to
Boissonnat and Pritam (2020)
.
Arguments
nb_iterationsAn integer value specifying the number of edge collapse iterations to perform. Defaults to
1L.
Method 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 to
$persistence() when you do not want the list that $persistence()
returns.
Usage
SimplexTree$compute_persistence(
homology_coeff_field = 11,
min_persistence = 0,
persistence_dim_max = FALSE
)Arguments
homology_coeff_fieldAn integer value specifying the homology coefficient field. Must be a prime number. Defaults to
11L. Maximum is46337L.min_persistenceA numeric value specifying the minimum persistence value to take into account (strictly greater than
min_persistence). Defaults to0.0. Setmin_persistence = -1.0to see all values.persistence_dim_maxA boolean specifying whether the persistent homology for the maximal dimension in the complex is computed (
persistence_dim_max = TRUE). IfFALSE, it is ignored. Defaults toFALSE.
Method dimension()
This function returns the dimension of the simplicial complex.
Method expansion()
Expands the simplex tree containing only its one skeleton
until dimension max_dim.
Arguments
max_dimAn integer value specifying the maximal dimension to expented the simplex tree to.
Details
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.
Method 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.
Details
Note that after calling this function, the filtration values are
actually modified within the simplex tree. The method
$extended_persistence() retrieves the original values.
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.
Method extended_persistence()
This function retrieves good values for extended persistence, and separate the diagrams into the Ordinary, Relative, Extended+ and Extended- subdiagrams.
Arguments
homology_coeff_fieldAn integer value specifying the homology coefficient field. Must be a prime number. Defaults to
11L. Maximum is46337L.min_persistenceA numeric value specifying the minimum persistence value to take into account (strictly greater than
min_persistence). Defaults to0.0. Setmin_persistence = -1.0to see all values.
Details
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.
Method 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.
Method find()
This function returns if the N-simplex was found in the simplicial complex or not.
Method 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
A list with the following components:
An
n x 3integer matrix containing the regular persistence pairs of dimension 0, with one vertex for birth and two for death;A list of
m x 4integer matrices containing the other regular persistence pairs, grouped by dimension, with 2 vertices per extremity;An
l x ?integer matrix containing the connected components, with one vertex each;A list of
k x 2integer matrices containing the other essential features, grouped by dimension, with 2 vertices for birth.
Method get_boundaries()
For a given N-simplex, this function returns a list of simplices of dimension N-1 corresponding to the boundaries of the N-simplex.
Returns
A tibble listing the (simplicies of the)
boundary of the input N-simplex in column simplex along with their
corresponding filtration value in column filtration.
Method get_cofaces()
This function returns the cofaces of a given N-simplex with a given codimension.
Arguments
simplexAn integer vector representing the N-simplex in the form of a list of vertices.
codimensionAn integer value specifying the codimension. If
codimension = 0, all cofaces are returned (equivalent of$get_star()function).
Returns
A tibble listing the (simplicies of the)
cofaces of the input N-simplex in column simplex along with their
corresponding filtration value in column filtration.
Method get_filtration()
This function retrieves the list of simplices and their given filtration values sorted by increasing filtration values.
Returns
A tibble listing the simplicies in column
simplex along with their corresponding filtration value in column
filtration, in increasing order of filtration value.
Method get_simplices()
This function retrieves the list of simplices and their given filtration values.
Returns
A tibble listing the simplicies in column
simplex along with their corresponding filtration value in column
filtration, in increasing order of filtration value.
Method get_skeleton()
This function returns a generator with the (simplices of the) skeleton of a maximum given dimension.
Returns
A tibble listing the (simplicies of the)
skeleton of a maximum dimension in column simplex along with their
corresponding filtration value in column filtration.
Method get_star()
This function returns the star of a given N-simplex.
Returns
A tibble listing the (simplicies of the)
star of a simplex in column simplex along with their corresponding
filtration value in column filtration.
Method insert()
This function inserts the given N-simplex and its subfaces with the given filtration value. If some of those simplices are already present with a higher filtration value, their filtration value is lowered.
Arguments
simplexAn integer vector representing the N-simplex in the form of a list of vertices.
filtrationA numeric value specifying the filtration value of the simplex. Defaults to
0.0.chainableA boolean specifying whether the method should return the class itself, hence allowing its use in pipe chaining. Defaults to
TRUE, which enables chaining.
Method 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.
Method make_filtration_non_decreasing()
This function ensures that each simplex has a higher filtration value than its faces by increasing the filtration values.
Method persistence()
This function computes and returns the persistence of the simplicial complex.
Usage
SimplexTree$persistence(
homology_coeff_field = 11,
min_persistence = 0,
persistence_dim_max = FALSE
)Arguments
homology_coeff_fieldAn integer value specifying the homology coefficient field. Must be a prime number. Defaults to
11L. Maximum is46337L.min_persistenceA numeric value specifying the minimum persistence value to take into account (strictly greater than
min_persistence). Defaults to0.0. Setmin_persistence = -1.0to see all values.persistence_dim_maxA boolean specifying whether the persistent homology for the maximal dimension in the complex is computed (
persistence_dim_max = TRUE). IfFALSE, it is ignored. Defaults toFALSE.
Returns
A tibble listing all persistence feature
summarised by 3 variables: dimension, birth and death.
Method persistence_intervals_in_dimension()
This function returns the persistence intervals of the simplicial complex in a specific dimension.
Returns
A tibble storing the persistence intervals
for the required dimension in two columns birth and death.
Method persistence_pairs()
This function returns a list of persistence birth and death simplices pairs.
Method persistent_betti_numbers()
This function returns the persistent Betti numbers of the simplicial complex.
Method prune_above_filtration()
Prune above filtration value given as parameter.
Arguments
filtrationA numeric value specifying the maximum threshold value.
chainableA boolean specifying whether the method should return the class itself, hence allowing its use in pipe chaining. Defaults to
TRUE, which enables chaining.
Details
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 call dimension() method to
recompute the exact dimension.
Method remove_maximal_simplex()
This function removes a given maximal N-simplex from the simplicial complex.
Method 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 = 0L. 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 filtration value, or
calling $make_filtration_non_decreasing() afterwards for instance).
Method set_dimension()
This function sets the dimension of the simplicial complex.
Method upper_bound_dimension()
This function returns a valid dimension upper bound of the simplicial complex.
Method write_persistence_diagram()
This function writes the persistence intervals of the simplicial complex in a user given file name.
Examples
if (FALSE) { # reticulate::py_module_available("gudhi")
st <- SimplexTree$new()
st
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$set_is_flag(TRUE)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$filtration(1)
st$assign_filtration(1, 0.8)
st$filtration(1)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$compute_persistence()$betti_numbers()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$collapse_edges()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$dimension()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$expansion(2)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$extend_filtration()
st$extended_persistence()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$filtration(0)
st$filtration(1:2)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$find(0)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
rc <- RipsComplex$new(data = X, max_edge_length = 1)
st <- rc$create_simplex_tree(1)
st$compute_persistence()$flag_persistence_generators()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
splx <- st$get_simplices()$simplex[[1]]
st$get_boundaries(splx)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$get_cofaces(1:2, 0)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$get_filtration()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$get_simplices()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$get_skeleton(0)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$get_star(1:2)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$insert(1:2)
st$insert(1:3, chainable = FALSE)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$compute_persistence()$lower_star_persistence_generators()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$make_filtration_non_decreasing()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$num_simplices()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$num_vertices()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$persistence()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$compute_persistence()$persistence_intervals_in_dimension(1)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$compute_persistence()$persistence_pairs()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$compute_persistence()$persistent_betti_numbers(0, 0.1)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$prune_above_filtration(0.12)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$remove_maximal_simplex(1:2)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$reset_filtration(0.1)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$set_dimension(1)
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
st$upper_bound_dimension()
}
if (FALSE) { # reticulate::py_module_available("gudhi")
X <- seq_circle(10)
ac <- AlphaComplex$new(points = X)
st <- ac$create_simplex_tree()
f <- fs::file_temp(ext = ".dgm")
st$compute_persistence()$write_persistence_diagram(f)
fs::file_delete(f)
}