Simplex Tree data structure for representing simplicial complexes. More...

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. More...

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...

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 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.

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	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 sh 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)
	Set a dimension for the simplicial complex. More...

void	initialize_filtration ()
	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...

void	expansion (int max_dim)
	Expands the Simplex_tree containing only its one skeleton until dimension max_dim. 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...

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...

bool	prune_above_filtration (Filtration_value filtration)
	Prune above filtration value given as parameter. 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...

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...

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)

Detailed Description

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>
class Gudhi::Simplex_tree< SimplexTreeOptions >

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].

Examples:: Alpha_complex/alpha_complex_3d_persistence.cpp, Alpha_complex/Alpha_complex_from_off.cpp, Alpha_complex/Alpha_complex_from_points.cpp, Alpha_complex/alpha_complex_persistence.cpp, Alpha_complex/Weighted_alpha_complex_3d_from_points.cpp, Bottleneck_distance/alpha_rips_persistence_bottleneck_distance.cpp, Nerve_GIC/CoordGIC.cpp, Nerve_GIC/FuncGIC.cpp, Nerve_GIC/Nerve.cpp, Nerve_GIC/VoronoiGIC.cpp, Persistent_cohomology/custom_persistence_sort.cpp, Persistent_cohomology/persistence_from_file.cpp, Persistent_cohomology/persistence_from_simple_simplex_tree.cpp, Persistent_cohomology/plain_homology.cpp, Persistent_cohomology/rips_multifield_persistence.cpp, Persistent_cohomology/rips_persistence_step_by_step.cpp, Persistent_cohomology/rips_persistence_via_boundary_matrix.cpp, Rips_complex/example_one_skeleton_rips_from_distance_matrix.cpp, Rips_complex/example_one_skeleton_rips_from_points.cpp, Rips_complex/example_rips_complex_from_csv_distance_matrix_file.cpp, Rips_complex/example_rips_complex_from_off_file.cpp, Rips_complex/rips_distance_matrix_persistence.cpp, Rips_complex/rips_persistence.cpp, Simplex_tree/cech_complex_cgal_mini_sphere_3d.cpp, Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp, Simplex_tree/graph_expansion_with_blocker.cpp, Simplex_tree/mini_simplex_tree.cpp, Simplex_tree/simple_simplex_tree.cpp, Simplex_tree/simplex_tree_from_cliques_of_graph.cpp, Tangential_complex/example_basic.cpp, Tangential_complex/example_with_perturb.cpp, Witness_complex/example_nearest_landmark_table.cpp, Witness_complex/example_strong_witness_complex_off.cpp, Witness_complex/example_witness_complex_off.cpp, Witness_complex/example_witness_complex_sphere.cpp, Witness_complex/strong_witness_persistence.cpp, and Witness_complex/weak_witness_persistence.cpp.

Member Typedef Documentation

◆ Boundary_simplex_iterator

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

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.

◆ Complex_simplex_iterator

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

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.

◆ Complex_vertex_iterator

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

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.

◆ Filtration_simplex_iterator

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

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.

◆ Filtration_value

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

typedef Options::Filtration_value Gudhi::Simplex_tree< SimplexTreeOptions >::Filtration_value

Type for the value of the filtration function.

Must be comparable with <.

Examples:: Alpha_complex/alpha_complex_3d_persistence.cpp, Alpha_complex/alpha_complex_persistence.cpp, Bottleneck_distance/alpha_rips_persistence_bottleneck_distance.cpp, Persistent_cohomology/persistence_from_simple_simplex_tree.cpp, Persistent_cohomology/rips_multifield_persistence.cpp, Persistent_cohomology/rips_persistence_step_by_step.cpp, Persistent_cohomology/rips_persistence_via_boundary_matrix.cpp, Rips_complex/example_one_skeleton_rips_from_distance_matrix.cpp, Rips_complex/example_one_skeleton_rips_from_points.cpp, Rips_complex/example_rips_complex_from_csv_distance_matrix_file.cpp, Rips_complex/example_rips_complex_from_off_file.cpp, Rips_complex/rips_distance_matrix_persistence.cpp, Rips_complex/rips_persistence.cpp, Simplex_tree/cech_complex_cgal_mini_sphere_3d.cpp, Simplex_tree/simple_simplex_tree.cpp, Witness_complex/strong_witness_persistence.cpp, and Witness_complex/weak_witness_persistence.cpp.

