Gudhi::persistence_matrix::RU_matrix< Master_matrix > Class Template Reference

Matrix structure to store the ordered boundary matrix \( R \cdot U \) of a filtered complex in order to compute its persistent homology, as well as representative cycles. Supports vineyards (see [21]) and the removal of maximal faces while maintaining a valid barcode. Provides an access to its columns and rows. More...

Public Types

using Field_operators = typename Master_matrix::Field_operators
 Field operators class. Necessary only if PersistenceMatrixOptions::is_z2 is false.
 
using Field_element_type = typename Master_matrix::element_type
 
using Column_type = typename Master_matrix::Column_type
 
using Row_type = typename Master_matrix::Row_type
 
using Cell_constructor = typename Master_matrix::Cell_constructor
 
using Column_settings = typename Master_matrix::Column_settings
 
using boundary_type = typename Master_matrix::boundary_type
 
using index = typename Master_matrix::index
 
using id_index = typename Master_matrix::id_index
 
using pos_index = typename Master_matrix::pos_index
 
using dimension_type = typename Master_matrix::dimension_type
 

Public Member Functions

 RU_matrix (Column_settings *colSettings)
 Constructs an empty matrix. More...
 
template<class Boundary_type = boundary_type>
 RU_matrix (const std::vector< Boundary_type > &orderedBoundaries, Column_settings *colSettings)
 Constructs a new matrix from the given ranges of Matrix::cell_rep_type. Each range corresponds to a column (the order of the ranges are preserved). The content of the ranges is assumed to be sorted by increasing IDs. The IDs of the simplices are also assumed to be consecutifs, ordered by filtration value, starting with 0. More...
 
 RU_matrix (unsigned int numberOfColumns, Column_settings *colSettings)
 Constructs a new empty matrix and reserves space for the given number of columns. More...
 
 RU_matrix (const RU_matrix &matrixToCopy, Column_settings *colSettings=nullptr)
 Copy constructor. If colSettings is not a null pointer, its value is kept instead of the one in the copied matrix. More...
 
 RU_matrix (RU_matrix &&other) noexcept
 Move constructor. More...
 
template<class Boundary_type = boundary_type>
void insert_boundary (const Boundary_type &boundary, dimension_type dim=-1)
 Inserts at the end of the matrix a new ordered column corresponding to the given boundary. This means that it is assumed that this method is called on boundaries in the order of the filtration. It also assumes that the faces in the given boundary are identified by their relative position in the filtration, starting at 0. If it is not the case, use the other insert_boundary instead by indicating the face ID used in the boundaries when the face is inserted. More...
 
template<class Boundary_type = boundary_type>
void insert_boundary (id_index faceIndex, const Boundary_type &boundary, dimension_type dim=-1)
 It does the same as the other version, but allows the boundary faces to be identified without restrictions except that all IDs have to be strictly increasing in the order of filtration. Note that you should avoid then to use the other insertion method to avoid overwriting IDs. More...
 
Column_typeget_column (index columnIndex, bool inR=true)
 Returns the column at the given MatIdx index in \( R \) if inR is true and in \( U \) if inR is false. The type of the column depends on the choosen options, see PersistenceMatrixOptions::column_type. More...
 
Row_typeget_row (index rowIndex, bool inR=true)
 Returns the row at the given row index in \( R \) if inR is true and in \( U \) if inR is false. The type of the row depends on the choosen options, see PersistenceMatrixOptions::has_intrusive_rows. More...
 
void erase_empty_row (index rowIndex)
 If PersistenceMatrixOptions::has_row_access and PersistenceMatrixOptions::has_removable_rows are true: assumes that the row is empty in \( R \) and removes it from \( R \). If the matrix is valid, a row will never be empty in \( U \), so \( U \) won't be affected. If PersistenceMatrixOptions::has_map_column_container and PersistenceMatrixOptions::has_column_and_row_swaps are true: cleans up maps used for the lazy row swaps. Otherwise, does nothing. More...
 
