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

branch.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2008
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-09-03 10:30:37 +0200 (Fri, 03 Sep 2010) $ by $Author: schulte $
00011  *     $Revision: 11386 $
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 <ctime>
00039 
00040 namespace Gecode {
00041 
00054   typedef bool (*BranchFilter)(const Space& home, int i, const Var& x);
00055 
00059   class VarBranchOptions {
00060   public:
00062     BranchFilter bf;
00064     unsigned int seed;
00066     GECODE_KERNEL_EXPORT static const VarBranchOptions def;
00068     VarBranchOptions(BranchFilter bf0=NULL);
00070     static VarBranchOptions time(BranchFilter bf=NULL);
00071   };
00072 
00076   class ValBranchOptions {
00077   public:
00079     unsigned int seed;
00081     GECODE_KERNEL_EXPORT static const ValBranchOptions def;
00083     ValBranchOptions(void);
00085     static ValBranchOptions time(void);
00086   };
00087 
00088 
00090   template<class VarBranch>
00091   class TieBreakVarBranch {
00092   public:
00094     VarBranch a, b, c, d;
00096     TieBreakVarBranch(VarBranch a0 = static_cast<VarBranch>(0),
00097                       VarBranch b0 = static_cast<VarBranch>(0),
00098                       VarBranch c0 = static_cast<VarBranch>(0),
00099                       VarBranch d0 = static_cast<VarBranch>(0));
00100   };
00101 
00103   class TieBreakVarBranchOptions {
00104   public:
00106     VarBranchOptions a, b, c, d;
00108     GECODE_KERNEL_EXPORT static const TieBreakVarBranchOptions def;
00110     TieBreakVarBranchOptions(const VarBranchOptions& a0
00111                              = VarBranchOptions::def,
00112                              const VarBranchOptions& b0
00113                              = VarBranchOptions::def,
00114                              const VarBranchOptions& c0
00115                              = VarBranchOptions::def,
00116                              const VarBranchOptions& d0
00117                              = VarBranchOptions::def);
00118   };
00119 
00126 
00127   template<class VarBranch>
00128   TieBreakVarBranch<VarBranch>
00129   tiebreak(VarBranch a, VarBranch b);
00131   template<class VarBranch>
00132   TieBreakVarBranch<VarBranch>
00133   tiebreak(VarBranch a, VarBranch b, VarBranch c);
00135   template<class VarBranch>
00136   TieBreakVarBranch<VarBranch>
00137   tiebreak(VarBranch a, VarBranch b, VarBranch c, VarBranch d);
00139   TieBreakVarBranchOptions
00140   tiebreak(VarBranchOptions a, VarBranchOptions b);
00142   TieBreakVarBranchOptions
00143   tiebreak(VarBranchOptions a, VarBranchOptions b, VarBranchOptions c);
00145   TieBreakVarBranchOptions
00146   tiebreak(VarBranchOptions a, VarBranchOptions b, VarBranchOptions c,
00147            VarBranchOptions d);
00149 
00161 
00162   GECODE_KERNEL_EXPORT void
00163   branch(Home home, void (*f)(Space& home));
00165 
00166 
00167   // Variable branch options
00168   forceinline
00169   VarBranchOptions::VarBranchOptions(BranchFilter bf0) 
00170     : bf(bf0), seed(0) {}
00171 
00172   forceinline VarBranchOptions
00173   VarBranchOptions::time(BranchFilter bf) {
00174     VarBranchOptions o(bf); 
00175     o.seed=static_cast<unsigned int>(::time(NULL));
00176     return o;
00177   }
00178 
00179   // Value branch options
00180   forceinline
00181   ValBranchOptions::ValBranchOptions(void) : seed(0) {}
00182 
00183   forceinline ValBranchOptions
00184   ValBranchOptions::time(void) {
00185     ValBranchOptions o; o.seed=static_cast<unsigned int>(::time(NULL));
00186     return o;
00187   }
00188 
00189 
00190   /*
00191    * Combine variable selection criteria for tie-breaking
00192    */
00193   template<class VarBranch>
00194   forceinline
00195   TieBreakVarBranch<VarBranch>::TieBreakVarBranch(VarBranch a0,
00196                                                   VarBranch b0,
00197                                                   VarBranch c0,
00198                                                   VarBranch d0)
00199     : a(a0), b(b0), c(c0), d(d0) {}
00200 
00201   template<class VarBranch>
00202   forceinline TieBreakVarBranch<VarBranch>
00203   tiebreak(VarBranch a, VarBranch b) {
00204     TieBreakVarBranch<VarBranch> ab(a,b);
00205     return ab;
00206   }
00207 
00208   template<class VarBranch>
00209   forceinline TieBreakVarBranch<VarBranch>
00210   tiebreak(VarBranch a, VarBranch b, VarBranch c) {
00211     TieBreakVarBranch<VarBranch> abc(a,b,c);
00212     return abc;
00213   }
00214 
00215   template<class VarBranch>
00216   forceinline TieBreakVarBranch<VarBranch>
00217   tiebreak(VarBranch a, VarBranch b, VarBranch c, VarBranch d) {
00218     TieBreakVarBranch<VarBranch> abcd(a,b,c,d);
00219     return abcd;
00220   }
00221 
00222   /*
00223    * Combine branch options for tie-breaking
00224    */
00225   forceinline
00226   TieBreakVarBranchOptions::
00227   TieBreakVarBranchOptions(const VarBranchOptions& a0,
00228                            const VarBranchOptions& b0,
00229                            const VarBranchOptions& c0,
00230                            const VarBranchOptions& d0)
00231     : a(a0), b(b0), c(c0), d(d0) {}
00232 
00233   forceinline TieBreakVarBranchOptions
00234   tiebreak(VarBranchOptions a, VarBranchOptions b) {
00235     TieBreakVarBranchOptions ab(a,b);
00236     return ab;
00237   }
00238 
00239   forceinline TieBreakVarBranchOptions
00240   tiebreak(VarBranchOptions a, VarBranchOptions b, VarBranchOptions c) {
00241     TieBreakVarBranchOptions abc(a,b,c);
00242     return abc;
00243   }
00244 
00245   forceinline TieBreakVarBranchOptions
00246   tiebreak(VarBranchOptions a, VarBranchOptions b, VarBranchOptions c,
00247            VarBranchOptions d) {
00248     TieBreakVarBranchOptions abcd(a,b,c,d);
00249     return abcd;
00250   }
00251 
00252 }
00253 
00254 // STATISTICS: kernel-branch