◆ Simplex_handle

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

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.

Examples:: Simplex_tree/cech_complex_cgal_mini_sphere_3d.cpp, and Simplex_tree/graph_expansion_with_blocker.cpp.

◆ Simplex_key

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

typedef Options::Simplex_key Gudhi::Simplex_tree< SimplexTreeOptions >::Simplex_key

Key associated to each simplex.

Must be an integer type.

◆ Simplex_vertex_iterator

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

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.

◆ Skeleton_simplex_iterator

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

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.

◆ Vertex_handle

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

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 <.

Examples:: Persistent_cohomology/rips_persistence_step_by_step.cpp, Simplex_tree/cech_complex_cgal_mini_sphere_3d.cpp, and Simplex_tree/simple_simplex_tree.cpp.

Constructor & Destructor Documentation

◆ Simplex_tree()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Gudhi::Simplex_tree< SimplexTreeOptions >::Simplex_tree ( Simplex_tree< SimplexTreeOptions > && complex_source )

inline

User-defined move constructor relocates the whole tree structure.

Exceptions

std::invalid_argument In debug mode, if the complex_source is invalid.

Member Function Documentation

◆ assign_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

void Gudhi::Simplex_tree< SimplexTreeOptions >::assign_filtration	(	Simplex_handle	sh,
		Filtration_value	fv
	)

inline

Sets the filtration value of a simplex.

Exceptions

std::invalid_argument In debug mode, if sh is a null_simplex.

Examples:: Simplex_tree/graph_expansion_with_blocker.cpp.

◆ boundary_simplex_range()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

template<class SimplexHandle >

Boundary_simplex_range Gudhi::Simplex_tree< SimplexTreeOptions >::boundary_simplex_range ( SimplexHandle sh )

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.

Parameters

[in] sh Simplex for which the boundary is computed.

Examples:: Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp, and Simplex_tree/simple_simplex_tree.cpp.

◆ clear_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

void Gudhi::Simplex_tree< SimplexTreeOptions >::clear_filtration ( )

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.

◆ cofaces_simplex_range()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Cofaces_simplex_range Gudhi::Simplex_tree< SimplexTreeOptions >::cofaces_simplex_range	(	const Simplex_handle	simplex,
		int	codimension
	)

inline

Compute the cofaces of a n simplex.

Parameters

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)

Returns: Vector of Simplex_handle, empty vector if no cofaces found.

Examples:: Simplex_tree/simple_simplex_tree.cpp.

◆ complex_simplex_range()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Complex_simplex_range Gudhi::Simplex_tree< SimplexTreeOptions >::complex_simplex_range ( )

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.

Examples:: Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp.

◆ decode_extended_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

std::pair<Filtration_value, Extended_simplex_type> Gudhi::Simplex_tree< SimplexTreeOptions >::decode_extended_filtration	(	Filtration_value	f,
		const Extended_filtration_data &	efd
	)

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.

Precondition: This function should be called only if extend_filtration() has been called first!

Postcondition: The output filtration value is supposed to be the same, but might be a little different, than the original filtration value, due to the internal transformation (scaling to [-2,-1]) that is performed on the original filtration values during the computation of extended persistence.

Parameters

