OR-Tools  8.2
affine_relation.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_UTIL_AFFINE_RELATION_H_
15#define OR_TOOLS_UTIL_AFFINE_RELATION_H_
16
17#include <vector>
18
21#include "ortools/base/macros.h"
22
23namespace operations_research {
24
25// Union-Find algorithm to maintain "representative" for relations of the form:
26// x = coeff * y + offset, where "coeff" and "offset" are integers. The variable
27// x and y are represented by non-negative integer indices. The idea is to
28// express variables in affine relation using as little different variables as
29// possible (the representatives).
30//
31// IMPORTANT: If there are relations with std::abs(coeff) != 1, then some
32// relations might be ignored. See TryAdd() for more details.
33//
34// TODO(user): it might be possible to do something fancier and drop less
35// relations if all the affine relations are given before hand.
37 public:
38 AffineRelation() : num_relations_(0) {}
39
40 // Returns the number of relations added to the class and not ignored.
41 int NumRelations() const { return num_relations_; }
42
43 // Adds the relation x = coeff * y + offset to the class.
44 // Returns true if it wasn't ignored.
45 //
46 // This relation will only be taken into account if the representative of x
47 // and the one of y are different and if the relation can be transformed into
48 // a similar relation with integer coefficient between the two
49 // representatives.
50 //
51 // That is, given that:
52 // - x = coeff_x * representative_x + offset_x
53 // - y = coeff_y * representative_y + offset_y
54 // we have:
55 // coeff_x * representative_x + offset_x =
56 // coeff * coeff_y * representative_y + coeff * offset_y + offset.
57 // Which can be simplified with the introduction of new variables to:
58 // coeff_x * representative_x = new_coeff * representative_y + new_offset.
59 // And we can merge the two if:
60 // - new_coeff and new_offset are divisible by coeff_x.
61 // - OR coeff_x and new_offset are divisible by new_coeff.
62 //
63 // Checked preconditions: x >=0, y >= 0, coeff != 0 and x != y.
64 //
65 // IMPORTANT: we do not check for integer overflow, but that could be added
66 // if it is needed.
67 bool TryAdd(int x, int y, int64 coeff, int64 offset);
68
69 // Same as TryAdd() with the option to disallow the use of a given
70 // representative.
71 bool TryAdd(int x, int y, int64 coeff, int64 offset, bool allow_rep_x,
72 bool allow_rep_y);
73
74 // Returns a valid relation of the form x = coeff * representative + offset.
75 // Note that this can return x = x. Non-const because of path-compression.
76 struct Relation {
80 Relation(int r, int64 c, int64 o)
81 : representative(r), coeff(c), offset(o) {}
82 const bool operator==(const Relation& other) const {
83 return representative == other.representative && coeff == other.coeff &&
84 offset == other.offset;
85 }
86 };
87 Relation Get(int x) const;
88
89 // Advanced usage. This is a bit hacky and will just decrease the class size
90 // of a variable without any extra checks. Use with care. In particular when
91 // this is called, then x should never be used anymore in any of the non const
92 // calls of this class.
93 void IgnoreFromClassSize(int x) {
94 if (x >= size_.size()) return; // never seen here.
95 CHECK_NE(size_[x], kSizeForRemovedEntry) << x;
96 const int r = Get(x).representative;
97 if (r != x) {
98 CHECK_GT(size_[r], 1);
99 size_[r]--;
100 } else {
101 CHECK_EQ(size_[r], 1);
102 }
103 size_[x] = kSizeForRemovedEntry;
104 }
105
106 // Returns the size of the class of x.
107 int ClassSize(int x) const {
108 if (x >= representative_.size()) return 1;
109 return size_[Get(x).representative];
110 }
111
112 private:
113 const int kSizeForRemovedEntry = 0;
114
115 void IncreaseSizeOfMemberVectors(int new_size) {
116 if (new_size <= representative_.size()) return;
117 for (int i = representative_.size(); i < new_size; ++i) {
118 representative_.push_back(i);
119 }
120 offset_.resize(new_size, 0);
121 coeff_.resize(new_size, 1);
122 size_.resize(new_size, 1);
123 }
124
125 void CompressPath(int x) const {
126 DCHECK_GE(x, 0);
127 DCHECK_LT(x, representative_.size());
128 tmp_path_.clear();
129 int parent = x;
130 while (parent != representative_[parent]) {
131 tmp_path_.push_back(parent);
132 parent = representative_[parent];
133 }
134 for (const int var : ::gtl::reversed_view(tmp_path_)) {
135 const int old_parent = representative_[var];
136 offset_[var] += coeff_[var] * offset_[old_parent];
137 coeff_[var] *= coeff_[old_parent];
138 representative_[var] = parent;
139 }
140 }
141
142 int num_relations_;
143
144 // The equivalence class representative for each variable index.
145 mutable std::vector<int> representative_;
146
147 // The offset and coefficient such that
148 // variable[index] = coeff * variable[representative_[index]] + offset;
149 mutable std::vector<int64> coeff_;
150 mutable std::vector<int64> offset_;
151
152 // The size of each representative "tree", used to get a good complexity when
153 // we have the choice of which tree to merge into the other.
154 //
155 // TODO(user): Using a "rank" might be faster, but because we sometimes
156 // need to merge the bad subtree into the better one, it is trickier to
157 // maintain than in the classic union-find algorihtm.
158 std::vector<int> size_;
159
160 // Used by CompressPath() to maintain the coeff/offset during compression.
161 mutable std::vector<int> tmp_path_;
162};
163
164inline bool AffineRelation::TryAdd(int x, int y, int64 coeff, int64 offset) {
165 return TryAdd(x, y, coeff, offset, true, true);
166}
167
168inline bool AffineRelation::TryAdd(int x, int y, int64 coeff, int64 offset,
169 bool allow_rep_x, bool allow_rep_y) {
170 CHECK_NE(coeff, 0);
171 CHECK_NE(x, y);
172 CHECK_GE(x, 0);
173 CHECK_GE(y, 0);
174 IncreaseSizeOfMemberVectors(std::max(x, y) + 1);
175 CHECK_NE(size_[x], kSizeForRemovedEntry) << x;
176 CHECK_NE(size_[y], kSizeForRemovedEntry) << y;
177 CompressPath(x);
178 CompressPath(y);
179 const int rep_x = representative_[x];
180 const int rep_y = representative_[y];
181 if (rep_x == rep_y) return false;
182
183 // TODO(user): It should be possible to optimize this code block a bit, for
184 // instance depending on the magnitude of new_coeff vs coeff_x, we may already
185 // know that one of the two merge is not possible.
186 const int64 coeff_x = coeff_[x];
187 const int64 new_coeff = coeff * coeff_[y];
188 const int64 new_offset = coeff * offset_[y] + offset - offset_[x];
189 const bool condition1 =
190 allow_rep_y && (new_coeff % coeff_x == 0) && (new_offset % coeff_x == 0);
191 const bool condition2 = allow_rep_x && (coeff_x % new_coeff == 0) &&
192 (new_offset % new_coeff == 0);
193 if (condition1 && (!condition2 || size_[x] <= size_[y])) {
194 representative_[rep_x] = rep_y;
195 size_[rep_y] += size_[rep_x];
196 coeff_[rep_x] = new_coeff / coeff_x;
197 offset_[rep_x] = new_offset / coeff_x;
198 } else if (condition2) {
199 representative_[rep_y] = rep_x;
200 size_[rep_x] += size_[rep_y];
201 coeff_[rep_y] = coeff_x / new_coeff;
202 offset_[rep_y] = -new_offset / new_coeff;
203 } else {
204 return false;
205 }
206 ++num_relations_;
207 return true;
208}
209
211 if (x >= representative_.size() || representative_[x] == x) return {x, 1, 0};
212 CompressPath(x);
213 return {representative_[x], coeff_[x], offset_[x]};
214}
215
216} // namespace operations_research
217
218#endif // OR_TOOLS_UTIL_AFFINE_RELATION_H_
int64 max
Definition: alldiff_cst.cc:139
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define CHECK_NE(val1, val2)
Definition: base/logging.h:698
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
bool TryAdd(int x, int y, int64 coeff, int64 offset)
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
ReverseView< Container > reversed_view(const Container &c)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
const bool operator==(const Relation &other) const