1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Guido Tack <tack@gecode.org> 5 * Christian Schulte <schulte@gecode.org> 6 * 7 * Contributing authors: 8 * Gabor Szokoli <szokoli@gecode.org> 9 * 10 * Copyright: 11 * Guido Tack, 2004 12 * Christian Schulte, 2004 13 * Gabor Szokoli, 2004 14 * 15 * This file is part of Gecode, the generic constraint 16 * development environment: 17 * http://www.gecode.org 18 * 19 * Permission is hereby granted, free of charge, to any person obtaining 20 * a copy of this software and associated documentation files (the 21 * "Software"), to deal in the Software without restriction, including 22 * without limitation the rights to use, copy, modify, merge, publish, 23 * distribute, sublicense, and/or sell copies of the Software, and to 24 * permit persons to whom the Software is furnished to do so, subject to 25 * the following conditions: 26 * 27 * The above copyright notice and this permission notice shall be 28 * included in all copies or substantial portions of the Software. 29 * 30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 37 * 38 */ 39 40 #ifndef GECODE_SET_BRANCH_HH 41 #define GECODE_SET_BRANCH_HH 42 43 #include <gecode/set.hh> 44 45 /** 46 * \namespace Gecode::Set::Branch 47 * \brief %Set branchings 48 */ 49 50 namespace Gecode { namespace Set { namespace Branch { 51 52 /** 53 * \defgroup FuncSetViewSel Merit-based set view selection for branchers 54 * 55 * Contains merit-based view selection strategies on set 56 * views that can be used together with the generic view/value 57 * brancher classes. 58 * 59 * All merit-based set view selection classes require 60 * \code #include <gecode/set/branch.hh> \endcode 61 * \ingroup Other 62 */ 63 64 /** 65 * \brief Merit class for mimimum of set views 66 * 67 * Requires \code #include <gecode/set/branch.hh> \endcode 68 * \ingroup FuncSetViewSel 69 */ 70 class MeritMin : public MeritBase<SetView,int> { 71 public: 72 /// Constructor for initialization 73 MeritMin(Space& home, const VarBranch<Var>& vb); 74 /// Constructor for cloning 75 MeritMin(Space& home, MeritMin& m); 76 /// Return minimum as merit for view \a x at position \a i 77 int operator ()(const Space& home, SetView x, int i); 78 }; 79 80 /** 81 * \brief Merit class for maximum of set view 82 * 83 * Requires \code #include <gecode/set/branch.hh> \endcode 84 * \ingroup FuncSetViewSel 85 */ 86 class MeritMax : public MeritBase<SetView,int> { 87 public: 88 /// Constructor for initialization 89 MeritMax(Space& home, const VarBranch<Var>& vb); 90 /// Constructor for cloning 91 MeritMax(Space& home, MeritMax& m); 92 /// Return maximum as merit for view \a x at position \a i 93 int operator ()(const Space& home, SetView x, int i); 94 }; 95 96 /** 97 * \brief Merit class for size of set view 98 * 99 * Requires \code #include <gecode/set/branch.hh> \endcode 100 * \ingroup FuncSetViewSel 101 */ 102 class MeritSize : public MeritBase<SetView,unsigned int> { 103 public: 104 /// Constructor for initialization 105 MeritSize(Space& home, const VarBranch<Var>& vb); 106 /// Constructor for cloning 107 MeritSize(Space& home, MeritSize& m); 108 /// Return size as merit for view \a x at position \a i 109 unsigned int operator ()(const Space& home, SetView x, int i); 110 }; 111 112 /** 113 * \brief Merit class for degree over size 114 * 115 * Requires \code #include <gecode/set/branch.hh> \endcode 116 * \ingroup FuncSetViewSel 117 */ 118 class MeritDegreeSize : public MeritBase<SetView,double> { 119 public: 120 /// Constructor for initialization 121 MeritDegreeSize(Space& home, const VarBranch<Var>& vb); 122 /// Constructor for cloning 123 MeritDegreeSize(Space& home, MeritDegreeSize& m); 124 /// Return degree over size as merit for view \a x at position \a i 125 double operator ()(const Space& home, SetView x, int i); 126 }; 127 128 /** 129 * \brief Merit class for AFC over size 130 * 131 * Requires \code #include <gecode/set/branch.hh> \endcode 132 * \ingroup FuncSetViewSel 133 */ 134 class MeritAFCSize : public MeritBase<SetView,double> { 135 protected: 136 /// AFC information 137 AFC afc; 138 public: 139 /// Constructor for initialization 140 MeritAFCSize(Space& home, const VarBranch<Var>& vb); 141 /// Constructor for cloning 142 MeritAFCSize(Space& home, MeritAFCSize& m); 143 /// Return AFC over size as merit for view \a x at position \a i 144 double operator ()(const Space& home, SetView x, int i); 145 /// Whether dispose must always be called (that is, notice is needed) 146 bool notice(void) const; 147 /// Dispose view selection 148 void dispose(Space& home); 149 }; 150 151 /** 152 * \brief Merit class for action over size 153 * 154 * Requires \code #include <gecode/set/branch.hh> \endcode 155 * \ingroup FuncSetViewSel 156 */ 157 class MeritActionSize : public MeritBase<SetView,double> { 158 protected: 159 /// Action information 160 Action action; 161 public: 162 /// Constructor for initialization 163 MeritActionSize(Space& home, const VarBranch<Var>& vb); 164 /// Constructor for cloning 165 MeritActionSize(Space& home, MeritActionSize& m); 166 /// Return action over size as merit for view \a x at position \a i 167 double operator ()(const Space& home, SetView x, int i); 168 /// Whether dispose must always be called (that is, notice is needed) 169 bool notice(void) const; 170 /// Dispose view selection 171 void dispose(Space& home); 172 }; 173 174 /** 175 * \brief Merit class for CHB Q-score over size 176 * 177 * Requires \code #include <gecode/set/branch.hh> \endcode 178 * \ingroup FuncSetViewSel 179 */ 180 class MeritCHBSize : public MeritBase<SetView,double> { 181 protected: 182 /// CHB information 183 CHB chb; 184 public: 185 /// Constructor for initialization 186 MeritCHBSize(Space& home, const VarBranch<Var>& vb); 187 /// Constructor for cloning 188 MeritCHBSize(Space& home, MeritCHBSize& m); 189 /// Return CHB Q-score over size as merit for view \a x at position \a i 190 double operator ()(const Space& home, SetView x, int i); 191 /// Whether dispose must always be called (that is, notice is needed) 192 bool notice(void) const; 193 /// Dispose view selection 194 void dispose(Space& home); 195 }; 196 197 }}} 198 199 #include <gecode/set/branch/merit.hpp> 200 201 namespace Gecode { namespace Set { namespace Branch { 202 203 /// Return view selectors for set views 204 GECODE_SET_EXPORT 205 ViewSel<SetView>* viewsel(Space& home, const SetVarBranch& svb); 206 207 }}} 208 209 namespace Gecode { namespace Set { namespace Branch { 210 211 /** 212 * \defgroup FuncSetValSel Set value selection for brancher 213 * 214 * Contains a description of value selection strategies on set 215 * views that can be used together with the generic view/value 216 * branchers. 217 * 218 * All value selection classes require 219 * \code #include <gecode/set/branch.hh> \endcode 220 * \ingroup Other 221 */ 222 223 /** 224 * \brief Value selection class for mimimum of view 225 * 226 * Requires \code #include <gecode/set/branch.hh> \endcode 227 * \ingroup FuncSetValSel 228 */ 229 class ValSelMin : public ValSel<SetView,int> { 230 public: 231 /// Constructor for initialization 232 ValSelMin(Space& home, const ValBranch<Var>& vb); 233 /// Constructor for cloning 234 ValSelMin(Space& home, ValSelMin& vs); 235 /// Return value of view \a x at position \a i 236 int val(const Space& home, SetView x, int i); 237 }; 238 239 /** 240 * \brief Value selection class for maximum of view 241 * 242 * Requires \code #include <gecode/set/branch.hh> \endcode 243 * \ingroup FuncSetValSel 244 */ 245 class ValSelMax : public ValSel<SetView,int> { 246 public: 247 /// Constructor for initialization 248 ValSelMax(Space& home, const ValBranch<Var>& vb); 249 /// Constructor for cloning 250 ValSelMax(Space& home, ValSelMax& vs); 251 /// Return value of view \a x at position \a i 252 int val(const Space& home, SetView x, int i); 253 }; 254 255 /** 256 * \brief Value selection class for median of view 257 * 258 * Requires \code #include <gecode/set/branch.hh> \endcode 259 * \ingroup FuncSetValSel 260 */ 261 class ValSelMed : public ValSel<SetView,int> { 262 public: 263 /// Constructor for initialization 264 ValSelMed(Space& home, const ValBranch<Var>& vb); 265 /// Constructor for cloning 266 ValSelMed(Space& home, ValSelMed& vs); 267 /// Return value of view \a x at position \a i 268 int val(const Space& home, SetView x, int i); 269 }; 270 271 /** 272 * \brief Value selection class for random value of view 273 * 274 * Requires \code #include <gecode/set/branch.hh> \endcode 275 * \ingroup FuncSetValSel 276 */ 277 class ValSelRnd : public ValSel<SetView,int> { 278 protected: 279 /// The used random number generator 280 Rnd r; 281 public: 282 /// Constructor for initialization 283 ValSelRnd(Space& home, const ValBranch<Var>& vb); 284 /// Constructor for cloning 285 ValSelRnd(Space& home, ValSelRnd& vs); 286 /// Return value of view \a x at position \a i 287 int val(const Space& home, SetView x, int i); 288 /// Whether dispose must always be called (that is, notice is needed) 289 bool notice(void) const; 290 /// Delete value selection 291 void dispose(Space& home); 292 }; 293 294 }}} 295 296 #include <gecode/set/branch/val-sel.hpp> 297 298 namespace Gecode { namespace Set { namespace Branch { 299 300 /// No-good literal for inclusion 301 class IncNGL : public ViewValNGL<SetView,int,PC_SET_ANY> { 302 public: 303 /// Constructor for creation 304 IncNGL(Space& home, SetView x, int n); 305 /// Constructor for cloning \a ngl 306 IncNGL(Space& home, IncNGL& ngl); 307 /// Test the status of the no-good literal 308 GECODE_SET_EXPORT 309 virtual NGL::Status status(const Space& home) const; 310 /// Propagate the negation of the no-good literal 311 GECODE_SET_EXPORT 312 virtual ExecStatus prune(Space& home); 313 /// Create copy 314 GECODE_SET_EXPORT 315 virtual NGL* copy(Space& home); 316 }; 317 318 /// No-good literal for exclusion 319 class ExcNGL : public ViewValNGL<SetView,int,PC_SET_ANY> { 320 public: 321 /// Constructor for creation 322 ExcNGL(Space& home, SetView x, int n); 323 /// Constructor for cloning \a ngl 324 ExcNGL(Space& home, ExcNGL& ngl); 325 /// Test the status of the no-good literal 326 GECODE_SET_EXPORT 327 virtual NGL::Status status(const Space& home) const; 328 /// Propagate the negation of the no-good literal 329 GECODE_SET_EXPORT 330 virtual ExecStatus prune(Space& home); 331 /// Create copy 332 GECODE_SET_EXPORT 333 virtual NGL* copy(Space& home); 334 }; 335 336 }}} 337 338 #include <gecode/set/branch/ngl.hpp> 339 340 namespace Gecode { namespace Set { namespace Branch { 341 342 /** 343 * \defgroup FuncSetValCommit Set value commit classes 344 * 345 * Contains the value commit classes for set 346 * views that can be used together with the generic view/value 347 * branchers. 348 * 349 * All value commit classes require 350 * \code #include <gecode/set/branch.hh> \endcode 351 * \ingroup Other 352 */ 353 354 /** 355 * \brief Value commit class for inclusion 356 * 357 * Requires \code #include <gecode/set/branch.hh> \endcode 358 * \ingroup FuncSetValCommit 359 */ 360 class ValCommitInc : public ValCommit<SetView,int> { 361 public: 362 /// Constructor for initialization 363 ValCommitInc(Space& home, const ValBranch<Var>& vb); 364 /// Constructor for cloning 365 ValCommitInc(Space& home, ValCommitInc& vc); 366 /// Commit view \a x at position \a i to value \a n for alternative \a a 367 ModEvent commit(Space& home, unsigned int a, SetView x, int i, int n); 368 /// Create no-good literal for alternative \a a 369 NGL* ngl(Space& home, unsigned int a, View x, int n) const; 370 /// Print on \a o the alternative \a with view \a x at position \a i and value \a n 371 void print(const Space& home, unsigned int a, SetView x, int i, int n, 372 std::ostream& o) const; 373 }; 374 375 /** 376 * \brief Value commit class for exclusion 377 * 378 * Requires \code #include <gecode/set/branch.hh> \endcode 379 * \ingroup FuncSetValCommit 380 */ 381 class ValCommitExc : public ValCommit<SetView,int> { 382 public: 383 /// Constructor for initialization 384 ValCommitExc(Space& home, const ValBranch<Var>& vb); 385 /// Constructor for cloning 386 ValCommitExc(Space& home, ValCommitExc& vc); 387 /// Commit view \a x at position \a i to value \a n for alternative \a a 388 ModEvent commit(Space& home, unsigned int a, SetView x, int i, int n); 389 /// Create no-good literal for alternative \a a 390 NGL* ngl(Space& home, unsigned int a, View x, int n) const; 391 /// Print on \a o the alternative \a with view \a x at position \a i and value \a n 392 void print(const Space& home, unsigned int a, SetView x, int i, int n, 393 std::ostream& o) const; 394 }; 395 396 }}} 397 398 #include <gecode/set/branch/val-commit.hpp> 399 400 namespace Gecode { namespace Set { namespace Branch { 401 402 /// Return value and commit for set views 403 GECODE_SET_EXPORT 404 ValSelCommitBase<SetView,int>* 405 valselcommit(Space& home, const SetValBranch& svb); 406 407 /// Return value and commit for set views 408 GECODE_SET_EXPORT 409 ValSelCommitBase<SetView,int>* 410 valselcommit(Space& home, const SetAssign& ia); 411 412 }}} 413 414 #endif 415 416 // STATISTICS: set-branch 417 418