void remove_maximal_face (index columnIndex)
 Only available if PersistenceMatrixOptions::has_removable_columns and PersistenceMatrixOptions::has_vine_update are true. Assumes that the face is maximal in the current complex and removes it such that the matrix remains consistent (i.e., RU is still an upper triangular decomposition of the boundary matrix). The maximality of the face is not verified. Also updates the barcode if it is stored. More...
 
void remove_last ()
 Only available if PersistenceMatrixOptions::has_removable_columns is true. Removes the last face in the filtration from the matrix and updates the barcode if it is stored. More...
 
dimension_type get_max_dimension () const
 Returns the maximal dimension of a face stored in the matrix. Only available if PersistenceMatrixOptions::has_matrix_maximal_dimension_access is true. More...
 
index get_number_of_columns () const
 Returns the current number of columns in the matrix. More...
 
dimension_type get_column_dimension (index columnIndex) const
 Returns the dimension of the given column. More...
 
void add_to (index sourceColumnIndex, index targetColumnIndex)
 Adds column at sourceColumnIndex onto the column at targetColumnIndex in the matrix. More...
 
void multiply_target_and_add_to (index sourceColumnIndex, const Field_element_type &coefficient, index targetColumnIndex)
 Multiplies the target column with the coefficiant and then adds the source column to it. That is: targetColumn = (targetColumn * coefficient) + sourceColumn. More...
 
void multiply_source_and_add_to (const Field_element_type &coefficient, index sourceColumnIndex, index targetColumnIndex)
 Multiplies the source column with the coefficiant before adding it to the target column. That is: targetColumn += (coefficient * sourceColumn). The source column will not be modified. More...
 
void zero_cell (index columnIndex, index rowIndex, bool inR=true)
 Zeroes the cell at the given coordinates in \( R \) if inR is true or in \( U \) if inR is false. Should be used with care to not destroy the validity of the persistence related properties of the matrix. More...
 
void zero_column (index columnIndex, bool inR=true)
 Zeroes the column at the given index in \( R \) if inR is true or in \( U \) if inR is false. Should be used with care to not destroy the validity of the persistence related properties of the matrix. More...
 
bool is_zero_cell (index columnIndex, index rowIndex, bool inR=true) const
 Indicates if the cell at given coordinates has value zero in \( R \) if inR is true or in \( U \) if inR is false. More...
 
bool is_zero_column (index columnIndex, bool inR=true)
 Indicates if the column at given index has value zero in \( R \) if inR is true or in \( U \) if inR is false. More...
 
index get_column_with_pivot (index faceIndex) const
 Returns the MatIdx index of the column which has the given row index as pivot in \( R \). Assumes that the pivot exists. More...
 
index get_pivot (index columnIndex)
 Returns the row index of the pivot of the given column in \( R \). More...
 
void reset (Column_settings *colSettings)
 Resets the matrix to an empty matrix. More...
 
RU_matrixoperator= (const RU_matrix &other)
 Assign operator.
 

Friends

void swap (RU_matrix &matrix1, RU_matrix &matrix2)
 Swap operator.
 

Detailed Description

template<class Master_matrix>
class Gudhi::persistence_matrix::RU_matrix< Master_matrix >

Matrix structure to store the ordered boundary matrix \( R \cdot U \) of a filtered complex in order to compute its persistent homology, as well as representative cycles. Supports vineyards (see [21]) and the removal of maximal faces while maintaining a valid barcode. Provides an access to its columns and rows.

Template Parameters
Master_matrixAn instanciation of Matrix from which all types and options are deduced.

Member Typedef Documentation

◆ boundary_type

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::boundary_type = typename Master_matrix::boundary_type

Type of an input column.

◆ Cell_constructor

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::Cell_constructor = typename Master_matrix::Cell_constructor

Factory of Cell classes.

◆ Column_settings

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::Column_settings = typename Master_matrix::Column_settings

Structure giving access to the columns to necessary external classes.

◆ Column_type

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::Column_type = typename Master_matrix::Column_type

Column type.

◆ dimension_type

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::dimension_type = typename Master_matrix::dimension_type

