1

2

3

4

5

6

7

8

9

10

11

12

13

14#include <algorithm>

15#include <cstdint>

16#include <deque>

17#include <memory>

18#include <string>

19#include <utility>

20#include <vector>

21

22#include "absl/container/flat_hash_set.h"

23#include "absl/strings/str_cat.h"

24#include "absl/strings/str_format.h"

25#include "absl/strings/str_join.h"

26#include "absl/types/span.h"

33

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49namespace {

51 public:

52 NoCycle(Solver* s, const std::vector<IntVar*>& nexts,

54 bool assume_paths);

55 ~NoCycle() override {}

56 void Post() override;

57 void InitialPropagate() override;

58 void NextChange(int index);

59 void ActiveBound(int index);

60 void NextBound(int index);

61 void ComputeSupports();

62 void ComputeSupport(int index);

63 std::string DebugString() const override;

64

65 void Accept(ModelVisitor* const visitor) const override {

68 nexts_);

70 active_);

71 visitor->VisitIntegerArgument("assume_paths", assume_paths_);

72 visitor->VisitInt64ToBoolExtension(sink_handler_, -size(), size());

74 }

75

76 private:

77 int64_t size() const { return nexts_.size(); }

78

79 const std::vector<IntVar*> nexts_;

80 const std::vector<IntVar*> active_;

81 std::vector<IntVarIterator*> iterators_;

82 RevArray<int64_t> starts_;

83 RevArray<int64_t> ends_;

84 RevArray<bool> marked_;

85 bool all_nexts_bound_;

86 std::vector<int64_t> outbound_supports_;

87 std::vector<int64_t> support_leaves_;

88 std::vector<int64_t> unsupported_;

90 std::vector<int64_t> sinks_;

91 bool assume_paths_;

92};

93

94NoCycle::NoCycle(Solver* const s, const std::vector<IntVar*>& nexts,

95 const std::vector<IntVar*>& active,

98 nexts_(nexts),

99 active_(active),

100 iterators_(nexts.size(), nullptr),

101 starts_(nexts.size(), -1),

102 ends_(nexts.size(), -1),

103 marked_(nexts.size(), false),

104 all_nexts_bound_(false),

105 outbound_supports_(nexts.size(), -1),

106 sink_handler_(std::move(sink_handler)),

107 assume_paths_(assume_paths) {

108 support_leaves_.reserve(size());

109 unsupported_.reserve(size());

110 for (int i = 0; i < size(); ++i) {

111 starts_.SetValue(s, i, i);

112 ends_.SetValue(s, i, i);

113 iterators_[i] = nexts_[i]->MakeDomainIterator(true);

114 }

115}

116

117void NoCycle::InitialPropagate() {

118

119 for (int i = 0; i < size(); ++i) {

120 outbound_supports_[i] = -1;

121 IntVar* next = nexts_[i];

122 for (int j = next->Min(); j < 0; ++j) {

123 if (!sink_handler_(j)) {

124 next->RemoveValue(j);

125 }

126 }

127 for (int j = next->Max(); j >= size(); --j) {

128 if (!sink_handler_(j)) {

129 next->RemoveValue(j);

130 }

131 }

132 }

133 solver()->SaveAndSetValue(&all_nexts_bound_, true);

134 for (int i = 0; i < size(); ++i) {

135 if (nexts_[i]->Bound()) {

136 NextBound(i);

137 } else {

138 solver()->SaveAndSetValue(&all_nexts_bound_, false);

139 }

140 }

141 ComputeSupports();

142}

143

144void NoCycle::Post() {

145 if (size() == 0) return;

146 for (int i = 0; i < size(); ++i) {

147 IntVar* next = nexts_[i];

149 solver(), this, &NoCycle::NextChange, "NextChange", i);

150 next->WhenDomain(support_demon);

152 solver(), this, &NoCycle::ActiveBound, "ActiveBound", i);

153 active_[i]->WhenBound(active_demon);

154 }

155

156 int64_t min_min = nexts_[0]->Min();

157 int64_t max_max = nexts_[0]->Max();

158 for (int i = 1; i < size(); ++i) {

159 const IntVar* next = nexts_[i];

160 min_min = std::min(min_min, next->Min());

161 max_max = std::max(max_max, next->Max());

162 }

163 sinks_.clear();

164 for (int i = min_min; i <= max_max; ++i) {

165 if (sink_handler_(i)) {

166 sinks_.push_back(i);

167 }

168 }

169}

170

171void NoCycle::NextChange(int index) {

172 IntVar* const next_var = nexts_[index];

173 if (next_var->Bound()) {

174 NextBound(index);

175 }

176 if (!all_nexts_bound_) {

177 bool all_nexts_bound = true;

178 for (int i = 0; i < size(); ++i) {

179 if (!nexts_[i]->Bound()) {

180 all_nexts_bound = false;

181 break;

182 }

183 }

184 solver()->SaveAndSetValue(&all_nexts_bound_, all_nexts_bound);

185 }

186 if (all_nexts_bound_) {

187 return;

188 }

189 if (!next_var->Contains(outbound_supports_[index])) {

190 ComputeSupport(index);

191 }

192}

193

194void NoCycle::ActiveBound(int index) {

195 if (nexts_[index]->Bound()) {

196 NextBound(index);

197 }

198}

199

200void NoCycle::NextBound(int index) {

201 if (active_[index]->Min() == 0) return;

202 if (marked_[index]) return;

203 Solver* const s = solver();

204

205

206 marked_.SetValue(s, index, true);

207 const int64_t next = nexts_[index]->Value();

208 const int64_t chain_start = starts_[index];

209 const int64_t chain_end = !sink_handler_(next) ? ends_[next] : next;

210 if (!sink_handler_(chain_start)) {

211 ends_.SetValue(s, chain_start, chain_end);

212 if (!sink_handler_(chain_end)) {

213 starts_.SetValue(s, chain_end, chain_start);

214 nexts_[chain_end]->RemoveValue(chain_start);

215 if (!assume_paths_) {

216 for (int i = 0; i < size(); ++i) {

217 int64_t current = i;

218 bool found = (current == chain_end);

219

220 int count = 0;

221 while (!found && count < size() && !sink_handler_(current) &&

222 nexts_[current]->Bound()) {

223 current = nexts_[current]->Value();

224 found = (current == chain_end);

225 ++count;

226 }

227 if (found) {

228 nexts_[chain_end]->RemoveValue(i);

229 }

230 }

231 }

232 }

233 }

234}

235

236

237

238

239

240

241

242

243

