Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
colored-matrix.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Lagerkvist <lagerkvist@gecode.org>
5 *
6 * Copyright:
7 * Mikael Lagerkvist, 2012
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/driver.hh>
35#include <gecode/int.hh>
36#include <gecode/minimodel.hh>
37
38#include <fstream>
39
40using namespace Gecode;
41
47private:
57 Driver::StringOption _not_all_equal;
59 Driver::StringOption _same_or_0;
61 Driver::StringOption _distinct_except_0;
63 Driver::StringOption _no_monochrome_rectangle;
64
65public:
67 ColoredMatrixOptions(const char* n);
68
70 void parse(int& argc, char* argv[]) {
71 Options::parse(argc,argv);
72 }
73
75 int height(void) const {
76 if (_size.value() == 0U)
77 return static_cast<int>(_height.value());
78 else
79 return static_cast<int>(_size.value());
80 }
81
82 int width(void) const {
83 if (_size.value() == 0U)
84 return static_cast<int>(_width.value());
85 else
86 return static_cast<int>(_size.value());
87 }
88
89 int colors(void) const { return static_cast<int>(_colors.value()); }
91 int not_all_equal(void) const { return _not_all_equal.value(); }
93 int same_or_0(void) const { return _same_or_0.value(); }
95 int distinct_except_0(void) const { return _distinct_except_0.value(); }
97 int no_monochrome_rectangle(void) const {
98 return _no_monochrome_rectangle.value();
99 }
100};
101
102namespace {
111
119
127
131
135
139
143
145}
146
165protected:
170 const int height;
171 const int width;
172 const int colors;
174
178
183
186 IntVar same_or_0(const IntVar& a, const IntVar& b)
187 {
188 switch (opt.same_or_0()) {
189 case SAME_OR_0_REIFIED: {
190 IntVar result(*this, 0, colors);
191 BoolVar same = expr(*this, (a == b));
192 rel(*this, result, IRT_EQ, a, same);
193 // Redundant (implied by previous), but improves efficiency
194 rel(*this, result, IRT_NQ, 0, same);
195 return result;
196 }
197 case SAME_OR_0_TUPLE_SET: {
198 static TupleSet table = same_or_0_tuple_set(colors);
199 IntVar result(*this, 0, colors);
200 extensional(*this, IntVarArgs() << a << b << result, table);
201 return result;
202 }
203 case SAME_OR_0_DFA: {
204 static const DFA automaton = same_or_0_dfa(colors);
205 IntVar result(*this, 0, colors);
206 extensional(*this, IntVarArgs() << a << b << result, automaton);
207 return result;
208 }
209 default:
211 return IntVar(*this, 0, 0);
212 }
213 }
214
218 {
219 switch (opt.distinct_except_0()) {
221 for (int i = v.size(); i--; ) {
222 BoolVar viIsZero = expr(*this, v[i] == 0);
223 for (int j = i; j--; ) {
224 rel(*this, viIsZero || (v[i] != v[j]));
225 }
226 }
227 break;
229 static const DFA automaton = distinct_except_0_dfa(colors);
230 extensional(*this, v, automaton);
231 break;
232 }
234 static const IntSetArgs counts = distinct_except_0_counts(colors, std::max(width, height));
235 count(*this, v, counts, opt.ipl());
236 break;
237 }
238 }
239 }
240
244 {
245 switch (opt.not_all_equal()) {
246 case NOT_ALL_EQUAL_NQ: {
247 rel(*this, v, IRT_NQ);
248 break;
249 }
250 case NOT_ALL_EQUAL_NAIVE: {
251 // At least one pair must be different.
252 // Bad decomposition since too many disjuncts are created.
253 BoolVarArgs disequalities;
254 for (int i = v.size(); i--; )
255 for (int j = i; j--; )
256 disequalities << expr(*this, v[i] != v[j]);
257 rel(*this, BOT_OR, disequalities, 1);
258 break;
259 }
261 // It must not be the case that all are equal
262 BoolVarArgs equalities;
263 for (int i = 0; i < v.size()-1; ++i)
264 equalities << expr(*this, v[i] == v[i+1]);
265 rel(*this, BOT_AND, equalities, 0);
266 break;
267 }
269 // More than one number
270 nvalues(*this, v, IRT_GR, 1);
271 break;
273 // No number in all positions
274 count(*this, v, IntSet(0, v.size()-1), IntArgs::create(colors, 1), opt.ipl());
275 break;
276 case NOT_ALL_EQUAL_DFA: {
277 static const DFA automaton = not_all_equal_dfa(colors);
278 extensional(*this, v, automaton);
279 break;
280 }
281 }
282 }
283
288 const int length = v1.size();
289 switch (opt.no_monochrome_rectangle()) {
291 IntVarArgs z(length);
292 for (int i = 0; i < length; ++i) {
293 z[i] = same_or_0(v1[i], v2[i]);
294 }
296 break;
297 }
298 case NO_MONOCHROME_DFA: {
299 static const DFA automaton = no_monochrome_rectangle_dfa(colors);
300 IntVarArgs z(2*length);
301 for (int i = length; i--; ) {
302 z[2*i + 0] = v1[i];
303 z[2*i + 1] = v2[i];
304 }
305 extensional(*this, z, automaton);
306 break;
307 }
308 }
309 }
310
311
312public:
314 enum {
317 };
319 enum {
323 };
325 enum {
329 };
331 enum {
338 };
340 enum {
344 };
346 enum {
350 };
352 enum {
355 };
356
357
360 : IntMinimizeScript(opt0),
361 opt(opt0), height(opt.height()), width(opt.width()), colors(opt.colors()),
362 x(*this, height*width, 1, colors),
363 max_color(*this, 1, colors)
364 {
365
366 max(*this, x, max_color);
367
369
370 // For each pair of columns and rows, the intersections may not be equal.
371 if (opt.model() & MODEL_CORNERS) {
372 for (int c1 = 0; c1 < width; ++c1) {
373 for (int c2 = c1+1; c2 < width; ++c2) {
374 for (int r1 = 0; r1 < height; ++r1) {
375 for (int r2 = r1+1; r2 < height; ++r2) {
376 not_all_equal(IntVarArgs() << m(c1,r1) << m(c1,r2) << m(c2,r1) << m(c2,r2));
377 }
378 }
379 }
380 }
381 }
382 // Given two rows/columns, construct variables representing if
383 // the corresponding places are equal (and if so, what value).
384 // For the new values, no non-zero value may appear more than
385 // once.
386 if (opt.model() & MODEL_ROWS) {
387 for (int r1 = 0; r1 < height; ++r1) {
388 for (int r2 = r1+1; r2 < height; ++r2) {
389 no_monochrome_rectangle(m.row(r1), m.row(r2));
390 }
391 }
392 }
393 if (opt.model() & MODEL_COLUMNS) {
394 for (int c1 = 0; c1 < width; ++c1) {
395 for (int c2 = c1+1; c2 < width; ++c2) {
396 no_monochrome_rectangle(m.col(c1), m.col(c2));
397 }
398 }
399 }
400
401 // Symmetry breaking constraints.
402 {
403 // Lexical order for all columns and rows (all are interchangable)
404 if (opt.symmetry() & SYMMETRY_MATRIX) {
405 for (int r = 0; r < height-1; ++r) {
406 rel(*this, m.row(r), IRT_LE, m.row(r+1));
407 }
408 for (int c = 0; c < width-1; ++c) {
409 rel(*this, m.col(c), IRT_LE, m.col(c+1));
410 }
411 }
412
413 // Value precedence. Compatible with row/column ordering
414 if (opt.symmetry() & SYMMETRY_VALUES) {
415 precede(*this, x, IntArgs::create(colors, 1));
416 }
417 }
418
420 }
421
423 virtual IntVar cost(void) const {
424 return max_color;
425 }
426
428 virtual void
429 print(std::ostream& os) const {
431 for (int r = 0; r < height; ++r) {
432 os << "\t";
433 for (int c = 0; c < width; ++c) {
434 os << m(c, r) << " ";
435 }
436 os << std::endl;
437 }
438 os << std::endl;
439 os << "\tmax color: " << max_color << std::endl;
440 os << std::endl;
441 }
442
445 : IntMinimizeScript(s), opt(s.opt),
446 height(s.height), width(s.width), colors(s.colors) {
447 x.update(*this, s.x);
448 max_color.update(*this, s.max_color);
449 }
450
451 virtual Space*
452 copy(void) {
453 return new ColoredMatrix(*this);
454 }
455};
456
458 : Options(n),
459 _height("height", "Height of matrix", 8),
460 _width("width", "Width of matrix", 8),
461 _size("size", "If different from 0, used as both width and height", 0),
462 _colors("colors", "Maximum number of colors", 4),
463 _not_all_equal("not-all-equal", "How to implement the not all equals constraint (used in corners model)",
464 ColoredMatrix::NOT_ALL_EQUAL_NQ),
465 _same_or_0("same-or-0", "How to implement the same or 0 constraint (used in the decomposed no monochrome rectangle constraint)",
466 ColoredMatrix::SAME_OR_0_DFA),
467 _distinct_except_0("distinct-except-0", "How to implement the distinct except 0 constraint (used in the decomposed no monochrome rectangle constraint)",
468 ColoredMatrix::DISTINCT_EXCEPT_0_DFA),
469 _no_monochrome_rectangle("no-monochrome-rectangle", "How to implement no monochrome rectangle (used in the rows model)",
470 ColoredMatrix::NO_MONOCHROME_DFA)
471{
472 add(_height);
473 add(_width);
474 add(_size);
475 add(_colors);
476 add(_not_all_equal);
477 add(_same_or_0);
478 add(_distinct_except_0);
479 add(_no_monochrome_rectangle);
480
481 // Add search options
482 _search.add(ColoredMatrix::SEARCH_DFS, "dfs", "Find a solution.");
483 _search.add(ColoredMatrix::SEARCH_BAB, "bab", "Find an optimal solution.");
485
486 // Add symmetry options
487 _symmetry.add(ColoredMatrix::SYMMETRY_NONE, "none", "Don't use symmetry breaking.");
488 _symmetry.add(ColoredMatrix::SYMMETRY_MATRIX, "matrix", "Order matrix rows and columns");
489 _symmetry.add(ColoredMatrix::SYMMETRY_VALUES, "values", "Order values");
491 "both", "Order both rows/columns and values");
493
494 // Add model options
495 _model.add(ColoredMatrix::MODEL_CORNERS, "corner", "Use direct corners model with not-all-equal constraints.");
496 _model.add(ColoredMatrix::MODEL_ROWS, "rows", "Use model on pairs of rows (same_or_0 and distinct_except_0 constraints).");
498 "both", "Use both rows and corners model");
499 _model.add(ColoredMatrix::MODEL_COLUMNS, "columns", "Use model on pairs of columns (same_or_0 and distinct_except_0 constraints).");
501 "matrix", "Use both rows and columns model");
503
504 // Add not all equal variants
505 _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_NQ, "nq", "Use nq constraint.");
506 _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_NAIVE, "naive", "Use naive reified decomposition.");
507 _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_REIFIED, "reified", "Use reified decomposition.");
508 _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_NVALUES, "nvalues", "Use nvalues.");
509 _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_COUNT, "count", "Use count.");
510 _not_all_equal.add(ColoredMatrix::NOT_ALL_EQUAL_DFA, "dfa", "Use dfa.");
511
512 // Add same or 0 variants
513 _same_or_0.add(ColoredMatrix::SAME_OR_0_REIFIED, "reified", "Use reified decomposition.");
514 _same_or_0.add(ColoredMatrix::SAME_OR_0_TUPLE_SET, "tuple-set", "Use tuple set representation.");
515 _same_or_0.add(ColoredMatrix::SAME_OR_0_DFA, "dfa", "Use dfa representation.");
516
517 // Add distinct except 0 variants
518 _distinct_except_0.add(ColoredMatrix::DISTINCT_EXCEPT_0_REIFIED, "reified", "Use reified decomposition.");
519 _distinct_except_0.add(ColoredMatrix::DISTINCT_EXCEPT_0_DFA, "dfa", "Use dfa decomposition.");
520 _distinct_except_0.add(ColoredMatrix::DISTINCT_EXCEPT_0_COUNT, "count", "Use global cardinality.");
521
522 // Add no monochrome rectangle variants
523 _no_monochrome_rectangle.add(ColoredMatrix::NO_MONOCHROME_DECOMPOSITION,
524 "decompositions",
525 "Use decompositions into same_or_0 and distinct_except_0.");
526 _no_monochrome_rectangle.add(ColoredMatrix::NO_MONOCHROME_DFA,
527 "dfa",
528 "Use DFA as direct implementation.");
529}
530
534int
535main(int argc, char* argv[]) {
536 ColoredMatrixOptions opt("Colored matrix");
537 opt.parse(argc,argv);
538 if (opt.search() == ColoredMatrix::SEARCH_DFS) {
540 } else {
542 }
543 return 0;
544}
545
546
547namespace {
548 DFA same_or_0_dfa(int colors)
549 {
550 /* DFA over variable sequences (x,y,z) where z equals x/y if x and
551 * y are equal, and z equals 0 otherwise.
552 *
553 * DFA is constructed to contain paths
554 * start -- c --> node -- c --> node' -- c --> end
555 * for all colors c representing the case when x and y
556 * are equal.
557 *
558 * For the cases where x and y are non-equal (c and c'), paths
559 * start -- c --> node -- c' --> not-equal -- 0 --> end
560 * are added.
561 */
562
563 const int start_state = 0;
564 const int not_equal_state = 2*colors+1;
565 const int final_state = 2*colors+2;
566
567 int n_transitions = colors*colors + 2*colors + 2;
568 DFA::Transition* trans =
569 new DFA::Transition[static_cast<size_t>(n_transitions)];
570 int current_transition = 0;
571
572 // From start state
573 for (int color = 1; color <= colors; ++color) {
574 trans[current_transition++] =
575 DFA::Transition(start_state, color, color);
576 }
577
578 // From first level states (indices [1..color])
579 // To second-level if same color, otherwise to not_equal_state
580 for (int state = 1; state <= colors; ++state) {
581 for (int color = 1; color <= colors; ++color) {
582 if (color == state) {
583 trans[current_transition++] =
584 DFA::Transition(state, color, colors+state);
585 } else {
586 trans[current_transition++] =
587 DFA::Transition(state, color, not_equal_state);
588 }
589 }
590 }
591
592 // From second level states (indices [colors+1..colors+colors])
593 // To final state with the same color
594 for (int color = 1; color <= colors; ++color) {
595 trans[current_transition++] =
596 DFA::Transition(colors+color, color, final_state);
597 }
598
599 // From not equal state to final state
600 trans[current_transition++] =
601 DFA::Transition(not_equal_state, 0, final_state);
602
603 // End sentinel
604 trans[current_transition++] =
605 DFA::Transition(-1, 0, -1);
606
607 int final_states[] = {final_state, -1};
608
609 DFA result(start_state, trans, final_states, true);
610
611 delete[] trans;
612
613 return result;
614 }
615
616 TupleSet same_or_0_tuple_set(int colors) {
617 TupleSet result(3);
618 for (int i = 1; i <= colors; ++i) {
619 for (int j = 1; j <= colors; ++j) {
620 if (i == j) {
621 result.add({i, j, i});
622 } else {
623 result.add({i, j, 0});
624 }
625 }
626 }
627 result.finalize();
628 return result;
629 }
630
631 DFA distinct_except_0_dfa(int colors)
632 {
633 /* DFA for a sequence that may use each color only once (and all
634 * others are zero).
635 *
636 * For n colors, 2^n nodes are used. For each node, if bit b is one, then
637 * that color has not been used yet. All nodes have self-loops for zero, and
638 * edges for still usable colors to the node with the corresponding bit un-set.
639 * All nodes are final nodes.
640 */
641
642 const int nstates = 1 << colors;
643 const int start_state = nstates-1;
644
645 DFA::Transition* trans =
646 new DFA::Transition[static_cast<size_t>(nstates*colors + 1)];
647 int current_transition = 0;
648
649 for (int state = nstates; state--; ) {
650 trans[current_transition++] = DFA::Transition(state, 0, state);
651
652 for (int color = 1; color <= colors; ++color) {
653 const int color_bit = (1 << (color-1));
654 if (state & color_bit) {
655 trans[current_transition++] =
656 DFA::Transition(state, color, state & ~color_bit);
657 }
658 }
659 }
660 trans[current_transition++] = DFA::Transition(-1, 0, -1);
661
662 int* final_states = new int[nstates+1];
663 final_states[nstates] = -1;
664 for (int i = nstates; i--; ) {
665 final_states[i] = i;
666 }
667
668 DFA result(start_state, trans, final_states);
669
670 delete[] trans;
671 delete[] final_states;
672
673 return result;
674 }
675
676 DFA no_monochrome_rectangle_dfa(int colors)
677 {
678 /* DFA for a sequence of pairs, where each monochromatic pair may
679 * only appear once.
680 *
681 * For n colors, there are 2^n base states representing which
682 * monochromatic pairs are still available. For each base state s,
683 * the color seen goes to a new intermediate state. A different
684 * color will go back to state s. Seeing the same color will move
685 * to the next base state with that color combination removed (if
686 * it is still allowed).
687 *
688 * In essence, this DFA represents the combination of same_or_0
689 * and distinct_except_0 as a single constraint.
690 */
691
692 const int base_states = 1 << colors;
693 const int start_state = base_states-1;
694 const int nstates = base_states + colors*base_states;
695
696 DFA::Transition* trans = new DFA::Transition[nstates*colors + 1];
697 int current_transition = 0;
698
699 for (int state = base_states; state--; ) {
700 for (int color = 1; color <= colors; ++color) {
701 const int color_bit = (1 << (color-1));
702 const int color_remembered_state = state + color*base_states;
703
704 trans[current_transition++] =
705 DFA::Transition(state, color, color_remembered_state);
706
707 for (int next_color = 1; next_color <= colors; ++next_color) {
708 if (next_color == color) {
709 // Two equal adjacent, only transition if color still allowed
710 if (state & color_bit) {
711 trans[current_transition++] =
712 DFA::Transition(color_remembered_state, color, state & ~color_bit);
713 }
714 } else {
715 trans[current_transition++] =
716 DFA::Transition(color_remembered_state, next_color, state);
717 }
718 }
719 }
720 }
721 trans[current_transition++] = DFA::Transition(-1, 0, -1);
722 assert(current_transition <= nstates*colors+1);
723
724 int* final_states = new int[base_states+1];
725 final_states[base_states] = -1;
726 for (int i = base_states; i--; ) {
727 final_states[i] = i;
728 }
729
730 DFA result(start_state, trans, final_states);
731
732 delete[] trans;
733 delete[] final_states;
734
735 return result;
736 }
737
738 IntSetArgs distinct_except_0_counts(int colors, int size)
739 {
740 IntSetArgs result(colors+1);
741
742 result[0] = IntSet(0, size);
743
744 for (int i = 1; i <= colors; ++i) {
745 result[i] = IntSet(0, 1);
746 }
747
748 return result;
749 }
750
751
752 DFA not_all_equal_dfa(int colors)
753 {
754 /* DFA for not all equal.
755 *
756 * From the start state, there is a transition for each color to
757 * that colors state. As long as the same color is seen, the
758 * automaton stays in that state. If a different color is seen,
759 * then it goes to the accepting state.
760 */
761
762 const int nstates = 1 + colors + 1;
763 const int start_state = 0;
764 const int final_state = nstates-1;
765
766 DFA::Transition* trans = new DFA::Transition[2*colors + colors*colors + 1];
767 int current_transition = 0;
768
769 // Each color to its own state
770 for (int color = 1; color <= colors; ++color) {
771 trans[current_transition++] = DFA::Transition(start_state, color, color);
772 }
773
774 // Each colors state loops on itself, and goes to final on all others
775 for (int state = 1; state <= colors; ++state) {
776 for (int color = 1; color <= colors; ++color) {
777 if (state == color) {
778 trans[current_transition++] = DFA::Transition(state, color, state);
779 } else {
780 trans[current_transition++] = DFA::Transition(state, color, final_state);
781 }
782 }
783 }
784
785 // Loop on all colors in final state
786 for (int color = 1; color <= colors; ++color) {
787 trans[current_transition++] = DFA::Transition(final_state, color, final_state);
788 }
789
790 trans[current_transition++] = DFA::Transition(-1, 0, -1);
791
792 int final_states[] = {final_state, -1};
793
794 DFA result(start_state, trans, final_states);
795
796 delete[] trans;
797
798 return result;
799 }
800
801}
802
803
804// STATISTICS: example-any
ColoredMatrixOptions.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
int colors(void) const
Return number of colors.
int distinct_except_0(void) const
Return how to implement distinct except 0.
int same_or_0(void) const
Return how to implement same or 0.
int height(void) const
Return height.
int width(void) const
Return width.
int no_monochrome_rectangle(void) const
Return how to implement distinct except 0.
ColoredMatrixOptions(const char *n)
Initialize options for example with name n.
int not_all_equal(void) const
Return how to implement not all equals.
Example: Colored matrix example.
IntVar same_or_0(const IntVar &a, const IntVar &b)
int main(int argc, char *argv[])
Main-function.
void distinct_except_0(const IntVarArgs &v)
const ColoredMatrixOptions & opt
Options for model.
DFA not_all_equal_dfa(int colors)
DFA no_monochrome_rectangle_dfa(int colors)
IntSetArgs distinct_except_0_counts(int colors, int size)
virtual void print(std::ostream &os) const
Print solution.
@ SYMMETRY_MATRIX
Order rows and columns of matrix.
@ SYMMETRY_NONE
No symmetry breaking.
@ SYMMETRY_VALUES
Order value occurences.
const int colors
Number of colors to use.
void not_all_equal(const IntVarArgs &v)
ColoredMatrix(ColoredMatrix &s)
Constructor for cloning s.
void no_monochrome_rectangle(IntVarArgs v1, IntVarArgs v2)
@ DISTINCT_EXCEPT_0_DFA
Use dfa for distinct except 0.
@ DISTINCT_EXCEPT_0_COUNT
Use count for distinct except 0.
@ DISTINCT_EXCEPT_0_REIFIED
Use reification for distinct except 0.
@ SEARCH_DFS
Find solution.
@ SEARCH_BAB
Find optimal solution.
virtual Space * copy(void)
Copy during cloning.
@ NO_MONOCHROME_DFA
Use dfa for no monochrome rectangle.
@ NO_MONOCHROME_DECOMPOSITION
Use decomposition for no monochrome rectangle.
DFA distinct_except_0_dfa(int colors)
@ MODEL_COLUMNS
Use model on pairs of columns.
@ MODEL_ROWS
Use model on pairs of rows.
@ MODEL_CORNERS
Use model on corner combinations.
TupleSet same_or_0_tuple_set(int colors)
@ SAME_OR_0_DFA
Use dfa for same or 0.
@ SAME_OR_0_TUPLE_SET
Use tuple set for same or 0.
@ SAME_OR_0_REIFIED
Use reification for same or 0.
virtual IntVar cost(void) const
Return cost.
IntVarArray x
Array for matrix variables.
ColoredMatrix(const ColoredMatrixOptions &opt0)
Actual model.
DFA same_or_0_dfa(int colors)
const int width
Width of matrix.
IntVar max_color
Maximum color used.
@ NOT_ALL_EQUAL_NQ
Use direct constraint for implemeting not all equals.
@ NOT_ALL_EQUAL_REIFIED
Use reification for implemeting not all equals.
@ NOT_ALL_EQUAL_NVALUES
Use nvalues for implementing not all equals.
@ NOT_ALL_EQUAL_NAIVE
Use naive reification for implemeting not all equals.
@ NOT_ALL_EQUAL_COUNT
Use count for implementing not all equals.
@ NOT_ALL_EQUAL_DFA
Use dfa for implementing not all equals.
const int height
Height of matrix.
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1613
void add(Driver::BaseOption &o)
Add new option o.
Definition options.cpp:474
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition options.cpp:548
Passing Boolean variables.
Definition int.hh:721
Boolean integer variables.
Definition int.hh:515
Specification of a DFA transition.
Definition int.hh:2073
Deterministic finite automaton (DFA)
Definition int.hh:2064
static void run(const Options &opt, Script *s=NULL)
String-valued option (integer value defined by strings)
Definition driver.hh:174
Unsigned integer option.
Definition driver.hh:229
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition array.hpp:76
Integer sets.
Definition int.hh:174
Passing integer variables.
Definition int.hh:662
Integer variable array.
Definition int.hh:772
Integer variables.
Definition int.hh:371
Matrix-interface for arrays.
Slice< A > col(int c) const
Access column c.
Definition matrix.hpp:183
Slice< A > row(int r) const
Access row r.
Definition matrix.hpp:177
Driver::StringOption _model
General model options.
Definition driver.hh:370
Driver::StringOption _search
Search options.
Definition driver.hh:382
Options(const char *s)
Initialize options for script with name s.
Definition options.cpp:576
Driver::StringOption _symmetry
General symmetry options.
Definition driver.hh:371
Computation spaces.
Definition core.hpp:1744
Class represeting a set of tuples.
Definition int.hh:2206
Driver::ScriptBase< Driver::IgnoreStepOption< IntMinimizeSpace > > IntMinimizeScript
Base-class for scripts for finding solution of lowest integer cost.
Definition driver.hh:808
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
void precede(Home home, const IntVarArgs &x, int s, int t, IntPropLevel=IPL_DEF)
Post propagator that s precedes t in x.
Definition precede.cpp:43
@ IRT_EQ
Equality ( )
Definition int.hh:941
@ IRT_NQ
Disequality ( )
Definition int.hh:942
@ IRT_LE
Less ( )
Definition int.hh:944
@ IRT_GR
Greater ( )
Definition int.hh:946
@ BOT_OR
Disjunction.
Definition int.hh:967
@ BOT_AND
Conjunction.
Definition int.hh:966
Gecode toplevel namespace
ArgArray< IntSet > IntSetArgs
Passing set arguments.
Definition int.hh:625
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:915
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition tiebreak.hpp:80
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition set.hh:773
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1943
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void nvalues(Home home, const IntVarArgs &x, IntRelType irt, int y, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition nvalues.cpp:40
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
IntVarBranch INT_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest min.
Definition var.hpp:186
Gecode::IntArgs i({1, 2, 3, 4})
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56