this repo has no description
dekker.one
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
50namespace 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
201namespace 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
209namespace 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
298namespace 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
340namespace 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
400namespace 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