244void NoCycle::ComputeSupports() {

245

246 unsupported_.clear();

247

248

249 support_leaves_.clear();

250

251

252 const int sink_size = sinks_.size();

253 for (int i = 0; i < size(); ++i) {

254 const IntVar* next = nexts_[i];

255

256 if (active_[i]->Max() != 0) {

257 const int64_t current_support = outbound_supports_[i];

258

259

260 if (current_support >= 0 && sink_handler_(current_support) &&

261 next->Contains(current_support)) {

262 support_leaves_.push_back(i);

263 } else {

264

265

266 outbound_supports_[i] = -1;

267 if (sink_size < next->Size()) {

268 for (int j = 0; j < sink_size; ++j) {

269 if (next->Contains(sinks_[j])) {

270 outbound_supports_[i] = sinks_[j];

271 support_leaves_.push_back(i);

272 break;

273 }

274 }

275 } else {

276 for (const int64_t value : InitAndGetValues(iterators_[i])) {

277 if (sink_handler_(value)) {

278 outbound_supports_[i] = value;

279 support_leaves_.push_back(i);

280 break;

281 }

282 }

283 }

284 }

285 if (outbound_supports_[i] == -1) {

286 unsupported_.push_back(i);

287 }

288 }

289 }

290

291

292

293 size_t leaves_begin = 0;

294 size_t leaves_end = support_leaves_.size();

295 while (!unsupported_.empty()) {

296

297 for (int64_t unsupported_index = 0; unsupported_index < unsupported_.size();

298 ++unsupported_index) {

299 const int64_t unsupported = unsupported_[unsupported_index];

300 const IntVar* const next = nexts_[unsupported];

301 for (int i = leaves_begin; i < leaves_end; ++i) {

302 if (next->Contains(support_leaves_[i])) {

303 outbound_supports_[unsupported] = support_leaves_[i];

304 support_leaves_.push_back(unsupported);

305

306 unsupported_[unsupported_index] = unsupported_.back();

307 unsupported_.pop_back();

308 --unsupported_index;

309 break;

310 }

311

312

313 }

314 }

315

316 if (leaves_end == support_leaves_.size()) {

317 break;

318 }

319 leaves_begin = leaves_end;

320 leaves_end = support_leaves_.size();

321 }

322

323 for (int64_t unsupported_index = 0; unsupported_index < unsupported_.size();

324 ++unsupported_index) {

325 active_[unsupported_[unsupported_index]]->SetMax(0);

326 }

327}

328

329void NoCycle::ComputeSupport(int index) {

330

331

332 if (active_[index]->Max() != 0) {

333 for (const int64_t next : InitAndGetValues(iterators_[index])) {

334 if (sink_handler_(next)) {

335 outbound_supports_[index] = next;

336 return;

337 }

338 if (next != index && next < outbound_supports_.size()) {

339 int64_t next_support = outbound_supports_[next];

340 if (next_support >= 0) {

341

342 bool ancestor_found = false;

343 while (next_support < outbound_supports_.size() &&

344 !sink_handler_(next_support)) {

345 if (next_support == index) {

346 ancestor_found = true;

347 break;

348 }

349 next_support = outbound_supports_[next_support];

350 }

351 if (!ancestor_found) {

352 outbound_supports_[index] = next;

353 return;

354 }

355 }

356 }

357 }

358 }

359

360 ComputeSupports();

361}

362

363std::string NoCycle::DebugString() const {

364 return absl::StrFormat("NoCycle(%s)", JoinDebugStringPtr(nexts_, ", "));

365}

366

367

368

370 public:

371 Circuit(Solver* const s, const std::vector<IntVar*>& nexts, bool sub_circuit)

372 : Constraint(s),

373 nexts_(nexts),

374 size_(nexts_.size()),

375 starts_(size_, -1),

376 ends_(size_, -1),

377 lengths_(size_, 1),

378 domains_(size_),

379 outbound_support_(size_, -1),

380 inbound_support_(size_, -1),

381 temp_support_(size_, -1),

382 inbound_demon_(nullptr),

383 outbound_demon_(nullptr),

384 root_(-1),

385 num_inactives_(0),

386 sub_circuit_(sub_circuit) {

387 for (int i = 0; i < size_; ++i) {

388 domains_[i] = nexts_[i]->MakeDomainIterator(true);

389 }

390 }

391

392 ~Circuit() override {}

393

394 void Post() override {

396 solver(), this, &Circuit::CheckReachabilityToRoot,

397 "CheckReachabilityToRoot");

399 solver(), this, &Circuit::CheckReachabilityFromRoot,

400 "CheckReachabilityFromRoot");

401 for (int i = 0; i < size_; ++i) {

402 if (!nexts_[i]->Bound()) {

404 solver(), this, &Circuit::NextBound, "NextBound", i);

405 nexts_[i]->WhenBound(bound_demon);

407 solver(), this, &Circuit::NextDomain, "NextDomain", i);

408 nexts_[i]->WhenDomain(domain_demon);

409 }

410 }

411 solver()->AddConstraint(solver()->MakeAllDifferent(nexts_));

412 }

413

414 void InitialPropagate() override {

415 Solver* const s = solver();

416 if (!sub_circuit_) {

417 root_.SetValue(solver(), 0);

418 }

419 for (int i = 0; i < size_; ++i) {

420 nexts_[i]->SetRange(0, size_ - 1);

421 if (!sub_circuit_) {

422 nexts_[i]->RemoveValue(i);

423 }

424 }

425 for (int i = 0; i < size_; ++i) {

426 starts_.SetValue(s, i, i);

427 ends_.SetValue(s, i, i);

428 lengths_.SetValue(s, i, 1);

429 }

430 for (int i = 0; i < size_; ++i) {

431 if (nexts_[i]->Bound()) {

432 NextBound(i);

433 }

434 }

435 CheckReachabilityFromRoot();

436 CheckReachabilityToRoot();

437 }

438

439 std::string DebugString() const override {

440 return absl::StrFormat("%sCircuit(%s)", sub_circuit_ ? "Sub" : "",

442 }

443

444 void Accept(ModelVisitor* const visitor) const override {

445 visitor->BeginVisitConstraint(ModelVisitor::kCircuit, this);

446 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,

447 nexts_);

448 visitor->VisitIntegerArgument(ModelVisitor::kPartialArgument, sub_circuit_);

449 visitor->EndVisitConstraint(ModelVisitor::kCircuit, this);

450 }

451

452 private:

453 bool Inactive(int index) const {

454 return nexts_[index]->Bound() && nexts_[index]->Min() == index;

455 }

456

457 void NextBound(int index) {

458 Solver* const s = solver();

459 const int destination = nexts_[index]->Value();

460 const int root = root_.Value();

461 if (destination != index) {

462 if (root == -1) {

463 root_.SetValue(s, index);

464 }

465 const int new_end = ends_.Value(destination);

466 const int new_start = starts_.Value(index);

467 starts_.SetValue(s, new_end, new_start);

468 ends_.SetValue(s, new_start, new_end);

469 lengths_.SetValue(

470 s, new_start,

471 lengths_.Value(new_start) + lengths_.Value(destination));

472 if (sub_circuit_) {

473

474 nexts_[destination]->RemoveValue(destination);

475 } else {

476 if (lengths_.Value(new_start) < size_ - 1 - num_inactives_.Value()) {

477 nexts_[new_end]->RemoveValue(new_start);

478 }

479 }

480 } else {

481 num_inactives_.Incr(solver());

482 }

483

484

485

486

487

488

489

490

491 }

492

493 void NextDomain(int index) {

494 if (root_.Value() == -1) {

495 return;

496 }

497 if (!nexts_[index]->Contains(outbound_support_[index])) {

498 EnqueueDelayedDemon(outbound_demon_);

499 }

500 if (!nexts_[index]->Contains(inbound_support_[index])) {

501 EnqueueDelayedDemon(inbound_demon_);

502 }

503 }

