branch.cpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Mikael Lagerkvist <lagerkvist@gecode.org> 00005 * 00006 * Copyright: 00007 * Mikael Lagerkvist, 2005 00008 * 00009 * Last modified: 00010 * $Date: 2009-10-20 13:28:57 +0200 (Tue, 20 Oct 2009) $ by $Author: schulte $ 00011 * $Revision: 9975 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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, // Use several single variable branchers 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, // Use several single variable branchers 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 // Find number of solutions 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 // Results of tests run 00341 map<int, vector<RunInfo> > results; 00342 // Set up root space 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 // Results of tests run 00398 map<int, vector<RunInfo> > results; 00399 // Set up root space 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 // Results of tests run 00456 map<int, vector<RunInfo> > results; 00457 // Set up root space 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 // STATISTICS: test-branch