Generated on Wed Jan 24 2018 21:22:26 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  * Last modified:
14  * $Date: 2017-02-17 09:01:39 +0100 (Fri, 17 Feb 2017) $ by $Author: schulte $
15  * $Revision: 15441 $
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  }
153 
159  const char* bool_assign_name[] = {
161  "BOOL_ASSIGN_MIN",
162  "BOOL_ASSIGN_MAX",
163  "BOOL_ASSIGN_RND",
164  "BOOL_ASSIGN"
165  };
167  const int n_bool_assign =
168  sizeof(bool_assign_name)/sizeof(const char*);
171  return x.min();
172  }
174 
175  IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
176  : Base("Int::Assign::"+s), arity(a), dom(d) {
177  }
178 
179  bool
180  IntTest::run(void) {
181  using namespace Gecode;
182  IntTestSpace* root = new IntTestSpace(arity,dom);
183  post(*root, root->x);
184  (void) root->status();
185 
186  for (int val = 0; val<n_int_assign; val++) {
187  IntTestSpace* clone = static_cast<IntTestSpace*>(root->clone(false));
189  o.a_d = Base::rand(10);
190  o.c_d = Base::rand(10);
191 
192  Rnd r(1);
193  IntAssign ia;
194  switch (val) {
195  case 0: ia = INT_ASSIGN_MIN(); break;
196  case 1: ia = INT_ASSIGN_MED(); break;
197  case 2: ia = INT_ASSIGN_MAX(); break;
198  case 3: ia = INT_ASSIGN_RND(r); break;
199  case 4: ia = INT_ASSIGN(&int_val); break;
200  }
201 
202  assign(*clone, clone->x, ia);
203  Gecode::DFS<IntTestSpace> e_s(clone, o);
204  delete clone;
205 
206  // Find number of solutions
207  int solutions = 0;
208  while (Space* s = e_s.next()) {
209  delete s; solutions++;
210  }
211  if (solutions != 1) {
212  std::cout << "FAILURE" << std::endl
213  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
214  << "\t" << int_assign_name[val] << std::endl;
215  delete root;
216  return false;
217  }
218  }
219  delete root;
220  return true;
221  }
222 
223  BoolTest::BoolTest(const std::string& s, int a)
224  : Base("Bool::Assign::"+s), arity(a) {
225  }
226 
227  bool
229  using namespace Gecode;
230  BoolTestSpace* root = new BoolTestSpace(arity);
231  post(*root, root->x);
232  (void) root->status();
233 
234  for (int val = n_bool_assign; val--; ) {
235  BoolTestSpace* clone = static_cast<BoolTestSpace*>(root->clone(false));
237  o.a_d = Base::rand(10);
238  o.c_d = Base::rand(10);
239  Rnd r(1);
240  BoolAssign ia;
241  switch (val) {
242  case 0: ia = BOOL_ASSIGN_MIN(); break;
243  case 1: ia = BOOL_ASSIGN_MAX(); break;
244  case 2: ia = BOOL_ASSIGN_RND(r); break;
245  case 3: ia = BOOL_ASSIGN(&bool_val); break;
246  }
247 
248  assign(*clone, clone->x, ia);
249  Gecode::DFS<BoolTestSpace> e_s(clone, o);
250  delete clone;
251 
252  // Find number of solutions
253  int solutions = 0;
254  while (Space* s = e_s.next()) {
255  delete s; solutions++;
256  }
257  if (solutions != 1) {
258  std::cout << "FAILURE" << std::endl
259  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
260  << "\t" << int_assign_name[val] << std::endl;
261  delete root;
262  return false;
263  }
264  }
265  delete root;
266  return true;
267  }
268 
269 #ifdef GECODE_HAS_SET_VARS
270 
276  const char* set_assign_name[] = {
278  "SET_ASSIGN_MIN_INC",
279  "SET_ASSIGN_MIN_EXC",
280  "SET_ASSIGN_MED_INC",
281  "SET_ASSIGN_MED_EXC",
282  "SET_ASSIGN_MAX_INC",
283  "SET_ASSIGN_MAX_EXC",
284  "SET_ASSIGN_RND_INC",
285  "SET_ASSIGN_RND_EXC",
286  "SET_ASSIGN"
287  };
289  const int n_set_assign =
290  sizeof(set_assign_name)/sizeof(const char*);
292  int set_val(const Gecode::Space&, Gecode::SetVar x, int) {
294  return r.min();
295  }
297 
298  SetTest::SetTest(const std::string& s, int a, const Gecode::IntSet& d)
299  : Base("Set::Assign::"+s), arity(a), dom(d) {
300  }
301 
302  bool
303  SetTest::run(void) {
304  using namespace Gecode;
305  SetTestSpace* root = new SetTestSpace(arity,dom);
306  post(*root, root->x);
307  (void) root->status();
308 
309  for (int val = n_int_assign; val--; ) {
310  SetTestSpace* clone = static_cast<SetTestSpace*>(root->clone(false));
312  o.a_d = Base::rand(10);
313  o.c_d = Base::rand(10);
314 
315  Rnd r(1);
316 
317  SetAssign sa;
318  switch (val) {
319  case 0: sa = SET_ASSIGN_MIN_INC(); break;
320  case 1: sa = SET_ASSIGN_MIN_EXC(); break;
321  case 2: sa = SET_ASSIGN_MED_INC(); break;
322  case 3: sa = SET_ASSIGN_MED_EXC(); break;
323  case 4: sa = SET_ASSIGN_MAX_INC(); break;
324  case 5: sa = SET_ASSIGN_MAX_EXC(); break;
325  case 6: sa = SET_ASSIGN_RND_INC(r); break;
326  case 7: sa = SET_ASSIGN_RND_EXC(r); break;
327  case 8: sa = SET_ASSIGN(&set_val); break;
328  }
329 
330  assign(*clone, clone->x, sa);
331  Gecode::DFS<SetTestSpace> e_s(clone, o);
332  delete clone;
333 
334  // Find number of solutions
335  int solutions = 0;
336  while (Space* s = e_s.next()) {
337  delete s; solutions++;
338  }
339  if (solutions != 1) {
340  std::cout << "FAILURE" << std::endl
341  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
342  << "\t" << set_assign_name[val] << std::endl;
343  delete root;
344  return false;
345  }
346  }
347  delete root;
348  return true;
349  }
350 
351 #endif
352 
353 #ifdef GECODE_HAS_FLOAT_VARS
354 
360  const char* float_assign_name[] = {
362  "FLOAT_ASSIGN_MIN",
363  "FLOAT_ASSIGN_MAX",
364  "FLOAT_ASSIGN_RND",
365  "FLOAT_ASSIGN"
366  };
368  const int n_float_assign =
369  sizeof(float_assign_name)/sizeof(const char*);
372  Gecode::FloatVar x, int) {
373  Gecode::FloatNumBranch nl; nl.n=x.med(); nl.l=true;
374  return nl;
375  }
377 
378  FloatTest::FloatTest(const std::string& s, int a, const Gecode::FloatVal& d)
379  : Base("Float::Assign::"+s), arity(a), dom(d) {
380  }
381 
382  bool
384  using namespace Gecode;
385  FloatTestSpace* root = new FloatTestSpace(arity,dom);
386  post(*root, root->x);
387  (void) root->status();
388 
389  for (int val = n_float_assign; val--; ) {
390  FloatTestSpace* clone = static_cast<FloatTestSpace*>(root->clone(false));
392  o.a_d = Base::rand(10);
393  o.c_d = Base::rand(10);
394 
395  Rnd r(1);
396 
397  FloatAssign fa;
398  switch (val) {
399  case 0: fa = FLOAT_ASSIGN_MIN(); break;
400  case 1: fa = FLOAT_ASSIGN_MAX(); break;
401  case 2: fa = FLOAT_ASSIGN_RND(r); break;
402  case 3: fa = FLOAT_ASSIGN(&float_val); break;
403  }
404 
405  assign(*clone, clone->x, fa);
406  Gecode::DFS<FloatTestSpace> e_s(clone, o);
407  delete clone;
408 
409  // Find number of solutions
410  int solutions = 0;
411  while (Space* s = e_s.next()) {
412  delete s; solutions++;
413  }
414  if (solutions != 1) {
415  std::cout << "FAILURE" << std::endl
416  << "\tc_d=" << o.c_d << ", a_d=" << o.a_d << std::endl
417  << "\t" << float_assign_name[val] << std::endl;
418  delete root;
419  return false;
420  }
421  }
422  delete root;
423  return true;
424  }
425 
426 #endif
427 
428 }}
429 
430 // STATISTICS: test-branch
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:455
FloatTestSpace(int n, const Gecode::FloatVal &d)
Initialize test space.
Definition: assign.cpp:117
int min(void) const
Return minimum of domain.
Definition: bool.hpp:67
const char * int_assign_name[]
Names for integer assignments.
Definition: assign.cpp:138
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
virtual bool run(void)
Perform test.
Definition: assign.cpp:180
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
BoolAssign BOOL_ASSIGN_MIN(void)
Select smallest value.
Definition: assign.hpp:104
int set_val(const Gecode::Space &, Gecode::SetVar x, int)
Test function for branch value function.
Definition: assign.cpp:292
const int n_int_assign
Number of integer value selections.
Definition: assign.cpp:146
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
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:453
Search engine options
Definition: search.hh:446
Base(const std::string &s)
Create and register test with name s.
Definition: test.cpp:63
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 T * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: base.hpp:50
Gecode::FloatNumBranch float_val(const Gecode::Space &, Gecode::FloatVar x, int)
Test function for branch value function.
Definition: assign.cpp:371
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
Which values to select for assignment.
Definition: int.hh:4649
BoolTestSpace(bool share, BoolTestSpace &s)
Constructor for cloning s.
Definition: assign.cpp:76
Integer variable array.
Definition: int.hh:744
BoolAssign BOOL_ASSIGN_MAX(void)
Select largest value.
Definition: assign.hpp:109
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3326
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:178
Float variable array.
Definition: float.hh:1031
Computation spaces.
Definition: core.hpp:1748
SetAssign SET_ASSIGN_RND_INC(Rnd r)
Definition: assign.hpp:89
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:338
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.
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
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:850
IntAssign INT_ASSIGN(IntBranchVal v, IntBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: assign.hpp:79
FloatNum n
The middle value for branching.
Definition: float.hh:1411
virtual bool run(void)
Perform test.
Definition: assign.cpp:228
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
SetAssign SET_ASSIGN_MAX_INC(void)
Definition: assign.hpp:79
IntAssign INT_ASSIGN_RND(Rnd r)
Select random value.
Definition: assign.hpp:74
Value description class for branching.
Definition: float.hh:1408
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 arity
Number of variables.
Definition: assign.hh:87
bool l
Whether to try the lower or upper half first.
Definition: float.hh:1413
Base class for all tests to be run
Definition: test.hh:107
BoolAssign BOOL_ASSIGN_RND(Rnd r)
Select random value.
Definition: assign.hpp:114
BoolAssign BOOL_ASSIGN(BoolBranchVal v, BoolBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: assign.hpp:119
virtual bool run(void)
Perform test.
Definition: assign.cpp:383
Integer sets.
Definition: int.hh:174
virtual bool run(void)
Perform test.
Definition: assign.cpp:303
Space for executing Boolean tests.
Definition: assign.cpp:112
FloatNum med(void) const
Return median of domain.
Definition: float.hpp:67
SetAssign SET_ASSIGN_MED_INC(void)
Definition: assign.hpp:69
Space for executing integer tests.
Definition: assign.cpp:49
Boolean variable array.
Definition: int.hh:789
Boolean integer variables.
Definition: int.hh:494
General test support.
Definition: afc.cpp:43
SetAssign SET_ASSIGN_RND_EXC(Rnd r)
Definition: assign.hpp:94
Float value type.
Definition: float.hh:338
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Set variables
Definition: set.hh:131
Space(void)
Default constructor.
Definition: core.cpp:114
Gecode::FloatVarArray x
Variables to be tested.
Definition: assign.cpp:115
int min(void) const
Return minimum of domain.
Definition: int.hpp:66
SetAssign SET_ASSIGN_MIN_INC(void)
Definition: assign.hpp:59
Region r
Definition: region.cpp:82
SetAssign SET_ASSIGN(SetBranchVal v, SetBranchCommit c)
Select value as defined by the value function v and commit function c.
Definition: assign.hpp:99
Integer variables.
Definition: int.hh:353
SetAssign SET_ASSIGN_MED_EXC(void)
Definition: assign.hpp:74
Which values to select for assignment.
Definition: int.hh:4620
Gecode::BoolVarArray x
Variables to be tested.
Definition: assign.cpp:71
int bool_val(const Gecode::Space &, Gecode::BoolVar x, int)
Test function for branch value function.
Definition: assign.cpp:170
BoolTestSpace(int n)
Initialize test space.
Definition: assign.cpp:73
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:224
Which values to select for assignment.
Definition: float.hh:1811
SetAssign SET_ASSIGN_MAX_EXC(void)
Definition: assign.hpp:84
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:874
Set variable array
Definition: set.hh:572
Which value to select for assignment.
Definition: set.hh:1554
SetAssign SET_ASSIGN_MIN_EXC(void)
Definition: assign.hpp:64
Gecode toplevel namespace
Gecode::IntVarArray x
Variables to be tested.
Definition: assign.cpp:52
Random number generator.
Definition: rnd.hpp:46
virtual Gecode::Space * copy(bool share)
Copy space during cloning.
Definition: assign.cpp:102
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:115
Depth-first search engine.
Definition: search.hh:739
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:416
BoolTest(const std::string &s, int a)
Construct and register test.
Definition: assign.cpp:223
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:104
IntTestSpace(int n, Gecode::IntSet &d)
Initialize test space.
Definition: assign.cpp:54