Dimension value type.

◆ Field_element_type

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::Field_element_type = typename Master_matrix::element_type

Type of an field element.

◆ id_index

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::id_index = typename Master_matrix::id_index

IDIdx index type.

◆ index

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::index = typename Master_matrix::index

MatIdx index type.

◆ pos_index

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::pos_index = typename Master_matrix::pos_index

PosIdx index type.

◆ Row_type

template<class Master_matrix >
using Gudhi::persistence_matrix::RU_matrix< Master_matrix >::Row_type = typename Master_matrix::Row_type

Row type, only necessary with row access option.

Constructor & Destructor Documentation

◆ RU_matrix() [1/5]

template<class Master_matrix >
Gudhi::persistence_matrix::RU_matrix< Master_matrix >::RU_matrix ( Column_settings colSettings)
inline

Constructs an empty matrix.

Parameters
colSettingsPointer to an existing setting structure for the columns. The structure should contain all the necessary external classes specifically necessary for the choosen column type, such as custom allocators.

◆ RU_matrix() [2/5]

template<class Master_matrix >
template<class Boundary_type >
Gudhi::persistence_matrix::RU_matrix< Master_matrix >::RU_matrix ( const std::vector< Boundary_type > &  orderedBoundaries,
Column_settings colSettings 
)
inline

Constructs a new matrix from the given ranges of Matrix::cell_rep_type. Each range corresponds to a column (the order of the ranges are preserved). The content of the ranges is assumed to be sorted by increasing IDs. The IDs of the simplices are also assumed to be consecutifs, ordered by filtration value, starting with 0.

Template Parameters
Boundary_typeRange type for Matrix::cell_rep_type ranges. Assumed to have a begin(), end() and size() method.
Parameters
orderedBoundariesRange of boundaries: orderedBoundaries is interpreted as a boundary matrix of a filtered simplicial complex, whose boundaries are ordered by filtration order. Therefore, orderedBoundaries[i] should store the boundary of the \( i^{th} \) simplex in the filtration, as an ordered list of indices of its facets (again those indices correspond to their respective position in the matrix). That is why the indices of the simplices are assumed to be consecutifs and starting with 0 (an empty boundary is interpreted as a vertex boundary and not as a non existing simplex). All dimensions up to the maximal dimension of interest have to be present. If only a higher dimension is of interest and not everything should be stored, then use the insert_boundary method instead (after creating the matrix with the RU_matrix(unsigned int, Column_settings*) constructor preferably).
colSettingsPointer to an existing setting structure for the columns. The structure should contain all the necessary external classes specifically necessary for the choosen column type, such as custom allocators.

◆ RU_matrix() [3/5]

template<class Master_matrix >
Gudhi::persistence_matrix::RU_matrix< Master_matrix >::RU_matrix ( unsigned int  numberOfColumns,
Column_settings colSettings 
)
inline

Constructs a new empty matrix and reserves space for the given number of columns.

Parameters
numberOfColumnsNumber of columns to reserve space for.
colSettingsPointer to an existing setting structure for the columns. The structure should contain all the necessary external classes specifically necessary for the choosen column type, such as custom allocators.

◆ RU_matrix() [4/5]

template<class Master_matrix >
Gudhi::persistence_matrix::RU_matrix< Master_matrix >::RU_matrix ( const RU_matrix< Master_matrix > &  matrixToCopy,
Column_settings colSettings = nullptr 
)
inline

Copy constructor. If colSettings is not a null pointer, its value is kept instead of the one in the copied matrix.

Parameters
matrixToCopyMatrix to copy.
colSettingsEither a pointer to an existing setting structure for the columns or a null pointer. The structure should contain all the necessary external classes specifically necessary for the choosen column type, such as custom allocators. If null pointer, the pointer stored in matrixToCopy is used instead.

◆ RU_matrix() [5/5]

template<class Master_matrix >
Gudhi::persistence_matrix::RU_matrix< Master_matrix >::RU_matrix ( RU_matrix< Master_matrix > &&  other)
inlinenoexcept

