OR-Tools  8.2
scattered_vector.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_LP_DATA_SCATTERED_VECTOR_H_
15#define OR_TOOLS_LP_DATA_SCATTERED_VECTOR_H_
16
17#include <cmath>
18#include <limits>
19
24#include "ortools/util/bitset.h"
25
26namespace operations_research {
27namespace glop {
28
29// A class representing an entry of a scattered vector. The i-th nonzero
30// element of the vector is assumed to be located at indices[i] and its value is
31// coefficients[indices[i]], i.e., coefficients is a dense array.
32template <typename IndexType>
34 public:
35 using Index = IndexType;
36
37 Index index() const { return index_[i_.value()]; }
39 return coefficient_[index_[i_.value()].value()];
40 }
41
42 protected:
44 EntryIndex i)
45 : i_(i), index_(indices), coefficient_(coefficients) {}
46
47 EntryIndex i_;
48 const Index* index_;
50};
51
52// A simple struct that contains a DenseVector and its non-zero indices.
53// TODO(user): This should be changed from struct to class.
54template <typename Index,
58
59 // This can be left empty in which case we just have the dense representation
60 // above. Otherwise, it should always be a superset of the actual non-zeros.
62 std::vector<Index> non_zeros;
63
64 // Temporary vector used in some sparse computation on the ScatteredVector.
65 // True indicates a possible non-zero value. Note that its state is not always
66 // consistent.
68
69 // In many cases there is a choice between treating the ScatteredVector as
70 // dense or as sparse. By default, dense algorithms are used when the
71 // proportion of non-zero entries is greater than
72 // kDefaultRatioForUsingDenseIteration.
73 //
74 // TODO(user): The constant should depend on what algorithm is used. Clearing
75 // a dense vector is a lot more efficient than doing more complex stuff. Clean
76 // this up by extracting all the currently used constants in one place with
77 // meaningful names.
78 constexpr static const double kDefaultRatioForUsingDenseIteration = 0.8;
79
82
83 // The iterator syntax for (auto entry : v) where v is a ScatteredVector only
84 // works when non_zeros is populated (i.e., when the vector is treated as
85 // sparse).
86 Iterator begin() const {
87 DCHECK(!non_zeros.empty() || IsAllZero(values));
88 return Iterator(this->non_zeros.data(), this->values.data(), EntryIndex(0));
89 }
90 Iterator end() const {
91 return Iterator(this->non_zeros.data(), this->values.data(),
92 EntryIndex(non_zeros.size()));
93 }
94
95 // Add the given value to the vector at position index. This interface
96 // encapsulates usage of the "is_non_zero" array, which should not be
97 // explicitly referenced outside of this struct.
99 values[index] += value;
100 if (!is_non_zero[index] && value != 0.0) {
101 is_non_zero[index] = true;
102 non_zeros.push_back(index);
103 non_zeros_are_sorted = false;
104 }
105 }
106
107 // Sorting the non-zeros is not always needed, but it allows us to have
108 // exactly the same behavior while using a sparse iteration or a dense one. So
109 // we always do it after a Solve().
112 std::sort(non_zeros.begin(), non_zeros.end());
114 }
115 }
116
117 // Returns true if it is more advantageous to use a dense iteration rather
118 // than using the non-zeros positions.
120 double ratio_for_using_dense_representation) const {
121 if (non_zeros.empty()) return true;
122 return static_cast<double>(non_zeros.size()) >
123 ratio_for_using_dense_representation *
124 static_cast<double>(values.size().value());
125 }
126
129 }
130
131 // Efficiently clears the is_non_zero vector.
134 is_non_zero.assign(values.size(), false);
135 } else {
136 is_non_zero.resize(values.size(), false);
137 for (const Index index : non_zeros) {
138 is_non_zero[index] = false;
139 }
141 }
142 }
143
144 // Update the is_non_zero vector to be consistent with the non_zeros vector.
147 for (const Index index : non_zeros) is_non_zero[index] = true;
148 }
149
150 // If the proportion of non-zero entries is too large, clears the vector of
151 // non-zeros.
152 void ClearNonZerosIfTooDense(double ratio_for_using_dense_representation) {
153 if (ShouldUseDenseIteration(ratio_for_using_dense_representation)) {
155 non_zeros.clear();
156 }
157 }
158
161 }
162};
163
164// Specializations used in the code.
166 public:
167 // Returns the row of the current entry.
168 RowIndex row() const { return index(); }
169
170 protected:
171 ScatteredColumnEntry(const RowIndex* indices, const Fractional* coefficients,
172 EntryIndex i)
173 : ScatteredVectorEntry<RowIndex>(indices, coefficients, i) {}
174};
175
176class ScatteredRowEntry : public ScatteredVectorEntry<ColIndex> {
177 public:
178 // Returns the column of the current entry.
179 ColIndex column() const { return index(); }
180
181 protected:
182 ScatteredRowEntry(const ColIndex* indices, const Fractional* coefficients,
183 EntryIndex i)
184 : ScatteredVectorEntry<ColIndex>(indices, coefficients, i) {}
185};
186
189
191 : public ScatteredVector<RowIndex, ScatteredColumnIterator> {};
192struct ScatteredRow : public ScatteredVector<ColIndex, ScatteredRowIterator> {};
193
195 return reinterpret_cast<const ScatteredRow&>(c);
196}
198 return reinterpret_cast<const ScatteredColumn&>(r);
199}
200
201} // namespace glop
202} // namespace operations_research
203
204#endif // OR_TOOLS_LP_DATA_SCATTERED_VECTOR_H_
#define DCHECK(condition)
Definition: base/logging.h:884
RowIndex row() const
ScatteredColumnEntry(const RowIndex *indices, const Fractional *coefficients, EntryIndex i)
ColIndex column() const
ScatteredRowEntry(const ColIndex *indices, const Fractional *coefficients, EntryIndex i)
ScatteredVectorEntry(const Index *indices, const Fractional *coefficients, EntryIndex i)
EntryIndex i_
Index index() const
IndexType Index
Fractional coefficient() const
const Fractional * coefficient_
const Index * index_
void assign(IntType size, const T &v)
Definition: lp_types.h:274
int64 value
bool IsAllZero(const Container &input)
const ScatteredRow & TransposedView(const ScatteredColumn &c)
bool IsAllFalse(const BoolVector &v)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int index
Definition: pack.cc:508
std::vector< double > coefficients
static constexpr const double kDefaultRatioForUsingDenseIteration
bool ShouldUseDenseIteration(double ratio_for_using_dense_representation) const
void Add(Index index, Fractional value)
void ClearNonZerosIfTooDense(double ratio_for_using_dense_representation)
StrictITIVector< Index, bool > is_non_zero
StrictITIVector< Index, Fractional > values
Fractional operator[](Index index) const