Generated on Sat Jul 28 2018 17:10:36 for Gecode by doxygen 1.8.14
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  * Last modified:
16  * $Date: 2017-02-28 08:29:39 +0100 (Tue, 28 Feb 2017) $ by $Author: schulte $
17  * $Revision: 15527 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #ifndef __GECODE_SET_BRANCH_HH__
45 #define __GECODE_SET_BRANCH_HH__
46 
47 #include <gecode/set.hh>
48 
54 namespace Gecode { namespace Set { namespace Branch {
55 
74  class MeritMin : public MeritBase<SetView,int> {
75  public:
77  MeritMin(Space& home, const VarBranch<Var>& vb);
79  MeritMin(Space& home, bool shared, MeritMin& m);
81  int operator ()(const Space& home, SetView x, int i);
82  };
83 
90  class MeritMax : public MeritBase<SetView,int> {
91  public:
93  MeritMax(Space& home, const VarBranch<Var>& vb);
95  MeritMax(Space& home, bool shared, MeritMax& m);
97  int operator ()(const Space& home, SetView x, int i);
98  };
99 
106  class MeritSize : public MeritBase<SetView,unsigned int> {
107  public:
109  MeritSize(Space& home, const VarBranch<Var>& vb);
111  MeritSize(Space& home, bool shared, MeritSize& m);
113  unsigned int operator ()(const Space& home, SetView x, int i);
114  };
115 
122  class MeritDegreeSize : public MeritBase<SetView,double> {
123  public:
125  MeritDegreeSize(Space& home, const VarBranch<Var>& vb);
127  MeritDegreeSize(Space& home, bool shared, MeritDegreeSize& m);
129  double operator ()(const Space& home, SetView x, int i);
130  };
131 
138  class MeritAFCSize : public MeritBase<SetView,double> {
139  protected:
142  public:
144  MeritAFCSize(Space& home, const VarBranch<Var>& vb);
146  MeritAFCSize(Space& home, bool shared, MeritAFCSize& m);
148  double operator ()(const Space& home, SetView x, int i);
150  bool notice(void) const;
152  void dispose(Space& home);
153  };
154 
161  class MeritActionSize : public MeritBase<SetView,double> {
162  protected:
165  public:
167  MeritActionSize(Space& home, const VarBranch<Var>& vb);
169  MeritActionSize(Space& home, bool shared, MeritActionSize& m);
171  double operator ()(const Space& home, SetView x, int i);
173  bool notice(void) const;
175  void dispose(Space& home);
176  };
177 
184  class MeritCHBSize : public MeritBase<SetView,double> {
185  protected:
188  public:
190  MeritCHBSize(Space& home, const VarBranch<Var>& vb);
192  MeritCHBSize(Space& home, bool shared, MeritCHBSize& m);
194  double operator ()(const Space& home, SetView x, int i);
196  bool notice(void) const;
198  void dispose(Space& home);
199  };
200 
201 }}}
202 
204 
205 namespace Gecode { namespace Set { namespace Branch {
206 
209  ViewSel<SetView>* viewsel(Space& home, const SetVarBranch& svb);
210 
211 }}}
212 
213 namespace Gecode { namespace Set { namespace Branch {
214 
233  class ValSelMin : public ValSel<SetView,int> {
234  public:
236  ValSelMin(Space& home, const ValBranch<Var>& vb);
238  ValSelMin(Space& home, bool shared, ValSelMin& vs);
240  int val(const Space& home, SetView x, int i);
241  };
242 
249  class ValSelMax : public ValSel<SetView,int> {
250  public:
252  ValSelMax(Space& home, const ValBranch<Var>& vb);
254  ValSelMax(Space& home, bool shared, ValSelMax& vs);
256  int val(const Space& home, SetView x, int i);
257  };
258 
265  class ValSelMed : public ValSel<SetView,int> {
266  public:
268  ValSelMed(Space& home, const ValBranch<Var>& vb);
270  ValSelMed(Space& home, bool shared, ValSelMed& vs);
272  int val(const Space& home, SetView x, int i);
273  };
274 
281  class ValSelRnd : public ValSel<SetView,int> {
282  protected:
285  public:
287  ValSelRnd(Space& home, const ValBranch<Var>& vb);
289  ValSelRnd(Space& home, bool shared, ValSelRnd& vs);
291  int val(const Space& home, SetView x, int i);
293  bool notice(void) const;
295  void dispose(Space& home);
296  };
297 
298 }}}
299 
301 
302 namespace Gecode { namespace Set { namespace Branch {
303 
305  class IncNGL : public ViewValNGL<SetView,int,PC_SET_ANY> {
306  public:
308  IncNGL(Space& home, SetView x, int n);
310  IncNGL(Space& home, bool share, IncNGL& ngl);
313  virtual NGL::Status status(const Space& home) const;
316  virtual ExecStatus prune(Space& home);
319  virtual NGL* copy(Space& home, bool share);
320  };
321 
323  class ExcNGL : public ViewValNGL<SetView,int,PC_SET_ANY> {
324  public:
326  ExcNGL(Space& home, SetView x, int n);
328  ExcNGL(Space& home, bool share, ExcNGL& ngl);
331  virtual NGL::Status status(const Space& home) const;
334  virtual ExecStatus prune(Space& home);
337  virtual NGL* copy(Space& home, bool share);
338  };
339 
340 }}}
341 
342 #include <gecode/set/branch/ngl.hpp>
343 
344 namespace Gecode { namespace Set { namespace Branch {
345 
364  class ValCommitInc : public ValCommit<SetView,int> {
365  public:
367  ValCommitInc(Space& home, const ValBranch<Var>& vb);
369  ValCommitInc(Space& home, bool shared, ValCommitInc& vc);
371  ModEvent commit(Space& home, unsigned int a, SetView x, int i, int n);
373  NGL* ngl(Space& home, unsigned int a, View x, int n) const;
375  void print(const Space& home, unsigned int a, SetView x, int i, int n,
376  std::ostream& o) const;
377  };
378 
385  class ValCommitExc : public ValCommit<SetView,int> {
386  public:
388  ValCommitExc(Space& home, const ValBranch<Var>& vb);
390  ValCommitExc(Space& home, bool shared, ValCommitExc& vc);
392  ModEvent commit(Space& home, unsigned int a, SetView x, int i, int n);
394  NGL* ngl(Space& home, unsigned int a, View x, int n) const;
396  void print(const Space& home, unsigned int a, SetView x, int i, int n,
397  std::ostream& o) const;
398  };
399 
400 }}}
401 
403 
404 namespace Gecode { namespace Set { namespace Branch {
405 
408  ValSelCommitBase<SetView,int>*
409  valselcommit(Space& home, const SetValBranch& svb);
410 
413  ValSelCommitBase<SetView,int>*
414  valselcommit(Space& home, const SetAssign& ia);
415 
416 }}}
417 
418 #endif
419 
420 // STATISTICS: set-branch
421 
No-good literal for inclusion.
Definition: branch.hh:305
Merit class for AFC over size.
Definition: branch.hh:138
Merit class for maximum of set view.
Definition: branch.hh:90
double operator()(const Space &home, SetView x, int i)
Return AFC over size as merit for view x at position i.
Definition: merit.hpp:110
int val(const Space &home, SetView x, int i)
Return value of view x at position i.
Definition: val-sel.hpp:65
ValCommitExc(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition: val-commit.hpp:71
virtual NGL::Status status(const Space &home) const
Test the status of the no-good literal.
Definition: ngl.cpp:66
void dispose(Space &home)
Dispose view selection.
Definition: merit.hpp:118
ValCommitInc(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition: val-commit.hpp:47
void dispose(Space &home)
Dispose view selection.
Definition: merit.hpp:142
Merit class for CHB Q-score over size.
Definition: branch.hh:184
Value selection class for median of view.
Definition: branch.hh:265
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:159
int val(const Space &home, SetView x, int i)
Return value of view x at position i.
Definition: val-sel.hpp:105
int operator()(const Space &home, SetView x, int i)
Return minimum as merit for view x at position i.
Definition: merit.hpp:54
Value selection class for mimimum of view.
Definition: branch.hh:233
Status
The status of a no-good literal.
Definition: core.hpp:1348
Value commit class for exclusion.
Definition: branch.hh:385
int ModEvent
Type for modification events.
Definition: core.hpp:142
Base-class for merit class.
double operator()(const Space &home, SetView x, int i)
Return degree over size as merit for view x at position i.
Definition: merit.hpp:95
Computation spaces.
Definition: core.hpp:1748
virtual ExecStatus prune(Space &home)
Propagate the negation of the no-good literal.
Definition: ngl.cpp:75
Base class for value commit.
bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition: merit.hpp:138
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
int val(const Space &home, SetView x, int i)
Return value of view x at position i.
Definition: val-sel.hpp:79
Gecode::IntArgs i(4, 1, 2, 3, 4)
Class for AFC (accumulated failure count) management.
Definition: afc.hpp:44
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
ViewSel< SetView > * viewsel(Space &home, const SetVarBranch &svb)
Return view selectors for set views.
Definition: view-sel.cpp:43
Merit class for action over size.
Definition: branch.hh:161
Class for CHB management.
Definition: chb.hpp:50
MeritDegreeSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition: merit.hpp:88
NGL * ngl(Space &home, unsigned int a, View x, int n) const
Create no-good literal for alternative a.
Definition: val-commit.hpp:57
AFC afc
AFC information.
Definition: branch.hh:141
MeritAFCSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition: merit.hpp:102
virtual NGL * copy(Space &home, bool share)
Create copy.
Definition: ngl.cpp: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:64
MeritSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition: merit.hpp:76
ValSelCommitBase< SetView, int > * valselcommit(Space &home, const SetValBranch &svb)
Return value and commit for set views.
No-good literal for exclusion.
Definition: branch.hh:323
double operator()(const Space &home, SetView x, int i)
Return action over size as merit for view x at position i.
Definition: merit.hpp:134
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:53
ValSelMin(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition: val-sel.hpp:47
MeritMax(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition: merit.hpp:61
CHB chb
CHB information.
Definition: branch.hh:187
MeritCHBSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition: merit.hpp:149
Set view for set variables
Definition: view.hpp:60
ValSelMax(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition: val-sel.hpp:59
void dispose(Space &home)
Dispose view selection.
Definition: merit.hpp:167
Value branching information.
Definition: branch-val.hpp:45
Merit class for size of set view.
Definition: branch.hh:106
bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition: val-sel.hpp:117
Variable branching information.
Definition: branch-var.hpp:59
Action action
Action information.
Definition: branch.hh:164
Value commit class for inclusion.
Definition: branch.hh:364
ExcNGL(Space &home, SetView x, int n)
Constructor for creation.
Definition: ngl.hpp:48
int operator()(const Space &home, SetView x, int i)
Return maximum as merit for view x at position i.
Definition: merit.hpp:67
ExecStatus
Definition: core.hpp:540
Merit class for degree over size.
Definition: branch.hh:122
virtual NGL::Status status(const Space &home) const
Test the status of the no-good literal.
Definition: ngl.cpp:47
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:88
bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition: merit.hpp:114
Post propagator for SetVar x
Definition: set.hh:784
View-value no-good literal.
Value selection class for maximum of view.
Definition: branch.hh:249
bool shared(const ConstView< ViewA > &, const ConstView< ViewB > &)
Test whether views share same variable.
Definition: view.hpp:702
ValSelRnd(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition: val-sel.hpp:97
MeritActionSize(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition: merit.hpp:124
unsigned int operator()(const Space &home, SetView x, int i)
Return size as merit for view x at position i.
Definition: merit.hpp:82
bool notice(void) const
Whether dispose must always be called (that is, notice is needed)
Definition: merit.hpp:163
Gecode toplevel namespace
Class for action management.
Definition: action.hpp:46
virtual NGL * copy(Space &home, bool share)
Create copy.
Definition: ngl.cpp:62
virtual ExecStatus prune(Space &home)
Propagate the negation of the no-good literal.
Definition: ngl.cpp:56
Random number generator.
Definition: rnd.hpp:46
IncNGL(Space &home, SetView x, int n)
Constructor for creation.
Definition: ngl.hpp:41
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:77
ValSelMed(Space &home, const ValBranch< Var > &vb)
Constructor for initialization.
Definition: val-sel.hpp:73
int val(const Space &home, SetView x, int i)
Return value of view x at position i.
Definition: val-sel.hpp:53
Value selection class for random value of view.
Definition: branch.hh:281
MeritMin(Space &home, const VarBranch< Var > &vb)
Constructor for initialization.
Definition: merit.hpp:48
#define GECODE_SET_EXPORT
Definition: set.hh:71
Merit class for mimimum of set views.
Definition: branch.hh:74
void dispose(Space &home)
Delete value selection.
Definition: val-sel.hpp:121
NGL * ngl(Space &home, unsigned int a, View x, int n) const
Create no-good literal for alternative a.
Definition: val-commit.hpp:81
Rnd r
The used random number generator.
Definition: branch.hh:284
Base class for value selection.
No-good literal recorded during search.
Definition: core.hpp:1342