Move constructor.

Parameters
otherMatrix to move.

Member Function Documentation

◆ add_to()

template<class Master_matrix >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::add_to ( index  sourceColumnIndex,
index  targetColumnIndex 
)
inline

Adds column at sourceColumnIndex onto the column at targetColumnIndex in the matrix.

Warning
They will be no verification to ensure that the addition makes sense for the validity of a boundary matrix of a filtered complex. For example, a right-to-left addition could corrupt the computation of the barcode if done blindly. So should be used with care.
Parameters
sourceColumnIndexMatIdx index of the source column.
targetColumnIndexMatIdx index of the target column.

◆ erase_empty_row()

template<class Master_matrix >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::erase_empty_row ( index  rowIndex)
inline

If PersistenceMatrixOptions::has_row_access and PersistenceMatrixOptions::has_removable_rows are true: assumes that the row is empty in \( R \) and removes it from \( R \). If the matrix is valid, a row will never be empty in \( U \), so \( U \) won't be affected. If PersistenceMatrixOptions::has_map_column_container and PersistenceMatrixOptions::has_column_and_row_swaps are true: cleans up maps used for the lazy row swaps. Otherwise, does nothing.

Warning
The removed rows are always assumed to be empty in \( R \). If it is not the case, the deleted row cells are not removed from their columns. And in the case of intrusive rows, this will generate a segmentation fault when the column cells are destroyed later. The row access is just meant as a "read only" access to the rows and the erase_empty_row method just as a way to specify that a row is empty and can therefore be removed from dictionnaries. This allows to avoid testing the emptiness of a row at each column cell removal, what can be quite frequent.
Parameters
rowIndexRow index of the empty row.

◆ get_column()

template<class Master_matrix >
RU_matrix< Master_matrix >::Column_type & Gudhi::persistence_matrix::RU_matrix< Master_matrix >::get_column ( index  columnIndex,
bool  inR = true 
)
inline

Returns the column at the given MatIdx index in \( R \) if inR is true and in \( U \) if inR is false. The type of the column depends on the choosen options, see PersistenceMatrixOptions::column_type.

Note that before returning the column, all column cells can eventually be reordered, if lazy swaps occurred. It is therefore recommended to avoid calling get_column between vine swaps, otherwise the benefits of the the lazyness is lost.

Parameters
columnIndexMatIdx index of the column to return.
inRIf true, returns the column in \( R \), if false, returns the column in \( U \). Default value: true.
Returns
Reference to the column.

◆ get_column_dimension()

template<class Master_matrix >
RU_matrix< Master_matrix >::dimension_type Gudhi::persistence_matrix::RU_matrix< Master_matrix >::get_column_dimension ( index  columnIndex) const
inline

Returns the dimension of the given column.

Parameters
columnIndexMatIdx index of the column representing the face.
Returns
Dimension of the face.

◆ get_column_with_pivot()

template<class Master_matrix >
RU_matrix< Master_matrix >::index Gudhi::persistence_matrix::RU_matrix< Master_matrix >::get_column_with_pivot ( index  faceIndex) const
inline

Returns the MatIdx index of the column which has the given row index as pivot in \( R \). Assumes that the pivot exists.

Parameters
faceIndexRow index of the pivot.
Returns
MatIdx index of the column in \( R \) with the given pivot.

◆ get_max_dimension()

template<class Master_matrix >
RU_matrix< Master_matrix >::dimension_type Gudhi::persistence_matrix::RU_matrix< Master_matrix >::get_max_dimension
inline

Returns the maximal dimension of a face stored in the matrix. Only available if PersistenceMatrixOptions::has_matrix_maximal_dimension_access is true.

Returns
The maximal dimension.

◆ get_number_of_columns()

template<class Master_matrix >
RU_matrix< Master_matrix >::index Gudhi::persistence_matrix::RU_matrix< Master_matrix >::get_number_of_columns
inline

Returns the current number of columns in the matrix.

Returns
The number of columns.

◆ get_pivot()