504

505 void TryInsertReached(int candidate, int64_t after) {

506 if (!reached_[after]) {

507 reached_[after] = true;

508 insertion_queue_.push_back(after);

509 temp_support_[candidate] = after;

510 }

511 }

512

513 void CheckReachabilityFromRoot() {

514 if (root_.Value() == -1) {

515 return;

516 }

517

518

519 temp_support_.assign(size_, -1);

520

521 int processed = 0;

522 reached_.assign(size_, false);

523 insertion_queue_.clear();

524

525 const int root_value = root_.Value();

526 reached_[root_value] = true;

527 insertion_queue_.push_back(root_value);

528

529 while (processed < insertion_queue_.size() &&

530 insertion_queue_.size() + num_inactives_.Value() < size_) {

531 const int candidate = insertion_queue_[processed++];

532 IntVar* const var = nexts_[candidate];

533 switch (var->Size()) {

534 case 1: {

535 TryInsertReached(candidate, var->Min());

536 break;

537 }

538 case 2: {

539 TryInsertReached(candidate, var->Min());

540 TryInsertReached(candidate, var->Max());

541 break;

542 }

543 default: {

544 IntVarIterator* const domain = domains_[candidate];

545 for (const int64_t value : InitAndGetValues(domain)) {

546 TryInsertReached(candidate, value);

547 }

548 }

549 }

550 }

551

552

553 for (int i = 0; i < size_; ++i) {

554 if (!reached_[i]) {

555 nexts_[i]->SetValue(i);

556 }

557 }

558

559 outbound_support_.swap(temp_support_);

560 }

561

562 void CheckReachabilityToRoot() {

563

564 if (root_.Value() == -1) {

565 return;

566 }

567

568 insertion_queue_.clear();

569 insertion_queue_.push_back(root_.Value());

570 temp_support_[root_.Value()] = nexts_[root_.Value()]->Min();

571 int processed = 0;

572 to_visit_.clear();

573 for (int i = 0; i < size_; ++i) {

574 if (!Inactive(i) && i != root_.Value()) {

575 to_visit_.push_back(i);

576 }

577 }

578 const int inactive = num_inactives_.Value();

579 while (processed < insertion_queue_.size() &&

580 insertion_queue_.size() + inactive < size_) {

581 const int inserted = insertion_queue_[processed++];

582 std::vector<int> rejected;

583 for (int index = 0; index < to_visit_.size(); ++index) {

584 const int candidate = to_visit_[index];

585 if (nexts_[candidate]->Contains(inserted)) {

586 insertion_queue_.push_back(candidate);

587 temp_support_[candidate] = inserted;

588 } else {

589 rejected.push_back(candidate);

590 }

591 }

592 to_visit_.swap(rejected);

593 }

594 for (int i = 0; i < to_visit_.size(); ++i) {

595 const int node = to_visit_[i];

596 nexts_[node]->SetValue(node);

597 }

598 temp_support_.swap(inbound_support_);

599 }

600

601 const std::vector<IntVar*> nexts_;

602 const int size_;

603 std::vector<int> insertion_queue_;

604 std::vector<int> to_visit_;

605 std::vector<bool> reached_;

606 RevArray<int> starts_;

607 RevArray<int> ends_;

608 RevArray<int> lengths_;

609 std::vector<IntVarIterator*> domains_;

610 std::vector<int> outbound_support_;

611 std::vector<int> inbound_support_;

612 std::vector<int> temp_support_;

613 Demon* inbound_demon_;

614 Demon* outbound_demon_;

615 Rev<int> root_;

616 NumericalRev<int> num_inactives_;

617 const bool sub_circuit_;

618};

619}

620

633

639

640

644

648

649

650

651namespace {

652class BasePathCumul : public Constraint {

653 public:

654 BasePathCumul(Solver* s, const std::vector<IntVar*>& nexts,

655 const std::vector<IntVar*>& active,

656 const std::vector<IntVar*>& cumuls);

657 ~BasePathCumul() override {}

658 void Post() override;

659 void InitialPropagate() override;

660 void ActiveBound(int index);

661 virtual void NextBound(int index) = 0;

662 virtual bool AcceptLink(int i, int j) const = 0;

663 void UpdateSupport(int index);

664 void CumulRange(int index);

665 std::string DebugString() const override;

666

667 protected:

668 int64_t size() const { return nexts_.size(); }

669 int cumul_size() const { return cumuls_.size(); }

670

671 const std::vector<IntVar*> nexts_;

672 const std::vector<IntVar*> active_;

673 const std::vector<IntVar*> cumuls_;

674 RevArray<int> prevs_;

675 std::vector<int> supports_;

676};

677

678BasePathCumul::BasePathCumul(Solver* const s, const std::vector<IntVar*>& nexts,

679 const std::vector<IntVar*>& active,

680 const std::vector<IntVar*>& cumuls)

682 nexts_(nexts),

683 active_(active),

684 cumuls_(cumuls),

685 prevs_(cumuls.size(), -1),

686 supports_(nexts.size()) {

687 CHECK_GE(cumul_size(), size());

688 for (int i = 0; i < size(); ++i) {

689 supports_[i] = -1;

690 }

691}

692

693void BasePathCumul::InitialPropagate() {

694 for (int i = 0; i < size(); ++i) {

695 if (nexts_[i]->Bound()) {

696 NextBound(i);

697 } else {

698 UpdateSupport(i);

699 }

700 }

701}

702

703void BasePathCumul::Post() {

704 for (int i = 0; i < size(); ++i) {

705 IntVar* var = nexts_[i];

707 "NextBound", i);

708 var->WhenBound(d);

710 solver(), this, &BasePathCumul::UpdateSupport, "UpdateSupport", i);

711 var->WhenDomain(ds);

713 solver(), this, &BasePathCumul::ActiveBound, "ActiveBound", i);

714 active_[i]->WhenBound(active_demon);

715 }

716 for (int i = 0; i < cumul_size(); ++i) {

717 IntVar* cumul = cumuls_[i];

719 "CumulRange", i);

720 cumul->WhenRange(d);

721 }

722}

723

724void BasePathCumul::ActiveBound(int index) {

725 if (nexts_[index]->Bound()) {

726 NextBound(index);

727 }

728}

729

730void BasePathCumul::CumulRange(int index) {

731 if (index < size()) {

732 if (nexts_[index]->Bound()) {

733 NextBound(index);

734 } else {

735 UpdateSupport(index);

736 }

737 }

738 if (prevs_[index] >= 0) {

739 NextBound(prevs_[index]);

740 } else {

741 for (int i = 0; i < size(); ++i) {

742 if (index == supports_[i]) {

743 UpdateSupport(i);

744 }

745 }

746 }

747}

748

749void BasePathCumul::UpdateSupport(int index) {

750 int support = supports_[index];

751 if (support < 0 || !AcceptLink(index, support)) {

752 IntVar* var = nexts_[index];

753 for (int i = var->Min(); i <= var->Max(); ++i) {

754 if (i != support && AcceptLink(index, i)) {

755 supports_[index] = i;

756 return;

757 }

758 }

759 active_[index]->SetMax(0);

760 }

761}

