00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include "test/branch.hh"
00039
00040 #include <algorithm>
00041 #include <map>
00042 #include <vector>
00043 #include <iostream>
00044
00045 #include <gecode/kernel.hh>
00046 #include <gecode/int.hh>
00047 #ifdef GECODE_HAS_SET_VARS
00048 #include <gecode/set.hh>
00049 #endif
00050
00051 #include <gecode/search.hh>
00052
00053 namespace Test { namespace Branch {
00054
00056 class IntTestSpace : public Gecode::Space {
00057 public:
00059 Gecode::IntVarArray x;
00061 Gecode::IntVarBranch vara, varb;
00063 Gecode::IntValBranch val;
00065 IntTestSpace(int n, Gecode::IntSet& d)
00066 : x(*this, n, d),
00067 vara(Gecode::INT_VAR_NONE), varb(Gecode::INT_VAR_NONE),
00068 val(Gecode::INT_VAL_MIN) {}
00070 IntTestSpace(bool share, IntTestSpace& s)
00071 : Gecode::Space(share,s), vara(s.vara), varb(s.varb), val(s.val) {
00072 x.update(*this, share, s.x);
00073 }
00075 virtual Gecode::Space* copy(bool share) {
00076 return new IntTestSpace(share,*this);
00077 }
00078 };
00079
00081 class BoolTestSpace : public Gecode::Space {
00082 public:
00084 Gecode::BoolVarArray x;
00086 BoolTestSpace(int n)
00087 : x(*this, n, 0, 1) {}
00089 BoolTestSpace(bool share, BoolTestSpace& s)
00090 : Gecode::Space(share,s) {
00091 x.update(*this, share, s.x);
00092 }
00094 virtual Gecode::Space* copy(bool share) {
00095 return new BoolTestSpace(share,*this);
00096 }
00097 };
00098
00099 #ifdef GECODE_HAS_SET_VARS
00100
00101 class SetTestSpace : public Gecode::Space {
00102 public:
00104 Gecode::SetVarArray x;
00106 SetTestSpace(int n, Gecode::IntSet& d)
00107 : x(*this, n, Gecode::IntSet::empty, d) {}
00109 SetTestSpace(bool share, SetTestSpace& s)
00110 : Gecode::Space(share,s) {
00111 x.update(*this, share, s.x);
00112 }
00114 virtual Gecode::Space* copy(bool share) {
00115 return new SetTestSpace(share,*this);
00116 }
00117 };
00118 #endif
00119
00125
00126 const Gecode::IntVarBranch int_var_branch[] = {
00127 Gecode::INT_VAR_NONE,
00128 Gecode::INT_VAR_NONE,
00129 Gecode::INT_VAR_RND,
00130 Gecode::INT_VAR_DEGREE_MIN,
00131 Gecode::INT_VAR_DEGREE_MAX,
00132 Gecode::INT_VAR_AFC_MIN,
00133 Gecode::INT_VAR_AFC_MAX,
00134 Gecode::INT_VAR_MIN_MIN,
00135 Gecode::INT_VAR_MIN_MAX,
00136 Gecode::INT_VAR_MAX_MIN,
00137 Gecode::INT_VAR_MAX_MAX,
00138 Gecode::INT_VAR_SIZE_MIN,
00139 Gecode::INT_VAR_SIZE_MAX,
00140 Gecode::INT_VAR_SIZE_DEGREE_MIN,
00141 Gecode::INT_VAR_SIZE_DEGREE_MAX,
00142 Gecode::INT_VAR_SIZE_AFC_MIN,
00143 Gecode::INT_VAR_SIZE_AFC_MAX,
00144 Gecode::INT_VAR_REGRET_MIN_MIN,
00145 Gecode::INT_VAR_REGRET_MIN_MAX,
00146 Gecode::INT_VAR_REGRET_MAX_MIN,
00147 Gecode::INT_VAR_REGRET_MAX_MAX
00148 };
00150 const int n_int_var_branch =
00151 sizeof(int_var_branch)/sizeof(Gecode::IntVarBranch);
00153 const char* int_var_branch_name[] = {
00154 "SINGLE VARIABLE",
00155 "INT_VAR_NONE",
00156 "INT_VAR_RND",
00157 "INT_VAR_DEGREE_MIN",
00158 "INT_VAR_DEGREE_MAX",
00159 "INT_VAR_AFC_MIN",
00160 "INT_VAR_AFC_MAX",
00161 "INT_VAR_MIN_MIN",
00162 "INT_VAR_MIN_MAX",
00163 "INT_VAR_MAX_MIN",
00164 "INT_VAR_MAX_MAX",
00165 "INT_VAR_SIZE_MIN",
00166 "INT_VAR_SIZE_MAX",
00167 "INT_VAR_SIZE_DEGREE_MIN",
00168 "INT_VAR_SIZE_DEGREE_MAX",
00169 "INT_VAR_SIZE_AFC_MIN",
00170 "INT_VAR_SIZE_AFC_MAX",
00171 "INT_VAR_REGRET_MIN_MIN",
00172 "INT_VAR_REGRET_MIN_MAX",
00173 "INT_VAR_REGRET_MAX_MIN",
00174 "INT_VAR_REGRET_MAX_MAX"
00175 };
00177 const Gecode::IntValBranch int_val_branch[] = {
00178 Gecode::INT_VAL_MIN,
00179 Gecode::INT_VAL_MED,
00180 Gecode::INT_VAL_MAX,
00181 Gecode::INT_VAL_RND,
00182 Gecode::INT_VAL_SPLIT_MIN,
00183 Gecode::INT_VAL_SPLIT_MAX,
00184 Gecode::INT_VAL_RANGE_MIN,
00185 Gecode::INT_VAL_RANGE_MAX,
00186 Gecode::INT_VALUES_MIN,
00187 Gecode::INT_VALUES_MAX
00188 };
00190 const int n_int_val_branch =
00191 sizeof(int_val_branch)/sizeof(Gecode::IntValBranch);
00193 const char* int_val_branch_name[] = {
00194 "INT_VAL_MIN",
00195 "INT_VAL_MED",
00196 "INT_VAL_MAX",
00197 "INT_VAL_RND",
00198 "INT_VAL_SPLIT_MIN",
00199 "INT_VAL_SPLIT_MAX",
00200 "INT_VAL_RANGE_MIN",
00201 "INT_VAL_RANGE_MAX",
00202 "INT_VALUES_MIN",
00203 "INT_VALUES_MAX"
00204 };
00206
00207 #ifdef GECODE_HAS_SET_VARS
00208
00213
00214 const Gecode::SetVarBranch set_var_branch[] = {
00215 Gecode::SET_VAR_NONE,
00216 Gecode::SET_VAR_NONE,
00217 Gecode::SET_VAR_RND,
00218 Gecode::SET_VAR_DEGREE_MIN,
00219 Gecode::SET_VAR_DEGREE_MAX,
00220 Gecode::SET_VAR_AFC_MIN,
00221 Gecode::SET_VAR_AFC_MAX,
00222 Gecode::SET_VAR_MIN_MIN,
00223 Gecode::SET_VAR_MIN_MAX,
00224 Gecode::SET_VAR_MAX_MIN,
00225 Gecode::SET_VAR_MAX_MAX,
00226 Gecode::SET_VAR_SIZE_MIN,
00227 Gecode::SET_VAR_SIZE_MAX,
00228 Gecode::SET_VAR_SIZE_DEGREE_MIN,
00229 Gecode::SET_VAR_SIZE_DEGREE_MAX,
00230 Gecode::SET_VAR_SIZE_AFC_MIN,
00231 Gecode::SET_VAR_SIZE_AFC_MAX
00232 };
00234 const int n_set_var_branch =
00235 sizeof(set_var_branch)/sizeof(Gecode::SetVarBranch);
00237 const char* set_var_branch_name[] = {
00238 "SINGLE VARIABLE",
00239 "SET_VAR_NONE",
00240 "SET_VAR_RND",
00241 "SET_VAR_DEGREE_MIN",
00242 "SET_VAR_DEGREE_MAX",
00243 "SET_VAR_AFC_MIN",
00244 "SET_VAR_AFC_MAX",
00245 "SET_VAR_MIN_MIN",
00246 "SET_VAR_MIN_MAX",
00247 "SET_VAR_MAX_MIN",
00248 "SET_VAR_MAX_MAX",
00249 "SET_VAR_SIZE_MIN",
00250 "SET_VAR_SIZE_MAX",
00251 "SET_VAR_SIZE_DEGREE_MIN",
00252 "SET_VAR_SIZE_DEGREE_MAX",
00253 "SET_VAR_SIZE_AFC_MIN",
00254 "SET_VAR_SIZE_AFC_MAX"
00255 };
00257 const Gecode::SetValBranch set_val_branch[] = {
00258 Gecode::SET_VAL_MIN_INC,
00259 Gecode::SET_VAL_MIN_EXC,
00260 Gecode::SET_VAL_MED_INC,
00261 Gecode::SET_VAL_MED_EXC,
00262 Gecode::SET_VAL_MAX_INC,
00263 Gecode::SET_VAL_MAX_EXC,
00264 Gecode::SET_VAL_RND_INC,
00265 Gecode::SET_VAL_RND_EXC
00266 };
00268 const int n_set_val_branch =
00269 sizeof(set_val_branch)/sizeof(Gecode::SetValBranch);
00271 const char* set_val_branch_name[] = {
00272 "SET_VAL_MIN_INC",
00273 "SET_VAL_MIN_EXC",
00274 "SET_VAL_MED_INC",
00275 "SET_VAL_MED_EXC",
00276 "SET_VAL_MAX_INC",
00277 "SET_VAL_MAX_EXC",
00278 "SET_VAL_RND_INC",
00279 "SET_VAL_RND_EXC"
00280 };
00282 #endif
00283
00285 class RunInfo {
00286 public:
00287 std::string var, val;
00288 unsigned int a_d, c_d;
00289 RunInfo(const std::string& vara, const std::string& varb,
00290 const std::string& valname,
00291 const Gecode::Search::Options& o)
00292 : var(vara + "::" + varb), val(valname), a_d(o.a_d), c_d(o.c_d) {}
00293 void print(std::ostream& o) const {
00294 o << "(" << var << ", " << val << ", " << a_d << ", " << c_d << ")";
00295 }
00296 };
00297
00298 }}
00299
00300 std::ostream&
00301 operator<<(std::ostream& os, const Test::Branch::RunInfo& ri) {
00302 ri.print(os);
00303 return os;
00304 }
00305
00306
00307 namespace Test { namespace Branch {
00308
00310 template<class TestSpace>
00311 int solutions(TestSpace* c, Gecode::Search::Options& o) {
00312 o.a_d = Base::rand(10);
00313 o.c_d = Base::rand(10);
00314 Gecode::DFS<TestSpace> e_s(c, o);
00315 delete c;
00316
00317
00318 int s = 0;
00319 do {
00320 Gecode::Space* ex = e_s.next();
00321 if (ex == NULL) break;
00322 delete ex;
00323 ++s;
00324 } while (true);
00325 return s;
00326 }
00327
00328 IntTest::IntTest(const std::string& s, int a, const Gecode::IntSet& d)
00329 : Base("Int::Branch::"+s), arity(a), dom(d) {
00330 }
00331
00332 bool
00333 IntTest::run(void) {
00334 using std::map;
00335 using std::vector;
00336 using std::string;
00337 using std::ostream;
00338 using namespace Gecode;
00339
00340
00341 map<int, vector<RunInfo> > results;
00342
00343 IntTestSpace* root = new IntTestSpace(arity,dom);
00344 post(*root, root->x);
00345 results.clear();
00346
00347 for (int vara = 0; vara<n_int_var_branch; vara++) {
00348 for (int varb = 1; varb<n_int_var_branch; varb++) {
00349 for (int val = 0; val<n_int_val_branch; val++) {
00350 IntTestSpace* c = static_cast<IntTestSpace*>(root->clone(false));
00351 if (vara == 0)
00352 for (int i=0; i<c->x.size(); i++)
00353 branch(*c, c->x[i], int_val_branch[val]);
00354 else
00355 branch(*c, c->x,
00356 tiebreak(int_var_branch[vara], int_var_branch[varb]),
00357 int_val_branch[val]);
00358 Gecode::Search::Options o;
00359 results[solutions(c,o)].push_back
00360 (RunInfo(int_var_branch_name[vara],
00361 int_var_branch_name[varb],
00362 int_val_branch_name[val],
00363 o));
00364 }
00365 }
00366 }
00367 if (results.size() > 1)
00368 goto failed;
00369 delete root;
00370 return true;
00371 failed:
00372 std::cout << "FAILURE" << std::endl;
00373 for (map<int, vector<RunInfo> >::iterator it = results.begin();
00374 it != results.end(); ++it) {
00375 std::cout << "Number of solutions: " << it->first << std::endl;
00376 for (unsigned int i = 0; i < it->second.size(); ++i)
00377 std::cout << it->second[i] << " ";
00378 std::cout << std::endl;
00379 }
00380
00381 delete root;
00382 return results.size() == 1;
00383 }
00384
00385 BoolTest::BoolTest(const std::string& s, int a)
00386 : Base("Bool::Branch::"+s), arity(a) {
00387 }
00388
00389 bool
00390 BoolTest::run(void) {
00391 using std::map;
00392 using std::vector;
00393 using std::string;
00394 using std::ostream;
00395 using namespace Gecode;
00396
00397
00398 map<int, vector<RunInfo> > results;
00399
00400 BoolTestSpace* root = new BoolTestSpace(arity);
00401 post(*root, root->x);
00402 results.clear();
00403
00404 for (int vara = 0; vara<n_int_var_branch; vara++) {
00405 for (int varb = 1; varb<n_int_var_branch; varb++) {
00406 for (int val = 0; val<n_int_val_branch; val++) {
00407 BoolTestSpace* c = static_cast<BoolTestSpace*>(root->clone(false));
00408 if (vara == 0)
00409 for (int i=0; i<c->x.size(); i++)
00410 branch(*c, c->x[i], int_val_branch[val]);
00411 else
00412 branch(*c, c->x,
00413 tiebreak(int_var_branch[vara], int_var_branch[varb]),
00414 int_val_branch[val]);
00415 Gecode::Search::Options o;
00416 results[solutions(c,o)].push_back
00417 (RunInfo(int_var_branch_name[vara],
00418 int_var_branch_name[varb],
00419 int_val_branch_name[val],
00420 o));
00421 }
00422 }
00423 }
00424 if (results.size() > 1)
00425 goto failed;
00426 delete root;
00427 return true;
00428 failed:
00429 std::cout << "FAILURE" << std::endl;
00430 for (map<int, vector<RunInfo> >::iterator it = results.begin();
00431 it != results.end(); ++it) {
00432 std::cout << "Number of solutions: " << it->first << std::endl;
00433 for (unsigned int i = 0; i < it->second.size(); ++i)
00434 std::cout << it->second[i] << " ";
00435 std::cout << std::endl;
00436 }
00437
00438 delete root;
00439 return results.size() == 1;
00440 }
00441
00442 #ifdef GECODE_HAS_SET_VARS
00443 SetTest::SetTest(const std::string& s, int a, const Gecode::IntSet& d)
00444 : Base("Set::Branch::"+s), arity(a), dom(d) {
00445 }
00446
00447 bool
00448 SetTest::run(void) {
00449 using std::map;
00450 using std::vector;
00451 using std::string;
00452 using std::ostream;
00453 using namespace Gecode;
00454
00455
00456 map<int, vector<RunInfo> > results;
00457
00458 SetTestSpace* root = new SetTestSpace(arity,dom);
00459 post(*root, root->x);
00460 root->status();
00461 results.clear();
00462
00463 for (int vara = 0; vara<n_set_var_branch; vara++) {
00464 for (int varb = 1; varb<n_set_var_branch; varb++) {
00465 for (int val = 0; val<n_set_val_branch; val++) {
00466 SetTestSpace* c = static_cast<SetTestSpace*>(root->clone(false));
00467 if (vara == 0)
00468 for (int i=0; i<c->x.size(); i++)
00469 branch(*c, c->x[i], set_val_branch[val]);
00470 else
00471 branch(*c, c->x,
00472 tiebreak(set_var_branch[vara], set_var_branch[varb]),
00473 set_val_branch[val]);
00474 Gecode::Search::Options o;
00475 results[solutions(c,o)].push_back
00476 (RunInfo(set_var_branch_name[vara],
00477 set_var_branch_name[varb],
00478 set_val_branch_name[val],
00479 o));
00480 }
00481 }
00482 }
00483 if (results.size() > 1)
00484 goto failed;
00485 delete root;
00486 return true;
00487 failed:
00488 std::cout << "FAILURE" << std::endl;
00489 for (map<int, vector<RunInfo> >::iterator it = results.begin();
00490 it != results.end(); ++it) {
00491 std::cout << "Number of solutions: " << it->first << std::endl;
00492 for (unsigned int i = 0; i < it->second.size(); ++i)
00493 std::cout << it->second[i] << " ";
00494 std::cout << std::endl;
00495 }
00496
00497 delete root;
00498 return results.size() == 1;
00499 }
00500 #endif
00501
00502 }}
00503
00504