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