762

763std::string BasePathCumul::DebugString() const {

764 std::string out = "PathCumul(";

765 for (int i = 0; i < size(); ++i) {

766 out += nexts_[i]->DebugString() + " " + cumuls_[i]->DebugString();

767 }

768 out += ")";

769 return out;

770}

771

772

773

774class PathCumul : public BasePathCumul {

775 public:

776 PathCumul(Solver* const s, const std::vector<IntVar*>& nexts,

777 const std::vector<IntVar*>& active,

778 const std::vector<IntVar*>& cumuls,

779 const std::vector<IntVar*>& transits)

780 : BasePathCumul(s, nexts, active, cumuls), transits_(transits) {}

781 ~PathCumul() override {}

782 void Post() override;

783 void NextBound(int index) override;

784 bool AcceptLink(int i, int j) const override;

785 void TransitRange(int index);

786

787 void Accept(ModelVisitor* const visitor) const override {

788 visitor->BeginVisitConstraint(ModelVisitor::kPathCumul, this);

789 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,

790 nexts_);

791 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kActiveArgument,

792 active_);

793 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCumulsArgument,

794 cumuls_);

795 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kTransitsArgument,

796 transits_);

797 visitor->EndVisitConstraint(ModelVisitor::kPathCumul, this);

798 }

799

800 private:

801 const std::vector<IntVar*> transits_;

802};

803

804void PathCumul::Post() {

805 BasePathCumul::Post();

806 for (int i = 0; i < size(); ++i) {

808 solver(), this, &PathCumul::TransitRange, "TransitRange", i);

809 transits_[i]->WhenRange(transit_demon);

810 }

811}

812

813void PathCumul::NextBound(int index) {

814 if (active_[index]->Min() == 0) return;

815 const int64_t next = nexts_[index]->Value();

816 IntVar* cumul = cumuls_[index];

817 IntVar* cumul_next = cumuls_[next];

818 IntVar* transit = transits_[index];

819 cumul_next->SetMin(cumul->Min() + transit->Min());

820 cumul_next->SetMax(CapAdd(cumul->Max(), transit->Max()));

821 cumul->SetMin(CapSub(cumul_next->Min(), transit->Max()));

822 cumul->SetMax(CapSub(cumul_next->Max(), transit->Min()));

823 transit->SetMin(CapSub(cumul_next->Min(), cumul->Max()));

824 transit->SetMax(CapSub(cumul_next->Max(), cumul->Min()));

825 if (prevs_[next] < 0) {

826 prevs_.SetValue(solver(), next, index);

827 }

828}

829

830void PathCumul::TransitRange(int index) {

831 if (nexts_[index]->Bound()) {

832 NextBound(index);

833 } else {

834 UpdateSupport(index);

835 }

836 if (prevs_[index] >= 0) {

837 NextBound(prevs_[index]);

838 } else {

839 for (int i = 0; i < size(); ++i) {

840 if (index == supports_[i]) {

841 UpdateSupport(i);

842 }

843 }

844 }

845}

846

847bool PathCumul::AcceptLink(int i, int j) const {

848 const IntVar* const cumul_i = cumuls_[i];

849 const IntVar* const cumul_j = cumuls_[j];

850 const IntVar* const transit_i = transits_[i];

851 return transit_i->Min() <= CapSub(cumul_j->Max(), cumul_i->Min()) &&

852 CapSub(cumul_j->Min(), cumul_i->Max()) <= transit_i->Max();

853}

854

855namespace {

856template <class T>

857class StampedVector {

858 public:

859 StampedVector() : stamp_(0) {}

860 const std::vector<T>& Values(Solver* solver) {

861 CheckStamp(solver);

862 return values_;

863 }

864 void PushBack(Solver* solver, const T& value) {

865 CheckStamp(solver);

866 values_.push_back(value);

867 }

868 void Clear(Solver* solver) {

869 values_.clear();

870 stamp_ = solver->fail_stamp();

871 }

872

873 private:

874 void CheckStamp(Solver* solver) {

875 if (solver->fail_stamp() > stamp_) {

876 Clear(solver);

877 }

878 }

879

880 std::vector<T> values_;

881 uint64_t stamp_;

882};

883}

884

885class DelayedPathCumul : public Constraint {

886 public:

887 DelayedPathCumul(Solver* const solver, const std::vector<IntVar*>& nexts,

888 const std::vector<IntVar*>& active,

889 const std::vector<IntVar*>& cumuls,

890 const std::vector<IntVar*>& transits)

891 : Constraint(solver),

892 nexts_(nexts),

893 active_(active),

894 cumuls_(cumuls),

895 transits_(transits),

896 cumul_transit_demons_(cumuls.size(), nullptr),

897 path_demon_(nullptr),

898 touched_(),

899 chain_starts_(cumuls.size(), -1),

900 chain_ends_(cumuls.size(), -1),

901 is_chain_start_(cumuls.size(), false),

902 prevs_(cumuls.size(), -1),

903 supports_(nexts.size()),

904 was_bound_(nexts.size(), false),

905 has_cumul_demon_(cumuls.size(), false) {

906 for (int64_t i = 0; i < cumuls_.size(); ++i) {

908 solver, this, &DelayedPathCumul::CumulRange, "CumulRange", i);

909 chain_starts_[i] = i;

910 chain_ends_[i] = i;

911 }

913 solver, this, &DelayedPathCumul::PropagatePaths, "PropagatePaths");

914 for (int i = 0; i < nexts_.size(); ++i) {

915 supports_[i] = -1;

916 }

917 }

918 ~DelayedPathCumul() override {}

919 void Post() override {

920 solver()->RegisterDemon(path_demon_);

921 for (int i = 0; i < nexts_.size(); ++i) {

922 if (!nexts_[i]->Bound()) {

924 solver(), this, &DelayedPathCumul::NextBound, "NextBound", i);

925 nexts_[i]->WhenBound(demon);

926 }

927 }

928 for (int i = 0; i < active_.size(); ++i) {

929 if (!active_[i]->Bound()) {

931 solver(), this, &DelayedPathCumul::ActiveBound, "ActiveBound", i);

932 active_[i]->WhenBound(demon);

933 }

934 }

935 }

936 void InitialPropagate() override {

937 touched_.Clear(solver());

938 for (int i = 0; i < nexts_.size(); ++i) {

939 if (nexts_[i]->Bound()) {

940 NextBound(i);

941 }

942 }

943 for (int i = 0; i < active_.size(); ++i) {

944 if (active_[i]->Bound()) {

945 ActiveBound(i);

946 }

947 }

948 }

949

950

951 void NextBound(int index) {

952 if (active_[index]->Min() > 0) {

953 const int next = nexts_[index]->Min();

954 PropagateLink(index, next);

955 touched_.PushBack(solver(), index);

956 EnqueueDelayedDemon(path_demon_);

957 }

958 }

959 void ActiveBound(int index) {

960 if (nexts_[index]->Bound()) {

961 NextBound(index);

962 }

963 }

