#include <sparse_matrix.h>

Public Member Functions
bool	set (RowId row, ColumnId column, double value)

double	get (RowId row, ColumnId column) const
	Zero is returned if the value is not present.

bool	contains (RowId row, ColumnId column) const
	Returns true if the value is present (nonzero).

void	DeleteRow (RowId row)
	Zeros out all coefficients for this variable.

void	DeleteColumn (ColumnId column)
	Zeros out all coefficients for this variable.

std::vector< ColumnId >	row (RowId row_id) const

std::vector< RowId >	column (ColumnId column_id) const

std::vector< std::pair< ColumnId, double > >	RowTerms (RowId row_id) const

std::vector< std::pair< RowId, double > >	ColumnTerms (ColumnId col_id) const

std::vector< std::tuple< RowId, ColumnId, double > >	Terms () const

void	Clear ()
	Removes all terms from the matrix.

int64_t	nonzeros () const
	The number of (row, column) keys with nonzero value.

int64_t	impl_detail_matrix_storage_size () const

SparseDoubleMatrixProto	Proto () const

SparseDoubleMatrixProto	Update (const absl::flat_hash_set< RowId > &deleted_rows, absl::Span< const RowId > new_rows, const absl::flat_hash_set< ColumnId > &deleted_columns, absl::Span< const ColumnId > new_columns, const absl::flat_hash_set< std::pair< RowId, ColumnId > > &dirty) const

Detailed Description

template<typename RowId, typename ColumnId>
class operations_research::math_opt::SparseMatrix< RowId, ColumnId >

A sparse double valued matrix over int-like rows and columns.

Note

the matrix is sparse in both:

The IDs of the rows/columns, stored as flat_hash_map.
The entries with nonzero value.

Getting/setting/clearing entries are O(1) operations. Getting a row of the matrix runs in O(size of the row) if nothing has been deleted, and getting all the rows runs in O(number of nonzero entries), even with deletions (with deletions, accessing a particular row or columns with many deletions may be slow).

Implementation: The entries are stored in a flat_hash_map<pair<RowId, ColumnId>, double> values_. Additionally, we maintain a flat_hash_map<RowId, vector<ColumnId>> rows_ and a flat_hash_map<ColumnId, vector<RowID>> columns_ that enable efficient queries of the nonzeros in any row or column. When a coefficient is set to zero or a variable is deleted, we do not immediately delete the data from values_, rows_, or columns_, we simply set the coefficient to zero in values_. We track how many zeros are in values_, and when more than some constant fraction of all entries are zero (see internal::kZerosCleanup), we clean up rows_, columns_, and values_ to remove all the zeros. Iteration over the rows or total entries of the matrix must check for zeros in values_ and skip these terms.

Memory use:

3*8 bytes per nonzero plus hash capacity overhead for values_.
2*8 bytes per nonzero plus vector capacity overhead for rows_ and columns_.
~5*8 bytes and one heap allocation per unique row and unique column.

Definition at line 175 of file sparse_matrix.h.

Member Function Documentation

◆ Clear()

template<typename RowId , typename ColumnId >

void operations_research::math_opt::SparseMatrix< RowId, ColumnId >::Clear ( )

Removes all terms from the matrix.

Definition at line 505 of file sparse_matrix.h.

◆ column()

template<typename RowId , typename ColumnId >

std::vector< RowId > operations_research::math_opt::SparseMatrix< RowId, ColumnId >::column ( ColumnId column_id ) const

Returns the variables that have nonzero entries with variable.

Todo: (b/233630053): expose an iterator based API to avoid making a copy.

Definition at line 445 of file sparse_matrix.h.

◆ ColumnTerms()

template<typename RowId , typename ColumnId >

std::vector< std::pair< RowId, double > > operations_research::math_opt::SparseMatrix< RowId, ColumnId >::ColumnTerms ( ColumnId col_id ) const

Returns the variable value pairs (x, c) where variable and x have nonzero coefficient c.

The return order is deterministic but not defined.

Todo: (b/233630053): expose an iterator based API to avoid making a copy.

Definition at line 477 of file sparse_matrix.h.

◆ contains()

template<typename RowId , typename ColumnId >

bool operations_research::math_opt::SparseMatrix< RowId, ColumnId >::contains	(	RowId	row,
		ColumnId	column ) const

Returns true if the value is present (nonzero).

Definition at line 391 of file sparse_matrix.h.

◆ DeleteColumn()

template<typename RowId , typename ColumnId >

void operations_research::math_opt::SparseMatrix< RowId, ColumnId >::DeleteColumn ( ColumnId column )

Zeros out all coefficients for this variable.

