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: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $ 00011 * $Revision: 9878 $ 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 class VarBranchOptions { 00055 public: 00057 unsigned int seed; 00059 GECODE_KERNEL_EXPORT static const VarBranchOptions def; 00061 VarBranchOptions(void); 00063 static VarBranchOptions time(void); 00064 }; 00065 00069 class ValBranchOptions { 00070 public: 00072 unsigned int seed; 00074 GECODE_KERNEL_EXPORT static const ValBranchOptions def; 00076 ValBranchOptions(void); 00078 static ValBranchOptions time(void); 00079 }; 00080 00081 00083 template<class VarBranch> 00084 class TieBreakVarBranch { 00085 public: 00087 VarBranch a, b, c, d; 00089 TieBreakVarBranch(VarBranch a0 = static_cast<VarBranch>(0), 00090 VarBranch b0 = static_cast<VarBranch>(0), 00091 VarBranch c0 = static_cast<VarBranch>(0), 00092 VarBranch d0 = static_cast<VarBranch>(0)); 00093 }; 00094 00096 class TieBreakVarBranchOptions { 00097 public: 00099 VarBranchOptions a, b, c, d; 00101 GECODE_KERNEL_EXPORT static const TieBreakVarBranchOptions def; 00103 TieBreakVarBranchOptions(const VarBranchOptions& a0 00104 = VarBranchOptions::def, 00105 const VarBranchOptions& b0 00106 = VarBranchOptions::def, 00107 const VarBranchOptions& c0 00108 = VarBranchOptions::def, 00109 const VarBranchOptions& d0 00110 = VarBranchOptions::def); 00111 }; 00112 00119 00120 template<class VarBranch> 00121 TieBreakVarBranch<VarBranch> 00122 tiebreak(VarBranch a, VarBranch b); 00124 template<class VarBranch> 00125 TieBreakVarBranch<VarBranch> 00126 tiebreak(VarBranch a, VarBranch b, VarBranch c); 00128 template<class VarBranch> 00129 TieBreakVarBranch<VarBranch> 00130 tiebreak(VarBranch a, VarBranch b, VarBranch c, VarBranch d); 00132 TieBreakVarBranchOptions 00133 tiebreak(VarBranchOptions a, VarBranchOptions b); 00135 TieBreakVarBranchOptions 00136 tiebreak(VarBranchOptions a, VarBranchOptions b, VarBranchOptions c); 00138 TieBreakVarBranchOptions 00139 tiebreak(VarBranchOptions a, VarBranchOptions b, VarBranchOptions c, 00140 VarBranchOptions d); 00142 00154 00155 GECODE_KERNEL_EXPORT void 00156 branch(Home home, void (*f)(Space& home)); 00158 00159 00160 // Variable branch options 00161 forceinline 00162 VarBranchOptions::VarBranchOptions(void) : seed(0) {} 00163 forceinline VarBranchOptions 00164 VarBranchOptions::time(void) { 00165 VarBranchOptions o; o.seed=static_cast<unsigned int>(::time(NULL)); 00166 return o; 00167 } 00168 00169 // Value branch options 00170 forceinline 00171 ValBranchOptions::ValBranchOptions(void) : seed(0) {} 00172 forceinline ValBranchOptions 00173 ValBranchOptions::time(void) { 00174 ValBranchOptions o; o.seed=static_cast<unsigned int>(::time(NULL)); 00175 return o; 00176 } 00177 00178 00179 /* 00180 * Combine variable selection criteria for tie-breaking 00181 */ 00182 template<class VarBranch> 00183 forceinline 00184 TieBreakVarBranch<VarBranch>::TieBreakVarBranch(VarBranch a0, 00185 VarBranch b0, 00186 VarBranch c0, 00187 VarBranch d0) 00188 : a(a0), b(b0), c(c0), d(d0) {} 00189 00190 template<class VarBranch> 00191 forceinline TieBreakVarBranch<VarBranch> 00192 tiebreak(VarBranch a, VarBranch b) { 00193 TieBreakVarBranch<VarBranch> ab(a,b); 00194 return ab; 00195 } 00196 00197 template<class VarBranch> 00198 forceinline TieBreakVarBranch<VarBranch> 00199 tiebreak(VarBranch a, VarBranch b, VarBranch c) { 00200 TieBreakVarBranch<VarBranch> abc(a,b,c); 00201 return abc; 00202 } 00203 00204 template<class VarBranch> 00205 forceinline TieBreakVarBranch<VarBranch> 00206 tiebreak(VarBranch a, VarBranch b, VarBranch c, VarBranch d) { 00207 TieBreakVarBranch<VarBranch> abcd(a,b,c,d); 00208 return abcd; 00209 } 00210 00211 /* 00212 * Combine branch options for tie-breaking 00213 */ 00214 forceinline 00215 TieBreakVarBranchOptions:: 00216 TieBreakVarBranchOptions(const VarBranchOptions& a0, 00217 const VarBranchOptions& b0, 00218 const VarBranchOptions& c0, 00219 const VarBranchOptions& d0) 00220 : a(a0), b(b0), c(c0), d(d0) {} 00221 00222 forceinline TieBreakVarBranchOptions 00223 tiebreak(VarBranchOptions a, VarBranchOptions b) { 00224 TieBreakVarBranchOptions ab(a,b); 00225 return ab; 00226 } 00227 00228 forceinline TieBreakVarBranchOptions 00229 tiebreak(VarBranchOptions a, VarBranchOptions b, VarBranchOptions c) { 00230 TieBreakVarBranchOptions abc(a,b,c); 00231 return abc; 00232 } 00233 00234 forceinline TieBreakVarBranchOptions 00235 tiebreak(VarBranchOptions a, VarBranchOptions b, VarBranchOptions c, 00236 VarBranchOptions d) { 00237 TieBreakVarBranchOptions abcd(a,b,c,d); 00238 return abcd; 00239 } 00240 00241 } 00242 00243 // STATISTICS: kernel-branch