964 void PropagatePaths() {

965

966 const std::vector<int>& touched_values = touched_.Values(solver());

967 for (const int touched : touched_values) {

968 chain_starts_[touched] = touched;

969 chain_ends_[touched] = touched;

970 is_chain_start_[touched] = false;

971 const int next = nexts_[touched]->Min();

972 chain_starts_[next] = next;

973 chain_ends_[next] = next;

974 is_chain_start_[next] = false;

975 }

976 for (const int touched : touched_values) {

977 if (touched >= nexts_.size()) continue;

978 IntVar* const next_var = nexts_[touched];

979 if (!was_bound_[touched] && next_var->Bound() &&

980 active_[touched]->Min() > 0) {

981 const int64_t next = next_var->Min();

982 was_bound_.SetValue(solver(), touched, true);

983 chain_starts_[chain_ends_[next]] = chain_starts_[touched];

984 chain_ends_[chain_starts_[touched]] = chain_ends_[next];

985 is_chain_start_[next] = false;

986 is_chain_start_[chain_starts_[touched]] = true;

987 }

988 }

989

990 for (const int touched : touched_values) {

991

992 if (is_chain_start_[touched]) {

993

994 int64_t current = touched;

995 int64_t next = nexts_[current]->Min();

996 while (current != chain_ends_[touched]) {

997 prevs_.SetValue(solver(), next, current);

998 PropagateLink(current, next);

999 current = next;

1000 if (current != chain_ends_[touched]) {

1001 next = nexts_[current]->Min();

1002 }

1003 }

1004

1005 int64_t prev = prevs_[current];

1006 while (current != touched) {

1007 PropagateLink(prev, current);

1008 current = prev;

1009 if (current != touched) {

1010 prev = prevs_[current];

1011 }

1012 }

1013

1014

1015

1016 current = touched;

1017 while (current != chain_ends_[touched]) {

1018 if (!has_cumul_demon_[current]) {

1019 Demon* const demon = cumul_transit_demons_[current];

1020 cumuls_[current]->WhenRange(demon);

1021 transits_[current]->WhenRange(demon);

1022 has_cumul_demon_.SetValue(solver(), current, true);

1023 }

1024 current = nexts_[current]->Min();

1025 }

1026 if (!has_cumul_demon_[current]) {

1027 Demon* const demon = cumul_transit_demons_[current];

1028 cumuls_[current]->WhenRange(demon);

1029 if (current < transits_.size()) {

1030 transits_[current]->WhenRange(demon);

1031 UpdateSupport(current);

1032 }

1033 has_cumul_demon_.SetValue(solver(), current, true);

1034 }

1035 }

1036 }

1037 touched_.Clear(solver());

1038 }

1039

1040 void Accept(ModelVisitor* const visitor) const override {

1041 visitor->BeginVisitConstraint(ModelVisitor::kDelayedPathCumul, this);

1042 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,

1043 nexts_);

1044 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kActiveArgument,

1045 active_);

1046 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCumulsArgument,

1047 cumuls_);

1048 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kTransitsArgument,

1049 transits_);

1050 visitor->EndVisitConstraint(ModelVisitor::kDelayedPathCumul, this);

1051 }

1052

1053 std::string DebugString() const override {

1054 std::string out = "DelayedPathCumul(";

1055 for (int i = 0; i < nexts_.size(); ++i) {

1056 out += nexts_[i]->DebugString() + " " + cumuls_[i]->DebugString();

1057 }

1058 out += ")";

1059 return out;

1060 }

1061

1062 private:

1063 void CumulRange(int64_t index) {

1064 if (index < nexts_.size()) {

1065 if (nexts_[index]->Bound()) {

1066 if (active_[index]->Min() > 0) {

1067 PropagateLink(index, nexts_[index]->Min());

1068 }

1069 } else {

1070 UpdateSupport(index);

1071 }

1072 }

1073 if (prevs_[index] >= 0) {

1074 PropagateLink(prevs_[index], index);

1075 } else {

1076 for (int i = 0; i < nexts_.size(); ++i) {

1077 if (index == supports_[i]) {

1078 UpdateSupport(i);

1079 }

1080 }

1081 }

1082 }

1083 void UpdateSupport(int index) {

1084 int support = supports_[index];

1085 if (support < 0 || !AcceptLink(index, support)) {

1086 IntVar* const next = nexts_[index];

1087 for (int i = next->Min(); i <= next->Max(); ++i) {

1088 if (i != support && AcceptLink(index, i)) {

1089 supports_[index] = i;

1090 return;

1091 }

1092 }

1093 active_[index]->SetMax(0);

1094 }

1095 }

1096 void PropagateLink(int64_t index, int64_t next) {

1097 IntVar* const cumul_var = cumuls_[index];

1098 IntVar* const next_cumul_var = cumuls_[next];

1099 IntVar* const transit = transits_[index];

1100 const int64_t transit_min = transit->Min();

1101 const int64_t transit_max = transit->Max();

1102 next_cumul_var->SetMin(CapAdd(cumul_var->Min(), transit_min));

1103 next_cumul_var->SetMax(CapAdd(cumul_var->Max(), transit_max));

1104 const int64_t next_cumul_min = next_cumul_var->Min();

1105 const int64_t next_cumul_max = next_cumul_var->Max();

1106 cumul_var->SetMin(CapSub(next_cumul_min, transit_max));

1107 cumul_var->SetMax(CapSub(next_cumul_max, transit_min));

1108 transit->SetMin(CapSub(next_cumul_min, cumul_var->Max()));

1109 transit->SetMax(CapSub(next_cumul_max, cumul_var->Min()));

1110 }

1111 bool AcceptLink(int index, int next) const {

1112 IntVar* const cumul_var = cumuls_[index];

1113 IntVar* const next_cumul_var = cumuls_[next];

1114 IntVar* const transit = transits_[index];

1115 return transit->Min() <= CapSub(next_cumul_var->Max(), cumul_var->Min()) &&

1116 CapSub(next_cumul_var->Min(), cumul_var->Max()) <= transit->Max();

1117 }

1118

1119 const std::vector<IntVar*> nexts_;

1120 const std::vector<IntVar*> active_;

1121 const std::vector<IntVar*> cumuls_;

1122 const std::vector<IntVar*> transits_;

1123 std::vector<Demon*> cumul_transit_demons_;

1124 Demon* path_demon_;

1125 StampedVector<int> touched_;

1126 std::vector<int64_t> chain_starts_;

1127 std::vector<int64_t> chain_ends_;

1128 std::vector<bool> is_chain_start_;

1129 RevArray<int> prevs_;

1130 std::vector<int> supports_;

1131 RevArray<bool> was_bound_;

1132 RevArray<bool> has_cumul_demon_;

1133};

1134

1135

1136

1137class IndexEvaluator2PathCumul : public BasePathCumul {

1138 public:

1139 IndexEvaluator2PathCumul(Solver* s, const std::vector<IntVar*>& nexts,

1140 const std::vector<IntVar*>& active,

1141 const std::vector<IntVar*>& cumuls,

1142 Solver::IndexEvaluator2 transit_evaluator);

1143 ~IndexEvaluator2PathCumul() override {}

1144 void NextBound(int index) override;

1145 bool AcceptLink(int i, int j) const override;

1146

1147 void Accept(ModelVisitor* const visitor) const override {

1148 visitor->BeginVisitConstraint(ModelVisitor::kPathCumul, this);

1149 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,

1150 nexts_);

1151 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kActiveArgument,

1152 active_);

