Generated on Fri Aug 31 2012 16:20:55 for Gecode by doxygen 1.8.1.2
branch.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, 2005
8  *
9  * Last modified:
10  * $Date: 2009-10-20 22:28:57 +1100 (Tue, 20 Oct 2009) $ by $Author: schulte $
11  * $Revision: 9975 $
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/branch.hh"
39 
40 #include <algorithm>
41 #include <map>
42 #include <vector>
43 #include <iostream>
44 
45 #include <gecode/kernel.hh>
46 #include <gecode/int.hh>
47 #ifdef GECODE_HAS_SET_VARS
48 #include <gecode/set.hh>
49 #endif
50 
51 #include <gecode/search.hh>
52 
53 namespace Test { namespace Branch {
54 
56  class IntTestSpace : public Gecode::Space {
57  public:
66  : x(*this, n, d),
67  vara(Gecode::INT_VAR_NONE), varb(Gecode::INT_VAR_NONE),
68  val(Gecode::INT_VAL_MIN) {}
70  IntTestSpace(bool share, IntTestSpace& s)
71  : Gecode::Space(share,s), vara(s.vara), varb(s.varb), val(s.val) {
72  x.update(*this, share, s.x);
73  }
75  virtual Gecode::Space* copy(bool share) {
76  return new IntTestSpace(share,*this);
77  }
78  };
79 
81  class BoolTestSpace : public Gecode::Space {
82  public:
87  : x(*this, n, 0, 1) {}
89  BoolTestSpace(bool share, BoolTestSpace& s)
90  : Gecode::Space(share,s) {
91  x.update(*this, share, s.x);
92  }
94  virtual Gecode::Space* copy(bool share) {
95  return new BoolTestSpace(share,*this);
96  }
97  };
98 
99 #ifdef GECODE_HAS_SET_VARS
100 
101  class SetTestSpace : public Gecode::Space {
102  public:
107  : x(*this, n, Gecode::IntSet::empty, d) {}
109  SetTestSpace(bool share, SetTestSpace& s)
110  : Gecode::Space(share,s) {
111  x.update(*this, share, s.x);
112  }
114  virtual Gecode::Space* copy(bool share) {
115  return new SetTestSpace(share,*this);
116  }
117  };
118 #endif
119 
125 
126  const Gecode::IntVarBranch int_var_branch[] = {
127  Gecode::INT_VAR_NONE, // Use several single variable branchers
148  };
150  const int n_int_var_branch =
151  sizeof(int_var_branch)/sizeof(Gecode::IntVarBranch);
153  const char* int_var_branch_name[] = {
154  "SINGLE VARIABLE",
155  "INT_VAR_NONE",
156  "INT_VAR_RND",
157  "INT_VAR_DEGREE_MIN",
158  "INT_VAR_DEGREE_MAX",
159  "INT_VAR_AFC_MIN",
160  "INT_VAR_AFC_MAX",
161  "INT_VAR_MIN_MIN",
162  "INT_VAR_MIN_MAX",
163  "INT_VAR_MAX_MIN",
164  "INT_VAR_MAX_MAX",
165  "INT_VAR_SIZE_MIN",
166  "INT_VAR_SIZE_MAX",
167  "INT_VAR_SIZE_DEGREE_MIN",
168  "INT_VAR_SIZE_DEGREE_MAX",
169  "INT_VAR_SIZE_AFC_MIN",
170  "INT_VAR_SIZE_AFC_MAX",
171  "INT_VAR_REGRET_MIN_MIN",
172  "INT_VAR_REGRET_MIN_MAX",
173  "INT_VAR_REGRET_MAX_MIN",
174  "INT_VAR_REGRET_MAX_MAX"
175  };
177  const Gecode::IntValBranch int_val_branch[] = {
188  };
190  const int n_int_val_branch =
191  sizeof(int_val_branch)/sizeof(Gecode::IntValBranch);
193  const char* int_val_branch_name[] = {
194  "INT_VAL_MIN",
195  "INT_VAL_MED",
196  "INT_VAL_MAX",
197  "INT_VAL_RND",
198  "INT_VAL_SPLIT_MIN",
199  "INT_VAL_SPLIT_MAX",
200  "INT_VAL_RANGE_MIN",
201  "INT_VAL_RANGE_MAX",
202  "INT_VALUES_MIN",
203  "INT_VALUES_MAX"
204  };
206 
207 #ifdef GECODE_HAS_SET_VARS
208 
213 
214  const Gecode::SetVarBranch set_var_branch[] = {
215  Gecode::SET_VAR_NONE, // Use several single variable branchers
232  };
234  const int n_set_var_branch =
235  sizeof(set_var_branch)/sizeof(Gecode::SetVarBranch);
237  const char* set_var_branch_name[] = {
238  "SINGLE VARIABLE",
239  "SET_VAR_NONE",
240  "SET_VAR_RND",
241  "SET_VAR_DEGREE_MIN",
242  "SET_VAR_DEGREE_MAX",
243  "SET_VAR_AFC_MIN",
244  "SET_VAR_AFC_MAX",
245  "SET_VAR_MIN_MIN",
246  "SET_VAR_MIN_MAX",
247  "SET_VAR_MAX_MIN",
248  "SET_VAR_MAX_MAX",
249  "SET_VAR_SIZE_MIN",
250  "SET_VAR_SIZE_MAX",
251  "SET_VAR_SIZE_DEGREE_MIN",
252  "SET_VAR_SIZE_DEGREE_MAX",
253  "SET_VAR_SIZE_AFC_MIN",
254  "SET_VAR_SIZE_AFC_MAX"
255  };
257  const Gecode::SetValBranch set_val_branch[] = {
266  };
268  const int n_set_val_branch =
269  sizeof(set_val_branch)/sizeof(Gecode::SetValBranch);
271  const char* set_val_branch_name[] = {
272  "SET_VAL_MIN_INC",
273  "SET_VAL_MIN_EXC",
274  "SET_VAL_MED_INC",
275  "SET_VAL_MED_EXC",
276  "SET_VAL_MAX_INC",
277  "SET_VAL_MAX_EXC",
278  "SET_VAL_RND_INC",
279  "SET_VAL_RND_EXC"
280  };
282 #endif
283 
285  class RunInfo {
286  public:
287  std::string var, val;
288  unsigned int a_d, c_d;
289  RunInfo(const std::string& vara, const std::string& varb,
290  const std::string& valname,
291  const Gecode::Search::Options& o)
292  : var(vara + "::" + varb), val(valname), a_d(o.a_d), c_d(o.c_d) {}
293  void print(std::ostream& o) const {
294  o << "(" << var << ", " << val << ", " << a_d << ", " << c_d << ")";
295  }
296  };
297 
298 }}
299 
300 std::ostream&
301 operator<<(std::ostream& os, const Test::Branch::RunInfo& ri) {
302  ri.print(os);
303  return os;
304 }
305 
306 
307 namespace Test { namespace Branch {
308 
310  template<class TestSpace>
311  int solutions(TestSpace* c, Gecode::Search::Options& o) {
312  o.a_d = Base::rand(10);
313  o.c_d = Base::rand(10);
314  Gecode::DFS<TestSpace> e_s(c, o);
315  delete c;
316 
317  // Find number of solutions
318  int s = 0;
319  do {
320  Gecode::Space* ex = e_s.next();
321  if (ex == NULL) break;
322  delete ex;
323  ++s;
324  } while (true);
325  return s;
326  }
327 
328  IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
329  : Base("Int::Branch::"+s), arity(a), dom(d) {
330  }
331 
332  bool
333  IntTest::run(void) {
334  using std::map;
335  using std::vector;
336  using std::string;
337  using std::ostream;
338  using namespace Gecode;
339 
340  // Results of tests run
341  map<int, vector<RunInfo> > results;
342  // Set up root space
343  IntTestSpace* root = new IntTestSpace(arity,dom);
344  post(*root, root->x);
345  results.clear();
346 
347  for (int vara = 0; vara<n_int_var_branch; vara++) {
348  for (int varb = 1; varb<n_int_var_branch; varb++) {
349  for (int val = 0; val<n_int_val_branch; val++) {
350  IntTestSpace* c = static_cast<IntTestSpace*>(root->clone(false));
351  if (vara == 0)
352  for (int i=0; i<c->x.size(); i++)
353  branch(*c, c->x[i], int_val_branch[val]);
354  else
355  branch(*c, c->x,
356  tiebreak(int_var_branch[vara], int_var_branch[varb]),
357  int_val_branch[val]);
359  results[solutions(c,o)].push_back
360  (RunInfo(int_var_branch_name[vara],
361  int_var_branch_name[varb],
362  int_val_branch_name[val],
363  o));
364  }
365  }
366  }
367  if (results.size() > 1)
368  goto failed;
369  delete root;
370  return true;
371  failed:
372  std::cout << "FAILURE" << std::endl;
373  for (map<int, vector<RunInfo> >::iterator it = results.begin();
374  it != results.end(); ++it) {
375  std::cout << "Number of solutions: " << it->first << std::endl;
376  for (unsigned int i = 0; i < it->second.size(); ++i)
377  std::cout << it->second[i] << " ";
378  std::cout << std::endl;
379  }
380 
381  delete root;
382  return results.size() == 1;
383  }
384 
385  BoolTest::BoolTest(const std::string& s, int a)
386  : Base("Bool::Branch::"+s), arity(a) {
387  }
388 
389  bool
391  using std::map;
392  using std::vector;
393  using std::string;
394  using std::ostream;
395  using namespace Gecode;
396 
397  // Results of tests run
398  map<int, vector<RunInfo> > results;
399  // Set up root space
400  BoolTestSpace* root = new BoolTestSpace(arity);
401  post(*root, root->x);
402  results.clear();
403 
404  for (int vara = 0; vara<n_int_var_branch; vara++) {
405  for (int varb = 1; varb<n_int_var_branch; varb++) {
406  for (int val = 0; val<n_int_val_branch; val++) {
407  BoolTestSpace* c = static_cast<BoolTestSpace*>(root->clone(false));
408  if (vara == 0)
409  for (int i=0; i<c->x.size(); i++)
410  branch(*c, c->x[i], int_val_branch[val]);
411  else
412  branch(*c, c->x,
413  tiebreak(int_var_branch[vara], int_var_branch[varb]),
414  int_val_branch[val]);
416  results[solutions(c,o)].push_back
417  (RunInfo(int_var_branch_name[vara],
418  int_var_branch_name[varb],
419  int_val_branch_name[val],
420  o));
421  }
422  }
423  }
424  if (results.size() > 1)
425  goto failed;
426  delete root;
427  return true;
428  failed:
429  std::cout << "FAILURE" << std::endl;
430  for (map<int, vector<RunInfo> >::iterator it = results.begin();
431  it != results.end(); ++it) {
432  std::cout << "Number of solutions: " << it->first << std::endl;
433  for (unsigned int i = 0; i < it->second.size(); ++i)
434  std::cout << it->second[i] << " ";
435  std::cout << std::endl;
436  }
437 
438  delete root;
439  return results.size() == 1;
440  }
441 
442 #ifdef GECODE_HAS_SET_VARS
443  SetTest::SetTest(const std::string& s, int a, const Gecode::IntSet& d)
444  : Base("Set::Branch::"+s), arity(a), dom(d) {
445  }
446 
447  bool
448  SetTest::run(void) {
449  using std::map;
450  using std::vector;
451  using std::string;
452  using std::ostream;
453  using namespace Gecode;
454 
455  // Results of tests run
456  map<int, vector<RunInfo> > results;
457  // Set up root space
458  SetTestSpace* root = new SetTestSpace(arity,dom);
459  post(*root, root->x);
460  root->status();
461  results.clear();
462 
463  for (int vara = 0; vara<n_set_var_branch; vara++) {
464  for (int varb = 1; varb<n_set_var_branch; varb++) {
465  for (int val = 0; val<n_set_val_branch; val++) {
466  SetTestSpace* c = static_cast<SetTestSpace*>(root->clone(false));
467  if (vara == 0)
468  for (int i=0; i<c->x.size(); i++)
469  branch(*c, c->x[i], set_val_branch[val]);
470  else
471  branch(*c, c->x,
472  tiebreak(set_var_branch[vara], set_var_branch[varb]),
473  set_val_branch[val]);
475  results[solutions(c,o)].push_back
476  (RunInfo(set_var_branch_name[vara],
477  set_var_branch_name[varb],
478  set_val_branch_name[val],
479  o));
480  }
481  }
482  }
483  if (results.size() > 1)
484  goto failed;
485  delete root;
486  return true;
487  failed:
488  std::cout << "FAILURE" << std::endl;
489  for (map<int, vector<RunInfo> >::iterator it = results.begin();
490  it != results.end(); ++it) {
491  std::cout << "Number of solutions: " << it->first << std::endl;
492  for (unsigned int i = 0; i < it->second.size(); ++i)
493  std::cout << it->second[i] << " ";
494  std::cout << std::endl;
495  }
496 
497  delete root;
498  return results.size() == 1;
499  }
500 #endif
501 
502 }}
503 
504 // STATISTICS: test-branch