template<class Master_matrix >
RU_matrix< Master_matrix >::index Gudhi::persistence_matrix::RU_matrix< Master_matrix >::get_pivot ( index  columnIndex)
inline

Returns the row index of the pivot of the given column in \( R \).

Parameters
columnIndexMatIdx index of the column in \( R \).
Returns
The row index of the pivot.

◆ get_row()

template<class Master_matrix >
RU_matrix< Master_matrix >::Row_type & Gudhi::persistence_matrix::RU_matrix< Master_matrix >::get_row ( index  rowIndex,
bool  inR = true 
)
inline

Returns the row at the given row index in \( R \) if inR is true and in \( U \) if inR is false. The type of the row depends on the choosen options, see PersistenceMatrixOptions::has_intrusive_rows.

Note that before returning the row, all column cells can eventually be reordered, if lazy swaps occurred. It is therefore recommended to avoid calling get_row between vine swaps, otherwise the benefits of the the lazyness is lost.

Parameters
rowIndexRow index of the row to return.
inRIf true, returns the row in \( R \), if false, returns the row in \( U \). Default value: true.
Returns
Reference to the row.

◆ insert_boundary() [1/2]

template<class Master_matrix >
template<class Boundary_type >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::insert_boundary ( const Boundary_type &  boundary,
dimension_type  dim = -1 
)
inline

Inserts at the end of the matrix a new ordered column corresponding to the given boundary. This means that it is assumed that this method is called on boundaries in the order of the filtration. It also assumes that the faces in the given boundary are identified by their relative position in the filtration, starting at 0. If it is not the case, use the other insert_boundary instead by indicating the face ID used in the boundaries when the face is inserted.

Different to the constructor, the boundaries do not have to come from a simplicial complex, but also from a more general cell complex. This includes cubical complexes or Morse complexes for example.

At the insertion, the boundary is stored in its reduced form and the barcode, if enabled, is updated.

Template Parameters
Boundary_typeRange of Matrix::cell_rep_type. Assumed to have a begin(), end() and size() method.
Parameters
boundaryBoundary generating the new column. The content should be ordered by ID.
dimDimension of the face whose boundary is given. If the complex is simplicial, this parameter can be omitted as it can be deduced from the size of the boundary.

◆ insert_boundary() [2/2]

template<class Master_matrix >
template<class Boundary_type >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::insert_boundary ( id_index  faceIndex,
const Boundary_type &  boundary,
dimension_type  dim = -1 
)
inline

It does the same as the other version, but allows the boundary faces to be identified without restrictions except that all IDs have to be strictly increasing in the order of filtration. Note that you should avoid then to use the other insertion method to avoid overwriting IDs.

As a face has to be inserted before one of its cofaces in a valid filtration (recall that it is assumed that the faces are inserted by order of filtration), it is sufficient to indicate the ID of the face being inserted.

Template Parameters
Boundary_typeRange of Matrix::cell_rep_type. Assumed to have a begin(), end() and size() method.
Parameters
faceIndexIDIdx index to use to indentify the new face.
boundaryBoundary generating the new column. The indices of the boundary have to correspond to the faceIndex values of precedent calls of the method for the corresponding faces and should be ordered in increasing order.
dimDimension of the face whose boundary is given. If the complex is simplicial, this parameter can be omitted as it can be deduced from the size of the boundary.

◆ is_zero_cell()

template<class Master_matrix >
bool Gudhi::persistence_matrix::RU_matrix< Master_matrix >::is_zero_cell ( index  columnIndex,
index  rowIndex,
bool  inR = true 
) const
inline

Indicates if the cell at given coordinates has value zero in \( R \) if inR is true or in \( U \) if inR is false.

Parameters
columnIndexMatIdx index of the column of the cell.
rowIndexRow index of the row of the cell.
inRBoolean indicating in which matrix to look: if true in \( R \) and if false in \( U \). Default value: true.
Returns
true If the cell has value zero.
false Otherwise.

◆ is_zero_column()