1153 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCumulsArgument,

1154 cumuls_);

1155

1156

1157

1158

1159 visitor->EndVisitConstraint(ModelVisitor::kPathCumul, this);

1160 }

1161

1162 private:

1163 Solver::IndexEvaluator2 transits_evaluator_;

1164};

1165

1166IndexEvaluator2PathCumul::IndexEvaluator2PathCumul(

1167 Solver* const s, const std::vector<IntVar*>& nexts,

1168 const std::vector<IntVar*>& active, const std::vector<IntVar*>& cumuls,

1170 : BasePathCumul(s, nexts, active, cumuls),

1171 transits_evaluator_(std::move(transit_evaluator)) {}

1172

1173void IndexEvaluator2PathCumul::NextBound(int index) {

1174 if (active_[index]->Min() == 0) return;

1175 const int64_t next = nexts_[index]->Value();

1176 IntVar* cumul = cumuls_[index];

1177 IntVar* cumul_next = cumuls_[next];

1178 const int64_t transit = transits_evaluator_(index, next);

1179 cumul_next->SetMin(cumul->Min() + transit);

1180 cumul_next->SetMax(CapAdd(cumul->Max(), transit));

1181 cumul->SetMin(CapSub(cumul_next->Min(), transit));

1182 cumul->SetMax(CapSub(cumul_next->Max(), transit));

1183 if (prevs_[next] < 0) {

1184 prevs_.SetValue(solver(), next, index);

1185 }

1186}

1187

1188bool IndexEvaluator2PathCumul::AcceptLink(int i, int j) const {

1189 const IntVar* const cumul_i = cumuls_[i];

1190 const IntVar* const cumul_j = cumuls_[j];

1191 const int64_t transit = transits_evaluator_(i, j);

1192 return transit <= CapSub(cumul_j->Max(), cumul_i->Min()) &&

1193 CapSub(cumul_j->Min(), cumul_i->Max()) <= transit;

1194}

1195

1196

1197

1198class IndexEvaluator2SlackPathCumul : public BasePathCumul {

1199 public:

1200 IndexEvaluator2SlackPathCumul(Solver* s, const std::vector<IntVar*>& nexts,

1201 const std::vector<IntVar*>& active,

1202 const std::vector<IntVar*>& cumuls,

1203 const std::vector<IntVar*>& slacks,

1204 Solver::IndexEvaluator2 transit_evaluator);

1205 ~IndexEvaluator2SlackPathCumul() override {}

1206 void Post() override;

1207 void NextBound(int index) override;

1208 bool AcceptLink(int i, int j) const override;

1209 void SlackRange(int index);

1210

1211 void Accept(ModelVisitor* const visitor) const override {

1212 visitor->BeginVisitConstraint(ModelVisitor::kPathCumul, this);

1213 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kNextsArgument,

1214 nexts_);

1215 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kActiveArgument,

1216 active_);

1217 visitor->VisitIntegerVariableArrayArgument(ModelVisitor::kCumulsArgument,

1218 cumuls_);

1219

1220

1221

1222

1223 visitor->EndVisitConstraint(ModelVisitor::kPathCumul, this);

1224 }

1225

1226 private:

1227 const std::vector<IntVar*> slacks_;

1228 Solver::IndexEvaluator2 transits_evaluator_;

1229};

1230

1231IndexEvaluator2SlackPathCumul::IndexEvaluator2SlackPathCumul(

1232 Solver* const s, const std::vector<IntVar*>& nexts,

1233 const std::vector<IntVar*>& active, const std::vector<IntVar*>& cumuls,

1234 const std::vector<IntVar*>& slacks,

1236 : BasePathCumul(s, nexts, active, cumuls),

1237 slacks_(slacks),

1238 transits_evaluator_(std::move(transit_evaluator)) {}

1239

1240void IndexEvaluator2SlackPathCumul::Post() {

1241 BasePathCumul::Post();

1242 for (int i = 0; i < size(); ++i) {

1244 solver(), this, &IndexEvaluator2SlackPathCumul::SlackRange,

1245 "SlackRange", i);

1246 slacks_[i]->WhenRange(slack_demon);

1247 }

1248}

1249

1250void IndexEvaluator2SlackPathCumul::SlackRange(int index) {

1251 if (nexts_[index]->Bound()) {

1252 NextBound(index);

1253 } else {

1254 UpdateSupport(index);

1255 }

1256 if (prevs_[index] >= 0) {

1257 NextBound(prevs_[index]);

1258 } else {

1259 for (int i = 0; i < size(); ++i) {

1260 if (index == supports_[i]) {

1261 UpdateSupport(i);

1262 }

1263 }

1264 }

1265}

1266

1267void IndexEvaluator2SlackPathCumul::NextBound(int index) {

1268 if (active_[index]->Min() == 0) return;

1269 const int64_t next = nexts_[index]->Value();

1270 IntVar* const cumul = cumuls_[index];

1271 IntVar* const cumul_next = cumuls_[next];

1272 IntVar* const slack = slacks_[index];

1273 const int64_t transit = transits_evaluator_(index, next);

1274 const int64_t cumul_next_minus_transit_min =

1275 CapSub(cumul_next->Min(), transit);

1276 const int64_t cumul_next_minus_transit_max =

1277 CapSub(cumul_next->Max(), transit);

1278 cumul_next->SetMin(CapAdd(CapAdd(cumul->Min(), transit), slack->Min()));

1279 cumul_next->SetMax(CapAdd(CapAdd(cumul->Max(), transit), slack->Max()));

1280 cumul->SetMin(CapSub(cumul_next_minus_transit_min, slack->Max()));

1281 cumul->SetMax(CapSub(cumul_next_minus_transit_max, slack->Min()));

1282 slack->SetMin(CapSub(cumul_next_minus_transit_min, cumul->Max()));

1283 slack->SetMax(CapSub(cumul_next_minus_transit_max, cumul->Min()));

1284 if (prevs_[next] < 0) {

1285 prevs_.SetValue(solver(), next, index);

1286 }

1287}

1288

1289bool IndexEvaluator2SlackPathCumul::AcceptLink(int i, int j) const {

1290 const IntVar* const cumul_i = cumuls_[i];

1291 const IntVar* const cumul_j = cumuls_[j];

1292 const IntVar* const slack = slacks_[i];

1293 const int64_t transit = transits_evaluator_(i, j);

1294 return CapAdd(transit, slack->Min()) <=

1295 CapSub(cumul_j->Max(), cumul_i->Min()) &&

1296 CapSub(cumul_j->Min(), cumul_i->Max()) <=

1297 CapAdd(slack->Max(), transit);

1298}

1299}

1300

1309

1318

1328

1337

1338

1339

