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 
19 namespace operations_research {
20 namespace glop {
21 
22 // TODO(user): Consider using kInvalidRow for this?
23 const 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.
28 class 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 
40 class ColumnView;
41 
42 // A SparseColumn is a SparseVector<RowIndex>, with a few methods renamed
43 // to help readability on the client side.
44 class 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.
65 class ColumnView {
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);
135  virtual ~RandomAccessSparseColumn();
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).
145  void SetCoefficient(RowIndex row, Fractional value) {
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