OR-Tools  8.2
graph_constraints.cc
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#include <algorithm>
15#include <deque>
16#include <memory>
17#include <string>
18#include <utility>
19#include <vector>
20
21#include "absl/container/flat_hash_set.h"
22#include "absl/strings/str_cat.h"
23#include "absl/strings/str_format.h"
24#include "absl/strings/str_join.h"
31
32namespace operations_research {
33// ---------- No cycle ----------
34
35// This constraint ensures there are no cycles in the variable/value graph.
36// "Sink" values are values outside the range of the array of variables; they
37// are used to end paths.
38// The constraint does essentially two things:
39// - forbid partial paths from looping back to themselves
40// - ensure each variable/node can be connected to a "sink".
41// If assume_paths is true, the constraint assumes the 'next' variables
42// represent paths (and performs a faster propagation); otherwise the
43// constraint assumes the 'next' variables represent a forest.
44// TODO(user): improve code when assume_paths is false (currently does an
45// expensive n^2 loop).
46
47namespace {
48class NoCycle : public Constraint {
49 public:
50 NoCycle(Solver* const s, const std::vector<IntVar*>& nexts,
51 const std::vector<IntVar*>& active, Solver::IndexFilter1 sink_handler,
52 bool assume_paths);
53 ~NoCycle() override {}
54 void Post() override;
55 void InitialPropagate() override;
56 void NextChange(int index);
57 void ActiveBound(int index);
58 void NextBound(int index);
59 void ComputeSupports();
60 void ComputeSupport(int index);
61 std::string DebugString() const override;
62
63 void Accept(ModelVisitor* const visitor) const override {
64 visitor->BeginVisitConstraint(ModelVisitor::kNoCycle, this);
65 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,
66 nexts_);
67 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kActiveArgument,
68 active_);
69 visitor->VisitIntegerArgument("assume_paths", assume_paths_);
70 visitor->VisitInt64ToBoolExtension(sink_handler_, -size(), size());
71 visitor->EndVisitConstraint(ModelVisitor::kNoCycle, this);
72 }
73
74 private:
75 int64 size() const { return nexts_.size(); }
76
77 const std::vector<IntVar*> nexts_;
78 const std::vector<IntVar*> active_;
79 std::vector<IntVarIterator*> iterators_;
80 RevArray<int64> starts_;
81 RevArray<int64> ends_;
82 RevArray<bool> marked_;
83 bool all_nexts_bound_;
84 std::vector<int64> outbound_supports_;
85 std::vector<int64> support_leaves_;
86 std::vector<int64> unsupported_;
87 Solver::IndexFilter1 sink_handler_;
88 std::vector<int64> sinks_;
89 bool assume_paths_;
90};
91
92NoCycle::NoCycle(Solver* const s, const std::vector<IntVar*>& nexts,
93 const std::vector<IntVar*>& active,
94 Solver::IndexFilter1 sink_handler, bool assume_paths)
95 : Constraint(s),
96 nexts_(nexts),
97 active_(active),
98 iterators_(nexts.size(), nullptr),
99 starts_(nexts.size(), -1),
100 ends_(nexts.size(), -1),
101 marked_(nexts.size(), false),
102 all_nexts_bound_(false),
103 outbound_supports_(nexts.size(), -1),
104 sink_handler_(std::move(sink_handler)),
105 assume_paths_(assume_paths) {
106 support_leaves_.reserve(size());
107 unsupported_.reserve(size());
108 for (int i = 0; i < size(); ++i) {
109 starts_.SetValue(s, i, i);
110 ends_.SetValue(s, i, i);
111 iterators_[i] = nexts_[i]->MakeDomainIterator(true);
112 }
113}
114
115void NoCycle::InitialPropagate() {
116 // Reduce next domains to sinks + range of nexts
117 for (int i = 0; i < size(); ++i) {
118 outbound_supports_[i] = -1;
119 IntVar* next = nexts_[i];
120 for (int j = next->Min(); j < 0; ++j) {
121 if (!sink_handler_(j)) {
122 next->RemoveValue(j);
123 }
124 }
125 for (int j = next->Max(); j >= size(); --j) {
126 if (!sink_handler_(j)) {
127 next->RemoveValue(j);
128 }
129 }
130 }
131 solver()->SaveAndSetValue(&all_nexts_bound_, true);
132 for (int i = 0; i < size(); ++i) {
133 if (nexts_[i]->Bound()) {
134 NextBound(i);
135 } else {
136 solver()->SaveAndSetValue(&all_nexts_bound_, false);
137 }
138 }
139 ComputeSupports();
140}
141
142void NoCycle::Post() {
143 if (size() == 0) return;
144 for (int i = 0; i < size(); ++i) {
145 IntVar* next = nexts_[i];
146 Demon* support_demon = MakeConstraintDemon1(
147 solver(), this, &NoCycle::NextChange, "NextChange", i);
148 next->WhenDomain(support_demon);
149 Demon* active_demon = MakeConstraintDemon1(
150 solver(), this, &NoCycle::ActiveBound, "ActiveBound", i);
151 active_[i]->WhenBound(active_demon);
152 }
153 // Setting up sinks
154 int64 min_min = nexts_[0]->Min();
155 int64 max_max = nexts_[0]->Max();
156 for (int i = 1; i < size(); ++i) {
157 const IntVar* next = nexts_[i];
158 min_min = std::min(min_min, next->Min());
159 max_max = std::max(max_max, next->Max());
160 }
161 sinks_.clear();
162 for (int i = min_min; i <= max_max; ++i) {
163 if (sink_handler_(i)) {
164 sinks_.push_back(i);
165 }
166 }
167}
168
169void NoCycle::NextChange(int index) {
170 IntVar* const next_var = nexts_[index];
171 if (next_var->Bound()) {
172 NextBound(index);
173 }
174 if (!all_nexts_bound_) {
175 bool all_nexts_bound = true;
176 for (int i = 0; i < size(); ++i) {
177 if (!nexts_[i]->Bound()) {
178 all_nexts_bound = false;
179 break;
180 }
181 }
182 solver()->SaveAndSetValue(&all_nexts_bound_, all_nexts_bound);
183 }
184 if (all_nexts_bound_) {
185 return;
186 }
187 if (!next_var->Contains(outbound_supports_[index])) {
188 ComputeSupport(index);
189 }
190}
191
192void NoCycle::ActiveBound(int index) {
193 if (nexts_[index]->Bound()) {
194 NextBound(index);
195 }
196}
197
198void NoCycle::NextBound(int index) {
199 if (active_[index]->Min() == 0) return;
200 if (marked_[index]) return;
201 Solver* const s = solver();
202 // Subtle: marking indices to avoid overwriting chain starts and ends if
203 // propagation for active_[index] or nexts_[index] has already been done.
204 marked_.SetValue(s, index, true);
205 const int64 next = nexts_[index]->Value();
206 const int64 chain_start = starts_[index];
207 const int64 chain_end = !sink_handler_(next) ? ends_[next] : next;
208 if (!sink_handler_(chain_start)) {
209 ends_.SetValue(s, chain_start, chain_end);
210 if (!sink_handler_(chain_end)) {
211 starts_.SetValue(s, chain_end, chain_start);
212 nexts_[chain_end]->RemoveValue(chain_start);
213 if (!assume_paths_) {
214 for (int i = 0; i < size(); ++i) {
215 int64 current = i;
216 bool found = (current == chain_end);
217 // Counter to detect implicit cycles.
218 int count = 0;
219 while (!found && count < size() && !sink_handler_(current) &&
220 nexts_[current]->Bound()) {
221 current = nexts_[current]->Value();
222 found = (current == chain_end);
223 ++count;
224 }
225 if (found) {
226 nexts_[chain_end]->RemoveValue(i);
227 }
228 }
229 }
230 }
231 }
232}
233
234// Compute the support tree. For each variable, find a path connecting to a
235// sink. Starts partial paths from the sinks down to all unconnected variables.
236// If some variables remain unconnected, make the corresponding active_
237// variable false.
238// Resulting tree is used as supports for next variables.
239// TODO(user): Try to see if we can find an algorithm which is less than
240// quadratic to do this (note that if the tree is flat we are already linear
241// for a given number of sinks).
242void NoCycle::ComputeSupports() {
243 // unsupported_ contains nodes not connected to sinks.
244 unsupported_.clear();
245 // supported_leaves_ contains the current frontier containing nodes surely
246 // connected to sinks.
247 support_leaves_.clear();
248 // Initial phase: find direct connections to sinks and initialize
249 // support_leaves_ and unsupported_ accordingly.
250 const int sink_size = sinks_.size();
251 for (int i = 0; i < size(); ++i) {
252 const IntVar* next = nexts_[i];
253 // If node is not active, no need to try to connect it to a sink.
254 if (active_[i]->Max() != 0) {
255 const int64 current_support = outbound_supports_[i];
256 // Optimization: if this node was already supported by a sink, check if
257 // it's still a valid support.
258 if (current_support >= 0 && sink_handler_(current_support) &&
259 next->Contains(current_support)) {
260 support_leaves_.push_back(i);
261 } else {
262 // Optimization: iterate on sinks or next domain depending on which is
263 // smaller.
264 outbound_supports_[i] = -1;
265 if (sink_size < next->Size()) {
266 for (int j = 0; j < sink_size; ++j) {
267 if (next->Contains(sinks_[j])) {
268 outbound_supports_[i] = sinks_[j];
269 support_leaves_.push_back(i);
270 break;
271 }
272 }
273 } else {
274 for (const int64 value : InitAndGetValues(iterators_[i])) {
275 if (sink_handler_(value)) {
276 outbound_supports_[i] = value;
277 support_leaves_.push_back(i);
278 break;
279 }
280 }
281 }
282 }
283 if (outbound_supports_[i] == -1) {
284 unsupported_.push_back(i);
285 }
286 }
287 }
288 // No need to iterate on all nodes connected to sinks but just on the ones
289 // added in the last iteration; leaves_begin and leaves_end mark the block
290 // in support_leaves_ corresponding to such nodes.
291 size_t leaves_begin = 0;
292 size_t leaves_end = support_leaves_.size();
293 while (!unsupported_.empty()) {
294 // Try to connected unsupported nodes to nodes connected to sinks.
295 for (int64 unsupported_index = 0; unsupported_index < unsupported_.size();
296 ++unsupported_index) {
297 const int64 unsupported = unsupported_[unsupported_index];
298 const IntVar* const next = nexts_[unsupported];
299 for (int i = leaves_begin; i < leaves_end; ++i) {
300 if (next->Contains(support_leaves_[i])) {
301 outbound_supports_[unsupported] = support_leaves_[i];
302 support_leaves_.push_back(unsupported);
303 // Remove current node from unsupported vector.
304 unsupported_[unsupported_index] = unsupported_.back();
305 unsupported_.pop_back();
306 --unsupported_index;
307 break;
308 }
309 // TODO(user): evaluate same trick as with the sinks by keeping a
310 // bitmap with supported nodes.
311 }
312 }
313 // No new leaves were added, we can bail out.
314 if (leaves_end == support_leaves_.size()) {
315 break;
316 }
317 leaves_begin = leaves_end;
318 leaves_end = support_leaves_.size();
319 }
320 // Mark as inactive any unsupported node.
321 for (int64 unsupported_index = 0; unsupported_index < unsupported_.size();
322 ++unsupported_index) {
323 active_[unsupported_[unsupported_index]]->SetMax(0);
324 }
325}
326
327void NoCycle::ComputeSupport(int index) {
328 // Try to reconnect the node to the support tree by finding a next node
329 // which is both supported and was not a descendant of the node in the tree.
330 if (active_[index]->Max() != 0) {
331 for (const int64 next : InitAndGetValues(iterators_[index])) {
332 if (sink_handler_(next)) {
333 outbound_supports_[index] = next;
334 return;
335 }
336 if (next != index && next < outbound_supports_.size()) {
337 int64 next_support = outbound_supports_[next];
338 if (next_support >= 0) {
339 // Check if next is not already a descendant of index.
340 bool ancestor_found = false;
341 while (next_support < outbound_supports_.size() &&
342 !sink_handler_(next_support)) {
343 if (next_support == index) {
344 ancestor_found = true;
345 break;
346 }
347 next_support = outbound_supports_[next_support];
348 }
349 if (!ancestor_found) {
350 outbound_supports_[index] = next;
351 return;
352 }
353 }
354 }
355 }
356 }
357 // No support was found, rebuild the support tree.
358 ComputeSupports();
359}
360
361std::string NoCycle::DebugString() const {
362 return absl::StrFormat("NoCycle(%s)", JoinDebugStringPtr(nexts_, ", "));
363}
364
365// ----- Circuit constraint -----
366
367class Circuit : public Constraint {
368 public:
369 Circuit(Solver* const s, const std::vector<IntVar*>& nexts, bool sub_circuit)
370 : Constraint(s),
371 nexts_(nexts),
372 size_(nexts_.size()),
373 starts_(size_, -1),
374 ends_(size_, -1),
375 lengths_(size_, 1),
376 domains_(size_),
377 outbound_support_(size_, -1),
378 inbound_support_(size_, -1),
379 temp_support_(size_, -1),
380 inbound_demon_(nullptr),
381 outbound_demon_(nullptr),
382 root_(-1),
383 num_inactives_(0),
384 sub_circuit_(sub_circuit) {
385 for (int i = 0; i < size_; ++i) {
386 domains_[i] = nexts_[i]->MakeDomainIterator(true);
387 }
388 }
389
390 ~Circuit() override {}
391
392 void Post() override {
393 inbound_demon_ = MakeDelayedConstraintDemon0(
394 solver(), this, &Circuit::CheckReachabilityToRoot,
395 "CheckReachabilityToRoot");
396 outbound_demon_ = MakeDelayedConstraintDemon0(
397 solver(), this, &Circuit::CheckReachabilityFromRoot,
398 "CheckReachabilityFromRoot");
399 for (int i = 0; i < size_; ++i) {
400 if (!nexts_[i]->Bound()) {
401 Demon* const bound_demon = MakeConstraintDemon1(
402 solver(), this, &Circuit::NextBound, "NextBound", i);
403 nexts_[i]->WhenBound(bound_demon);
404 Demon* const domain_demon = MakeConstraintDemon1(
405 solver(), this, &Circuit::NextDomain, "NextDomain", i);
406 nexts_[i]->WhenDomain(domain_demon);
407 }
408 }
409 solver()->AddConstraint(solver()->MakeAllDifferent(nexts_));
410 }
411
412 void InitialPropagate() override {
413 Solver* const s = solver();
414 if (!sub_circuit_) {
415 root_.SetValue(solver(), 0);
416 }
417 for (int i = 0; i < size_; ++i) {
418 nexts_[i]->SetRange(0, size_ - 1);
419 if (!sub_circuit_) {
420 nexts_[i]->RemoveValue(i);
421 }
422 }
423 for (int i = 0; i < size_; ++i) {
424 starts_.SetValue(s, i, i);
425 ends_.SetValue(s, i, i);
426 lengths_.SetValue(s, i, 1);
427 }
428 for (int i = 0; i < size_; ++i) {
429 if (nexts_[i]->Bound()) {
430 NextBound(i);
431 }
432 }
433 CheckReachabilityFromRoot();
434 CheckReachabilityToRoot();
435 }
436
437 std::string DebugString() const override {
438 return absl::StrFormat("%sCircuit(%s)", sub_circuit_ ? "Sub" : "",
439 JoinDebugStringPtr(nexts_, " "));
440 }
441
442 void Accept(ModelVisitor* const visitor) const override {
443 visitor->BeginVisitConstraint(ModelVisitor::kCircuit, this);
444 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,
445 nexts_);
446 visitor->VisitIntegerArgument(ModelVisitor::kPartialArgument, sub_circuit_);
447 visitor->EndVisitConstraint(ModelVisitor::kCircuit, this);
448 }
449
450 private:
451 bool Inactive(int index) const {
452 return nexts_[index]->Bound() && nexts_[index]->Min() == index;
453 }
454
455 void NextBound(int index) {
456 Solver* const s = solver();
457 const int destination = nexts_[index]->Value();
458 const int root = root_.Value();
459 if (destination != index) {
460 if (root == -1) {
461 root_.SetValue(s, index);
462 }
463 const int new_end = ends_.Value(destination);
464 const int new_start = starts_.Value(index);
465 starts_.SetValue(s, new_end, new_start);
466 ends_.SetValue(s, new_start, new_end);
467 lengths_.SetValue(
468 s, new_start,
469 lengths_.Value(new_start) + lengths_.Value(destination));
470 if (sub_circuit_) {
471 // You are creating the only path. Nexts can no longer loop upon itself.
472 nexts_[destination]->RemoveValue(destination);
473 } else {
474 if (lengths_.Value(new_start) < size_ - 1 - num_inactives_.Value()) {
475 nexts_[new_end]->RemoveValue(new_start);
476 }
477 }
478 } else {
479 num_inactives_.Incr(solver());
480 }
481 // TODO(user): You might get more propagation if you maintain
482 // num_undecided_actives_;
483 // then
484 // if (num_undecided_actives_ == 0 &&
485 // lengths_.Value(new_start) < size_ - 1 - num_inactives_.Value()) {
486 // nexts_[new_end]->RemoveValue(new_start);
487 // }
488 // for both complete == true and false.
489 }
490
491 void NextDomain(int index) {
492 if (root_.Value() == -1) {
493 return;
494 }
495 if (!nexts_[index]->Contains(outbound_support_[index])) {
496 EnqueueDelayedDemon(outbound_demon_);
497 }
498 if (!nexts_[index]->Contains(inbound_support_[index])) {
499 EnqueueDelayedDemon(inbound_demon_);
500 }
501 }
502
503 void TryInsertReached(int candidate, int64 after) {
504 if (!reached_[after]) {
505 reached_[after] = true;
506 insertion_queue_.push_back(after);
507 temp_support_[candidate] = after;
508 }
509 }
510
511 void CheckReachabilityFromRoot() {
512 if (root_.Value() == -1) { // Root is not yet defined. Nothing to deduce.
513 return;
514 }
515
516 // Assign temp_support_ to a dummy value.
517 temp_support_.assign(size_, -1);
518 // Clear the spanning tree.
519 int processed = 0;
520 reached_.assign(size_, false);
521 insertion_queue_.clear();
522 // Add the root node.
523 const int root_value = root_.Value();
524 reached_[root_value] = true;
525 insertion_queue_.push_back(root_value);
526 // Compute reachable nodes.
527 while (processed < insertion_queue_.size() &&
528 insertion_queue_.size() + num_inactives_.Value() < size_) {
529 const int candidate = insertion_queue_[processed++];
530 IntVar* const var = nexts_[candidate];
531 switch (var->Size()) {
532 case 1: {
533 TryInsertReached(candidate, var->Min());
534 break;
535 }
536 case 2: {
537 TryInsertReached(candidate, var->Min());
538 TryInsertReached(candidate, var->Max());
539 break;
540 }
541 default: {
542 IntVarIterator* const domain = domains_[candidate];
543 for (const int64 value : InitAndGetValues(domain)) {
544 TryInsertReached(candidate, value);
545 }
546 }
547 }
548 }
549 // All non reachable nodes should point to themselves in the incomplete
550 // case
551 for (int i = 0; i < size_; ++i) {
552 if (!reached_[i]) {
553 nexts_[i]->SetValue(i);
554 }
555 }
556 // Update the outbound_support_ vector.
557 outbound_support_.swap(temp_support_);
558 }
559
560 void CheckReachabilityToRoot() {
561 // TODO(user): Improve with prev_ data structure.
562 if (root_.Value() == -1) {
563 return;
564 }
565
566 insertion_queue_.clear();
567 insertion_queue_.push_back(root_.Value());
568 temp_support_[root_.Value()] = nexts_[root_.Value()]->Min();
569 int processed = 0;
570 to_visit_.clear();
571 for (int i = 0; i < size_; ++i) {
572 if (!Inactive(i) && i != root_.Value()) {
573 to_visit_.push_back(i);
574 }
575 }
576 const int inactive = num_inactives_.Value();
577 while (processed < insertion_queue_.size() &&
578 insertion_queue_.size() + inactive < size_) {
579 const int inserted = insertion_queue_[processed++];
580 std::vector<int> rejected;
581 for (int index = 0; index < to_visit_.size(); ++index) {
582 const int candidate = to_visit_[index];
583 if (nexts_[candidate]->Contains(inserted)) {
584 insertion_queue_.push_back(candidate);
585 temp_support_[candidate] = inserted;
586 } else {
587 rejected.push_back(candidate);
588 }
589 }
590 to_visit_.swap(rejected);
591 }
592 for (int i = 0; i < to_visit_.size(); ++i) {
593 const int node = to_visit_[i];
594 nexts_[node]->SetValue(node);
595 }
596 temp_support_.swap(inbound_support_);
597 }
598
599 const std::vector<IntVar*> nexts_;
600 const int size_;
601 std::vector<int> insertion_queue_;
602 std::vector<int> to_visit_;
603 std::vector<bool> reached_;
604 RevArray<int> starts_;
605 RevArray<int> ends_;
606 RevArray<int> lengths_;
607 std::vector<IntVarIterator*> domains_;
608 std::vector<int> outbound_support_;
609 std::vector<int> inbound_support_;
610 std::vector<int> temp_support_;
611 Demon* inbound_demon_;
612 Demon* outbound_demon_;
613 Rev<int> root_;
614 NumericalRev<int> num_inactives_;
615 const bool sub_circuit_;
616};
617} // namespace
618
619Constraint* Solver::MakeNoCycle(const std::vector<IntVar*>& nexts,
620 const std::vector<IntVar*>& active,
621 Solver::IndexFilter1 sink_handler,
622 bool assume_paths) {
623 CHECK_EQ(nexts.size(), active.size());
624 if (sink_handler == nullptr) {
625 const int64 size = nexts.size();
626 sink_handler = [size](int64 index) { return index >= size; };
627 }
628 return RevAlloc(new NoCycle(this, nexts, active, sink_handler, assume_paths));
629}
630
631Constraint* Solver::MakeNoCycle(const std::vector<IntVar*>& nexts,
632 const std::vector<IntVar*>& active,
633 Solver::IndexFilter1 sink_handler) {
634 return MakeNoCycle(nexts, active, std::move(sink_handler), true);
635}
636
637// TODO(user): Merge NoCycle and Circuit.
638Constraint* Solver::MakeCircuit(const std::vector<IntVar*>& nexts) {
639 return RevAlloc(new Circuit(this, nexts, false));
640}
641
642Constraint* Solver::MakeSubCircuit(const std::vector<IntVar*>& nexts) {
643 return RevAlloc(new Circuit(this, nexts, true));
644}
645
646// ----- Path cumul constraints -----
647
648namespace {
649class BasePathCumul : public Constraint {
650 public:
651 BasePathCumul(Solver* const s, const std::vector<IntVar*>& nexts,
652 const std::vector<IntVar*>& active,
653 const std::vector<IntVar*>& cumuls);
654 ~BasePathCumul() override {}
655 void Post() override;
656 void InitialPropagate() override;
657 void ActiveBound(int index);
658 virtual void NextBound(int index) = 0;
659 virtual bool AcceptLink(int i, int j) const = 0;
660 void UpdateSupport(int index);
661 void CumulRange(int index);
662 std::string DebugString() const override;
663
664 protected:
665 int64 size() const { return nexts_.size(); }
666 int cumul_size() const { return cumuls_.size(); }
667
668 const std::vector<IntVar*> nexts_;
669 const std::vector<IntVar*> active_;
670 const std::vector<IntVar*> cumuls_;
671 RevArray<int> prevs_;
672 std::vector<int> supports_;
673};
674
675BasePathCumul::BasePathCumul(Solver* const s, const std::vector<IntVar*>& nexts,
676 const std::vector<IntVar*>& active,
677 const std::vector<IntVar*>& cumuls)
678 : Constraint(s),
679 nexts_(nexts),
680 active_(active),
681 cumuls_(cumuls),
682 prevs_(cumuls.size(), -1),
683 supports_(nexts.size()) {
684 CHECK_GE(cumul_size(), size());
685 for (int i = 0; i < size(); ++i) {
686 supports_[i] = -1;
687 }
688}
689
690void BasePathCumul::InitialPropagate() {
691 for (int i = 0; i < size(); ++i) {
692 if (nexts_[i]->Bound()) {
693 NextBound(i);
694 } else {
695 UpdateSupport(i);
696 }
697 }
698}
699
700void BasePathCumul::Post() {
701 for (int i = 0; i < size(); ++i) {
702 IntVar* var = nexts_[i];
703 Demon* d = MakeConstraintDemon1(solver(), this, &BasePathCumul::NextBound,
704 "NextBound", i);
705 var->WhenBound(d);
706 Demon* ds = MakeConstraintDemon1(
707 solver(), this, &BasePathCumul::UpdateSupport, "UpdateSupport", i);
708 var->WhenDomain(ds);
709 Demon* active_demon = MakeConstraintDemon1(
710 solver(), this, &BasePathCumul::ActiveBound, "ActiveBound", i);
711 active_[i]->WhenBound(active_demon);
712 }
713 for (int i = 0; i < cumul_size(); ++i) {
714 IntVar* cumul = cumuls_[i];
715 Demon* d = MakeConstraintDemon1(solver(), this, &BasePathCumul::CumulRange,
716 "CumulRange", i);
717 cumul->WhenRange(d);
718 }
719}
720
721void BasePathCumul::ActiveBound(int index) {
722 if (nexts_[index]->Bound()) {
723 NextBound(index);
724 }
725}
726
727void BasePathCumul::CumulRange(int index) {
728 if (index < size()) {
729 if (nexts_[index]->Bound()) {
730 NextBound(index);
731 } else {
732 UpdateSupport(index);
733 }
734 }
735 if (prevs_[index] >= 0) {
736 NextBound(prevs_[index]);
737 } else {
738 for (int i = 0; i < size(); ++i) {
739 if (index == supports_[i]) {
740 UpdateSupport(i);
741 }
742 }
743 }
744}
745
746void BasePathCumul::UpdateSupport(int index) {
747 int support = supports_[index];
748 if (support < 0 || !AcceptLink(index, support)) {
749 IntVar* var = nexts_[index];
750 for (int i = var->Min(); i <= var->Max(); ++i) {
751 if (i != support && AcceptLink(index, i)) {
752 supports_[index] = i;
753 return;
754 }
755 }
756 active_[index]->SetMax(0);
757 }
758}
759
760std::string BasePathCumul::DebugString() const {
761 std::string out = "PathCumul(";
762 for (int i = 0; i < size(); ++i) {
763 out += nexts_[i]->DebugString() + " " + cumuls_[i]->DebugString();
764 }
765 out += ")";
766 return out;
767}
768
769// cumuls[next[i]] = cumuls[i] + transits[i]
770
771class PathCumul : public BasePathCumul {
772 public:
773 PathCumul(Solver* const s, const std::vector<IntVar*>& nexts,
774 const std::vector<IntVar*>& active,
775 const std::vector<IntVar*>& cumuls,
776 const std::vector<IntVar*>& transits)
777 : BasePathCumul(s, nexts, active, cumuls), transits_(transits) {}
778 ~PathCumul() override {}
779 void Post() override;
780 void NextBound(int index) override;
781 bool AcceptLink(int i, int j) const override;
782 void TransitRange(int index);
783
784 void Accept(ModelVisitor* const visitor) const override {
785 visitor->BeginVisitConstraint(ModelVisitor::kPathCumul, this);
786 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,
787 nexts_);
788 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kActiveArgument,
789 active_);
790 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCumulsArgument,
791 cumuls_);
792 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kTransitsArgument,
793 transits_);
794 visitor->EndVisitConstraint(ModelVisitor::kPathCumul, this);
795 }
796
797 private:
798 const std::vector<IntVar*> transits_;
799};
800
801void PathCumul::Post() {
802 BasePathCumul::Post();
803 for (int i = 0; i < size(); ++i) {
804 Demon* transit_demon = MakeConstraintDemon1(
805 solver(), this, &PathCumul::TransitRange, "TransitRange", i);
806 transits_[i]->WhenRange(transit_demon);
807 }
808}
809
810void PathCumul::NextBound(int index) {
811 if (active_[index]->Min() == 0) return;
812 const int64 next = nexts_[index]->Value();
813 IntVar* cumul = cumuls_[index];
814 IntVar* cumul_next = cumuls_[next];
815 IntVar* transit = transits_[index];
816 cumul_next->SetMin(cumul->Min() + transit->Min());
817 cumul_next->SetMax(CapAdd(cumul->Max(), transit->Max()));
818 cumul->SetMin(CapSub(cumul_next->Min(), transit->Max()));
819 cumul->SetMax(CapSub(cumul_next->Max(), transit->Min()));
820 transit->SetMin(CapSub(cumul_next->Min(), cumul->Max()));
821 transit->SetMax(CapSub(cumul_next->Max(), cumul->Min()));
822 if (prevs_[next] < 0) {
823 prevs_.SetValue(solver(), next, index);
824 }
825}
826
827void PathCumul::TransitRange(int index) {
828 if (nexts_[index]->Bound()) {
829 NextBound(index);
830 } else {
831 UpdateSupport(index);
832 }
833 if (prevs_[index] >= 0) {
834 NextBound(prevs_[index]);
835 } else {
836 for (int i = 0; i < size(); ++i) {
837 if (index == supports_[i]) {
838 UpdateSupport(i);
839 }
840 }
841 }
842}
843
844bool PathCumul::AcceptLink(int i, int j) const {
845 const IntVar* const cumul_i = cumuls_[i];
846 const IntVar* const cumul_j = cumuls_[j];
847 const IntVar* const transit_i = transits_[i];
848 return transit_i->Min() <= CapSub(cumul_j->Max(), cumul_i->Min()) &&
849 CapSub(cumul_j->Min(), cumul_i->Max()) <= transit_i->Max();
850}
851
852namespace {
853template <class T>
854class StampedVector {
855 public:
856 StampedVector() : stamp_(0) {}
857 const std::vector<T>& Values(Solver* solver) {
858 CheckStamp(solver);
859 return values_;
860 }
861 void PushBack(Solver* solver, const T& value) {
862 CheckStamp(solver);
863 values_.push_back(value);
864 }
865 void Clear(Solver* solver) {
866 values_.clear();
867 stamp_ = solver->fail_stamp();
868 }
869
870 private:
871 void CheckStamp(Solver* solver) {
872 if (solver->fail_stamp() > stamp_) {
873 Clear(solver);
874 }
875 }
876
877 std::vector<T> values_;
879};
880} // namespace
881
882class DelayedPathCumul : public Constraint {
883 public:
884 DelayedPathCumul(Solver* const solver, const std::vector<IntVar*>& nexts,
885 const std::vector<IntVar*>& active,
886 const std::vector<IntVar*>& cumuls,
887 const std::vector<IntVar*>& transits)
888 : Constraint(solver),
889 nexts_(nexts),
890 active_(active),
891 cumuls_(cumuls),
892 transits_(transits),
893 cumul_transit_demons_(cumuls.size(), nullptr),
894 path_demon_(nullptr),
895 touched_(),
896 chain_starts_(cumuls.size(), -1),
897 chain_ends_(cumuls.size(), -1),
898 is_chain_start_(cumuls.size(), false),
899 prevs_(cumuls.size(), -1),
900 supports_(nexts.size()),
901 was_bound_(nexts.size(), false),
902 has_cumul_demon_(cumuls.size(), false) {
903 for (int64 i = 0; i < cumuls_.size(); ++i) {
904 cumul_transit_demons_[i] = MakeDelayedConstraintDemon1(
905 solver, this, &DelayedPathCumul::CumulRange, "CumulRange", i);
906 chain_starts_[i] = i;
907 chain_ends_[i] = i;
908 }
909 path_demon_ = MakeDelayedConstraintDemon0(
910 solver, this, &DelayedPathCumul::PropagatePaths, "PropagatePaths");
911 for (int i = 0; i < nexts_.size(); ++i) {
912 supports_[i] = -1;
913 }
914 }
915 ~DelayedPathCumul() override {}
916 void Post() override {
917 solver()->RegisterDemon(path_demon_);
918 for (int i = 0; i < nexts_.size(); ++i) {
919 if (!nexts_[i]->Bound()) {
920 Demon* const demon = MakeConstraintDemon1(
921 solver(), this, &DelayedPathCumul::NextBound, "NextBound", i);
922 nexts_[i]->WhenBound(demon);
923 }
924 }
925 for (int i = 0; i < active_.size(); ++i) {
926 if (!active_[i]->Bound()) {
927 Demon* const demon = MakeConstraintDemon1(
928 solver(), this, &DelayedPathCumul::ActiveBound, "ActiveBound", i);
929 active_[i]->WhenBound(demon);
930 }
931 }
932 }
933 void InitialPropagate() override {
934 touched_.Clear(solver());
935 for (int i = 0; i < nexts_.size(); ++i) {
936 if (nexts_[i]->Bound()) {
937 NextBound(i);
938 }
939 }
940 for (int i = 0; i < active_.size(); ++i) {
941 if (active_[i]->Bound()) {
942 ActiveBound(i);
943 }
944 }
945 }
946 // TODO(user): Merge NextBound and ActiveBound to re-use the same demon
947 // for next and active variables.
948 void NextBound(int index) {
949 if (active_[index]->Min() > 0) {
950 const int next = nexts_[index]->Min();
951 PropagateLink(index, next);
952 touched_.PushBack(solver(), index);
953 EnqueueDelayedDemon(path_demon_);
954 }
955 }
956 void ActiveBound(int index) {
957 if (nexts_[index]->Bound()) {
958 NextBound(index);
959 }
960 }
961 void PropagatePaths() {
962 // Detecting new chains.
963 const std::vector<int>& touched_values = touched_.Values(solver());
964 for (const int touched : touched_values) {
965 chain_starts_[touched] = touched;
966 chain_ends_[touched] = touched;
967 is_chain_start_[touched] = false;
968 const int next = nexts_[touched]->Min();
969 chain_starts_[next] = next;
970 chain_ends_[next] = next;
971 is_chain_start_[next] = false;
972 }
973 for (const int touched : touched_values) {
974 if (touched >= nexts_.size()) continue;
975 IntVar* const next_var = nexts_[touched];
976 if (!was_bound_[touched] && next_var->Bound() &&
977 active_[touched]->Min() > 0) {
978 const int64 next = next_var->Min();
979 was_bound_.SetValue(solver(), touched, true);
980 chain_starts_[chain_ends_[next]] = chain_starts_[touched];
981 chain_ends_[chain_starts_[touched]] = chain_ends_[next];
982 is_chain_start_[next] = false;
983 is_chain_start_[chain_starts_[touched]] = true;
984 }
985 }
986 // Propagating new chains.
987 for (const int touched : touched_values) {
988 // Is touched the start of a chain ?
989 if (is_chain_start_[touched]) {
990 // Propagate min cumuls from chain_starts[touch] to chain_ends_[touch].
991 int64 current = touched;
992 int64 next = nexts_[current]->Min();
993 while (current != chain_ends_[touched]) {
994 prevs_.SetValue(solver(), next, current);
995 PropagateLink(current, next);
996 current = next;
997 if (current != chain_ends_[touched]) {
998 next = nexts_[current]->Min();
999 }
1000 }
1001 // Propagate max cumuls from chain_ends_[i] to chain_starts_[i].
1002 int64 prev = prevs_[current];
1003 while (current != touched) {
1004 PropagateLink(prev, current);
1005 current = prev;
1006 if (current != touched) {
1007 prev = prevs_[current];
1008 }
1009 }
1010 // Now that the chain has been propagated in both directions, adding
1011 // demons for the corresponding cumul and transit variables for
1012 // future changes in their range.
1013 current = touched;
1014 while (current != chain_ends_[touched]) {
1015 if (!has_cumul_demon_[current]) {
1016 Demon* const demon = cumul_transit_demons_[current];
1017 cumuls_[current]->WhenRange(demon);
1018 transits_[current]->WhenRange(demon);
1019 has_cumul_demon_.SetValue(solver(), current, true);
1020 }
1021 current = nexts_[current]->Min();
1022 }
1023 if (!has_cumul_demon_[current]) {
1024 Demon* const demon = cumul_transit_demons_[current];
1025 cumuls_[current]->WhenRange(demon);
1026 if (current < transits_.size()) {
1027 transits_[current]->WhenRange(demon);
1028 UpdateSupport(current);
1029 }
1030 has_cumul_demon_.SetValue(solver(), current, true);
1031 }
1032 }
1033 }
1034 touched_.Clear(solver());
1035 }
1036
1037 void Accept(ModelVisitor* const visitor) const override {
1038 visitor->BeginVisitConstraint(ModelVisitor::kDelayedPathCumul, this);
1039 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,
1040 nexts_);
1041 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kActiveArgument,
1042 active_);
1043 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCumulsArgument,
1044 cumuls_);
1045 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kTransitsArgument,
1046 transits_);
1047 visitor->EndVisitConstraint(ModelVisitor::kDelayedPathCumul, this);
1048 }
1049
1050 std::string DebugString() const override {
1051 std::string out = "DelayedPathCumul(";
1052 for (int i = 0; i < nexts_.size(); ++i) {
1053 out += nexts_[i]->DebugString() + " " + cumuls_[i]->DebugString();
1054 }
1055 out += ")";
1056 return out;
1057 }
1058
1059 private:
1060 void CumulRange(int64 index) {
1061 if (index < nexts_.size()) {
1062 if (nexts_[index]->Bound()) {
1063 if (active_[index]->Min() > 0) {
1064 PropagateLink(index, nexts_[index]->Min());
1065 }
1066 } else {
1067 UpdateSupport(index);
1068 }
1069 }
1070 if (prevs_[index] >= 0) {
1071 PropagateLink(prevs_[index], index);
1072 } else {
1073 for (int i = 0; i < nexts_.size(); ++i) {
1074 if (index == supports_[i]) {
1075 UpdateSupport(i);
1076 }
1077 }
1078 }
1079 }
1080 void UpdateSupport(int index) {
1081 int support = supports_[index];
1082 if (support < 0 || !AcceptLink(index, support)) {
1083 IntVar* const next = nexts_[index];
1084 for (int i = next->Min(); i <= next->Max(); ++i) {
1085 if (i != support && AcceptLink(index, i)) {
1086 supports_[index] = i;
1087 return;
1088 }
1089 }
1090 active_[index]->SetMax(0);
1091 }
1092 }
1093 void PropagateLink(int64 index, int64 next) {
1094 IntVar* const cumul_var = cumuls_[index];
1095 IntVar* const next_cumul_var = cumuls_[next];
1096 IntVar* const transit = transits_[index];
1097 const int64 transit_min = transit->Min();
1098 const int64 transit_max = transit->Max();
1099 next_cumul_var->SetMin(CapAdd(cumul_var->Min(), transit_min));
1100 next_cumul_var->SetMax(CapAdd(cumul_var->Max(), transit_max));
1101 const int64 next_cumul_min = next_cumul_var->Min();
1102 const int64 next_cumul_max = next_cumul_var->Max();
1103 cumul_var->SetMin(CapSub(next_cumul_min, transit_max));
1104 cumul_var->SetMax(CapSub(next_cumul_max, transit_min));
1105 transit->SetMin(CapSub(next_cumul_min, cumul_var->Max()));
1106 transit->SetMax(CapSub(next_cumul_max, cumul_var->Min()));
1107 }
1108 bool AcceptLink(int index, int next) const {
1109 IntVar* const cumul_var = cumuls_[index];
1110 IntVar* const next_cumul_var = cumuls_[next];
1111 IntVar* const transit = transits_[index];
1112 return transit->Min() <= CapSub(next_cumul_var->Max(), cumul_var->Min()) &&
1113 CapSub(next_cumul_var->Min(), cumul_var->Max()) <= transit->Max();
1114 }
1115
1116 const std::vector<IntVar*> nexts_;
1117 const std::vector<IntVar*> active_;
1118 const std::vector<IntVar*> cumuls_;
1119 const std::vector<IntVar*> transits_;
1120 std::vector<Demon*> cumul_transit_demons_;
1121 Demon* path_demon_;
1122 StampedVector<int> touched_;
1123 std::vector<int64> chain_starts_;
1124 std::vector<int64> chain_ends_;
1125 std::vector<bool> is_chain_start_;
1126 RevArray<int> prevs_;
1127 std::vector<int> supports_;
1128 RevArray<bool> was_bound_;
1129 RevArray<bool> has_cumul_demon_;
1130};
1131
1132// cumuls[next[i]] = cumuls[i] + transit_evaluator(i, next[i])
1133
1134class IndexEvaluator2PathCumul : public BasePathCumul {
1135 public:
1136 IndexEvaluator2PathCumul(Solver* const s, const std::vector<IntVar*>& nexts,
1137 const std::vector<IntVar*>& active,
1138 const std::vector<IntVar*>& cumuls,
1139 Solver::IndexEvaluator2 transit_evaluator);
1140 ~IndexEvaluator2PathCumul() override {}
1141 void NextBound(int index) override;
1142 bool AcceptLink(int i, int j) const override;
1143
1144 void Accept(ModelVisitor* const visitor) const override {
1145 visitor->BeginVisitConstraint(ModelVisitor::kPathCumul, this);
1146 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,
1147 nexts_);
1148 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kActiveArgument,
1149 active_);
1150 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCumulsArgument,
1151 cumuls_);
1152 // TODO(user): Visit transit correctly.
1153 // visitor->VisitIntegerVariableArrayArgument(
1154 // ModelVisitor::kTransitsArgument,
1155 // transit_evaluator);
1156 visitor->EndVisitConstraint(ModelVisitor::kPathCumul, this);
1157 }
1158
1159 private:
1160 Solver::IndexEvaluator2 transits_evaluator_;
1161};
1162
1163IndexEvaluator2PathCumul::IndexEvaluator2PathCumul(
1164 Solver* const s, const std::vector<IntVar*>& nexts,
1165 const std::vector<IntVar*>& active, const std::vector<IntVar*>& cumuls,
1166 Solver::IndexEvaluator2 transit_evaluator)
1167 : BasePathCumul(s, nexts, active, cumuls),
1168 transits_evaluator_(std::move(transit_evaluator)) {}
1169
1170void IndexEvaluator2PathCumul::NextBound(int index) {
1171 if (active_[index]->Min() == 0) return;
1172 const int64 next = nexts_[index]->Value();
1173 IntVar* cumul = cumuls_[index];
1174 IntVar* cumul_next = cumuls_[next];
1175 const int64 transit = transits_evaluator_(index, next);
1176 cumul_next->SetMin(cumul->Min() + transit);
1177 cumul_next->SetMax(CapAdd(cumul->Max(), transit));
1178 cumul->SetMin(CapSub(cumul_next->Min(), transit));
1179 cumul->SetMax(CapSub(cumul_next->Max(), transit));
1180 if (prevs_[next] < 0) {
1181 prevs_.SetValue(solver(), next, index);
1182 }
1183}
1184
1185bool IndexEvaluator2PathCumul::AcceptLink(int i, int j) const {
1186 const IntVar* const cumul_i = cumuls_[i];
1187 const IntVar* const cumul_j = cumuls_[j];
1188 const int64 transit = transits_evaluator_(i, j);
1189 return transit <= CapSub(cumul_j->Max(), cumul_i->Min()) &&
1190 CapSub(cumul_j->Min(), cumul_i->Max()) <= transit;
1191}
1192
1193// ----- ResulatCallback2SlackPathCumul -----
1194
1195class IndexEvaluator2SlackPathCumul : public BasePathCumul {
1196 public:
1197 IndexEvaluator2SlackPathCumul(Solver* const s,
1198 const std::vector<IntVar*>& nexts,
1199 const std::vector<IntVar*>& active,
1200 const std::vector<IntVar*>& cumuls,
1201 const std::vector<IntVar*>& slacks,
1202 Solver::IndexEvaluator2 transit_evaluator);
1203 ~IndexEvaluator2SlackPathCumul() override {}
1204 void Post() override;
1205 void NextBound(int index) override;
1206 bool AcceptLink(int i, int j) const override;
1207 void SlackRange(int index);
1208
1209 void Accept(ModelVisitor* const visitor) const override {
1210 visitor->BeginVisitConstraint(ModelVisitor::kPathCumul, this);
1211 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,
1212 nexts_);
1213 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kActiveArgument,
1214 active_);
1215 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCumulsArgument,
1216 cumuls_);
1217 // TODO(user): Visit transit correctly.
1218 // visitor->VisitIntegerVariableArrayArgument(
1219 // ModelVisitor::kTransitsArgument,
1220 // transit_evaluator);
1221 visitor->EndVisitConstraint(ModelVisitor::kPathCumul, this);
1222 }
1223
1224 private:
1225 const std::vector<IntVar*> slacks_;
1226 Solver::IndexEvaluator2 transits_evaluator_;
1227};
1228
1229IndexEvaluator2SlackPathCumul::IndexEvaluator2SlackPathCumul(
1230 Solver* const s, const std::vector<IntVar*>& nexts,
1231 const std::vector<IntVar*>& active, const std::vector<IntVar*>& cumuls,
1232 const std::vector<IntVar*>& slacks,
1233 Solver::IndexEvaluator2 transit_evaluator)
1234 : BasePathCumul(s, nexts, active, cumuls),
1235 slacks_(slacks),
1236 transits_evaluator_(std::move(transit_evaluator)) {}
1237
1238void IndexEvaluator2SlackPathCumul::Post() {
1239 BasePathCumul::Post();
1240 for (int i = 0; i < size(); ++i) {
1241 Demon* slack_demon = MakeConstraintDemon1(
1242 solver(), this, &IndexEvaluator2SlackPathCumul::SlackRange,
1243 "SlackRange", i);
1244 slacks_[i]->WhenRange(slack_demon);
1245 }
1246}
1247
1248void IndexEvaluator2SlackPathCumul::SlackRange(int index) {
1249 if (nexts_[index]->Bound()) {
1250 NextBound(index);
1251 } else {
1252 UpdateSupport(index);
1253 }
1254 if (prevs_[index] >= 0) {
1255 NextBound(prevs_[index]);
1256 } else {
1257 for (int i = 0; i < size(); ++i) {
1258 if (index == supports_[i]) {
1259 UpdateSupport(i);
1260 }
1261 }
1262 }
1263}
1264
1265void IndexEvaluator2SlackPathCumul::NextBound(int index) {
1266 if (active_[index]->Min() == 0) return;
1267 const int64 next = nexts_[index]->Value();
1268 IntVar* const cumul = cumuls_[index];
1269 IntVar* const cumul_next = cumuls_[next];
1270 IntVar* const slack = slacks_[index];
1271 const int64 transit = transits_evaluator_(index, next);
1272 const int64 cumul_next_minus_transit_min = CapSub(cumul_next->Min(), transit);
1273 const int64 cumul_next_minus_transit_max = CapSub(cumul_next->Max(), transit);
1274 cumul_next->SetMin(CapAdd(CapAdd(cumul->Min(), transit), slack->Min()));
1275 cumul_next->SetMax(CapAdd(CapAdd(cumul->Max(), transit), slack->Max()));
1276 cumul->SetMin(CapSub(cumul_next_minus_transit_min, slack->Max()));
1277 cumul->SetMax(CapSub(cumul_next_minus_transit_max, slack->Min()));
1278 slack->SetMin(CapSub(cumul_next_minus_transit_min, cumul->Max()));
1279 slack->SetMax(CapSub(cumul_next_minus_transit_max, cumul->Min()));
1280 if (prevs_[next] < 0) {
1281 prevs_.SetValue(solver(), next, index);
1282 }
1283}
1284
1285bool IndexEvaluator2SlackPathCumul::AcceptLink(int i, int j) const {
1286 const IntVar* const cumul_i = cumuls_[i];
1287 const IntVar* const cumul_j = cumuls_[j];
1288 const IntVar* const slack = slacks_[i];
1289 const int64 transit = transits_evaluator_(i, j);
1290 return CapAdd(transit, slack->Min()) <=
1291 CapSub(cumul_j->Max(), cumul_i->Min()) &&
1292 CapSub(cumul_j->Min(), cumul_i->Max()) <=
1293 CapAdd(slack->Max(), transit);
1294}
1295} // namespace
1296
1297Constraint* Solver::MakePathCumul(const std::vector<IntVar*>& nexts,
1298 const std::vector<IntVar*>& active,
1299 const std::vector<IntVar*>& cumuls,
1300 const std::vector<IntVar*>& transits) {
1301 CHECK_EQ(nexts.size(), active.size());
1302 CHECK_EQ(transits.size(), nexts.size());
1303 return RevAlloc(new PathCumul(this, nexts, active, cumuls, transits));
1304}
1305
1306Constraint* Solver::MakePathCumul(const std::vector<IntVar*>& nexts,
1307 const std::vector<IntVar*>& active,
1308 const std::vector<IntVar*>& cumuls,
1309 Solver::IndexEvaluator2 transit_evaluator) {
1310 CHECK_EQ(nexts.size(), active.size());
1311 return RevAlloc(new IndexEvaluator2PathCumul(this, nexts, active, cumuls,
1312 std::move(transit_evaluator)));
1313}
1314
1315Constraint* Solver::MakePathCumul(const std::vector<IntVar*>& nexts,
1316 const std::vector<IntVar*>& active,
1317 const std::vector<IntVar*>& cumuls,
1318 const std::vector<IntVar*>& slacks,
1319 Solver::IndexEvaluator2 transit_evaluator) {
1320 CHECK_EQ(nexts.size(), active.size());
1321 return RevAlloc(new IndexEvaluator2SlackPathCumul(
1322 this, nexts, active, cumuls, slacks, std::move(transit_evaluator)));
1323}
1324
1325Constraint* Solver::MakeDelayedPathCumul(const std::vector<IntVar*>& nexts,
1326 const std::vector<IntVar*>& active,
1327 const std::vector<IntVar*>& cumuls,
1328 const std::vector<IntVar*>& transits) {
1329 CHECK_EQ(nexts.size(), active.size());
1330 CHECK_EQ(transits.size(), nexts.size());
1331 return RevAlloc(new DelayedPathCumul(this, nexts, active, cumuls, transits));
1332}
1333
1334// Constraint enforcing that status[i] is true iff there's a path defined on
1335// next variables from sources[i] to sinks[i].
1336namespace {
1337class PathConnectedConstraint : public Constraint {
1338 public:
1339 PathConnectedConstraint(Solver* solver, std::vector<IntVar*> nexts,
1340 const std::vector<int64>& sources,
1341 std::vector<int64> sinks, std::vector<IntVar*> status)
1342 : Constraint(solver),
1343 sources_(sources.size(), -1),
1344 index_to_path_(nexts.size(), -1),
1345 sinks_(std::move(sinks)),
1346 nexts_(std::move(nexts)),
1347 status_(std::move(status)),
1348 touched_(nexts_.size()) {
1349 CHECK_EQ(status_.size(), sources_.size());
1350 CHECK_EQ(status_.size(), sinks_.size());
1351 for (int i = 0; i < status_.size(); ++i) {
1352 const int64 source = sources[i];
1353 sources_.SetValue(solver, i, source);
1354 if (source < index_to_path_.size()) {
1355 index_to_path_.SetValue(solver, source, i);
1356 }
1357 }
1358 }
1359 void Post() override {
1360 for (int i = 0; i < nexts_.size(); ++i) {
1361 nexts_[i]->WhenBound(MakeConstraintDemon1(
1362 solver(), this, &PathConnectedConstraint::NextBound, "NextValue", i));
1363 }
1364 for (int i = 0; i < status_.size(); ++i) {
1365 if (sources_[i] < nexts_.size()) {
1366 status_[i]->SetRange(0, 1);
1367 } else {
1368 status_[i]->SetValue(0);
1369 }
1370 }
1371 }
1372 void InitialPropagate() override {
1373 for (int i = 0; i < status_.size(); ++i) {
1374 EvaluatePath(i);
1375 }
1376 }
1377 std::string DebugString() const override {
1378 std::string output = "PathConnected(";
1379 std::vector<std::string> elements;
1380 for (IntVar* const next : nexts_) {
1381 elements.push_back(next->DebugString());
1382 }
1383 for (int i = 0; i < sources_.size(); ++i) {
1384 elements.push_back(absl::StrCat(sources_[i]));
1385 }
1386 for (int64 sink : sinks_) {
1387 elements.push_back(absl::StrCat(sink));
1388 }
1389 for (IntVar* const status : status_) {
1390 elements.push_back(status->DebugString());
1391 }
1392 output += absl::StrJoin(elements, ",") + ")";
1393 return output;
1394 }
1395
1396 private:
1397 void NextBound(int index) {
1398 const int path = index_to_path_[index];
1399 if (path >= 0) {
1400 EvaluatePath(path);
1401 }
1402 }
1403 void EvaluatePath(int path) {
1404 touched_.SparseClearAll();
1405 int64 source = sources_[path];
1406 const int64 end = sinks_[path];
1407 while (source != end) {
1408 if (source >= nexts_.size() || touched_[source]) {
1409 status_[path]->SetValue(0);
1410 return;
1411 }
1412 touched_.Set(source);
1413 IntVar* const next = nexts_[source];
1414 if (next->Bound()) {
1415 source = next->Min();
1416 } else {
1417 sources_.SetValue(solver(), path, source);
1418 index_to_path_.SetValue(solver(), source, path);
1419 return;
1420 }
1421 }
1422 status_[path]->SetValue(1);
1423 }
1424
1425 RevArray<int64> sources_;
1426 RevArray<int> index_to_path_;
1427 const std::vector<int64> sinks_;
1428 const std::vector<IntVar*> nexts_;
1429 const std::vector<IntVar*> status_;
1430 SparseBitset<int64> touched_;
1431};
1432} // namespace
1433
1434Constraint* Solver::MakePathConnected(std::vector<IntVar*> nexts,
1435 std::vector<int64> sources,
1436 std::vector<int64> sinks,
1437 std::vector<IntVar*> status) {
1438 return RevAlloc(new PathConnectedConstraint(
1439 this, std::move(nexts), sources, std::move(sinks), std::move(status)));
1440}
1441
1442namespace {
1443class PathTransitPrecedenceConstraint : public Constraint {
1444 public:
1445 enum PrecedenceType {
1446 ANY,
1447 LIFO,
1448 FIFO,
1449 };
1450 PathTransitPrecedenceConstraint(
1451 Solver* solver, std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1452 const std::vector<std::pair<int, int>>& precedences,
1453 absl::flat_hash_map<int, PrecedenceType> precedence_types)
1454 : Constraint(solver),
1455 nexts_(std::move(nexts)),
1456 transits_(std::move(transits)),
1457 predecessors_(nexts_.size()),
1458 successors_(nexts_.size()),
1459 precedence_types_(std::move(precedence_types)),
1460 starts_(nexts_.size(), -1),
1461 ends_(nexts_.size(), -1),
1462 transit_cumuls_(nexts_.size(), 0) {
1463 for (int i = 0; i < nexts_.size(); ++i) {
1464 starts_.SetValue(solver, i, i);
1465 ends_.SetValue(solver, i, i);
1466 }
1467 for (const auto& precedence : precedences) {
1468 if (precedence.second < nexts_.size()) {
1469 predecessors_[precedence.second].push_back(precedence.first);
1470 }
1471 if (precedence.first < nexts_.size()) {
1472 successors_[precedence.first].push_back(precedence.second);
1473 }
1474 }
1475 }
1476 ~PathTransitPrecedenceConstraint() override {}
1477 void Post() override {
1478 for (int i = 0; i < nexts_.size(); ++i) {
1479 nexts_[i]->WhenBound(MakeDelayedConstraintDemon1(
1480 solver(), this, &PathTransitPrecedenceConstraint::NextBound,
1481 "NextBound", i));
1482 }
1483 for (int i = 0; i < transits_.size(); ++i) {
1484 transits_[i]->WhenRange(MakeDelayedConstraintDemon1(
1485 solver(), this, &PathTransitPrecedenceConstraint::NextBound,
1486 "TransitRange", i));
1487 }
1488 }
1489 void InitialPropagate() override {
1490 for (int i = 0; i < nexts_.size(); ++i) {
1491 if (nexts_[i]->Bound()) {
1492 NextBound(i);
1493 }
1494 }
1495 }
1496 std::string DebugString() const override {
1497 std::string output = "PathPrecedence(";
1498 std::vector<std::string> elements = {JoinDebugStringPtr(nexts_, ",")};
1499 if (!transits_.empty()) {
1500 elements.push_back(JoinDebugStringPtr(transits_, ","));
1501 }
1502 for (int i = 0; i < predecessors_.size(); ++i) {
1503 for (const int predecessor : predecessors_[i]) {
1504 elements.push_back(absl::StrCat("(", predecessor, ", ", i, ")"));
1505 }
1506 }
1507 output += absl::StrJoin(elements, ",") + ")";
1508 return output;
1509 }
1510 void Accept(ModelVisitor* const visitor) const override {
1511 // TODO(user): Implement.
1512 }
1513
1514 private:
1515 void NextBound(int index) {
1516 if (!nexts_[index]->Bound()) return;
1517 const int next = nexts_[index]->Min();
1518 const int start = starts_[index];
1519 const int end = (next < nexts_.size()) ? ends_[next] : next;
1520 if (end < nexts_.size()) starts_.SetValue(solver(), end, start);
1521 ends_.SetValue(solver(), start, end);
1522 int current = start;
1523 PrecedenceType type = ANY;
1524 auto it = precedence_types_.find(start);
1525 if (it != precedence_types_.end()) {
1526 type = it->second;
1527 }
1528 forbidden_.clear();
1529 marked_.clear();
1530 pushed_.clear();
1531 int64 transit_cumul = 0;
1532 const bool has_transits = !transits_.empty();
1533 while (current < nexts_.size() && current != end) {
1534 transit_cumuls_[current] = transit_cumul;
1535 marked_.insert(current);
1536 // If current has predecessors and we are in LIFO/FIFO mode.
1537 if (!predecessors_[current].empty() && !pushed_.empty()) {
1538 bool found = false;
1539 // One of the predecessors must be at the top of the stack.
1540 for (const int predecessor : predecessors_[current]) {
1541 if (pushed_.back() == predecessor) {
1542 found = true;
1543 break;
1544 }
1545 }
1546 if (!found) solver()->Fail();
1547 pushed_.pop_back();
1548 }
1549 if (forbidden_.find(current) != forbidden_.end()) {
1550 for (const int successor : successors_[current]) {
1551 if (marked_.find(successor) != marked_.end()) {
1552 if (!has_transits ||
1553 CapSub(transit_cumul, transit_cumuls_[successor]) > 0) {
1554 solver()->Fail();
1555 }
1556 }
1557 }
1558 }
1559 if (!successors_[current].empty()) {
1560 switch (type) {
1561 case LIFO:
1562 pushed_.push_back(current);
1563 break;
1564 case FIFO:
1565 pushed_.push_front(current);
1566 break;
1567 case ANY:
1568 break;
1569 }
1570 }
1571 for (const int predecessor : predecessors_[current]) {
1572 forbidden_.insert(predecessor);
1573 }
1574 if (has_transits) {
1575 transit_cumul = CapAdd(transit_cumul, transits_[current]->Min());
1576 }
1577 current = nexts_[current]->Min();
1578 }
1579 if (forbidden_.find(current) != forbidden_.end()) {
1580 for (const int successor : successors_[current]) {
1581 if (marked_.find(successor) != marked_.end()) {
1582 if (!has_transits ||
1583 CapSub(transit_cumul, transit_cumuls_[successor]) > 0) {
1584 solver()->Fail();
1585 }
1586 }
1587 }
1588 }
1589 }
1590
1591 const std::vector<IntVar*> nexts_;
1592 const std::vector<IntVar*> transits_;
1593 std::vector<std::vector<int>> predecessors_;
1594 std::vector<std::vector<int>> successors_;
1595 const absl::flat_hash_map<int, PrecedenceType> precedence_types_;
1596 RevArray<int> starts_;
1597 RevArray<int> ends_;
1598 absl::flat_hash_set<int> forbidden_;
1599 absl::flat_hash_set<int> marked_;
1600 std::deque<int> pushed_;
1601 std::vector<int64> transit_cumuls_;
1602};
1603
1604Constraint* MakePathTransitTypedPrecedenceConstraint(
1605 Solver* solver, std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1606 const std::vector<std::pair<int, int>>& precedences,
1607 absl::flat_hash_map<int, PathTransitPrecedenceConstraint::PrecedenceType>
1608 precedence_types) {
1609 if (precedences.empty()) {
1610 return solver->MakeTrueConstraint();
1611 }
1612 return solver->RevAlloc(new PathTransitPrecedenceConstraint(
1613 solver, std::move(nexts), std::move(transits), precedences,
1614 std::move(precedence_types)));
1615}
1616
1617} // namespace
1618
1619Constraint* Solver::MakePathPrecedenceConstraint(
1620 std::vector<IntVar*> nexts,
1621 const std::vector<std::pair<int, int>>& precedences) {
1622 return MakePathTransitPrecedenceConstraint(std::move(nexts), {}, precedences);
1623}
1624
1625Constraint* Solver::MakePathPrecedenceConstraint(
1626 std::vector<IntVar*> nexts,
1627 const std::vector<std::pair<int, int>>& precedences,
1628 const std::vector<int>& lifo_path_starts,
1629 const std::vector<int>& fifo_path_starts) {
1630 absl::flat_hash_map<int, PathTransitPrecedenceConstraint::PrecedenceType>
1631 precedence_types;
1632 for (int start : lifo_path_starts) {
1633 precedence_types[start] = PathTransitPrecedenceConstraint::LIFO;
1634 }
1635 for (int start : fifo_path_starts) {
1636 precedence_types[start] = PathTransitPrecedenceConstraint::FIFO;
1637 }
1638 return MakePathTransitTypedPrecedenceConstraint(
1639 this, std::move(nexts), {}, precedences, std::move(precedence_types));
1640}
1641
1642Constraint* Solver::MakePathTransitPrecedenceConstraint(
1643 std::vector<IntVar*> nexts, std::vector<IntVar*> transits,
1644 const std::vector<std::pair<int, int>>& precedences) {
1645 return MakePathTransitTypedPrecedenceConstraint(
1646 this, std::move(nexts), std::move(transits), precedences, {{}});
1647}
1648} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
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
A constraint is the main modeling object.
virtual void InitialPropagate()=0
This method performs the initial propagation of the constraint.
virtual void Accept(ModelVisitor *const visitor) const
Accepts the given visitor.
std::string DebugString() const override
virtual void Post()=0
This method is called when the constraint is processed by the solver.
static const char kActiveArgument[]
argument names:
void SetValue(Solver *const s, const T &val)
std::function< bool(int64)> IndexFilter1
std::function< int64(int64, int64)> IndexEvaluator2
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
std::vector< IntVarIterator * > iterators_
Block * next
int64 value
IntVar * var
Definition: expr_array.cc:1858
const std::vector< IntVar * > cumuls_
RevArray< int > prevs_
std::vector< int > supports_
int64_t int64
uint64_t uint64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int64 CapAdd(int64 x, int64 y)
Demon * MakeDelayedConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
int64 CapSub(int64 x, int64 y)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
std::string JoinDebugStringPtr(const std::vector< T > &v, const std::string &separator)
Definition: string_array.h:45
STL namespace.
int index
Definition: pack.cc:508
const int64 stamp_
Definition: search.cc:3039