template<class Master_matrix >
bool Gudhi::persistence_matrix::RU_matrix< Master_matrix >::is_zero_column ( index  columnIndex,
bool  inR = true 
)
inline

Indicates if the column at given index has value zero in \( R \) if inR is true or in \( U \) if inR is false.

Note that if inR is false, this method should usually return false.

Parameters
columnIndexMatIdx index of the column.
inRBoolean indicating in which matrix to look: if true in \( R \) and if false in \( U \). Default value: true.
Returns
true If the column has value zero.
false Otherwise.

◆ multiply_source_and_add_to()

template<class Master_matrix >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::multiply_source_and_add_to ( const Field_element_type coefficient,
index  sourceColumnIndex,
index  targetColumnIndex 
)
inline

Multiplies the source column with the coefficiant before adding it to the target column. That is: targetColumn += (coefficient * sourceColumn). The source column will not be modified.

Warning
They will be no verification to ensure that the addition makes sense for the validity of a boundary matrix of a filtered complex. For example, a right-to-left addition could corrupt the computation of the barcode if done blindly. So should be used with care.
Parameters
coefficientValue to multiply.
sourceColumnIndexMatIdx index of the source column.
targetColumnIndexMatIdx index of the target column.

◆ multiply_target_and_add_to()

template<class Master_matrix >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::multiply_target_and_add_to ( index  sourceColumnIndex,
const Field_element_type coefficient,
index  targetColumnIndex 
)
inline

Multiplies the target column with the coefficiant and then adds the source column to it. That is: targetColumn = (targetColumn * coefficient) + sourceColumn.

Warning
They will be no verification to ensure that the addition makes sense for the validity of a boundary matrix of a filtered complex. For example, a right-to-left addition could corrupt the computation of the barcode if done blindly. So should be used with care.
Parameters
sourceColumnIndexMatIdx index of the source column.
coefficientValue to multiply.
targetColumnIndexMatIdx index of the target column.

◆ remove_last()

template<class Master_matrix >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::remove_last
inline

Only available if PersistenceMatrixOptions::has_removable_columns is true. Removes the last face in the filtration from the matrix and updates the barcode if it is stored.

See also remove_maximal_face.

◆ remove_maximal_face()

template<class Master_matrix >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::remove_maximal_face ( index  columnIndex)
inline

Only available if PersistenceMatrixOptions::has_removable_columns and PersistenceMatrixOptions::has_vine_update are true. Assumes that the face is maximal in the current complex and removes it such that the matrix remains consistent (i.e., RU is still an upper triangular decomposition of the boundary matrix). The maximality of the face is not verified. Also updates the barcode if it is stored.

See also remove_last.

Parameters
columnIndexMatIdx index of the face to remove.

◆ reset()

template<class Master_matrix >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::reset ( Column_settings colSettings)
inline

Resets the matrix to an empty matrix.

Parameters
colSettingsPointer to an existing setting structure for the columns. The structure should contain all the necessary external classes specifically necessary for the choosen column type, such as custom allocators.

◆ zero_cell()

template<class Master_matrix >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::zero_cell ( index  columnIndex,
index  rowIndex,
bool  inR = true 
)
inline

Zeroes the cell at the given coordinates in \( R \) if inR is true or in \( U \) if inR is false. Should be used with care to not destroy the validity of the persistence related properties of the matrix.

Parameters
columnIndexMatIdx index of the column of the cell.
rowIndexRow index of the row of the cell.
inRBoolean indicating in which matrix to zero: if true in \( R \) and if false in \( U \). Default value: true.

◆ zero_column()

template<class Master_matrix >
void Gudhi::persistence_matrix::RU_matrix< Master_matrix >::zero_column ( index  columnIndex,
bool  inR = true 
)
inline

Zeroes the column at the given index in \( R \) if inR is true or in \( U \) if inR is false. Should be used with care to not destroy the validity of the persistence related properties of the matrix.

Parameters
columnIndexMatIdx index of the column to zero.
inRBoolean indicating in which matrix to zero: if true in \( R \) and if false in \( U \). Default value: true.

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