Generated on Thu Mar 22 10:39:34 2012 for Gecode by doxygen 1.6.3

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