operations_research::math_opt::GlpkSparseVector Class Reference

#include <glpk_sparse_vector.h>

Public Member Functions
	GlpkSparseVector (int capacity)
int	capacity () const
	Returns the capacity (the size of the vector if it was dense).
int	size () const
	Returns the number of entries in the sparse vector.
const int *	indices () const
const double *	values () const
void	Clear ()
std::optional< double >	Get (int index) const
void	Set (int index, double value)
void	Load (std::function< int(int *indices, double *values)> getter)

Detailed Description

Sparse vector in GLPK format.

GLPK represents a sparse vector of size n with two arrays of size n+1, one for indices and one for values. The first element of each of these arrays is ignored (GLPK uses one-based indices). On top of that, the array of indices contains one-based indices (typically rows or columns indices). The entries are not necessarily sorted.

For example to store a sparse vector where we have:

idx | value -—+---— GLPK would use two arrays:

const int indices[] = { /*ignored*‍/-1, 3, 1, 5 }; const double values[] = { /*ignored*‍/NAN, -1.0, 2.5, 0.5 };

This class also keeps an additional vector which size is the capacity of the sparse vector (i.e. the corresponding size of a dense vector). It associates to each index an optional position of the corresponding entry in the indices and values arrays. This is used to make Set() and Get() O(1) and this makes Clear() O(size()) since indices associated to entries need to be cleared.

This additional vector along with the ones used for indices and values are all pre-allocated to fit the capacity. Hence an instance of this class allocates:

capacity * (2 * sizeof(int) + sizeof(double))

It is thus recommended to reuse the same instance multiple times instead of reallocating one for it to be efficient.

Definition at line 64 of file glpk_sparse_vector.h.

Constructor & Destructor Documentation

GlpkSparseVector()

operations_research::math_opt::GlpkSparseVector::GlpkSparseVector ( int capacity )

explicit

Builds a sparse vector with the provided capacity (i.e. the size of the vector it was dense).

This operation has O(capacity) complexity (see the class documentation for allocated memory).

Definition at line 24 of file glpk_sparse_vector.cc.

Member Function Documentation

capacity()

int operations_research::math_opt::GlpkSparseVector::capacity ( ) const

inline

Returns the capacity (the size of the vector if it was dense).

Definition at line 74 of file glpk_sparse_vector.h.

Clear()

void operations_research::math_opt::GlpkSparseVector::Clear

(

)

Clears the sparse vector, removing all entries.

This operation has O(size()) complexity.

Resets the elements of the index_to_entry_ map we have modified.

Cleanup the used items to make sure we don't reuse those values by mistake later.

Definition at line 32 of file glpk_sparse_vector.cc.

Get()

std::optional< double > operations_research::math_opt::GlpkSparseVector::Get ( int index ) const

inline

Returns the value at the given index if there is a corresponding entry or nullopt.

It CHECKs that the index is in [1, capacity]. The operation has O(1) complexity.

Inline implementations

Definition at line 164 of file glpk_sparse_vector.h.

indices()

const int * operations_research::math_opt::GlpkSparseVector::indices ( ) const

inline

Returns the indices array of the GLPK sparse vector.

Only values in [1, size()] are meaningful.

Definition at line 82 of file glpk_sparse_vector.h.

Load()

void operations_research::math_opt::GlpkSparseVector::Load

(

std::function< int(int *indices, double *values)>

getter

)

Replaces the content of the sparse vector by calling a GLPK API.

Since GLPK functions have other parameters, here we expect the caller to provide a wrapping lambda expression that passes the indices and values buffers to the GLPK function and returns the number of written elements.

It CHECKs that the returned number of elements is not greater than the capacity, that the indices are in [1, capacity] range and that there is no duplicated indices.

Example:

GlpkSparseVector row_values(num_cols); row_values.Set([&](int* const indices, double* const values) { return glp_get_mat_row(problem, row_index, indices, values); });

We don't know if the GLPK API has written to the first element but we reset those values anyway.

Update index_to_entry_.

Definition at line 48 of file glpk_sparse_vector.cc.

Set()

void operations_research::math_opt::GlpkSparseVector::Set ( int index, double value )

inline

Changes the value of the given index, adding a new entry if necessary.

Note

entries are only removed by Clear() or Load(). Setting a value to 0.0 does not remove the corresponding entry.

It CHECKs that the index is in [1, capacity]. The operation has O(1) complexity.

Definition at line 180 of file glpk_sparse_vector.h.

size()

int operations_research::math_opt::GlpkSparseVector::size ( ) const

inline

Returns the number of entries in the sparse vector.

Definition at line 77 of file glpk_sparse_vector.h.

values()

const double * operations_research::math_opt::GlpkSparseVector::values ( ) const

inline

Returns the values array of the GLPK sparse vector.

Only values in [1, size()] are meaningful.

Definition at line 87 of file glpk_sparse_vector.h.

---

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

• ortools/math_opt/solvers/glpk/glpk_sparse_vector.h
• ortools/math_opt/solvers/glpk/glpk_sparse_vector.cc