operations_research::glop::ScatteredVector< Index, Iterator > Struct Template Reference

#include <scattered_vector.h>

Public Member Functions
Fractional	operator[] (Index index) const
Fractional &	operator[] (Index index)
Iterator	begin () const
Iterator	end () const
void	Add (Index index, Fractional value)
void	SortNonZerosIfNeeded ()
bool	ShouldUseDenseIteration (double ratio_for_using_dense_representation) const
bool	ShouldUseDenseIteration () const
void	ClearSparseMask ()
	Efficiently clears the is_non_zero vector.
void	RepopulateSparseMask ()
	Update the is_non_zero vector to be consistent with the non_zeros vector.
void	ClearNonZerosIfTooDense (double ratio_for_using_dense_representation)
void	ClearNonZerosIfTooDense ()
size_t	NumNonZerosEstimate () const

Public Attributes
StrictITIVector< Index, Fractional >	values
bool	non_zeros_are_sorted = false
std::vector< Index >	non_zeros
StrictITIVector< Index, bool >	is_non_zero

Static Public Attributes
static constexpr const double	kDefaultRatioForUsingDenseIteration = 0.8

Detailed Description

template<typename Index, typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>
struct operations_research::glop::ScatteredVector< Index, Iterator >

A simple struct that contains a DenseVector and its non-zero indices.

Todo

(user): This should be changed from struct to class.

Definition at line 53 of file scattered_vector.h.

Member Function Documentation

Add()

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

void operations_research::glop::ScatteredVector< Index, Iterator >::Add ( Index index, Fractional value )

inline

Add the given value to the vector at position index. This interface encapsulates usage of the "is_non_zero" array, which should not be explicitly referenced outside of this struct.

Definition at line 95 of file scattered_vector.h.

begin()

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

Iterator operations_research::glop::ScatteredVector< Index, Iterator >::begin ( ) const

inline

The iterator syntax for (auto entry : v) where v is a ScatteredVector only works when non_zeros is populated (i.e., when the vector is treated as sparse).

Definition at line 83 of file scattered_vector.h.

ClearNonZerosIfTooDense() [1/2]

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

void operations_research::glop::ScatteredVector< Index, Iterator >::ClearNonZerosIfTooDense ( )

inline

Definition at line 156 of file scattered_vector.h.

ClearNonZerosIfTooDense() [2/2]

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

void operations_research::glop::ScatteredVector< Index, Iterator >::ClearNonZerosIfTooDense ( double ratio_for_using_dense_representation )

inline

If the proportion of non-zero entries is too large, clears the vector of non-zeros.

Definition at line 149 of file scattered_vector.h.

ClearSparseMask()

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

void operations_research::glop::ScatteredVector< Index, Iterator >::ClearSparseMask ( )

inline

Efficiently clears the is_non_zero vector.

Definition at line 129 of file scattered_vector.h.

end()

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

Iterator operations_research::glop::ScatteredVector< Index, Iterator >::end ( ) const

inline

Definition at line 87 of file scattered_vector.h.

NumNonZerosEstimate()

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

size_t operations_research::glop::ScatteredVector< Index, Iterator >::NumNonZerosEstimate ( ) const

inline

Returns an overestimate of the number of non-zeros. This is actually exact for sparse vector, or the full size otherwise.

Definition at line 162 of file scattered_vector.h.

operator[]() [1/2]

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

Fractional & operations_research::glop::ScatteredVector< Index, Iterator >::operator[] ( Index index )

inline

Definition at line 78 of file scattered_vector.h.

operator[]() [2/2]

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

Fractional operations_research::glop::ScatteredVector< Index, Iterator >::operator[] ( Index index ) const

inline

Definition at line 77 of file scattered_vector.h.

RepopulateSparseMask()

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

void operations_research::glop::ScatteredVector< Index, Iterator >::RepopulateSparseMask ( )

inline

Update the is_non_zero vector to be consistent with the non_zeros vector.

Definition at line 142 of file scattered_vector.h.

ShouldUseDenseIteration() [1/2]

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

bool operations_research::glop::ScatteredVector< Index, Iterator >::ShouldUseDenseIteration ( ) const

inline

Definition at line 124 of file scattered_vector.h.

ShouldUseDenseIteration() [2/2]

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

bool operations_research::glop::ScatteredVector< Index, Iterator >::ShouldUseDenseIteration ( double ratio_for_using_dense_representation ) const

inline

Returns true if it is more advantageous to use a dense iteration rather than using the non-zeros positions.

Definition at line 116 of file scattered_vector.h.

SortNonZerosIfNeeded()

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

void operations_research::glop::ScatteredVector< Index, Iterator >::SortNonZerosIfNeeded ( )

inline

Sorting the non-zeros is not always needed, but it allows us to have exactly the same behavior while using a sparse iteration or a dense one. So we always do it after a Solve().

Definition at line 107 of file scattered_vector.h.

Member Data Documentation

is_non_zero

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

StrictITIVector<Index, bool> operations_research::glop::ScatteredVector< Index, Iterator >::is_non_zero

Temporary vector used in some sparse computation on the ScatteredVector. True indicates a possible non-zero value. Note that its state is not always consistent.

Definition at line 64 of file scattered_vector.h.

kDefaultRatioForUsingDenseIteration

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

const double operations_research::glop::ScatteredVector< Index, Iterator >::kDefaultRatioForUsingDenseIteration = 0.8

staticconstexpr

In many cases there is a choice between treating the ScatteredVector as dense or as sparse. By default, dense algorithms are used when the proportion of non-zero entries is greater than kDefaultRatioForUsingDenseIteration.

Todo

(user): The constant should depend on what algorithm is used. Clearing a dense vector is a lot more efficient than doing more complex stuff. Clean this up by extracting all the currently used constants in one place with meaningful names.

Definition at line 75 of file scattered_vector.h.

non_zeros

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

std::vector<Index> operations_research::glop::ScatteredVector< Index, Iterator >::non_zeros

Definition at line 59 of file scattered_vector.h.

non_zeros_are_sorted

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

bool operations_research::glop::ScatteredVector< Index, Iterator >::non_zeros_are_sorted = false

This can be left empty in which case we just have the dense representation above. Otherwise, it should always be a superset of the actual non-zeros.

Definition at line 58 of file scattered_vector.h.

values

template<typename Index , typename Iterator = VectorIterator<ScatteredVectorEntry<Index>>>

StrictITIVector<Index, Fractional> operations_research::glop::ScatteredVector< Index, Iterator >::values

Definition at line 54 of file scattered_vector.h.

---

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

• ortools/lp_data/scattered_vector.h