Generated on Sat Oct 20 2018 12:43:45 for Gecode by doxygen 1.8.13
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  * 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 "test/assign.hh"
39 
40 #include <gecode/search.hh>
41 
42 namespace Test { namespace Assign {
43 
45  class IntTestSpace : public Gecode::Space {
46  public:
51  : x(*this, n, d) {}
54  : Gecode::Space(s) {
55  x.update(*this, s.x);
56  }
58  virtual Gecode::Space* copy(void) {
59  return new IntTestSpace(*this);
60  }
61  };
62 
64  class BoolTestSpace : public Gecode::Space {
65  public:
70  : x(*this, n, 0, 1) {}
73  : Gecode::Space(s) {
74  x.update(*this, s.x);
75  }
77  virtual Gecode::Space* copy(void) {
78  return new BoolTestSpace(*this);
79  }
80  };
81 
82 #ifdef GECODE_HAS_SET_VARS
83 
85  class SetTestSpace : public Gecode::Space {
86  public:
91  : x(*this, n, Gecode::IntSet::empty, d) {}
94  : Gecode::Space(s) {
95  x.update(*this, s.x);
96  }
98  virtual Gecode::Space* copy(void) {
99  return new SetTestSpace(*this);
100  }
101  };
102 
103 #endif
104 
105 #ifdef GECODE_HAS_FLOAT_VARS
106 
108  class FloatTestSpace : public Gecode::Space {
109  public:
114  : x(*this, n, d.min(), d.max()) {}
117  : Gecode::Space(s) {
118  x.update(*this, s.x);
119  }
121  virtual Gecode::Space* copy(void) {
122  return new FloatTestSpace(*this);
123  }
124  };
125 
126 #endif
127 
133  const char* int_assign_name[] = {
135  "INT_ASSIGN_MIN",
136  "INT_ASSIGN_MED",
137  "INT_ASSIGN_MAX",
138  "INT_ASSIGN_RND",
139  "INT_ASSIGN"
140  };
142  const int n_int_assign =
143  sizeof(int_assign_name)/sizeof(const char*);
145  int int_val(const Gecode::Space&, Gecode::IntVar x, int) {
146  return x.min();
147  }
149 
155  const char* bool_assign_name[] = {
157  "BOOL_ASSIGN_MIN",
158  "BOOL_ASSIGN_MAX",
159  "BOOL_ASSIGN_RND",
160  "BOOL_ASSIGN"
161  };
163  const int n_bool_assign =
164  sizeof(bool_assign_name)/sizeof(const char*);
167  return x.min();
168  }
170 
171  IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
172  : Base("Int::Assign::"+s), arity(a), dom(d) {
173  }
174 
175  bool
176  IntTest::run(void) {
177  using namespace Gecode;
178  IntTestSpace* root = new IntTestSpace(arity,dom);
179  post(*root, root->x);
180  (void) root->status();
181 
182  for (int val = 0; val<n_int_assign; val++) {
183  IntTestSpace* clone = static_cast<IntTestSpace*>(root->clone());
185  o.a_d = Base::rand(10);
186  o.c_d = Base::rand(10);
187 
188  Rnd r(1);
189  IntAssign ia;
190  switch (val) {
191  case 0: ia = INT_ASSIGN_MIN(); break;
192  case 1: ia = INT_ASSIGN_MED(); break;
193  case 2: ia = INT_ASSIGN_MAX(); break;
194  case 3: ia = INT_ASSIGN_RND(r); break;
195  case 4: ia = INT_ASSIGN(&int_val); break;
196  }
197 
198  assign(*clone, clone->x, ia);
199  Gecode::DFS<IntTestSpace> e_s(clone, o);
200  delete clone;
201 
202  // Find number of solutions
203  int solutions = 0;
204  while (Space* s = e_s.next()) {
205  delete s; solutions++;
206  }
207  if (solutions != 1) {
208  std::cout << "FAILURE" << std::endl
209  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
210  << "\t" << int_assign_name[val] << std::endl;
211  delete root;
212  return false;
213  }
214  }
215  delete root;
216  return true;
217  }
218 
219  BoolTest::BoolTest(const std::string& s, int a)
220  : Base("Bool::Assign::"+s), arity(a) {
221  }
222 
223  bool
225  using namespace Gecode;
226  BoolTestSpace* root = new BoolTestSpace(arity);
227  post(*root, root->x);
228  (void) root->status();
229 
230  for (int val = n_bool_assign; val--; ) {
231  BoolTestSpace* clone = static_cast<BoolTestSpace*>(root->clone());
233  o.a_d = Base::rand(10);
234  o.c_d = Base::rand(10);
235  Rnd r(1);
236  BoolAssign ia;
237  switch (val) {
238  case 0: ia = BOOL_ASSIGN_MIN(); break;
239  case 1: ia = BOOL_ASSIGN_MAX(); break;
240  case 2: ia = BOOL_ASSIGN_RND(r); break;
241  case 3: ia = BOOL_ASSIGN(&bool_val); break;
242  }
243 
244  assign(*clone, clone->x, ia);
245  Gecode::DFS<BoolTestSpace> e_s(clone, o);
246  delete clone;
247 
248  // Find number of solutions
249  int solutions = 0;
250  while (Space* s = e_s.next()) {
251  delete s; solutions++;
252  }
253  if (solutions != 1) {
254  std::cout << "FAILURE" << std::endl
255  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
256  << "\t" << int_assign_name[val] << std::endl;
257  delete root;
258  return false;
259  }
260  }
261  delete root;
262  return true;
263  }
264 
265 #ifdef GECODE_HAS_SET_VARS
266 
272  const char* set_assign_name[] = {
274  "SET_ASSIGN_MIN_INC",
275  "SET_ASSIGN_MIN_EXC",
276  "SET_ASSIGN_MED_INC",
277  "SET_ASSIGN_MED_EXC",
278  "SET_ASSIGN_MAX_INC",
279  "SET_ASSIGN_MAX_EXC",
280  "SET_ASSIGN_RND_INC",
281  "SET_ASSIGN_RND_EXC",
282  "SET_ASSIGN"
283  };
285  const int n_set_assign =
286  sizeof(set_assign_name)/sizeof(const char*);
288  int set_val(const Gecode::Space&, Gecode::SetVar x, int) {
290  return r.min();
291  }
293 
294  SetTest::SetTest(const std::string& s, int a, const Gecode::IntSet& d)
295  : Base("Set::Assign::"+s), arity(a), dom(d) {
296  }
297 
298  bool
299  SetTest::run(void) {
300  using namespace Gecode;
301  SetTestSpace* root = new SetTestSpace(arity,dom);
302  post(*root, root->x);
303  (void) root->status();
304 
305  for (int val = n_int_assign; val--; ) {
306  SetTestSpace* clone = static_cast<SetTestSpace*>(root->clone());
308  o.a_d = Base::rand(10);
309  o.c_d = Base::rand(10);
310 
311  Rnd r(1);
312 
313  SetAssign sa;
314  switch (val) {
315  case 0: sa = SET_ASSIGN_MIN_INC(); break;
316  case 1: sa = SET_ASSIGN_MIN_EXC(); break;
317  case 2: sa = SET_ASSIGN_MED_INC(); break;
318  case 3: sa = SET_ASSIGN_MED_EXC(); break;
319  case 4: sa = SET_ASSIGN_MAX_INC(); break;
320  case 5: sa = SET_ASSIGN_MAX_EXC(); break;
321  case 6: sa = SET_ASSIGN_RND_INC(r); break;
322  case 7: sa = SET_ASSIGN_RND_EXC(r); break;
323  case 8: sa = SET_ASSIGN(&set_val); break;
324  }
325 
326  assign(*clone, clone->x, sa);
327  Gecode::DFS<SetTestSpace> e_s(clone, o);
328  delete clone;
329 
330  // Find number of solutions
331  int solutions = 0;
332  while (Space* s = e_s.next()) {
333  delete s; solutions++;
334  }
335  if (solutions != 1) {
336  std::cout << "FAILURE" << std::endl
337  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
338  << "\t" << set_assign_name[val] << std::endl;
339  delete root;
340  return false;
341  }
342  }
343  delete root;
344  return true;
345  }
346 
347 #endif
348 
349 #ifdef GECODE_HAS_FLOAT_VARS
350 
356  const char* float_assign_name[] = {
358  "FLOAT_ASSIGN_MIN",
359  "FLOAT_ASSIGN_MAX",
360  "FLOAT_ASSIGN_RND",
361  "FLOAT_ASSIGN"
362  };
364  const int n_float_assign =
365  sizeof(float_assign_name)/sizeof(const char*);
368  Gecode::FloatVar x, int) {
369  Gecode::FloatNumBranch nl; nl.n=x.med(); nl.l=true;
370  return nl;
371  }
373 
374  FloatTest::FloatTest(const std::string& s, int a, const Gecode::FloatVal& d)
375  : Base("Float::Assign::"+s), arity(a), dom(d) {
376  }
377 
378  bool
380  using namespace Gecode;
381  FloatTestSpace* root = new FloatTestSpace(arity,dom);
382  post(*root, root->x);
383  (void) root->status();
384 
385  for (int val = n_float_assign; val--; ) {
386  FloatTestSpace* clone = static_cast<FloatTestSpace*>(root->clone());
388  o.a_d = Base::rand(10);
389  o.c_d = Base::rand(10);
390 
391  Rnd r(1);
392 
393  FloatAssign fa;
394  switch (val) {
395  case 0: fa = FLOAT_ASSIGN_MIN(); break;
396  case 1: fa = FLOAT_ASSIGN_MAX(); break;
397  case 2: fa = FLOAT_ASSIGN_RND(r); break;
398  case 3: fa = FLOAT_ASSIGN(&float_val); break;
399  }
400 
401  assign(*clone, clone->x, fa);
402  Gecode::DFS<FloatTestSpace> e_s(clone, o);
403  delete clone;
404 
405  // Find number of solutions
406  int solutions = 0;
407  while (Space* s = e_s.next()) {
408  delete s; solutions++;
409  }
410  if (solutions != 1) {
411  std::cout << "FAILURE" << std::endl
412  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
413  << "\t" << float_assign_name[val] << std::endl;
414  delete root;
415  return false;
416  }
417  }
418  delete root;
419  return true;
420  }
421 
422 #endif
423 
424 }}
425 
426 // STATISTICS: test-branch
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:755
FloatTestSpace(int n, const Gecode::FloatVal &d)
Initialize test space.
Definition: assign.cpp:113
int min(void) const
Return minimum of domain.
Definition: bool.hpp:63
const char * int_assign_name[]
Names for integer assignments.
Definition: assign.cpp:134
int int_val(const Gecode::Space &, Gecode::IntVar x, int)
Test function for branch value function.
Definition: assign.cpp:145
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition: assign.cpp:58
virtual bool run(void)
Perform test.
Definition: assign.cpp:176
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition: assign.cpp:77
FloatTestSpace(FloatTestSpace &s)
Constructor for cloning s.
Definition: assign.cpp:116
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:238
BoolAssign BOOL_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:100
int set_val(const Gecode::Space &, Gecode::SetVar x, int)
Test function for branch value function.
Definition: assign.cpp:288
const int n_int_assign
Number of integer value selections.
Definition: assign.cpp:142
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
FloatAssign FLOAT_ASSIGN_MAX(void)
Select median value of the upper part.
Definition: assign.hpp:60
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:995
static Gecode::Support::RandomGenerator rand
Random number generator.
Definition: test.hh:134
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:753
Search engine options
Definition: search.hh:746
Base(const std::string &s)
Create and register test with name s.
Definition: test.cpp:59
IntAssign INT_ASSIGN_MED(void)
Select greatest value not greater than the median.
Definition: assign.hpp:60
virtual T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:46
Gecode::FloatNumBranch float_val(const Gecode::Space &, Gecode::FloatVar x, int)
Test function for branch value function.
Definition: assign.cpp:367
FloatAssign FLOAT_ASSIGN_MIN(void)
Select median value of the lower part.
Definition: assign.hpp:55
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
Which values to select for assignment.
Definition: int.hh:4937
Integer variable array.
Definition: int.hh:763
BoolAssign BOOL_ASSIGN_MAX(void)
Select largest value.
Definition: assign.hpp:105
SetTest(const std::string &s, int a, const Gecode::IntSet &d)
Construct and register test.
int min(void) const
Return smallest value of range.
Definition: set.hpp:174
Float variable array.
Definition: float.hh:1030
Computation spaces.
Definition: core.hpp:1701
SetAssign SET_ASSIGN_RND_INC(Rnd r)
Definition: assign.hpp:85
SetTestSpace(int n, const Gecode::IntSet &d)
Initialize test space.
Definition: assign.cpp:90
IntAssign INT_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:55
Iterator for the unknown ranges of a set variable.
Definition: set.hh:334
Space for executing Boolean tests.
Definition: assign.cpp:64
Gecode::IntSet d(v, 7)
virtual void post(Gecode::Space &home, Gecode::BoolVarArray &x)=0
Post assignment on variables x.
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
IntAssign INT_ASSIGN(IntBranchVal v, IntBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: assign.hpp:75
FloatNum n
The middle value for branching.
Definition: float.hh:1465
virtual bool run(void)
Perform test.
Definition: assign.cpp:224
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
FloatAssign FLOAT_ASSIGN_RND(Rnd r)
Select median value of a randomly chosen part.
Definition: assign.hpp:65
SetAssign SET_ASSIGN_MAX_INC(void)
Definition: assign.hpp:75
IntAssign INT_ASSIGN_RND(Rnd r)
Select random value.
Definition: assign.hpp:70
Value description class for branching.
Definition: float.hh:1462
IntTest(const std::string &s, int a, const Gecode::IntSet &d)
Construct and register test.
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3181
IntAssign INT_ASSIGN_MAX(void)
Select largest value.
Definition: assign.hpp:65
int arity
Number of variables.
Definition: assign.hh:83
bool l
Whether to try the lower or upper half first.
Definition: float.hh:1467
Base class for all tests to be run
Definition: test.hh:103
BoolTestSpace(BoolTestSpace &s)
Constructor for cloning s.
Definition: assign.cpp:72
BoolAssign BOOL_ASSIGN_RND(Rnd r)
Select random value.
Definition: assign.hpp:110
BoolAssign BOOL_ASSIGN(BoolBranchVal v, BoolBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: assign.hpp:115
virtual bool run(void)
Perform test.
Definition: assign.cpp:379
Integer sets.
Definition: int.hh:174
virtual bool run(void)
Perform test.
Definition: assign.cpp:299
Space for executing Boolean tests.
Definition: assign.cpp:108
IntTestSpace(IntTestSpace &s)
Constructor for cloning s.
Definition: assign.cpp:53
FloatNum med(void) const
Return median of domain.
Definition: float.hpp:63
SetAssign SET_ASSIGN_MED_INC(void)
Definition: assign.hpp:65
Space for executing integer tests.
Definition: assign.cpp:45
Boolean variable array.
Definition: int.hh:808
Boolean integer variables.
Definition: int.hh:512
SetTestSpace(SetTestSpace &s)
Constructor for cloning s.
Definition: assign.cpp:93
General test support.
Definition: afc.cpp:39
SetAssign SET_ASSIGN_RND_EXC(Rnd r)
Definition: assign.hpp:90
Float value type.
Definition: float.hh:334
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Set variables
Definition: set.hh:127
Space(void)
Default constructor.
Definition: core.cpp:115
Gecode::FloatVarArray x
Variables to be tested.
Definition: assign.cpp:111
int min(void) const
Return minimum of domain.
Definition: int.hpp:62
SetAssign SET_ASSIGN_MIN_INC(void)
Definition: assign.hpp:55
Region r
Definition: region.cpp:65
SetAssign SET_ASSIGN(SetBranchVal v, SetBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: assign.hpp:95
Integer variables.
Definition: int.hh:371
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition: assign.cpp:121
SetAssign SET_ASSIGN_MED_EXC(void)
Definition: assign.hpp:70
Which values to select for assignment.
Definition: int.hh:4908
Gecode::BoolVarArray x
Variables to be tested.
Definition: assign.cpp:67
int bool_val(const Gecode::Space &, Gecode::BoolVar x, int)
Test function for branch value function.
Definition: assign.cpp:166
BoolTestSpace(int n)
Initialize test space.
Definition: assign.cpp:69
virtual Gecode::Space * copy(void)
Copy space during cloning.
Definition: assign.cpp:98
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:232
Which values to select for assignment.
Definition: float.hh:1874
SetAssign SET_ASSIGN_MAX_EXC(void)
Definition: assign.hpp:80
FloatAssign FLOAT_ASSIGN(FloatBranchVal v, FloatBranchCommit c)
Definition: assign.hpp:70
Space for executing Boolean tests.
Definition: assign.cpp:85
FloatTest(const std::string &s, int a, const Gecode::FloatVal &d)
Construct and register test.
Float variables.
Definition: float.hh:870
Set variable array
Definition: set.hh:570
Which value to select for assignment.
Definition: set.hh:1517
SetAssign SET_ASSIGN_MIN_EXC(void)
Definition: assign.hpp:60
Gecode toplevel namespace
Gecode::IntVarArray x
Variables to be tested.
Definition: assign.cpp:48
Random number generator.
Definition: rnd.hpp:42
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:111
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
Depth-first search engine.
Definition: search.hh:1036
Gecode::SetVarArray x
Variables to be tested.
Definition: assign.cpp:88
int solutions(TestSpace *c, Gecode::Search::Options &o, int maxNbSol=-1)
Find number of solutions.
Definition: branch.cpp:412
BoolTest(const std::string &s, int a)
Construct and register test.
Definition: assign.cpp:219
const bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:108
IntTestSpace(int n, Gecode::IntSet &d)
Initialize test space.
Definition: assign.cpp:50