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