Generated on Sat Feb 7 2015 02:01:23 for Gecode by doxygen 1.8.9.1
gcc.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * Patrick Pekczynski, 2005
11  * Christian Schulte, 2007
12  *
13  * Last modified:
14  * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
15  * $Revision: 10684 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include "test/int.hh"
43 
44 namespace Test { namespace Int {
45 
47  namespace GCC {
48 
54  class IntAllMinMax : public Test {
56  public:
59  : Test("GCC::Int::All::MinMax::"+str(icl),4,-1,3,false,icl) {}
61  virtual bool solution(const Assignment& x) const {
62  int n[5];
63  for (int i=5; i--; )
64  n[i]=0;
65  for (int i=x.size(); i--; )
66  n[x[i]+1]++;
67  if (n[2] > 0)
68  return false;
69  for (int i=5; i--;)
70  if (n[i]>2)
71  return false;
72  return true;
73  }
75  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
76  using namespace Gecode;
77  IntArgs values(5);
78  IntSet fixed(0,2);
79  IntSetArgs cards(5);
80  for (int i=0; i<5; i++) {
81  values[i] = i-1; cards[i] = fixed;
82  }
83  cards[2] = IntSet(0,0);
84  count(home, x, cards, values, icl);
85  }
86  };
87 
89  class IntAllMinMaxDef : public Test {
90  public:
93  : Test("GCC::Int::All::MinMaxDef::"+str(icl),4,0,3,false,icl) {}
95  virtual bool solution(const Assignment& x) const {
96  int n[4];
97  for (int i=4; i--; )
98  n[i]=0;
99  for (int i=x.size(); i--; )
100  n[x[i]]++;
101  if (n[2] > 0)
102  return false;
103  for (int i=4; i--;)
104  if (n[i]>2)
105  return false;
106  return true;
107  }
109  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
110  using namespace Gecode;
111  IntSet fixed(0,2);
112  IntSetArgs cards(4);
113  for (int i=0; i<4; i++) {
114  cards[i] = fixed;
115  }
116  cards[2] = IntSet(0,0);
117  count(home, x, cards, icl);
118  }
119  };
120 
122  class IntAllMax : public Test {
123  public:
126  : Test("GCC::Int::All::Max::"+str(icl), 4, 1,2, false, icl) {}
128  virtual bool solution(const Assignment& x) const {
129  int n[2];
130  for (int i=2; i--; )
131  n[i] = 0;
132  for (int i=x.size(); i--; )
133  n[x[i] - 1]++;
134  if (n[0] != 2 || n[1] != 2)
135  return false;
136  return true;
137  }
139  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
140  Gecode::IntArgs values(2, 1,2);
141  Gecode::count(home, x, Gecode::IntSet(2,2), values, icl);
142  }
143  };
144 
145 
147  template<bool hole>
148  class IntSome : public Test {
149  public:
152  : Test(std::string("GCC::Int::Some::")+
153  (hole ? "::Hole" : "::Full")+str(icl),4,1,4,false,icl) {}
155  virtual bool solution(const Assignment& x) const {
156  int n[4];
157  for (int i=4; i--; )
158  n[i]=0;
159  for (int i=x.size(); i--; )
160  n[x[i]-1]++;
161  if ((n[0] < 2) || (n[1] < 2) || (n[2] > 0) || (n[3] > 0))
162  return false;
163  return true;
164  }
166  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
167  using namespace Gecode;
168  IntArgs values(2, 1,2);
169  Gecode::IntSet fixed;
170  if (!hole) {
171  fixed = IntSet(0,2);
172  } else {
173  int ish[] = {0,2};
174  fixed = IntSet(ish,2);
175  }
176  Gecode::IntSetArgs cards(2);
177  cards[0]=fixed; cards[1]=fixed;
178  count(home, x, cards, values, icl);
179  }
180  };
181 
183  class VarAll : public Test {
184  protected:
186  static const int n = 4;
187  public:
190  : Test("GCC::Var::All::"+str(icl),7,0,2,false,icl) {}
192  virtual bool solution(const Assignment& x) const {
193  // Number of cardinality variables
194  int m = x.size()-n;
195  for (int i=0; i<n; i++)
196  if ((x[i] < 0) || (x[i] > 2))
197  return false;
198  int* card = new int[m];
199  for (int i=0; i<m; i++) {
200  card[i] = 0;
201  if ((x[n+i] < 0) || (x[n+i] > 2)) {
202  delete [] card;
203  return false;
204  }
205  }
206  for (int i=0; i<n; i++)
207  card[x[i]]++;
208  for (int i=0; i<m; i++)
209  if (card[i] != x[n+i]) {
210  delete [] card;
211  return false;
212  }
213  delete [] card;
214  return true;
215  }
217  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
218  using namespace Gecode;
219  // Number of cardinality variables
220  int m = xy.size()-n;
221 
222  IntVarArgs x(n), y(m);
223  for (int i=0; i<n; i++)
224  x[i]=xy[i];
225  for (int i=0; i<m; i++)
226  y[i]=xy[n+i];
227  count(home, x, y, icl);
228  }
229  };
230 
232  class VarSome : public Test {
233  protected:
235  int n;
237  static const int randomArity = 7;
238  public:
240  VarSome(std::string s, int n0, int min, int max,
242  : Test("GCC::Var::Some::"+s+"::"+str(icl),
243  n0+(max-min)+1,min,max,false,icl)
244  , n(n0)
245  {
246  contest = CTL_NONE;
247  if (arity>randomArity)
248  testsearch = false;
249  }
251  virtual bool solution(const Assignment& x) const {
252  // Number of cardinality variables
253  int m = x.size()-n;
254  int* card = new int[m];
255  for (int i=0; i<m; i++) {
256  card[i] = 0;
257  if ((x[n+i] < 0) || (x[n+i] > n)) {
258  delete [] card;
259  return false;
260  }
261  }
262  for (int i=0; i<n; i++)
263  card[x[i]-dom.min()]++;
264  for (int i=0; i<m; i++)
265  if (card[i] != x[n+i]) {
266  delete [] card;
267  return false;
268  }
269  delete [] card;
270  return true;
271  }
273  virtual Assignment* assignment(void) const {
274  if (arity > randomArity)
275  return new RandomAssignment(arity,dom,4000);
276  else
277  return new CpltAssignment(arity,dom);
278  }
280  virtual void post(Gecode::Space& home, Gecode::IntVarArray& xy) {
281  using namespace Gecode;
282  // Number of cardinality variables
283  int m = xy.size()-n;
284  IntVarArgs x(n), y(m);
285  for (int i=0; i<n; i++)
286  x[i]=xy[i];
287  for (int i=0; i<m; i++)
288  y[i]=xy[n+i];
289  IntArgs values(m);
290  for (int i=m; i--;)
291  values[i] = i+dom.min();
292  count(home,x,y,values,icl);
293  }
294  };
295 
297  class Create {
298  public:
300  Create(void) {
301  for (IntConLevels icls; icls(); ++icls) {
302  (void) new IntAllMinMax(icls.icl());
303  (void) new IntAllMinMaxDef(icls.icl());
304  (void) new IntAllMax(icls.icl());
305  (void) new IntSome<false>(icls.icl());
306  (void) new IntSome<true>(icls.icl());
307  (void) new VarAll(icls.icl());
308  (void) new VarSome("Small",2,-1,3,icls.icl());
309  (void) new VarSome("Large",3,-1,4,icls.icl());
310  }
311  }
312  };
313 
316 
317  }
318 }}
319 
320 // STATISTICS: test-int
IntConLevel
Consistency levels for integer propagators.
Definition: int.hh:937
Help class to create and register tests.
Definition: gcc.cpp:297
Test for integer cardinality with max cardinality for all variables
Definition: gcc.cpp:122
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: gcc.cpp:166
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
IntSome(Gecode::IntConLevel icl)
Create and register test.
Definition: gcc.cpp:151
virtual Assignment * assignment(void) const
Create and register initial assignment.
Definition: gcc.cpp:273
VarAll(Gecode::IntConLevel icl)
Create and register test.
Definition: gcc.cpp:189
int n
Number of non-cardinality variables.
Definition: gcc.cpp:235
Test for variable cardinality for all cardinality values
Definition: gcc.cpp:183
IntAllMinMaxDef(Gecode::IntConLevel icl)
Create and register test.
Definition: gcc.cpp:92
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: gcc.cpp:251
Gecode::IntSet dom
Domain of variables.
Definition: int.hh:220
Iterator for integer consistency levels.
Definition: int.hh:324
Integer variable array.
Definition: int.hh:741
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
ConTestLevel contest
Whether to test for certain consistency.
Definition: int.hh:228
Computation spaces.
Definition: core.hpp:1362
Generate random selection of assignments.
Definition: int.hh:100
void count(Home home, const IntVarArgs &x, const IntSet &c, const IntArgs &v, IntConLevel icl)
Posts a global count (cardinality) constraint.
Definition: gcc.cpp:224
static std::string str(Gecode::ExtensionalPropKind epk)
Map extensional propagation kind to string.
Definition: int.hpp:212
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: gcc.cpp:95
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition: gcc.cpp:280
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
VarSome(std::string s, int n0, int min, int max, Gecode::IntConLevel icl)
Create and register test.
Definition: gcc.cpp:240
No consistency-test.
Definition: int.hh:144
Gecode::IntConLevel icl
Consistency level.
Definition: int.hh:226
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: gcc.cpp:75
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: gcc.cpp:155
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: gcc.cpp:109
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: gcc.cpp:192
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: gcc.cpp:61
Integer sets.
Definition: int.hh:171
Test for variable cardinality for some cardinality values
Definition: gcc.cpp:232
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition: gcc.cpp:139
Passing integer variables.
Definition: int.hh:636
Passing integer arguments.
Definition: int.hh:607
General test support.
Definition: afc.cpp:43
Create c
Definition: gcc.cpp:314
void values(Home home, const IntVarArgs &x, IntSet y, IntConLevel icl=ICL_DEF)
Post constraint .
Definition: minimodel.hh:1869
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
Definition: count.cpp:44
bool testsearch
Whether to perform search test.
Definition: int.hh:230
virtual void post(Gecode::Space &home, Gecode::IntVarArray &xy)
Post constraint on xy.
Definition: gcc.cpp:217
Base class for assignments
Definition: int.hh:63
IntAllMinMax(Gecode::IntConLevel icl)
Create and register test.
Definition: gcc.cpp:58
Test for integer cardinality with min and max for all variables
Definition: gcc.cpp:89
Gecode toplevel namespace
Create(void)
Perform creation and registration.
Definition: gcc.cpp:300
int arity
Number of variables.
Definition: int.hh:218
Test for integer cardinality with min and max for all variables
Definition: gcc.cpp:55
Test for integer cardinality for some variables
Definition: gcc.cpp:148
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition: gcc.cpp:128
int size(void) const
Return number of variables.
Definition: int.hpp:50
IntAllMax(Gecode::IntConLevel icl)
Create and register test.
Definition: gcc.cpp:125
Generate all assignments.
Definition: int.hh:83
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:115