OR-Tools  8.1
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_
operations_research::glop::ColumnView::LookUpCoefficient
Fractional LookUpCoefficient(RowIndex index) const
Definition: sparse_column.h:100
operations_research::glop::SparseColumn::SparseColumn
SparseColumn()
Definition: sparse_column.h:48
operations_research::glop::RandomAccessSparseColumn::GetNumberOfRows
RowIndex GetNumberOfRows() const
Definition: sparse_column.h:167
coefficients
std::vector< double > coefficients
Definition: sat/lp_utils.cc:497
operations_research::glop::RandomAccessSparseColumn::Clear
void Clear()
Definition: sparse_column.cc:31
operations_research::glop::SparseColumnEntry
Definition: sparse_column.h:28
operations_research::glop::ColumnView::IsEmpty
bool IsEmpty() const
Definition: sparse_column.h:114
value
int64 value
Definition: demon_profiler.cc:43
operations_research::glop::DenseBooleanColumn
StrictITIVector< RowIndex, bool > DenseBooleanColumn
Definition: lp_types.h:331
operations_research::glop::RandomAccessSparseColumn::GetCoefficient
Fractional GetCoefficient(RowIndex row) const
Definition: sparse_column.h:171
operations_research::glop::SparseVector< RowIndex, SparseColumnIterator >::GetFirstIndex
Index GetFirstIndex() const
Definition: sparse_vector.h:279
operations_research::glop::RandomAccessSparseColumn::Resize
void Resize(RowIndex num_rows)
Definition: sparse_column.cc:41
operations_research::glop::StrictITIVector::size
IntType size() const
Definition: lp_types.h:276
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
operations_research::glop::RandomAccessSparseColumn::SetCoefficient
void SetCoefficient(RowIndex row, Fractional value)
Definition: sparse_column.h:145
operations_research::glop::SparseColumn
Definition: sparse_column.h:44
operations_research::glop::SparseColumn::ApplyPartialRowPermutation
void ApplyPartialRowPermutation(const RowPermutation &p)
Definition: sparse_column.h:58
operations_research::glop::SparseColumn::EntryRow
RowIndex EntryRow(EntryIndex i) const
Definition: sparse_column.h:51
operations_research::glop::RandomAccessSparseColumn::PopulateSparseColumn
void PopulateSparseColumn(SparseColumn *sparse_column) const
Definition: sparse_column.cc:57
index
int index
Definition: pack.cc:508
operations_research::glop::SparseVector< RowIndex, SparseColumnIterator >::ApplyIndexPermutation
void ApplyIndexPermutation(const IndexPermutation &index_perm)
Definition: sparse_vector.h:926
operations_research::glop::Fractional
double Fractional
Definition: lp_types.h:77
operations_research::glop::ColumnView::Iterator
VectorIterator< Entry > Iterator
Definition: sparse_column.h:73
operations_research::glop::ColumnView::GetFirstCoefficient
Fractional GetFirstCoefficient() const
Definition: sparse_column.h:86
operations_research::glop::ColumnView::ColumnView
ColumnView(const SparseColumn &column)
Definition: sparse_column.h:78
sparse_vector.h
operations_research::glop::ColumnView::begin
Iterator begin() const
Definition: sparse_column.h:92
operations_research::glop::ColumnView::GetFirstRow
RowIndex GetFirstRow() const
Definition: sparse_column.h:90
operations_research::glop::SparseColumn::EntryCoefficient
Fractional EntryCoefficient(EntryIndex i) const
Definition: sparse_column.h:52
operations_research::glop::kNonPivotal
const RowIndex kNonPivotal(-1)
operations_research::glop::SparseVector
Definition: sparse_vector.h:83
operations_research::glop::SparseVectorEntry< RowIndex >::index
Index index() const
Definition: sparse_vector.h:415
operations_research::glop::RandomAccessSparseColumn::PopulateFromSparseColumn
void PopulateFromSparseColumn(const SparseColumn &sparse_column)
Definition: sparse_column.cc:49
operations_research::glop::SparseVector< RowIndex, SparseColumnIterator >::GetIndex
Index GetIndex(EntryIndex i) const
Definition: sparse_vector.h:344
operations_research::glop::ColumnView::Entry
SparseColumnEntry Entry
Definition: sparse_column.h:72
operations_research::glop::RandomAccessSparseColumn::~RandomAccessSparseColumn
virtual ~RandomAccessSparseColumn()
Definition: sparse_column.cc:29
operations_research::glop::ColumnView::end
Iterator end() const
Definition: sparse_column.h:96
operations_research::glop::ColumnView::EntryRow
RowIndex EntryRow(EntryIndex i) const
Definition: sparse_column.h:89
operations_research::glop::Permutation< RowIndex >
operations_research::glop::SparseVectorEntry
Definition: sparse_vector.h:411
operations_research::glop::ColumnView::num_entries
EntryIndex num_entries() const
Definition: sparse_column.h:82
operations_research::glop::VectorIterator
Definition: lp_types.h:356
operations_research::glop::ColumnView::ColumnView
ColumnView(EntryIndex num_entries, const RowIndex *rows, const Fractional *const coefficients)
Definition: sparse_column.h:75
operations_research::glop::RandomAccessSparseColumn::RandomAccessSparseColumn
RandomAccessSparseColumn(RowIndex num_rows)
Definition: sparse_column.cc:26
operations_research::glop::SparseColumn::GetFirstRow
RowIndex GetFirstRow() const
Definition: sparse_column.h:53
row
RowIndex row
Definition: markowitz.cc:175
operations_research::glop::SparseColumn::GetLastRow
RowIndex GetLastRow() const
Definition: sparse_column.h:54
operations_research::glop::SparseVector< RowIndex, SparseColumnIterator >::GetLastIndex
Index GetLastIndex() const
Definition: sparse_vector.h:289
operations_research::glop::DenseColumn
StrictITIVector< RowIndex, Fractional > DenseColumn
Definition: lp_types.h:328
operations_research::glop::ColumnView
Definition: sparse_column.h:65
operations_research::glop::RandomAccessSparseColumn
Definition: sparse_column.h:130
operations_research::glop::SparseVector< RowIndex, SparseColumnIterator >::GetCoefficient
Fractional GetCoefficient(EntryIndex i) const
Definition: sparse_vector.h:349
operations_research::glop::SparseColumn::ApplyRowPermutation
void ApplyRowPermutation(const RowPermutation &p)
Definition: sparse_column.h:55
operations_research::glop::RandomAccessSparseColumn::AddToCoefficient
void AddToCoefficient(RowIndex row, Fractional value)
Definition: sparse_column.h:152
operations_research::glop::SparseColumnEntry::SparseColumnEntry
SparseColumnEntry(const RowIndex *indices, const Fractional *coefficients, EntryIndex i)
Definition: sparse_column.h:34
operations_research::glop::SparseColumnEntry::row
RowIndex row() const
Definition: sparse_column.h:31
operations_research::glop::SparseVector< RowIndex, SparseColumnIterator >::ApplyPartialIndexPermutation
void ApplyPartialIndexPermutation(const IndexPermutation &index_perm)
Definition: sparse_vector.h:934
operations_research::glop::ColumnView::EntryCoefficient
Fractional EntryCoefficient(EntryIndex i) const
Definition: sparse_column.h:83