Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
branch.hh
Go to the documentation of this file.
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
50namespace Gecode { namespace Set { namespace Branch {
51
70 class MeritMin : public MeritBase<SetView,int> {
71 public:
73 MeritMin(Space& home, const VarBranch<Var>& vb);
75 MeritMin(Space& home, MeritMin& m);
77 int operator ()(const Space& home, SetView x, int i);
78 };
79
86 class MeritMax : public MeritBase<SetView,int> {
87 public:
89 MeritMax(Space& home, const VarBranch<Var>& vb);
91 MeritMax(Space& home, MeritMax& m);
93 int operator ()(const Space& home, SetView x, int i);
94 };
95
102 class MeritSize : public MeritBase<SetView,unsigned int> {
103 public:
105 MeritSize(Space& home, const VarBranch<Var>& vb);
107 MeritSize(Space& home, MeritSize& m);
109 unsigned int operator ()(const Space& home, SetView x, int i);
110 };
111
118 class MeritDegreeSize : public MeritBase<SetView,double> {
119 public:
121 MeritDegreeSize(Space& home, const VarBranch<Var>& vb);
125 double operator ()(const Space& home, SetView x, int i);
126 };
127
134 class MeritAFCSize : public MeritBase<SetView,double> {
135 protected:
138 public:
140 MeritAFCSize(Space& home, const VarBranch<Var>& vb);
144 double operator ()(const Space& home, SetView x, int i);
146 bool notice(void) const;
148 void dispose(Space& home);
149 };
150
157 class MeritActionSize : public MeritBase<SetView,double> {
158 protected:
161 public:
163 MeritActionSize(Space& home, const VarBranch<Var>& vb);
167 double operator ()(const Space& home, SetView x, int i);
169 bool notice(void) const;
171 void dispose(Space& home);
172 };
173
180 class MeritCHBSize : public MeritBase<SetView,double> {
181 protected:
184 public:
186 MeritCHBSize(Space& home, const VarBranch<Var>& vb);
190 double operator ()(const Space& home, SetView x, int i);
192 bool notice(void) const;
194 void dispose(Space& home);
195 };
196
197}}}
198
200
201namespace Gecode { namespace Set { namespace Branch {
202
205 ViewSel<SetView>* viewsel(Space& home, const SetVarBranch& svb);
206
207}}}
208
209namespace Gecode { namespace Set { namespace Branch {
210
229 class ValSelMin : public ValSel<SetView,int> {
230 public:
232 ValSelMin(Space& home, const ValBranch<Var>& vb);
234 ValSelMin(Space& home, ValSelMin& vs);
236 int val(const Space& home, SetView x, int i);
237 };
238
245 class ValSelMax : public ValSel<SetView,int> {
246 public:
248 ValSelMax(Space& home, const ValBranch<Var>& vb);
250 ValSelMax(Space& home, ValSelMax& vs);
252 int val(const Space& home, SetView x, int i);
253 };
254
261 class ValSelMed : public ValSel<SetView,int> {
262 public:
264 ValSelMed(Space& home, const ValBranch<Var>& vb);
266 ValSelMed(Space& home, ValSelMed& vs);
268 int val(const Space& home, SetView x, int i);
269 };
270
277 class ValSelRnd : public ValSel<SetView,int> {
278 protected:
281 public:
283 ValSelRnd(Space& home, const ValBranch<Var>& vb);
285 ValSelRnd(Space& home, ValSelRnd& vs);
287 int val(const Space& home, SetView x, int i);
289 bool notice(void) const;
291 void dispose(Space& home);
292 };
293
294}}}
295
297
298namespace Gecode { namespace Set { namespace Branch {
299
301 class IncNGL : public ViewValNGL<SetView,int,PC_SET_ANY> {
302 public:
304 IncNGL(Space& home, SetView x, int n);
306 IncNGL(Space& home, IncNGL& ngl);
309 virtual NGL::Status status(const Space& home) const;
312 virtual ExecStatus prune(Space& home);
315 virtual NGL* copy(Space& home);
316 };
317
319 class ExcNGL : public ViewValNGL<SetView,int,PC_SET_ANY> {
320 public:
322 ExcNGL(Space& home, SetView x, int n);
324 ExcNGL(Space& home, ExcNGL& ngl);
327 virtual NGL::Status status(const Space& home) const;
330 virtual ExecStatus prune(Space& home);
333 virtual NGL* copy(Space& home);
334 };
335
336}}}
337
339
340namespace Gecode { namespace Set { namespace Branch {
341
360 class ValCommitInc : public ValCommit<SetView,int> {
361 public:
363 ValCommitInc(Space& home, const ValBranch<Var>& vb);
365 ValCommitInc(Space& home, ValCommitInc& vc);
367 ModEvent commit(Space& home, unsigned int a, SetView x, int i, int n);
369 NGL* ngl(Space& home, unsigned int a, View x, int n) const;
371 void print(const Space& home, unsigned int a, SetView x, int i, int n,
372 std::ostream& o) const;
373 };
374
381 class ValCommitExc : public ValCommit<SetView,int> {
382 public:
384 ValCommitExc(Space& home, const ValBranch<Var>& vb);
386 ValCommitExc(Space& home, ValCommitExc& vc);
388 ModEvent commit(Space& home, unsigned int a, SetView x, int i, int n);
390 NGL* ngl(Space& home, unsigned int a, View x, int n) const;
392 void print(const Space& home, unsigned int a, SetView x, int i, int n,
393 std::ostream& o) const;
394 };
395
396}}}
397
399
400namespace Gecode { namespace Set { namespace Branch {
401
404 ValSelCommitBase<SetView,int>*
405 valselcommit(Space& home, const SetValBranch& svb);
406
409 ValSelCommitBase<SetView,int>*
410 valselcommit(Space& home, const SetAssign& ia);
411
412}}}
413
414#endif
415
416// STATISTICS: set-branch
417
int n
Number of negative literals for node type.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Class for AFC (accumulated failure count) management.
Definition afc.hpp:40
Class for action management.
Definition action.hpp:42
Class for CHB management.
Definition chb.hpp:46
Base-class for merit class.
Definition merit.hpp:46
No-good literal recorded during search.
Definition core.hpp:1340
Status
The status of a no-good literal.
Definition core.hpp:1346
Random number generator.
Definition rnd.hpp:42
No-good literal for exclusion.
Definition branch.hh:319
virtual NGL::Status status(const Space &home) const
Test the status of the no-good literal.
Definition ngl.cpp:62
virtual NGL * copy(Space &home)
Create copy.
Definition ngl.cpp:58
ExcNGL(Space &home, SetView x, int n)
Constructor for creation.
Definition ngl.hpp:44
virtual ExecStatus prune(Space &home)
Propagate the negation of the no-good literal.
Definition ngl.cpp:71
No-good literal for inclusion.
Definition branch.hh:301
IncNGL(Space &home, SetView x, int n)
Constructor for creation.
Definition ngl.hpp:37
virtual NGL::Status status(const Space &home) const
Test the status of the no-good literal.
Definition ngl.cpp:43
virtual NGL * copy(Space &home)
Create copy.
Definition ngl.cpp:39
virtual ExecStatus prune(Space &home)
Propagate the negation of the no-good literal.
Definition ngl.cpp:52
Merit class for AFC over size.
Definition branch.hh:134
bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition merit.hpp:107
double operator()(const Space &home, SetView x, int i)
Return AFC over size as merit for view x at position i.
Definition merit.hpp:103
AFC afc
AFC information.
Definition branch.hh:137
MeritAFCSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition merit.hpp:97
void dispose(Space &home)
Dispose view selection.
Definition merit.hpp:111
Merit class for action over size.
Definition branch.hh:157
bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition merit.hpp:128
void dispose(Space &home)
Dispose view selection.
Definition merit.hpp:132
Action action
Action information.
Definition branch.hh:160
MeritActionSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition merit.hpp:118
double operator()(const Space &home, SetView x, int i)
Return action over size as merit for view x at position i.
Definition merit.hpp:124
Merit class for CHB Q-score over size.
Definition branch.hh:180
double operator()(const Space &home, SetView x, int i)
Return CHB Q-score over size as merit for view x at position i.
Definition merit.hpp:145
bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition merit.hpp:149
void dispose(Space &home)
Dispose view selection.
Definition merit.hpp:153
MeritCHBSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition merit.hpp:139
CHB chb
CHB information.
Definition branch.hh:183
Merit class for degree over size.
Definition branch.hh:118
double operator()(const Space &home, SetView x, int i)
Return degree over size as merit for view x at position i.
Definition merit.hpp:90
MeritDegreeSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition merit.hpp:84
Merit class for maximum of set view.
Definition branch.hh:86
MeritMax(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition merit.hpp:57
int operator()(const Space &home, SetView x, int i)
Return maximum as merit for view x at position i.
Definition merit.hpp:63
Merit class for mimimum of set views.
Definition branch.hh:70
MeritMin(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition merit.hpp:44
int operator()(const Space &home, SetView x, int i)
Return minimum as merit for view x at position i.
Definition merit.hpp:50
Merit class for size of set view.
Definition branch.hh:102
MeritSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition merit.hpp:72
unsigned int operator()(const Space &home, SetView x, int i)
Return size as merit for view x at position i.
Definition merit.hpp:78
Value commit class for exclusion.
Definition branch.hh:381
NGL * ngl(Space &home, unsigned int a, View x, int n) const
Create no-good literal for alternative a.
void print(const Space &home, unsigned int a, SetView x, int i, int n, std::ostream &o) const
Print on o the alternative with view x at position i and value n.
ValCommitExc(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
ModEvent commit(Space &home, unsigned int a, SetView x, int i, int n)
Commit view x at position i to value n for alternative a.
Value commit class for inclusion.
Definition branch.hh:360
ModEvent commit(Space &home, unsigned int a, SetView x, int i, int n)
Commit view x at position i to value n for alternative a.
ValCommitInc(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
void print(const Space &home, unsigned int a, SetView x, int i, int n, std::ostream &o) const
Print on o the alternative with view x at position i and value n.
NGL * ngl(Space &home, unsigned int a, View x, int n) const
Create no-good literal for alternative a.
Value selection class for maximum of view.
Definition branch.hh:245
int val(const Space &home, SetView x, int i)
Return value of view x at position i.
Definition val-sel.hpp:61
ValSelMax(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition val-sel.hpp:55
Value selection class for median of view.
Definition branch.hh:261
ValSelMed(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition val-sel.hpp:69
int val(const Space &home, SetView x, int i)
Return value of view x at position i.
Definition val-sel.hpp:75
Value selection class for mimimum of view.
Definition branch.hh:229
ValSelMin(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition val-sel.hpp:43
int val(const Space &home, SetView x, int i)
Return value of view x at position i.
Definition val-sel.hpp:49
Value selection class for random value of view.
Definition branch.hh:277
bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition val-sel.hpp:112
ValSelRnd(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition val-sel.hpp:93
Rnd r
The used random number generator.
Definition branch.hh:280
int val(const Space &home, SetView x, int i)
Return value of view x at position i.
Definition val-sel.hpp:100
void dispose(Space &home)
Delete value selection.
Definition val-sel.hpp:116
Set view for set variables
Definition view.hpp:56
Computation spaces.
Definition core.hpp:1742
Value branching information.
Definition val.hpp:41
Base class for value commit.
Base class for value selection.
Definition val-sel.hpp:44
Variable branching information.
Definition var.hpp:55
View-value no-good literal.
Definition view-val.hpp:61
#define GECODE_SET_EXPORT
Definition set.hh:67
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition view-sel.cpp:39
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
Gecode toplevel namespace
ExecStatus
Definition core.hpp:472
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62