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 
21 #include "ortools/base/int_type.h"
22 #include "ortools/base/logging.h"
24 #include "ortools/util/bitset.h"
25 
26 namespace operations_research {
27 namespace 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.
32 template <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.
54 template <typename Index,
55  typename Iterator = VectorIterator<ScatteredVectorEntry<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.
61  bool non_zeros_are_sorted = false;
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().
111  if (!non_zeros_are_sorted) {
112  std::sort(non_zeros.begin(), non_zeros.end());
113  non_zeros_are_sorted = true;
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 
127  bool ShouldUseDenseIteration() const {
129  }
130 
131  // Efficiently clears the is_non_zero vector.
133  if (ShouldUseDenseIteration()) {
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.
146  ClearSparseMask();
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)) {
154  ClearSparseMask();
155  non_zeros.clear();
156  }
157  }
158 
161  }
162 };
163 
164 // Specializations used in the code.
165 class ScatteredColumnEntry : public ScatteredVectorEntry<RowIndex> {
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 
176 class 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> {};
192 struct ScatteredRow : public ScatteredVector<ColIndex, ScatteredRowIterator> {};
193 
194 inline const ScatteredRow& TransposedView(const ScatteredColumn& c) {
195  return reinterpret_cast<const ScatteredRow&>(c);
196 }
197 inline const ScatteredColumn& TransposedView(const ScatteredRow& r) {
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)
bool IsAllFalse(const BoolVector &v)
const ScatteredRow & TransposedView(const ScatteredColumn &c)
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
bool ShouldUseDenseIteration(double ratio_for_using_dense_representation) const
constexpr static const double kDefaultRatioForUsingDenseIteration
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