operations_research::math_opt::SparseSymmetricMatrix Class Reference

#include <sparse_matrix.h>

Public Member Functions
bool	set (VariableId first, VariableId second, double value)
double	get (VariableId first, VariableId second) const
	Zero is returned if the value is not present.
void	Delete (VariableId variable)
	Zeros out all coefficients for this variable.
std::vector< VariableId >	Variables () const
std::vector< VariableId >	RelatedVariables (VariableId variable) const
std::vector< std::pair< VariableId, double > >	Terms (VariableId variable) const
std::vector< std::tuple< VariableId, VariableId, double > >	Terms () const
void	Clear ()
	Removes all terms from the matrix.
int64_t	nonzeros () const
int64_t	impl_detail_matrix_storage_size () const
const absl::flat_hash_map< std::pair< VariableId, VariableId >, double > &	values () const
SparseDoubleMatrixProto	Proto () const
SparseDoubleMatrixProto	Update (const absl::flat_hash_set< VariableId > &deleted_variables, absl::Span< const VariableId > new_variables, const absl::flat_hash_set< std::pair< VariableId, VariableId > > &dirty) const

Detailed Description

A sparse symmetric double valued matrix over VariableIds.

Note

the matrix is sparse in both:

• The IDs of the rows/columns (both VariableIds), 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 with many deletions may be slow).

Implementation: The entries are stored in a flat_hash_map<pair<VariableId, VariableId>, double> values_ where for each key, key.first <= key.second. Additionally, we maintain a flat_hash_map<VariableId, vector<VariableId>> related_variables_ that says for each variable, which variables they have a nonzero term with. When a coefficient is set to zero or a variable is deleted, we do not immediately delete the data from values_ or related_variables_, 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 kZerosCleanup in cc file), we clean up related_variables_ 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 related_variables_.
• ~5*8 bytes per variable participating in any quadratic term; one heap allocation per such variable.

Definition at line 66 of file sparse_matrix.h.

Member Function Documentation

Clear()

void operations_research::math_opt::SparseSymmetricMatrix::Clear

(

)

Removes all terms from the matrix.

Definition at line 134 of file sparse_matrix.cc.

Delete()

void operations_research::math_opt::SparseSymmetricMatrix::Delete

(

VariableId

variable

)

Zeros out all coefficients for this variable.

Definition at line 32 of file sparse_matrix.cc.

get()

double operations_research::math_opt::SparseSymmetricMatrix::get ( VariableId first, VariableId second ) const

inline

Zero is returned if the value is not present.

Definition at line 340 of file sparse_matrix.h.

impl_detail_matrix_storage_size()

int64_t operations_research::math_opt::SparseSymmetricMatrix::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 113 of file sparse_matrix.h.

nonzeros()

int64_t operations_research::math_opt::SparseSymmetricMatrix::nonzeros ( ) const

inline

The number of (var, var) keys with nonzero value. Note that (x, y) and (y, x) are the same key.

Definition at line 109 of file sparse_matrix.h.

Proto()

SparseDoubleMatrixProto operations_research::math_opt::SparseSymmetricMatrix::Proto

(

)

const

Todo

(b/233630053): reuse the allocation once an iterator API is supported.

Definition at line 140 of file sparse_matrix.cc.

RelatedVariables()

std::vector< VariableId > operations_research::math_opt::SparseSymmetricMatrix::RelatedVariables

(

VariableId

variable

)

const

Returns the variables that have nonzero entries with variable.

The return order is deterministic but not defined.

Todo

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

Definition at line 47 of file sparse_matrix.cc.

set()

bool operations_research::math_opt::SparseSymmetricMatrix::set ( VariableId first, VariableId second, double value )

inline

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

Definition at line 308 of file sparse_matrix.h.

Terms() [1/2]

std::vector< std::tuple< VariableId, VariableId, double > > operations_research::math_opt::SparseSymmetricMatrix::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 92 of file sparse_matrix.cc.

Terms() [2/2]

std::vector< std::pair< VariableId, double > > operations_research::math_opt::SparseSymmetricMatrix::Terms

(

VariableId

variable

)

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 76 of file sparse_matrix.cc.

Update()

SparseDoubleMatrixProto operations_research::math_opt::SparseSymmetricMatrix::Update	(	const absl::flat_hash_set< VariableId > &	deleted_variables,
		absl::Span< const VariableId >	new_variables,
		const absl::flat_hash_set< std::pair< VariableId, VariableId > > &	dirty ) const

If either variable has been deleted, don't add it.

Todo

(b/233630053): do not allocate here.

Definition at line 165 of file sparse_matrix.cc.

values()

const absl::flat_hash_map< std::pair< VariableId, VariableId >, double > & operations_research::math_opt::SparseSymmetricMatrix::values ( ) const

inline

Todo

(b/233630053): do not expose values_ directly, instead offer a way to iterate over all the nonzero entries.

Warning

this map will contain zeros.

Definition at line 118 of file sparse_matrix.h.

Variables()

std::vector< VariableId > operations_research::math_opt::SparseSymmetricMatrix::Variables

(

)

const

Returns the variables with any nonzero in the matrix.

The return order is deterministic but not defined.

Todo

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

Note

we could make this more efficient in the presence of deletions by storing the actual number of neighbors in the value of related_variables_.

Definition at line 61 of file sparse_matrix.cc.

---

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

• ortools/math_opt/storage/sparse_matrix.h
• ortools/math_opt/storage/sparse_matrix.cc