1340namespace {

1341class PathConnectedConstraint : public Constraint {

1342 public:

1343 PathConnectedConstraint(Solver* solver, std::vector<IntVar*> nexts,

1344 absl::Span<const int64_t> sources,

1345 std::vector<int64_t> sinks,

1346 std::vector<IntVar*> status)

1348 sources_(sources.size(), -1),

1349 index_to_path_(nexts.size(), -1),

1350 sinks_(std::move(sinks)),

1351 nexts_(std::move(nexts)),

1352 status_(std::move(status)),

1353 touched_(nexts_.size()) {

1354 CHECK_EQ(status_.size(), sources_.size());

1355 CHECK_EQ(status_.size(), sinks_.size());

1356 for (int i = 0; i < status_.size(); ++i) {

1357 const int64_t source = sources[i];

1358 sources_.SetValue(solver, i, source);

1359 if (source < index_to_path_.size()) {

1360 index_to_path_.SetValue(solver, source, i);

1361 }

1362 }

1363 }

1364 void Post() override {

1365 for (int i = 0; i < nexts_.size(); ++i) {

1367 solver(), this, &PathConnectedConstraint::NextBound, "NextValue", i));

1368 }

1369 for (int i = 0; i < status_.size(); ++i) {

1370 if (sources_[i] < nexts_.size()) {

1371 status_[i]->SetRange(0, 1);

1372 } else {

1373 status_[i]->SetValue(0);

1374 }

1375 }

1376 }

1377 void InitialPropagate() override {

1378 for (int i = 0; i < status_.size(); ++i) {

1379 EvaluatePath(i);

1380 }

1381 }

1382 std::string DebugString() const override {

1383 std::string output = "PathConnected(";

1384 std::vector<std::string> elements;

1385 for (IntVar* const next : nexts_) {

1386 elements.push_back(next->DebugString());

1387 }

1388 for (int i = 0; i < sources_.size(); ++i) {

1389 elements.push_back(absl::StrCat(sources_[i]));

1390 }

1391 for (int64_t sink : sinks_) {

1392 elements.push_back(absl::StrCat(sink));

1393 }

1394 for (IntVar* const status : status_) {

1395 elements.push_back(status->DebugString());

1396 }

1397 output += absl::StrJoin(elements, ",") + ")";

1398 return output;

1399 }

1400

1401 private:

1402 void NextBound(int index) {

1403 const int path = index_to_path_[index];

1404 if (path >= 0) {

1405 EvaluatePath(path);

1406 }

1407 }

1408 void EvaluatePath(int path) {

1410 int64_t source = sources_[path];

1411 const int64_t end = sinks_[path];

1412 while (source != end) {

1413 if (source >= nexts_.size() || touched_[source]) {

1414 status_[path]->SetValue(0);

1415 return;

1416 }

1417 touched_.Set(source);

1418 IntVar* const next = nexts_[source];

1419 if (next->Bound()) {

1420 source = next->Min();

1421 } else {

1422 sources_.SetValue(solver(), path, source);

1423 index_to_path_.SetValue(solver(), source, path);

1424 return;

1425 }

1426 }

1427 status_[path]->SetValue(1);

1428 }

1429

1430 RevArray<int64_t> sources_;

1431 RevArray<int> index_to_path_;

1432 const std::vector<int64_t> sinks_;

1433 const std::vector<IntVar*> nexts_;

1434 const std::vector<IntVar*> status_;

1435 SparseBitset<int64_t> touched_;

1436};

1437}

1438

1446

1447namespace {

1448class PathTransitPrecedenceConstraint : public Constraint {

1449 public:

1450 enum PrecedenceType {

1451 ANY,

1452 LIFO,

1453 FIFO,

1454 };

1455 PathTransitPrecedenceConstraint(

1456 Solver* solver, std::vector<IntVar*> nexts, std::vector<IntVar*> transits,

1457 absl::Span<const std::pair<int, int>> precedences,

1458 absl::flat_hash_map<int, PrecedenceType> precedence_types)

1460 nexts_(std::move(nexts)),

1461 transits_(std::move(transits)),

1462 predecessors_(nexts_.size()),

1463 successors_(nexts_.size()),

1464 precedence_types_(std::move(precedence_types)),

1465 starts_(nexts_.size(), -1),

1466 ends_(nexts_.size(), -1),

1467 transit_cumuls_(nexts_.size(), 0) {

1468 for (int i = 0; i < nexts_.size(); ++i) {

1469 starts_.SetValue(solver, i, i);

1470 ends_.SetValue(solver, i, i);

1471 }

1472 for (const auto& precedence : precedences) {

1473 if (precedence.second < nexts_.size()) {

1474 predecessors_[precedence.second].push_back(precedence.first);

1475 }

1476 if (precedence.first < nexts_.size()) {

1477 successors_[precedence.first].push_back(precedence.second);

1478 }

1479 }

1480 }

1481 ~PathTransitPrecedenceConstraint() override {}

1482 void Post() override {

1483 for (int i = 0; i < nexts_.size(); ++i) {

1485 solver(), this, &PathTransitPrecedenceConstraint::NextBound,

1486 "NextBound", i));

1487 }

1488 for (int i = 0; i < transits_.size(); ++i) {

1490 solver(), this, &PathTransitPrecedenceConstraint::NextBound,

1491 "TransitRange", i));

1492 }

1493 }

1494 void InitialPropagate() override {

1495 for (int i = 0; i < nexts_.size(); ++i) {

1496 if (nexts_[i]->Bound()) {

1497 NextBound(i);

1498 }

1499 }

1500 }

1501 std::string DebugString() const override {

1502 std::string output = "PathPrecedence(";

1503 std::vector<std::string> elements = {JoinDebugStringPtr(nexts_, ",")};

1504 if (!transits_.empty()) {

1506 }

1507 for (int i = 0; i < predecessors_.size(); ++i) {

1508 for (const int predecessor : predecessors_[i]) {

1509 elements.push_back(absl::StrCat("(", predecessor, ", ", i, ")"));

1510 }

1511 }

1512 output += absl::StrJoin(elements, ",") + ")";

1513 return output;

1514 }

1515 void Accept(ModelVisitor* const visitor) const override {

1516

1517 }

1518

1519 private:

1520 void NextBound(int index) {

1521 if (!nexts_[index]->Bound()) return;

1522 const int next = nexts_[index]->Min();

1523 const int start = starts_[index];

1524 const int end = (next < nexts_.size()) ? ends_[next] : next;

1525 if (end < nexts_.size()) starts_.SetValue(solver(), end, start);

1526 ends_.SetValue(solver(), start, end);

1527 int current = start;

1528 PrecedenceType type = ANY;

1529 auto it = precedence_types_.find(start);

1530 if (it != precedence_types_.end()) {

1531 type = it->second;

1532 }

1533 forbidden_.clear();

1534 marked_.clear();

1535 pushed_.clear();

1536 int64_t transit_cumul = 0;

1537 const bool has_transits = !transits_.empty();

1538 while (current < nexts_.size() && current != end) {

1539 transit_cumuls_[current] = transit_cumul;

1540 marked_.insert(current);

1541

1542 if (!predecessors_[current].empty() && !pushed_.empty()) {

1543 bool found = false;

1544

1545 for (const int predecessor : predecessors_[current]) {

1546 if (pushed_.back() == predecessor) {

1547 found = true;

1548 break;

1549 }

1550 }

1551 if (!found) solver()->Fail();

1552 pushed_.pop_back();

1553 }

1554 if (forbidden_.find(current) != forbidden_.end()) {

1555 for (const int successor : successors_[current]) {

1556 if (marked_.find(successor) != marked_.end()) {

1557 if (!has_transits ||

1558 CapSub(transit_cumul, transit_cumuls_[successor]) > 0) {

1559 solver()->Fail();

1560 }

1561 }

1562 }

1563 }

1564 if (!successors_[current].empty()) {

1565 switch (type) {

1566 case LIFO:

1567 pushed_.push_back(current);

1568 break;

1569 case FIFO:

1570 pushed_.push_front(current);

1571 break;

1572 case ANY:

1573 break;

1574 }

1575 }

1576 for (const int predecessor : predecessors_[current]) {

1577 forbidden_.insert(predecessor);

1578 }

1579 if (has_transits) {

1580 transit_cumul = CapAdd(transit_cumul, transits_[current]->Min());

1581 }

1582 current = nexts_[current]->Min();

1583 }

1584 if (forbidden_.find(current) != forbidden_.end()) {

1585 for (const int successor : successors_[current]) {

1586 if (marked_.find(successor) != marked_.end()) {

1587 if (!has_transits ||

1588 CapSub(transit_cumul, transit_cumuls_[successor]) > 0) {

1589 solver()->Fail();

1590 }

1591 }

1592 }

1593 }

1594 }

1595

1596 const std::vector<IntVar*> nexts_;

1597 const std::vector<IntVar*> transits_;

1598 std::vector<std::vector<int>> predecessors_;

1599 std::vector<std::vector<int>> successors_;

1600 const absl::flat_hash_map<int, PrecedenceType> precedence_types_;

1601 RevArray<int> starts_;

1602 RevArray<int> ends_;

1603 absl::flat_hash_set<int> forbidden_;

1604 absl::flat_hash_set<int> marked_;

1605 std::deque<int> pushed_;

1606 std::vector<int64_t> transit_cumuls_;

1607};

1608

1609Constraint* MakePathTransitTypedPrecedenceConstraint(

1610 Solver* solver, std::vector<IntVar*> nexts, std::vector<IntVar*> transits,

1611 absl::Span<const std::pair<int, int>> precedences,

1612 absl::flat_hash_map<int, PathTransitPrecedenceConstraint::PrecedenceType>

1613 precedence_types) {

1614 if (precedences.empty()) {

1615 return solver->MakeTrueConstraint();

1616 }

1617 return solver->RevAlloc(new PathTransitPrecedenceConstraint(

1618 solver, std::move(nexts), std::move(transits), precedences,

1619 std::move(precedence_types)));

1620}

1621

1622}

1623

1629

1646

1653

1654namespace {

1655

1656class PathEnergyCostConstraint : public Constraint {

1657 public:

1658 PathEnergyCostConstraint(

1661 : Constraint(solver), specification_(std::move(specification)) {

1662 const int num_nexts = specification_.nexts.size();

1663 DCHECK_EQ(num_nexts, specification_.distances.size());

1664

1666 DCHECK_EQ(num_paths, specification_.costs.size());

1668 DCHECK_EQ(num_paths, specification_.path_starts.size());

1669 DCHECK_EQ(num_paths, specification_.path_ends.size());

1670

1671 const int num_nodes = specification_.forces.size();

1672 DCHECK_EQ(num_nodes, specification_.paths.size());

1673 }

1674

1675 void Post() override;

1676 void InitialPropagate() override;

1677

1678 private:

1679 void NodeDispatcher(int node);

1680 void PropagatePath(int path);

1681 Solver::PathEnergyCostConstraintSpecification specification_;

1682 std::vector<Demon*> path_demons_;

1683};

1684

1685

1686

1687void PathEnergyCostConstraint::Post() {

1688

1690 path_demons_.resize(num_paths, nullptr);

1691 for (int path = 0; path < num_paths; ++path) {

1692

1693

1695 if (cost.IsNull()) continue;

1697 solver(), this, &PathEnergyCostConstraint::PropagatePath,

1698 "PropagatePath", path);

1699 }

1700

1701 const int num_nodes = specification_.forces.size();

1702 const int num_nexts = specification_.nexts.size();

1703 for (int node = 0; node < num_nodes; ++node) {

1705 solver(), this, &PathEnergyCostConstraint::NodeDispatcher,

1706 "NodeDispatcher", node);

1707 specification_.forces[node]->WhenRange(demon);

1708 specification_.paths[node]->WhenBound(demon);

1709 if (node < num_nexts) {

1710 specification_.nexts[node]->WhenBound(demon);

1711 specification_.distances[node]->WhenRange(demon);

1712 }

1713 }

1714}

1715

1716void PathEnergyCostConstraint::InitialPropagate() {

1718 for (int path = 0; path < num_paths; ++path) {

1720 if (cost.IsNull()) {

1721 specification_.costs[path]->SetValue(0);

1722 } else {

1723 PropagatePath(path);

1724 }

1725 }

1726}

1727

1728

1729void PathEnergyCostConstraint::NodeDispatcher(int node) {

1730 if (!specification_.paths[node]->Bound()) return;

1731 const int path = specification_.paths[node]->Min();

1732 if (path < 0) return;

1733 if (path_demons_[path] == nullptr) return;

1734 EnqueueDelayedDemon(path_demons_[path]);

1735}

1736

1737

1738void PathEnergyCostConstraint::PropagatePath(int path) {

1739

1740 const auto& [threshold, cost_per_unit_below, cost_per_unit_above] =

1742 int64_t energy_below_min = 0;

1743 int64_t energy_below_max = 0;

1744 int64_t energy_above_min = 0;

1745 int64_t energy_above_max = 0;

1746 int current = specification_.path_starts[path];

1747 const int num_nodes = specification_.nexts.size();

1748 int num_nonend_nodes = 0;

1749 while (current < num_nodes) {

1750 ++num_nonend_nodes;

1751 if (!specification_.nexts[current]->Bound()) break;

1752 const int next = specification_.nexts[current]->Min();

1753

1754 const int64_t distance_min = specification_.distances[current]->Min();

1755 const int64_t distance_max = specification_.distances[current]->Max();

1756 DCHECK_GE(distance_min, 0);

1757 const IntVar* force = specification_.forces[next];

1758 CapAddTo(CapProd(std::min(threshold, force->Min()), distance_min),

1759 &energy_below_min);

1760 CapAddTo(CapProd(std::min(threshold, force->Max()), distance_max),

1761 &energy_below_max);

1763 distance_min),

1764 &energy_above_min);

1766 distance_max),

1767 &energy_above_max);

1768 current = next;

1769 }

1770 if (current == specification_.path_ends[path]) {

1772 specification_.costs[path]->SetValue(0);

1773 } else {

1774 specification_.costs[path]->SetRange(

1775 CapAdd(CapProd(energy_below_min, cost_per_unit_below),

1776 CapProd(energy_above_min, cost_per_unit_above)),

1777 CapAdd(CapProd(energy_below_max, cost_per_unit_below),

1778 CapProd(energy_above_max, cost_per_unit_above)));

1779 }

1780 }

1781}

1782

1783}

1784

1789

1790}