[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()`.

Returns: A pair containing the original filtration value of the simplex as well as the simplex type.

◆ dimension() [1/2]

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

int Gudhi::Simplex_tree< SimplexTreeOptions >::dimension ( Simplex_handle sh )

inline

Returns the dimension of a simplex.

Must be different from null_simplex().

Examples:: Alpha_complex/alpha_complex_3d_persistence.cpp, Alpha_complex/alpha_complex_persistence.cpp, Persistent_cohomology/custom_persistence_sort.cpp, Persistent_cohomology/persistence_from_simple_simplex_tree.cpp, Rips_complex/example_one_skeleton_rips_from_distance_matrix.cpp, Rips_complex/example_one_skeleton_rips_from_points.cpp, Rips_complex/example_rips_complex_from_csv_distance_matrix_file.cpp, Rips_complex/example_rips_complex_from_off_file.cpp, Rips_complex/rips_distance_matrix_persistence.cpp, Simplex_tree/graph_expansion_with_blocker.cpp, Simplex_tree/simple_simplex_tree.cpp, Witness_complex/strong_witness_persistence.cpp, and Witness_complex/weak_witness_persistence.cpp.

◆ dimension() [2/2]

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

int Gudhi::Simplex_tree< SimplexTreeOptions >::dimension ( )

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()).

◆ edge_with_same_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Simplex_handle Gudhi::Simplex_tree< SimplexTreeOptions >::edge_with_same_filtration ( Simplex_handle sh )

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.

Precondition: sh must have dimension at least 1.

◆ endpoints()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

std::pair<Simplex_handle, Simplex_handle> Gudhi::Simplex_tree< SimplexTreeOptions >::endpoints ( Simplex_handle sh )

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.

◆ expansion()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

void Gudhi::Simplex_tree< SimplexTreeOptions >::expansion ( int max_dim )

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.

◆ expansion_with_blockers()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

template<typename Blocker >

void Gudhi::Simplex_tree< SimplexTreeOptions >::expansion_with_blockers	(	int	max_dim,
		Blocker	block_simplex
	)

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.

Parameters

[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.

Warning: several candidates of the same dimension may be inserted simultaneously before calling 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.

Examples:: Simplex_tree/graph_expansion_with_blocker.cpp.

◆ extend_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Extended_filtration_data Gudhi::Simplex_tree< SimplexTreeOptions >::extend_filtration ( )

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.

Postcondition: Note that after calling this function, the filtration values are actually modified. The function decode_extended_filtration() retrieves the original values and outputs the extended simplex type.

Precondition: 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 Vertex_handle.

Returns: A data structure containing the maximum and minimum values of the original filtration. It is meant to be provided as input to decode_extended_filtration() in order to retrieve the original filtration values for each simplex.

◆ filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

static Filtration_value Gudhi::Simplex_tree< SimplexTreeOptions >::filtration ( Simplex_handle sh )

inlinestatic

Returns the filtration value of a simplex.

Called on the null_simplex, it returns infinity. If SimplexTreeOptions::store_filtration is false, returns 0.

Examples:: Persistent_cohomology/custom_persistence_sort.cpp, Persistent_cohomology/persistence_from_simple_simplex_tree.cpp, Rips_complex/example_one_skeleton_rips_from_distance_matrix.cpp, Rips_complex/example_one_skeleton_rips_from_points.cpp, Rips_complex/example_rips_complex_from_csv_distance_matrix_file.cpp, Rips_complex/example_rips_complex_from_off_file.cpp, Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp, Simplex_tree/graph_expansion_with_blocker.cpp, and Simplex_tree/simple_simplex_tree.cpp.

◆ filtration_simplex_range()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Filtration_simplex_range const& Gudhi::Simplex_tree< SimplexTreeOptions >::filtration_simplex_range ( Indexing_tag = Indexing_tag() )

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.

Examples:: Persistent_cohomology/persistence_from_simple_simplex_tree.cpp, Rips_complex/example_one_skeleton_rips_from_distance_matrix.cpp, Rips_complex/example_one_skeleton_rips_from_points.cpp, Rips_complex/example_rips_complex_from_csv_distance_matrix_file.cpp, Rips_complex/example_rips_complex_from_off_file.cpp, Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp, Simplex_tree/graph_expansion_with_blocker.cpp, and Simplex_tree/simple_simplex_tree.cpp.

◆ find()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

template<class InputVertexRange = std::initializer_list<Vertex_handle>>

Simplex_handle Gudhi::Simplex_tree< SimplexTreeOptions >::find ( const InputVertexRange & s )

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

Examples:: Simplex_tree/simple_simplex_tree.cpp.

◆ initialize_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

void Gudhi::Simplex_tree< SimplexTreeOptions >::initialize_filtration ( )

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().

Examples:: Witness_complex/strong_witness_persistence.cpp, and Witness_complex/weak_witness_persistence.cpp.

◆ insert_graph()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

template<class OneSkeletonGraph >

void Gudhi::Simplex_tree< SimplexTreeOptions >::insert_graph ( const OneSkeletonGraph & skel_graph )

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::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 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.

Examples:: Persistent_cohomology/rips_persistence_step_by_step.cpp, and Simplex_tree/cech_complex_cgal_mini_sphere_3d.cpp.

◆ insert_simplex()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

template<class InputVertexRange = std::initializer_list<Vertex_handle>>

std::pair<Simplex_handle, bool> Gudhi::Simplex_tree< SimplexTreeOptions >::insert_simplex	(	const InputVertexRange &	simplex,
		Filtration_value	filtration = `0`
	)

inline

Insert a simplex, represented by a range of Vertex_handles, in the simplicial complex.

Parameters

[in]	simplex	range of Vertex_handles, representing the vertices of the new simplex
[in]	filtration	the filtration value assigned to the new simplex.

Returns: 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.

Examples:: Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp, Simplex_tree/graph_expansion_with_blocker.cpp, and Simplex_tree/simple_simplex_tree.cpp.

◆ insert_simplex_and_subfaces()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

template<class InputVertexRange = std::initializer_list<Vertex_handle>>

std::pair<Simplex_handle, bool> Gudhi::Simplex_tree< SimplexTreeOptions >::insert_simplex_and_subfaces	(	const InputVertexRange &	Nsimplex,
		Filtration_value	filtration = `0`
	)

inline

Insert a N-simplex and all his subfaces, from a N-simplex represented by a range of Vertex_handles, in the simplicial complex.

Parameters

[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.

Returns: 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.

Examples:: Persistent_cohomology/persistence_from_simple_simplex_tree.cpp.

◆ key()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

static Simplex_key Gudhi::Simplex_tree< SimplexTreeOptions >::key ( Simplex_handle sh )

inlinestatic

Returns the key associated to a simplex.

If no key has been assigned, returns null_key().

Precondition: SimplexTreeOptions::store_key

◆ make_filtration_non_decreasing()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

bool Gudhi::Simplex_tree< SimplexTreeOptions >::make_filtration_non_decreasing ( )

inline

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.

If a simplex has a NaN filtration value, it is considered lower than any other defined filtration value.

◆ maybe_initialize_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

void Gudhi::Simplex_tree< SimplexTreeOptions >::maybe_initialize_filtration ( )

inline

Initializes the filtration cache if it isn't initialized yet.

Automatically called by filtration_simplex_range().

◆ minimal_simplex_with_same_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Simplex_handle Gudhi::Simplex_tree< SimplexTreeOptions >::minimal_simplex_with_same_filtration ( Simplex_handle sh )

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.

◆ null_simplex()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

static Simplex_handle Gudhi::Simplex_tree< SimplexTreeOptions >::null_simplex ( )

inlinestatic

Returns a Simplex_handle different from all Simplex_handles associated to the simplices in the simplicial complex.

One can call filtration(null_simplex()).

Examples:: Simplex_tree/simple_simplex_tree.cpp.

◆ operator=()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Simplex_tree& Gudhi::Simplex_tree< SimplexTreeOptions >::operator= ( Simplex_tree< SimplexTreeOptions > && complex_source )

inline

User-defined move assignment relocates the whole tree structure.

Exceptions

std::invalid_argument In debug mode, if the complex_source is invalid.

◆ print_hasse()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

void Gudhi::Simplex_tree< SimplexTreeOptions >::print_hasse ( std::ostream & os )

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.

◆ prune_above_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

bool Gudhi::Simplex_tree< SimplexTreeOptions >::prune_above_filtration ( Filtration_value filtration )

inline

Prune above filtration value given as parameter.

Parameters

[in] filtration Maximum threshold value.

Returns: True if any simplex was removed, false if all simplices already had a value below the threshold.

Postcondition: 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() to recompute the exact dimension.

◆ remove_maximal_simplex()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

void Gudhi::Simplex_tree< SimplexTreeOptions >::remove_maximal_simplex ( Simplex_handle sh )

inline

Remove a maximal simplex.

Parameters

[in] sh Simplex handle on the maximal simplex to remove.

Precondition: Please check the simplex has no coface before removing it.

Exceptions

std::invalid_argument In debug mode, if sh has children.

Postcondition: Note that the dimension of the simplicial complex may be lower after calling 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.

◆ root()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Siblings* Gudhi::Simplex_tree< SimplexTreeOptions >::root ( )

inline

Returns a pointer to the root nodes of the simplex tree.

◆ self_siblings()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

template<class SimplexHandle >

static Siblings* Gudhi::Simplex_tree< SimplexTreeOptions >::self_siblings ( SimplexHandle sh )

inlinestatic

Returns the Siblings containing a simplex.

◆ set_dimension()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

void Gudhi::Simplex_tree< SimplexTreeOptions >::set_dimension ( int dimension )

inline

Set a dimension for the simplicial complex.

This function must be used with caution because it disables dimension recomputation when required (this recomputation can be triggered by remove_maximal_simplex() or prune_above_filtration()).

◆ simplex()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Simplex_handle Gudhi::Simplex_tree< SimplexTreeOptions >::simplex ( Simplex_key idx ) const

inline

Returns the simplex that has index idx in the filtration.

The filtration must be initialized.

◆ simplex_vertex_range()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Simplex_vertex_range Gudhi::Simplex_tree< SimplexTreeOptions >::simplex_vertex_range ( Simplex_handle sh ) const

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.

Examples:: Persistent_cohomology/persistence_from_simple_simplex_tree.cpp, Rips_complex/example_one_skeleton_rips_from_distance_matrix.cpp, Rips_complex/example_one_skeleton_rips_from_points.cpp, Rips_complex/example_rips_complex_from_csv_distance_matrix_file.cpp, Rips_complex/example_rips_complex_from_off_file.cpp, Simplex_tree/example_alpha_shapes_3_simplex_tree_from_off_file.cpp, Simplex_tree/graph_expansion_with_blocker.cpp, and Simplex_tree/simple_simplex_tree.cpp.

◆ skeleton_simplex_range()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Skeleton_simplex_range Gudhi::Simplex_tree< SimplexTreeOptions >::skeleton_simplex_range ( int dim )

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\).

Parameters

[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.

◆ star_simplex_range()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Cofaces_simplex_range Gudhi::Simplex_tree< SimplexTreeOptions >::star_simplex_range ( const Simplex_handle simplex )

inline

Compute the star of a n simplex.

Parameters

simplex represent the simplex of which we search the star

Returns: Vector of Simplex_handle, empty vector if no cofaces found.

Examples:: Simplex_tree/simple_simplex_tree.cpp.

◆ vertex_with_same_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>

Vertex_handle Gudhi::Simplex_tree< SimplexTreeOptions >::vertex_with_same_filtration ( Simplex_handle sh )

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.

The documentation for this class was generated from the following file:

include/gudhi/Simplex_tree.h

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured> class Gudhi::Simplex_tree< SimplexTreeOptions >

Member Typedef Documentation

◆ Boundary_simplex_iterator

◆ Complex_simplex_iterator

◆ Complex_vertex_iterator

◆ Filtration_simplex_iterator

◆ Filtration_value

◆ Simplex_handle

◆ Simplex_key

◆ Simplex_vertex_iterator

◆ Skeleton_simplex_iterator

◆ Vertex_handle

Constructor & Destructor Documentation

◆ Simplex_tree()

Member Function Documentation

◆ assign_filtration()

◆ boundary_simplex_range()

◆ clear_filtration()

◆ cofaces_simplex_range()

◆ complex_simplex_range()

◆ decode_extended_filtration()

◆ dimension() [1/2]

◆ dimension() [2/2]

◆ edge_with_same_filtration()

◆ endpoints()

◆ expansion()

◆ expansion_with_blockers()

◆ extend_filtration()

◆ filtration()

◆ filtration_simplex_range()

◆ find()

◆ initialize_filtration()

◆ insert_graph()

◆ insert_simplex()

◆ insert_simplex_and_subfaces()

◆ key()

◆ make_filtration_non_decreasing()

◆ maybe_initialize_filtration()

◆ minimal_simplex_with_same_filtration()

◆ null_simplex()

◆ operator=()

◆ print_hasse()

◆ prune_above_filtration()

◆ remove_maximal_simplex()

◆ root()

◆ self_siblings()

◆ set_dimension()

◆ simplex()

◆ simplex_vertex_range()

◆ skeleton_simplex_range()

◆ star_simplex_range()

◆ vertex_with_same_filtration()

template<typename SimplexTreeOptions = Simplex_tree_options_full_featured>
class Gudhi::Simplex_tree< SimplexTreeOptions >