OR-Tools  8.2
utilities.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 <string>
15
16#include "absl/container/flat_hash_map.h"
17#include "absl/container/flat_hash_set.h"
18#include "absl/strings/str_format.h"
19#include "absl/strings/str_join.h"
20#include "ortools/base/hash.h"
26#include "ortools/util/bitset.h"
27
28namespace operations_research {
29
30// ---------- SmallRevBitSet ----------
31
33 DCHECK_GT(size, 0);
34 DCHECK_LE(size, 64);
35}
36
37void SmallRevBitSet::SetToOne(Solver* const solver, int64 pos) {
38 DCHECK_GE(pos, 0);
39 bits_.SetValue(solver, bits_.Value() | OneBit64(pos));
40}
41
42void SmallRevBitSet::SetToZero(Solver* const solver, int64 pos) {
43 DCHECK_GE(pos, 0);
44 bits_.SetValue(solver, bits_.Value() & ~OneBit64(pos));
45}
46
48
50 if (bits_.Value() == 0) {
51 return -1;
52 }
54}
55
56// ---------- RevBitSet ----------
57
59 : size_(size),
60 length_(BitLength64(size)),
61 bits_(new uint64[length_]),
62 stamps_(new uint64[length_]) {
63 DCHECK_GE(size, 1);
64 memset(bits_, 0, sizeof(*bits_) * length_);
65 memset(stamps_, 0, sizeof(*stamps_) * length_);
66}
67
69 delete[] bits_;
70 delete[] stamps_;
71}
72
73void RevBitSet::Save(Solver* const solver, int offset) {
74 const uint64 current_stamp = solver->stamp();
75 if (current_stamp > stamps_[offset]) {
76 stamps_[offset] = current_stamp;
77 solver->SaveValue(&bits_[offset]);
78 }
79}
80
81void RevBitSet::SetToOne(Solver* const solver, int64 index) {
82 DCHECK_GE(index, 0);
83 DCHECK_LT(index, size_);
84 const int64 offset = BitOffset64(index);
85 const int64 pos = BitPos64(index);
86 if (!(bits_[offset] & OneBit64(pos))) {
87 Save(solver, offset);
88 bits_[offset] |= OneBit64(pos);
89 }
90}
91
92void RevBitSet::SetToZero(Solver* const solver, int64 index) {
93 DCHECK_GE(index, 0);
94 DCHECK_LT(index, size_);
95 const int64 offset = BitOffset64(index);
96 const int64 pos = BitPos64(index);
97 if (bits_[offset] & OneBit64(pos)) {
98 Save(solver, offset);
99 bits_[offset] &= ~OneBit64(pos);
100 }
101}
102
104 DCHECK_GE(index, 0);
105 DCHECK_LT(index, size_);
106 return IsBitSet64(bits_, index);
107}
108
110 int64 card = 0;
111 for (int i = 0; i < length_; ++i) {
112 card += BitCount64(bits_[i]);
113 }
114 return card;
115}
116
118 for (int i = 0; i < length_; ++i) {
119 if (bits_[i]) {
120 return false;
121 }
122 }
123 return true;
124}
125
127 bool found_one = false;
128 for (int i = 0; i < length_; ++i) {
129 const uint64 partial = bits_[i];
130 if (partial) {
131 if (!(partial & (partial - 1))) {
132 if (found_one) {
133 return false;
134 }
135 found_one = true;
136 } else {
137 return false;
138 }
139 }
140 }
141 return found_one;
142}
143
145 return LeastSignificantBitPosition64(bits_, start, size_ - 1);
146}
147
148void RevBitSet::ClearAll(Solver* const solver) {
149 for (int offset = 0; offset < length_; ++offset) {
150 if (bits_[offset]) {
151 Save(solver, offset);
152 bits_[offset] = uint64_t{0};
153 }
154 }
155}
156
157// ----- RevBitMatrix -----
158
160 : RevBitSet(rows * columns), rows_(rows), columns_(columns) {
161 DCHECK_GE(rows, 1);
162 DCHECK_GE(columns, 1);
163}
164
166
167void RevBitMatrix::SetToOne(Solver* const solver, int64 row, int64 column) {
168 DCHECK_GE(row, 0);
169 DCHECK_LT(row, rows_);
170 DCHECK_GE(column, 0);
171 DCHECK_LT(column, columns_);
172 RevBitSet::SetToOne(solver, row * columns_ + column);
173}
174
175void RevBitMatrix::SetToZero(Solver* const solver, int64 row, int64 column) {
176 DCHECK_GE(row, 0);
177 DCHECK_LT(row, rows_);
178 DCHECK_GE(column, 0);
179 DCHECK_LT(column, columns_);
180 RevBitSet::SetToZero(solver, row * columns_ + column);
181}
182
184 DCHECK_GE(row, 0);
185 DCHECK_LT(row, rows_);
186 const int start = row * columns_;
187 return BitCountRange64(bits_, start, start + columns_ - 1);
188}
189
191 // TODO(user) : Optimize this one.
192 return Cardinality(row) == 1;
193}
194
196 const int start = row * columns_;
197 return IsEmptyRange64(bits_, start, start + columns_ - 1);
198}
199
200int64 RevBitMatrix::GetFirstBit(int row, int start) const {
201 DCHECK_GE(start, 0);
202 DCHECK_GE(row, 0);
203 DCHECK_LT(row, rows_);
204 DCHECK_LT(start, columns_);
205 const int beginning = row * columns_;
206 const int end = beginning + columns_ - 1;
207 int64 position = LeastSignificantBitPosition64(bits_, beginning + start, end);
208 if (position == -1) {
209 return -1;
210 } else {
211 return position - beginning;
212 }
213}
214
215void RevBitMatrix::ClearAll(Solver* const solver) {
216 RevBitSet::ClearAll(solver);
217}
218
219// ----- UnsortedNullableRevBitset -----
220
222 : bit_size_(bit_size),
223 word_size_(BitLength64(bit_size)),
224 bits_(word_size_, 0),
225 active_words_(word_size_) {}
226
228 const std::vector<uint64>& mask) {
229 CHECK_LE(mask.size(), word_size_);
230 for (int i = 0; i < mask.size(); ++i) {
231 if (mask[i]) {
232 bits_.SetValue(solver, i, mask[i]);
233 active_words_.Insert(solver, i);
234 }
235 }
236}
237
239 const std::vector<uint64>& mask) {
240 bool changed = false;
241 to_remove_.clear();
242 for (int index : active_words_) {
243 if (index < mask.size() && (bits_[index] & mask[index]) != 0) {
244 changed = true;
245 const uint64 result = bits_[index] & ~mask[index];
246 bits_.SetValue(solver, index, result);
247 if (result == 0) {
248 to_remove_.push_back(index);
249 }
250 }
251 }
252
253 CleanUpActives(solver);
254 return changed;
255}
256
257void UnsortedNullableRevBitset::CleanUpActives(Solver* const solver) {
258 // We remove indices of null words in reverse order, as this may be a simpler
259 // operations on the RevIntSet (no actual swap).
260 for (int i = to_remove_.size() - 1; i >= 0; --i) {
261 active_words_.Remove(solver, to_remove_[i]);
262 }
263}
264
266 const std::vector<uint64>& mask) {
267 bool changed = false;
268 to_remove_.clear();
269 for (int index : active_words_) {
270 if (index < mask.size()) {
271 if ((bits_[index] & ~mask[index]) != 0) {
272 changed = true;
273 const uint64 result = bits_[index] & mask[index];
274 bits_.SetValue(solver, index, result);
275 if (result == 0) {
276 to_remove_.push_back(index);
277 }
278 }
279 } else {
280 // Zero the word as the mask is implicitely null.
281 changed = true;
282 bits_.SetValue(solver, index, 0);
283 to_remove_.push_back(index);
284 }
285 }
286 CleanUpActives(solver);
287 return changed;
288}
289
290bool UnsortedNullableRevBitset::Intersects(const std::vector<uint64>& mask,
291 int* support_index) {
292 DCHECK_GE(*support_index, 0);
293 DCHECK_LT(*support_index, word_size_);
294 if (mask[*support_index] & bits_[*support_index]) {
295 return true;
296 }
297 for (int index : active_words_) {
298 if (bits_[index] & mask[index]) {
299 *support_index = index;
300 return true;
301 }
302 }
303 return false;
304}
305
306// ----- PrintModelVisitor -----
307
308namespace {
309class PrintModelVisitor : public ModelVisitor {
310 public:
311 PrintModelVisitor() : indent_(0) {}
312 ~PrintModelVisitor() override {}
313
314 // Header/footers.
315 void BeginVisitModel(const std::string& solver_name) override {
316 LOG(INFO) << "Model " << solver_name << " {";
317 Increase();
318 }
319
320 void EndVisitModel(const std::string& solver_name) override {
321 LOG(INFO) << "}";
322 Decrease();
323 CHECK_EQ(0, indent_);
324 }
325
326 void BeginVisitConstraint(const std::string& type_name,
327 const Constraint* const constraint) override {
328 LOG(INFO) << Spaces() << type_name;
329 Increase();
330 }
331
332 void EndVisitConstraint(const std::string& type_name,
333 const Constraint* const constraint) override {
334 Decrease();
335 }
336
337 void BeginVisitIntegerExpression(const std::string& type_name,
338 const IntExpr* const expr) override {
339 LOG(INFO) << Spaces() << type_name;
340 Increase();
341 }
342
343 void EndVisitIntegerExpression(const std::string& type_name,
344 const IntExpr* const expr) override {
345 Decrease();
346 }
347
348 void BeginVisitExtension(const std::string& type_name) override {
349 LOG(INFO) << Spaces() << type_name;
350 Increase();
351 }
352
353 void EndVisitExtension(const std::string& type_name) override { Decrease(); }
354
355 void VisitIntegerVariable(const IntVar* const variable,
356 IntExpr* const delegate) override {
357 if (delegate != nullptr) {
358 delegate->Accept(this);
359 } else {
360 if (variable->Bound() && variable->name().empty()) {
361 LOG(INFO) << Spaces() << variable->Min();
362 } else {
363 LOG(INFO) << Spaces() << variable->DebugString();
364 }
365 }
366 }
367
368 void VisitIntegerVariable(const IntVar* const variable,
369 const std::string& operation, int64 value,
370 IntVar* const delegate) override {
371 LOG(INFO) << Spaces() << "IntVar";
372 Increase();
373 LOG(INFO) << Spaces() << value;
374 LOG(INFO) << Spaces() << operation;
375 delegate->Accept(this);
376 Decrease();
377 }
378
379 void VisitIntervalVariable(const IntervalVar* const variable,
380 const std::string& operation, int64 value,
381 IntervalVar* const delegate) override {
382 if (delegate != nullptr) {
383 LOG(INFO) << Spaces() << operation << " <" << value << ", ";
384 Increase();
385 delegate->Accept(this);
386 Decrease();
387 LOG(INFO) << Spaces() << ">";
388 } else {
389 LOG(INFO) << Spaces() << variable->DebugString();
390 }
391 }
392
393 void VisitSequenceVariable(const SequenceVar* const sequence) override {
394 LOG(INFO) << Spaces() << sequence->DebugString();
395 }
396
397 // Variables.
398 void VisitIntegerArgument(const std::string& arg_name, int64 value) override {
399 LOG(INFO) << Spaces() << arg_name << ": " << value;
400 }
401
402 void VisitIntegerArrayArgument(const std::string& arg_name,
403 const std::vector<int64>& values) override {
404 LOG(INFO) << Spaces() << arg_name << ": [" << absl::StrJoin(values, ", ")
405 << "]";
406 }
407
408 void VisitIntegerMatrixArgument(const std::string& arg_name,
409 const IntTupleSet& values) override {
410 const int rows = values.NumTuples();
411 const int columns = values.Arity();
412 std::string array = "[";
413 for (int i = 0; i < rows; ++i) {
414 if (i != 0) {
415 array.append(", ");
416 }
417 array.append("[");
418 for (int j = 0; j < columns; ++j) {
419 if (j != 0) {
420 array.append(", ");
421 }
422 absl::StrAppendFormat(&array, "%d", values.Value(i, j));
423 }
424 array.append("]");
425 }
426 array.append("]");
427 LOG(INFO) << Spaces() << arg_name << ": " << array;
428 }
429
430 void VisitIntegerExpressionArgument(const std::string& arg_name,
431 IntExpr* const argument) override {
432 set_prefix(absl::StrFormat("%s: ", arg_name));
433 Increase();
434 argument->Accept(this);
435 Decrease();
436 }
437
438 void VisitIntegerVariableArrayArgument(
439 const std::string& arg_name,
440 const std::vector<IntVar*>& arguments) override {
441 LOG(INFO) << Spaces() << arg_name << ": [";
442 Increase();
443 for (int i = 0; i < arguments.size(); ++i) {
444 arguments[i]->Accept(this);
445 }
446 Decrease();
447 LOG(INFO) << Spaces() << "]";
448 }
449
450 // Visit interval argument.
451 void VisitIntervalArgument(const std::string& arg_name,
452 IntervalVar* const argument) override {
453 set_prefix(absl::StrFormat("%s: ", arg_name));
454 Increase();
455 argument->Accept(this);
456 Decrease();
457 }
458
459 virtual void VisitIntervalArgumentArray(
460 const std::string& arg_name, const std::vector<IntervalVar*>& arguments) {
461 LOG(INFO) << Spaces() << arg_name << ": [";
462 Increase();
463 for (int i = 0; i < arguments.size(); ++i) {
464 arguments[i]->Accept(this);
465 }
466 Decrease();
467 LOG(INFO) << Spaces() << "]";
468 }
469
470 // Visit sequence argument.
471 void VisitSequenceArgument(const std::string& arg_name,
472 SequenceVar* const argument) override {
473 set_prefix(absl::StrFormat("%s: ", arg_name));
474 Increase();
475 argument->Accept(this);
476 Decrease();
477 }
478
479 virtual void VisitSequenceArgumentArray(
480 const std::string& arg_name, const std::vector<SequenceVar*>& arguments) {
481 LOG(INFO) << Spaces() << arg_name << ": [";
482 Increase();
483 for (int i = 0; i < arguments.size(); ++i) {
484 arguments[i]->Accept(this);
485 }
486 Decrease();
487 LOG(INFO) << Spaces() << "]";
488 }
489
490 std::string DebugString() const override { return "PrintModelVisitor"; }
491
492 private:
493 void Increase() { indent_ += 2; }
494
495 void Decrease() { indent_ -= 2; }
496
497 std::string Spaces() {
498 std::string result;
499 for (int i = 0; i < indent_ - 2 * (!prefix_.empty()); ++i) {
500 result.append(" ");
501 }
502 if (!prefix_.empty()) {
503 result.append(prefix_);
504 prefix_ = "";
505 }
506 return result;
507 }
508
509 void set_prefix(const std::string& prefix) { prefix_ = prefix; }
510
511 int indent_;
512 std::string prefix_;
513};
514
515// ---------- ModelStatisticsVisitor -----------
516
517class ModelStatisticsVisitor : public ModelVisitor {
518 public:
519 ModelStatisticsVisitor()
520 : num_constraints_(0),
521 num_variables_(0),
522 num_expressions_(0),
523 num_casts_(0),
524 num_intervals_(0),
525 num_sequences_(0),
526 num_extensions_(0) {}
527
528 ~ModelStatisticsVisitor() override {}
529
530 // Begin/End visit element.
531 void BeginVisitModel(const std::string& solver_name) override {
532 // Reset statistics.
533 num_constraints_ = 0;
534 num_variables_ = 0;
535 num_expressions_ = 0;
536 num_casts_ = 0;
537 num_intervals_ = 0;
538 num_sequences_ = 0;
539 num_extensions_ = 0;
540 already_visited_.clear();
541 constraint_types_.clear();
542 expression_types_.clear();
543 extension_types_.clear();
544 }
545
546 void EndVisitModel(const std::string& solver_name) override {
547 // Display statistics.
548 LOG(INFO) << "Model has:";
549 LOG(INFO) << " - " << num_constraints_ << " constraints.";
550 for (const auto& it : constraint_types_) {
551 LOG(INFO) << " * " << it.second << " " << it.first;
552 }
553 LOG(INFO) << " - " << num_variables_ << " integer variables.";
554 LOG(INFO) << " - " << num_expressions_ << " integer expressions.";
555 for (const auto& it : expression_types_) {
556 LOG(INFO) << " * " << it.second << " " << it.first;
557 }
558 LOG(INFO) << " - " << num_casts_ << " expressions casted into variables.";
559 LOG(INFO) << " - " << num_intervals_ << " interval variables.";
560 LOG(INFO) << " - " << num_sequences_ << " sequence variables.";
561 LOG(INFO) << " - " << num_extensions_ << " model extensions.";
562 for (const auto& it : extension_types_) {
563 LOG(INFO) << " * " << it.second << " " << it.first;
564 }
565 }
566
567 void BeginVisitConstraint(const std::string& type_name,
568 const Constraint* const constraint) override {
569 num_constraints_++;
570 AddConstraintType(type_name);
571 }
572
573 void BeginVisitIntegerExpression(const std::string& type_name,
574 const IntExpr* const expr) override {
575 AddExpressionType(type_name);
576 num_expressions_++;
577 }
578
579 void BeginVisitExtension(const std::string& type_name) override {
580 AddExtensionType(type_name);
581 num_extensions_++;
582 }
583
584 void VisitIntegerVariable(const IntVar* const variable,
585 IntExpr* const delegate) override {
586 num_variables_++;
587 Register(variable);
588 if (delegate) {
589 num_casts_++;
590 VisitSubArgument(delegate);
591 }
592 }
593
594 void VisitIntegerVariable(const IntVar* const variable,
595 const std::string& operation, int64 value,
596 IntVar* const delegate) override {
597 num_variables_++;
598 Register(variable);
599 num_casts_++;
600 VisitSubArgument(delegate);
601 }
602
603 void VisitIntervalVariable(const IntervalVar* const variable,
604 const std::string& operation, int64 value,
605 IntervalVar* const delegate) override {
606 num_intervals_++;
607 if (delegate) {
608 VisitSubArgument(delegate);
609 }
610 }
611
612 void VisitSequenceVariable(const SequenceVar* const sequence) override {
613 num_sequences_++;
614 for (int i = 0; i < sequence->size(); ++i) {
615 VisitSubArgument(sequence->Interval(i));
616 }
617 }
618
619 // Visit integer expression argument.
620 void VisitIntegerExpressionArgument(const std::string& arg_name,
621 IntExpr* const argument) override {
622 VisitSubArgument(argument);
623 }
624
625 void VisitIntegerVariableArrayArgument(
626 const std::string& arg_name,
627 const std::vector<IntVar*>& arguments) override {
628 for (int i = 0; i < arguments.size(); ++i) {
629 VisitSubArgument(arguments[i]);
630 }
631 }
632
633 // Visit interval argument.
634 void VisitIntervalArgument(const std::string& arg_name,
635 IntervalVar* const argument) override {
636 VisitSubArgument(argument);
637 }
638
639 void VisitIntervalArrayArgument(
640 const std::string& arg_name,
641 const std::vector<IntervalVar*>& arguments) override {
642 for (int i = 0; i < arguments.size(); ++i) {
643 VisitSubArgument(arguments[i]);
644 }
645 }
646
647 // Visit sequence argument.
648 void VisitSequenceArgument(const std::string& arg_name,
649 SequenceVar* const argument) override {
650 VisitSubArgument(argument);
651 }
652
653 void VisitSequenceArrayArgument(
654 const std::string& arg_name,
655 const std::vector<SequenceVar*>& arguments) override {
656 for (int i = 0; i < arguments.size(); ++i) {
657 VisitSubArgument(arguments[i]);
658 }
659 }
660
661 std::string DebugString() const override { return "ModelStatisticsVisitor"; }
662
663 private:
664 void Register(const BaseObject* const object) {
665 already_visited_.insert(object);
666 }
667
668 bool AlreadyVisited(const BaseObject* const object) {
669 return gtl::ContainsKey(already_visited_, object);
670 }
671
672 // T should derive from BaseObject
673 template <typename T>
674 void VisitSubArgument(T* object) {
675 if (!AlreadyVisited(object)) {
676 Register(object);
677 object->Accept(this);
678 }
679 }
680
681 void AddConstraintType(const std::string& constraint_type) {
682 constraint_types_[constraint_type]++;
683 }
684
685 void AddExpressionType(const std::string& expression_type) {
686 expression_types_[expression_type]++;
687 }
688
689 void AddExtensionType(const std::string& extension_type) {
690 extension_types_[extension_type]++;
691 }
692
693 absl::flat_hash_map<std::string, int> constraint_types_;
694 absl::flat_hash_map<std::string, int> expression_types_;
695 absl::flat_hash_map<std::string, int> extension_types_;
696 int num_constraints_;
697 int num_variables_;
698 int num_expressions_;
699 int num_casts_;
700 int num_intervals_;
701 int num_sequences_;
702 int num_extensions_;
703 absl::flat_hash_set<const BaseObject*> already_visited_;
704};
705
706// ---------- Variable Degree Visitor ---------
707
708class VariableDegreeVisitor : public ModelVisitor {
709 public:
710 explicit VariableDegreeVisitor(
711 absl::flat_hash_map<const IntVar*, int>* const map)
712 : map_(map) {}
713
714 ~VariableDegreeVisitor() override {}
715
716 // Begin/End visit element.
717 void VisitIntegerVariable(const IntVar* const variable,
718 IntExpr* const delegate) override {
719 IntVar* const var = const_cast<IntVar*>(variable);
720 if (gtl::ContainsKey(*map_, var)) {
721 (*map_)[var]++;
722 }
723 if (delegate) {
724 VisitSubArgument(delegate);
725 }
726 }
727
728 void VisitIntegerVariable(const IntVar* const variable,
729 const std::string& operation, int64 value,
730 IntVar* const delegate) override {
731 IntVar* const var = const_cast<IntVar*>(variable);
732 if (gtl::ContainsKey(*map_, var)) {
733 (*map_)[var]++;
734 }
735 VisitSubArgument(delegate);
736 }
737
738 void VisitIntervalVariable(const IntervalVar* const variable,
739 const std::string& operation, int64 value,
740 IntervalVar* const delegate) override {
741 if (delegate) {
742 VisitSubArgument(delegate);
743 }
744 }
745
746 void VisitSequenceVariable(const SequenceVar* const sequence) override {
747 for (int i = 0; i < sequence->size(); ++i) {
748 VisitSubArgument(sequence->Interval(i));
749 }
750 }
751
752 // Visit integer expression argument.
753 void VisitIntegerExpressionArgument(const std::string& arg_name,
754 IntExpr* const argument) override {
755 VisitSubArgument(argument);
756 }
757
758 void VisitIntegerVariableArrayArgument(
759 const std::string& arg_name,
760 const std::vector<IntVar*>& arguments) override {
761 for (int i = 0; i < arguments.size(); ++i) {
762 VisitSubArgument(arguments[i]);
763 }
764 }
765
766 // Visit interval argument.
767 void VisitIntervalArgument(const std::string& arg_name,
768 IntervalVar* const argument) override {
769 VisitSubArgument(argument);
770 }
771
772 void VisitIntervalArrayArgument(
773 const std::string& arg_name,
774 const std::vector<IntervalVar*>& arguments) override {
775 for (int i = 0; i < arguments.size(); ++i) {
776 VisitSubArgument(arguments[i]);
777 }
778 }
779
780 // Visit sequence argument.
781 void VisitSequenceArgument(const std::string& arg_name,
782 SequenceVar* const argument) override {
783 VisitSubArgument(argument);
784 }
785
786 void VisitSequenceArrayArgument(
787 const std::string& arg_name,
788 const std::vector<SequenceVar*>& arguments) override {
789 for (int i = 0; i < arguments.size(); ++i) {
790 VisitSubArgument(arguments[i]);
791 }
792 }
793
794 std::string DebugString() const override { return "VariableDegreeVisitor"; }
795
796 private:
797 // T should derive from BaseObject
798 template <typename T>
799 void VisitSubArgument(T* object) {
800 object->Accept(this);
801 }
802
803 absl::flat_hash_map<const IntVar*, int>* const map_;
804};
805} // namespace
806
808 return RevAlloc(new PrintModelVisitor);
809}
810
812 return RevAlloc(new ModelStatisticsVisitor);
813}
814
816 absl::flat_hash_map<const IntVar*, int>* const map) {
817 return RevAlloc(new VariableDegreeVisitor(map));
818}
819
820// ----- Vector manipulations -----
821
822std::vector<int64> ToInt64Vector(const std::vector<int>& input) {
823 std::vector<int64> result(input.size());
824 for (int i = 0; i < input.size(); ++i) {
825 result[i] = input[i];
826 }
827 return result;
828}
829} // namespace operations_research
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
void SetValue(Solver *const s, int index, const T &val)
int64 GetFirstBit(int row, int start) const
Returns the first bit in the row 'row' which position is >= 'start'.
Definition: utilities.cc:200
void SetToOne(Solver *const solver, int64 row, int64 column)
Sets the 'column' bit in the 'row' row.
Definition: utilities.cc:167
void ClearAll(Solver *const solver)
Cleans all bits.
Definition: utilities.cc:215
void SetToZero(Solver *const solver, int64 row, int64 column)
Erases the 'column' bit in the 'row' row.
Definition: utilities.cc:175
This class represents a reversible bitset.
bool IsCardinalityOne() const
Does it contains only one bit set?
Definition: utilities.cc:126
bool IsSet(int64 index) const
Returns whether the 'index' bit is set.
Definition: utilities.cc:103
void SetToOne(Solver *const solver, int64 index)
Sets the 'index' bit.
Definition: utilities.cc:81
int64 GetFirstBit(int start) const
Gets the index of the first bit set starting from start.
Definition: utilities.cc:144
void ClearAll(Solver *const solver)
Cleans all bits.
Definition: utilities.cc:148
bool IsCardinalityZero() const
Is bitset null?
Definition: utilities.cc:117
int64 Cardinality() const
Returns the number of bits set to one.
Definition: utilities.cc:109
void SetToZero(Solver *const solver, int64 index)
Erases the 'index' bit.
Definition: utilities.cc:92
void SetValue(Solver *const s, const T &val)
void Insert(Solver *const solver, const T &elt)
void Remove(Solver *const solver, const T &value_index)
void SetToZero(Solver *const solver, int64 pos)
Erases the 'pos' bit.
Definition: utilities.cc:42
void SetToOne(Solver *const solver, int64 pos)
Sets the 'pos' bit.
Definition: utilities.cc:37
int64 GetFirstOne() const
Gets the index of the first bit set starting from 0.
Definition: utilities.cc:49
int64 Cardinality() const
Returns the number of bits set to one.
Definition: utilities.cc:47
void SaveValue(T *o)
reversibility
ModelVisitor * MakeVariableDegreeVisitor(absl::flat_hash_map< const IntVar *, int > *const map)
Compute the number of constraints a variable is attached to.
Definition: utilities.cc:815
uint64 stamp() const
The stamp indicates how many moves in the search tree we have performed.
ModelVisitor * MakePrintModelVisitor()
Prints the model.
Definition: utilities.cc:807
T * RevAlloc(T *object)
Registers the given object as being reversible.
ModelVisitor * MakeStatisticsModelVisitor()
Displays some nice statistics on the model.
Definition: utilities.cc:811
bool RevSubtract(Solver *const solver, const std::vector< uint64 > &mask)
This method subtracts the mask from the active bitset.
Definition: utilities.cc:238
bool RevAnd(Solver *const solver, const std::vector< uint64 > &mask)
This method ANDs the mask with the active bitset.
Definition: utilities.cc:265
bool Intersects(const std::vector< uint64 > &mask, int *support_index)
This method returns true iff the mask and the active bitset have a non null intersection.
Definition: utilities.cc:290
void Init(Solver *const solver, const std::vector< uint64 > &mask)
This methods overwrites the active bitset with the mask.
Definition: utilities.cc:227
UnsortedNullableRevBitset(int bit_size)
Size is the number of bits to store in the bitset.
Definition: utilities.cc:221
int64 value
IntVar * var
Definition: expr_array.cc:1858
int64_t int64
uint64_t uint64
const int INFO
Definition: log_severity.h:31
RowIndex row
Definition: markowitz.cc:175
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
uint64 BitLength64(uint64 size)
Definition: bitset.h:338
bool IsBitSet64(const uint64 *const bitset, uint64 pos)
Definition: bitset.h:346
uint32 BitPos64(uint64 pos)
Definition: bitset.h:330
uint64 OneBit64(int pos)
Definition: bitset.h:38
uint64 BitOffset64(uint64 pos)
Definition: bitset.h:334
std::vector< int64 > ToInt64Vector(const std::vector< int > &input)
Definition: utilities.cc:822
int LeastSignificantBitPosition64(uint64 n)
Definition: bitset.h:127
uint64 BitCountRange64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 BitCount64(uint64 n)
Definition: bitset.h:42
bool IsEmptyRange64(const uint64 *const bitset, uint64 start, uint64 end)
int index
Definition: pack.cc:508
static int input(yyscan_t yyscanner)