Generated on Tue Jan 26 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
50 namespace 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);
142  MeritAFCSize(Space& home, MeritAFCSize& m);
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);
188  MeritCHBSize(Space& home, MeritCHBSize& m);
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 
201 namespace Gecode { namespace Set { namespace Branch {
202 
205  ViewSel<SetView>* viewsel(Space& home, const SetVarBranch& svb);
206 
207 }}}
208 
209 namespace 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 
298 namespace 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 
338 #include <gecode/set/branch/ngl.hpp>
339 
340 namespace 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 
400 namespace 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.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::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.
Definition: val-commit.hpp:77
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.
Definition: val-commit.hpp:84
ValCommitExc(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition: val-commit.hpp:67
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.
Definition: val-commit.hpp:73
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.
Definition: val-commit.hpp:49
ValCommitInc(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition: val-commit.hpp:43
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.
Definition: val-commit.hpp:60
NGL * ngl(Space &home, unsigned int a, View x, int n) const
Create no-good literal for alternative a.
Definition: val-commit.hpp:53
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.
Definition: val-commit.hpp:44
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
ExecStatus
Definition: core.hpp:472
int ModEvent
Type for modification events.
Definition: core.hpp:62
#define GECODE_SET_EXPORT
Definition: set.hh:67
ValSelCommitBase< SetView, int > * valselcommit(Space &home, const SetValBranch &svb)
Return value and commit for set views.
ViewSel< SetView > * viewsel(Space &home, const SetVarBranch &svb)
Return view selectors for set views.
Definition: view-sel.cpp:39
Gecode::IntArgs i({1, 2, 3, 4})