OR-Tools  8.2
sparse_column.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_SPARSE_COLUMN_H_
15#define OR_TOOLS_LP_DATA_SPARSE_COLUMN_H_
16
18
19namespace operations_research {
20namespace glop {
21
22// TODO(user): Consider using kInvalidRow for this?
23const RowIndex kNonPivotal(-1);
24
25// Specialization of SparseVectorEntry and SparseColumnIterator for the
26// SparseColumn class. In addition to index(), it also provides row() for better
27// readability on the client side.
28class SparseColumnEntry : public SparseVectorEntry<RowIndex> {
29 public:
30 // Returns the row of the current entry.
31 RowIndex row() const { return index(); }
32
33 protected:
34 SparseColumnEntry(const RowIndex* indices, const Fractional* coefficients,
35 EntryIndex i)
36 : SparseVectorEntry<RowIndex>(indices, coefficients, i) {}
37};
39
40class ColumnView;
41
42// A SparseColumn is a SparseVector<RowIndex>, with a few methods renamed
43// to help readability on the client side.
44class SparseColumn : public SparseVector<RowIndex, SparseColumnIterator> {
45 friend class ColumnView;
46
47 public:
49
50 // Use a separate API to get the row and coefficient of entry #i.
51 RowIndex EntryRow(EntryIndex i) const { return GetIndex(i); }
52 Fractional EntryCoefficient(EntryIndex i) const { return GetCoefficient(i); }
53 RowIndex GetFirstRow() const { return GetFirstIndex(); }
54 RowIndex GetLastRow() const { return GetLastIndex(); }
57 }
60 }
61};
62
63// Class to iterate on the entries of a given column with the same interface
64// as for SparseColumn.
66 public:
67 // Clients should pass Entry by value rather than by reference.
68 // This is because SparseColumnEntry is small (2 pointers and an index) and
69 // previous profiling of this type of use showed no performance penalty
70 // (see cl/51057736).
71 // Example: for(const Entry e : column_view)
74
75 ColumnView(EntryIndex num_entries, const RowIndex* rows,
76 const Fractional* const coefficients)
77 : num_entries_(num_entries), rows_(rows), coefficients_(coefficients) {}
78 explicit ColumnView(const SparseColumn& column)
79 : num_entries_(column.num_entries()),
80 rows_(column.index_),
81 coefficients_(column.coefficient_) {}
82 EntryIndex num_entries() const { return num_entries_; }
83 Fractional EntryCoefficient(EntryIndex i) const {
84 return coefficients_[i.value()];
85 }
87 return EntryCoefficient(EntryIndex(0));
88 }
89 RowIndex EntryRow(EntryIndex i) const { return rows_[i.value()]; }
90 RowIndex GetFirstRow() const { return EntryRow(EntryIndex(0)); }
91
92 Iterator begin() const {
93 return Iterator(this->rows_, this->coefficients_, EntryIndex(0));
94 }
95
96 Iterator end() const {
97 return Iterator(this->rows_, this->coefficients_, num_entries_);
98 }
99
101 Fractional value(0.0);
102 for (const auto e : *this) {
103 if (e.row() == index) {
104 // Keep in mind the vector may contains several entries with the same
105 // index. In such a case the last one is returned.
106 // TODO(user): investigate whether an optimized version of
107 // LookUpCoefficient for "clean" columns yields speed-ups.
108 value = e.coefficient();
109 }
110 }
111 return value;
112 }
113
114 bool IsEmpty() const { return num_entries_ == EntryIndex(0); }
115
116 private:
117 const EntryIndex num_entries_;
118 const RowIndex* const rows_;
119 const Fractional* const coefficients_;
120};
121
122// --------------------------------------------------------
123// RandomAccessSparseColumn
124// --------------------------------------------------------
125// A RandomAccessSparseColumn is a mix between a DenseColumn and a SparseColumn.
126// It makes it possible to populate a dense column from a sparse column in
127// O(num_entries) instead of O(num_rows), and to access an entry in O(1).
128// As the constructor runs in O(num_rows), a RandomAccessSparseColumn should be
129// used several times to amortize the creation cost.
131 public:
132 // Creates a RandomAccessSparseColumn.
133 // Runs in O(num_rows).
134 explicit RandomAccessSparseColumn(RowIndex num_rows);
136
137 // Clears the column.
138 // Runs in O(num_entries).
139 void Clear();
140
141 void Resize(RowIndex num_rows);
142
143 // Sets value at row.
144 // Runs in O(1).
146 column_[row] = value;
147 MarkRowAsChanged(row);
148 }
149
150 // Adds value to the current value at row.
151 // Runs in O(1).
153 column_[row] += value;
154 MarkRowAsChanged(row);
155 }
156
157 // Populates from a sparse column.
158 // Runs in O(num_entries).
159 void PopulateFromSparseColumn(const SparseColumn& sparse_column);
160
161 // Populates a sparse column from the lazy dense column.
162 // Runs in O(num_entries).
163 void PopulateSparseColumn(SparseColumn* sparse_column) const;
164
165 // Returns the number of rows.
166 // Runs in O(1).
167 RowIndex GetNumberOfRows() const { return RowIndex(column_.size()); }
168
169 // Returns the value in position row.
170 // Runs in O(1).
171 Fractional GetCoefficient(RowIndex row) const { return column_[row]; }
172
173 private:
174 // Keeps a trace of which rows have been changed.
175 void MarkRowAsChanged(RowIndex row) {
176 if (!changed_[row]) {
177 changed_[row] = true;
178 row_change_.push_back(row);
179 }
180 }
181
182 // The dense version of the column.
183 DenseColumn column_;
184
185 // Dense Boolean vector used to mark changes.
186 DenseBooleanColumn changed_;
187
188 // Stack to store changes.
189 std::vector<RowIndex> row_change_;
190
191 DISALLOW_COPY_AND_ASSIGN(RandomAccessSparseColumn);
192};
193
194} // namespace glop
195} // namespace operations_research
196
197#endif // OR_TOOLS_LP_DATA_SPARSE_COLUMN_H_
ColumnView(EntryIndex num_entries, const RowIndex *rows, const Fractional *const coefficients)
Definition: sparse_column.h:75
Fractional LookUpCoefficient(RowIndex index) const
VectorIterator< Entry > Iterator
Definition: sparse_column.h:73
Fractional EntryCoefficient(EntryIndex i) const
Definition: sparse_column.h:83
ColumnView(const SparseColumn &column)
Definition: sparse_column.h:78
RowIndex EntryRow(EntryIndex i) const
Definition: sparse_column.h:89
void AddToCoefficient(RowIndex row, Fractional value)
void PopulateSparseColumn(SparseColumn *sparse_column) const
void PopulateFromSparseColumn(const SparseColumn &sparse_column)
void SetCoefficient(RowIndex row, Fractional value)
Definition: sparse_column.h:28
SparseColumnEntry(const RowIndex *indices, const Fractional *coefficients, EntryIndex i)
Definition: sparse_column.h:34
RowIndex row() const
Definition: sparse_column.h:31
void ApplyRowPermutation(const RowPermutation &p)
Definition: sparse_column.h:55
void ApplyPartialRowPermutation(const RowPermutation &p)
Definition: sparse_column.h:58
Fractional EntryCoefficient(EntryIndex i) const
Definition: sparse_column.h:52
RowIndex EntryRow(EntryIndex i) const
Definition: sparse_column.h:51
Index index() const
int64 value
RowIndex row
Definition: markowitz.cc:175
const RowIndex kNonPivotal(-1)
StrictITIVector< RowIndex, Fractional > DenseColumn
Definition: lp_types.h:328
StrictITIVector< RowIndex, bool > DenseBooleanColumn
Definition: lp_types.h:331
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