Generated on Sat Feb 7 2015 02:01:31 for Gecode by doxygen 1.8.9.1
assign.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Contributing authors:
7  * Vincent Barichard <Vincent.Barichard@univ-angers.fr>
8  *
9  * Copyright:
10  * Christian Schulte, 2008
11  * Vincent Barichard, 2012
12  *
13  * Last modified:
14  * $Date: 2013-05-29 13:53:43 +0200 (Wed, 29 May 2013) $ by $Author: schulte $
15  * $Revision: 13672 $
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/assign.hh"
43 
44 #include <gecode/search.hh>
45 
46 namespace Test { namespace Assign {
47 
49  class IntTestSpace : public Gecode::Space {
50  public:
55  : x(*this, n, d) {}
57  IntTestSpace(bool share, IntTestSpace& s)
58  : Gecode::Space(share,s) {
59  x.update(*this, share, s.x);
60  }
62  virtual Gecode::Space* copy(bool share) {
63  return new IntTestSpace(share,*this);
64  }
65  };
66 
68  class BoolTestSpace : public Gecode::Space {
69  public:
74  : x(*this, n, 0, 1) {}
76  BoolTestSpace(bool share, BoolTestSpace& s)
77  : Gecode::Space(share,s) {
78  x.update(*this, share, s.x);
79  }
81  virtual Gecode::Space* copy(bool share) {
82  return new BoolTestSpace(share,*this);
83  }
84  };
85 
86 #ifdef GECODE_HAS_SET_VARS
87 
89  class SetTestSpace : public Gecode::Space {
90  public:
95  : x(*this, n, Gecode::IntSet::empty, d) {}
97  SetTestSpace(bool share, SetTestSpace& s)
98  : Gecode::Space(share,s) {
99  x.update(*this, share, s.x);
100  }
102  virtual Gecode::Space* copy(bool share) {
103  return new SetTestSpace(share,*this);
104  }
105  };
106 
107 #endif
108 
109 #ifdef GECODE_HAS_FLOAT_VARS
110 
112  class FloatTestSpace : public Gecode::Space {
113  public:
118  : x(*this, n, d.min(), d.max()) {}
121  : Gecode::Space(share,s) {
122  x.update(*this, share, s.x);
123  }
125  virtual Gecode::Space* copy(bool share) {
126  return new FloatTestSpace(share,*this);
127  }
128  };
129 
130 #endif
131 
137  const char* int_assign_name[] = {
139  "INT_ASSIGN_MIN",
140  "INT_ASSIGN_MED",
141  "INT_ASSIGN_MAX",
142  "INT_ASSIGN_RND",
143  "INT_ASSIGN"
144  };
146  const int n_int_assign =
147  sizeof(int_assign_name)/sizeof(const char*);
149  int int_val(const Gecode::Space&, Gecode::IntVar x, int) {
150  return x.min();
151  }
154  return x.min();
155  }
157 
158  IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
159  : Base("Int::Assign::"+s), arity(a), dom(d) {
160  }
161 
162  bool
163  IntTest::run(void) {
164  using namespace Gecode;
165  IntTestSpace* root = new IntTestSpace(arity,dom);
166  post(*root, root->x);
167  (void) root->status();
168 
169  for (int val = 0; val<n_int_assign; val++) {
170  IntTestSpace* clone = static_cast<IntTestSpace*>(root->clone(false));
172  o.a_d = Base::rand(10);
173  o.c_d = Base::rand(10);
174 
175  Rnd r(1);
176  IntAssign ia;
177  switch (val) {
178  case 0: ia = INT_ASSIGN_MIN(); break;
179  case 1: ia = INT_ASSIGN_MED(); break;
180  case 2: ia = INT_ASSIGN_MAX(); break;
181  case 3: ia = INT_ASSIGN_RND(r); break;
182  case 4: ia = INT_ASSIGN(&int_val); break;
183  }
184 
185  assign(*clone, clone->x, ia);
186  Gecode::DFS<IntTestSpace> e_s(clone, o);
187  delete clone;
188 
189  // Find number of solutions
190  int solutions = 0;
191  while (Space* s = e_s.next()) {
192  delete s; solutions++;
193  }
194  if (solutions != 1) {
195  std::cout << "FAILURE" << std::endl
196  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
197  << "\t" << int_assign_name[val] << std::endl;
198  delete root;
199  return false;
200  }
201  }
202  delete root;
203  return true;
204  }
205 
206  BoolTest::BoolTest(const std::string& s, int a)
207  : Base("Bool::Assign::"+s), arity(a) {
208  }
209 
210  bool
212  using namespace Gecode;
213  BoolTestSpace* root = new BoolTestSpace(arity);
214  post(*root, root->x);
215  (void) root->status();
216 
217  for (int val = n_int_assign; val--; ) {
218  BoolTestSpace* clone = static_cast<BoolTestSpace*>(root->clone(false));
220  o.a_d = Base::rand(10);
221  o.c_d = Base::rand(10);
222  Rnd r(1);
223  IntAssign ia;
224  switch (val) {
225  case 0: ia = INT_ASSIGN_MIN(); break;
226  case 1: ia = INT_ASSIGN_MED(); break;
227  case 2: ia = INT_ASSIGN_MAX(); break;
228  case 3: ia = INT_ASSIGN_RND(r); break;
229  case 4: ia = INT_ASSIGN(&bool_val); break;
230  }
231 
232  assign(*clone, clone->x, ia);
233  Gecode::DFS<BoolTestSpace> e_s(clone, o);
234  delete clone;
235 
236  // Find number of solutions
237  int solutions = 0;
238  while (Space* s = e_s.next()) {
239  delete s; solutions++;
240  }
241  if (solutions != 1) {
242  std::cout << "FAILURE" << std::endl
243  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
244  << "\t" << int_assign_name[val] << std::endl;
245  delete root;
246  return false;
247  }
248  }
249  delete root;
250  return true;
251  }
252 
253 #ifdef GECODE_HAS_SET_VARS
254 
260  const char* set_assign_name[] = {
262  "SET_ASSIGN_MIN_INC",
263  "SET_ASSIGN_MIN_EXC",
264  "SET_ASSIGN_MED_INC",
265  "SET_ASSIGN_MED_EXC",
266  "SET_ASSIGN_MAX_INC",
267  "SET_ASSIGN_MAX_EXC",
268  "SET_ASSIGN_RND_INC",
269  "SET_ASSIGN_RND_EXC",
270  "SET_ASSIGN"
271  };
273  const int n_set_assign =
274  sizeof(set_assign_name)/sizeof(const char*);
276  int set_val(const Gecode::Space&, Gecode::SetVar x, int) {
278  return r.min();
279  }
281 
282  SetTest::SetTest(const std::string& s, int a, const Gecode::IntSet& d)
283  : Base("Set::Assign::"+s), arity(a), dom(d) {
284  }
285 
286  bool
287  SetTest::run(void) {
288  using namespace Gecode;
289  SetTestSpace* root = new SetTestSpace(arity,dom);
290  post(*root, root->x);
291  (void) root->status();
292 
293  for (int val = n_int_assign; val--; ) {
294  SetTestSpace* clone = static_cast<SetTestSpace*>(root->clone(false));
296  o.a_d = Base::rand(10);
297  o.c_d = Base::rand(10);
298 
299  Rnd r(1);
300 
301  SetAssign sa;
302  switch (val) {
303  case 0: sa = SET_ASSIGN_MIN_INC(); break;
304  case 1: sa = SET_ASSIGN_MIN_EXC(); break;
305  case 2: sa = SET_ASSIGN_MED_INC(); break;
306  case 3: sa = SET_ASSIGN_MED_EXC(); break;
307  case 4: sa = SET_ASSIGN_MAX_INC(); break;
308  case 5: sa = SET_ASSIGN_MAX_EXC(); break;
309  case 6: sa = SET_ASSIGN_RND_INC(r); break;
310  case 7: sa = SET_ASSIGN_RND_EXC(r); break;
311  case 8: sa = SET_ASSIGN(&set_val); break;
312  }
313 
314  assign(*clone, clone->x, sa);
315  Gecode::DFS<SetTestSpace> e_s(clone, o);
316  delete clone;
317 
318  // Find number of solutions
319  int solutions = 0;
320  while (Space* s = e_s.next()) {
321  delete s; solutions++;
322  }
323  if (solutions != 1) {
324  std::cout << "FAILURE" << std::endl
325  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
326  << "\t" << set_assign_name[val] << std::endl;
327  delete root;
328  return false;
329  }
330  }
331  delete root;
332  return true;
333  }
334 
335 #endif
336 
337 #ifdef GECODE_HAS_FLOAT_VARS
338 
344  const char* float_assign_name[] = {
346  "FLOAT_ASSIGN_MIN",
347  "FLOAT_ASSIGN_MAX",
348  "FLOAT_ASSIGN_RND",
349  "FLOAT_ASSIGN"
350  };
352  const int n_float_assign =
353  sizeof(float_assign_name)/sizeof(const char*);
356  Gecode::FloatVar x, int) {
357  Gecode::FloatNumBranch nl; nl.n=x.med(); nl.l=true;
358  return nl;
359  }
361 
362  FloatTest::FloatTest(const std::string& s, int a, const Gecode::FloatVal& d)
363  : Base("Float::Assign::"+s), arity(a), dom(d) {
364  }
365 
366  bool
368  using namespace Gecode;
369  FloatTestSpace* root = new FloatTestSpace(arity,dom);
370  post(*root, root->x);
371  (void) root->status();
372 
373  for (int val = n_float_assign; val--; ) {
374  FloatTestSpace* clone = static_cast<FloatTestSpace*>(root->clone(false));
376  o.a_d = Base::rand(10);
377  o.c_d = Base::rand(10);
378 
379  Rnd r(1);
380 
381  FloatAssign fa;
382  switch (val) {
383  case 0: fa = FLOAT_ASSIGN_MIN(); break;
384  case 1: fa = FLOAT_ASSIGN_MAX(); break;
385  case 2: fa = FLOAT_ASSIGN_RND(r); break;
386  case 3: fa = FLOAT_ASSIGN(&float_val); break;
387  }
388 
389  assign(*clone, clone->x, fa);
390  Gecode::DFS<FloatTestSpace> e_s(clone, o);
391  delete clone;
392 
393  // Find number of solutions
394  int solutions = 0;
395  while (Space* s = e_s.next()) {
396  delete s; solutions++;
397  }
398  if (solutions != 1) {
399  std::cout << "FAILURE" << std::endl
400  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
401  << "\t" << float_assign_name[val] << std::endl;
402  delete root;
403  return false;
404  }
405  }
406  delete root;
407  return true;
408  }
409 
410 #endif
411 
412 }}
413 
414 // STATISTICS: test-branch
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:213
FloatTestSpace(int n, const Gecode::FloatVal &d)
Initialize test space.
Definition: assign.cpp:117
Gecode::FloatVal dom
Domain of variables.
Definition: assign.hh:131
int int_val(const Gecode::Space &, Gecode::IntVar x, int)
Test function for branch value function.
Definition: assign.cpp:149
IntTestSpace(bool share, IntTestSpace &s)
Constructor for cloning s.
Definition: assign.cpp:57
SetAssign SET_ASSIGN_MIN_EXC(void)
Exclude smallest element.
Definition: assign.hpp:64
virtual bool run(void)
Perform test.
Definition: assign.cpp:163
int set_val(const Gecode::Space &, Gecode::SetVar x, int)
Test function for branch value function.
Definition: assign.cpp:276
FloatNum med(void) const
Return median of domain.
Definition: float.hpp:67
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
FloatAssign FLOAT_ASSIGN_MAX(void)
Select median value of the upper part.
Definition: assign.hpp:64
static Gecode::Support::RandomGenerator rand
Random number generator.
Definition: test.hh:138
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:211
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:2854
Search engine options
Definition: search.hh:204
FloatTestSpace(bool share, FloatTestSpace &s)
Constructor for cloning s.
Definition: assign.cpp:120
IntAssign INT_ASSIGN_MED(void)
Select greatest value not greater than the median.
Definition: assign.hpp:64
virtual Gecode::Space * copy(bool share)
Copy space during cloning.
Definition: assign.cpp:125
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)=0
Post assignment on variables x.
Gecode::FloatNumBranch float_val(const Gecode::Space &, Gecode::FloatVar x, int)
Test function for branch value function.
Definition: assign.cpp:355
FloatAssign FLOAT_ASSIGN_MIN(void)
Select median value of the lower part.
Definition: assign.hpp:59
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
SetAssign SET_ASSIGN(SetBranchVal v, SetBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: assign.hpp:99
BoolTestSpace(bool share, BoolTestSpace &s)
Constructor for cloning s.
Definition: assign.cpp:76
Integer variable array.
Definition: int.hh:741
SetTest(const std::string &s, int a, const Gecode::IntSet &d)
Construct and register test.
SetAssign SET_ASSIGN_MAX_INC(void)
Include largest element.
Definition: assign.hpp:79
Float variable array.
Definition: float.hh:1016
Computation spaces.
Definition: core.hpp:1362
virtual void post(Gecode::Space &home, Gecode::FloatVarArray &x)=0
Post assignment on variables x.
SetAssign SET_ASSIGN_RND_EXC(Rnd r)
Exclude random element.
Definition: assign.hpp:94
SetTestSpace(int n, const Gecode::IntSet &d)
Initialize test space.
Definition: assign.cpp:94
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:59
Iterator for the unknown ranges of a set variable.
Definition: set.hh:336
Space for executing Boolean tests.
Definition: assign.cpp:68
Gecode::IntSet d(v, 7)
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
virtual void post(Gecode::Space &home, Gecode::BoolVarArray &x)=0
Post assignment on variables x.
SetAssign SET_ASSIGN_MAX_EXC(void)
Exclude largest element.
Definition: assign.hpp:84
virtual Gecode::Space * copy(bool share)
Copy space during cloning.
Definition: assign.cpp:81
SetTestSpace(bool share, SetTestSpace &s)
Constructor for cloning s.
Definition: assign.cpp:97
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
FloatNum n
The middle value for branching.
Definition: float.hh:1375
virtual bool run(void)
Perform test.
Definition: assign.cpp:211
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
FloatAssign FLOAT_ASSIGN_RND(Rnd r)
Select median value of a randomly chosen part.
Definition: assign.hpp:69
IntAssign INT_ASSIGN_RND(Rnd r)
Select random value.
Definition: assign.hpp:74
Value description class for branching.
Definition: float.hh:1372
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
IntTest(const std::string &s, int a, const Gecode::IntSet &d)
Construct and register test.
IntAssign INT_ASSIGN_MAX(void)
Select largest value.
Definition: assign.hpp:69
int bool_val(const Gecode::Space &, Gecode::BoolVar x, int)
Test function for branch value function.
Definition: assign.cpp:153
int arity
Number of variables.
Definition: assign.hh:87
int arity
Number of variables.
Definition: assign.hh:129
bool l
Whether to try the lower or upper half first.
Definition: float.hh:1377
Base class for all tests to be run
Definition: test.hh:107
virtual bool run(void)
Perform test.
Definition: assign.cpp:367
Integer sets.
Definition: int.hh:171
virtual bool run(void)
Perform test.
Definition: assign.cpp:287
Space for executing Boolean tests.
Definition: assign.cpp:112
Space for executing integer tests.
Definition: assign.cpp:49
Boolean variable array.
Definition: int.hh:786
Boolean integer variables.
Definition: int.hh:491
SetAssign SET_ASSIGN_MIN_INC(void)
Include smallest element.
Definition: assign.hpp:59
General test support.
Definition: afc.cpp:43
SetAssign SET_ASSIGN_MED_INC(void)
Include median element (rounding downwards)
Definition: assign.hpp:69
Float value type.
Definition: float.hh:321
IntAssign INT_ASSIGN(IntBranchVal v, IntBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: assign.hpp:79
BrancherHandle assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:113
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Set variables
Definition: set.hh:129
Space(void)
Default constructor.
Definition: core.cpp:114
Gecode::FloatVarArray x
Variables to be tested.
Definition: assign.cpp:115
Integer variables.
Definition: int.hh:350
SetAssign SET_ASSIGN_MED_EXC(void)
Exclude median element (rounding downwards)
Definition: assign.hpp:74
T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: dfs.hpp:52
Which values to select for assignment.
Definition: int.hh:4081
Gecode::BoolVarArray x
Variables to be tested.
Definition: assign.cpp:71
BoolTestSpace(int n)
Initialize test space.
Definition: assign.cpp:73
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
Which values to select for assignment.
Definition: float.hh:1700
FloatAssign FLOAT_ASSIGN(FloatBranchVal v, FloatBranchCommit c)
Definition: assign.hpp:74
Space for executing Boolean tests.
Definition: assign.cpp:89
FloatTest(const std::string &s, int a, const Gecode::FloatVal &d)
Construct and register test.
Float variables.
Definition: float.hh:857
int min(void) const
Return smallest value of range.
Definition: set.hpp:178
Set variable array
Definition: set.hh:571
Which value to select for assignment.
Definition: set.hh:1452
Gecode toplevel namespace
Gecode::IntVarArray x
Variables to be tested.
Definition: assign.cpp:52
int min(void) const
Return minimum of domain.
Definition: int.hpp:66
SetAssign SET_ASSIGN_RND_INC(Rnd r)
Include random element.
Definition: assign.hpp:89
int min(void) const
Return minimum of domain.
Definition: bool.hpp:67
int arity
Number of variables.
Definition: assign.hh:68
Random number generator.
Definition: rnd.hpp:46
virtual Gecode::Space * copy(bool share)
Copy space during cloning.
Definition: assign.cpp:102
virtual void post(Gecode::Space &home, Gecode::SetVarArray &x)=0
Post assignment on variables x.
Gecode::IntSet dom
Domain of variables.
Definition: assign.hh:70
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
Depth-first search engine.
Definition: search.hh:494
Gecode::SetVarArray x
Variables to be tested.
Definition: assign.cpp:92
int solutions(TestSpace *c, Gecode::Search::Options &o, int maxNbSol=-1)
Find number of solutions.
Definition: branch.cpp:379
int arity
Number of variables.
Definition: assign.hh:106
Gecode::IntSet dom
Upper bound of variable domains.
Definition: assign.hh:108
BoolTest(const std::string &s, int a)
Construct and register test.
Definition: assign.cpp:206
virtual Gecode::Space * copy(bool share)
Copy space during cloning.
Definition: assign.cpp:62
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:93
IntTestSpace(int n, Gecode::IntSet &d)
Initialize test space.
Definition: assign.cpp:54