Definition at line 414 of file sparse_matrix.h.

◆ DeleteRow()

template<typename RowId , typename ColumnId >

void operations_research::math_opt::SparseMatrix< RowId, ColumnId >::DeleteRow ( RowId row )

Zeros out all coefficients for this variable.

Definition at line 398 of file sparse_matrix.h.

◆ get()

template<typename RowId , typename ColumnId >

double operations_research::math_opt::SparseMatrix< RowId, ColumnId >::get	(	RowId	row,
		ColumnId	column ) const

Zero is returned if the value is not present.

Definition at line 382 of file sparse_matrix.h.

◆ impl_detail_matrix_storage_size()

template<typename RowId , typename ColumnId >

int64_t operations_research::math_opt::SparseMatrix< RowId, ColumnId >::impl_detail_matrix_storage_size ( ) const

inline

For testing/debugging only, do not depend on this value, behavior may change based on implementation.

Definition at line 230 of file sparse_matrix.h.

◆ nonzeros()

template<typename RowId , typename ColumnId >

int64_t operations_research::math_opt::SparseMatrix< RowId, ColumnId >::nonzeros ( ) const

The number of (row, column) keys with nonzero value.

Definition at line 512 of file sparse_matrix.h.

◆ Proto()

template<typename RowId , typename ColumnId >

SparseDoubleMatrixProto operations_research::math_opt::SparseMatrix< RowId, ColumnId >::Proto ( ) const

Definition at line 517 of file sparse_matrix.h.

◆ row()

template<typename RowId , typename ColumnId >

std::vector< ColumnId > operations_research::math_opt::SparseMatrix< RowId, ColumnId >::row ( RowId row_id ) const

Returns the variables that have nonzero entries with variable.

Todo: (b/233630053): expose an iterator based API to avoid making a copy.

Definition at line 430 of file sparse_matrix.h.

◆ RowTerms()

template<typename RowId , typename ColumnId >

std::vector< std::pair< ColumnId, double > > operations_research::math_opt::SparseMatrix< RowId, ColumnId >::RowTerms ( RowId row_id ) const

Returns the variable value pairs (x, c) where variable and x have nonzero coefficient c.

The return order is deterministic but not defined.

Todo: (b/233630053): expose an iterator based API to avoid making a copy.

Definition at line 461 of file sparse_matrix.h.

◆ set()

template<typename RowId , typename ColumnId >

bool operations_research::math_opt::SparseMatrix< RowId, ColumnId >::set	(	RowId	row,
		ColumnId	column,
		double	value )

Setting value to zero removes the value from the matrix. Returns true if value is different from the existing value in the matrix.

SparseMatrix

Definition at line 352 of file sparse_matrix.h.

◆ Terms()

template<typename RowId , typename ColumnId >

std::vector< std::tuple< RowId, ColumnId, double > > operations_research::math_opt::SparseMatrix< RowId, ColumnId >::Terms ( ) const

Returns (x, y, c) tuples where variables x and y have nonzero coefficient c, and x <= y.

The return order is non-deterministic and not defined.

Todo: (b/233630053): expose an iterator based API to avoid making a copy.

Definition at line 493 of file sparse_matrix.h.

◆ Update()

template<typename RowId , typename ColumnId >

SparseDoubleMatrixProto operations_research::math_opt::SparseMatrix< RowId, ColumnId >::Update	(	const absl::flat_hash_set< RowId > &	deleted_rows,
		absl::Span< const RowId >	new_rows,
		const absl::flat_hash_set< ColumnId > &	deleted_columns,
		absl::Span< const ColumnId >	new_columns,
		const absl::flat_hash_set< std::pair< RowId, ColumnId > > &	dirty ) const

Extract changes to the matrix of linear constraint coefficients

Note: it is important that we check for deleted constraints and variables here. While we generally try to remove elements from matrix_keys_ when either their variable or constraint is deleted, if a coefficient is set to zero and then the variable/constraint is deleted, we will miss it.

Todo: (b/233630053): use iterator API.

Todo: (b/233630053) use iterator API.

NOTE(user): we already have the columns above the checkpoint from the loop above, but we will do at most twice as much as needed here.

Definition at line 530 of file sparse_matrix.h.

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

ortools/math_opt/storage/sparse_matrix.h

Public Member Functions

Detailed Description

Member Function Documentation

◆ Clear()

◆ column()

◆ ColumnTerms()

◆ contains()

◆ DeleteColumn()

◆ DeleteRow()

◆ get()

◆ impl_detail_matrix_storage_size()

◆ nonzeros()

◆ Proto()

◆ row()

◆ RowTerms()

◆ set()

◆ Terms()

◆ Update()