Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
brancher.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christopher Mears <chris.mears@monash.edu>
5  *
6  * Copyright:
7  * Christopher Mears, 2012
8  *
9  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode { namespace Set { namespace LDSB {
35 
36  template<class View, int n, class Val, unsigned int a,
37  class Filter, class Print>
40  ViewSel<View>* vs[n],
42  SymmetryImp<View>** syms, int nsyms,
46  (home, x, vs, vsc, syms, nsyms, bf, vvp),
47  _prevPos(-1),
48  _copiedSyms(NULL),
49  _nCopiedSyms(0),
50  _stable(false) {
51  // Put all the value symmetries at the end of the list.
52  int seen = 0;
53  int dest = this->_nsyms - 1;
54  for (int i = 0 ; i < this->_nsyms - seen ; i++) {
55  if (dynamic_cast<ValueSymmetryImp<View>*>(this->_syms[i])) {
56  SymmetryImp<View>* t = this->_syms[i];
57  this->_syms[i] = this->_syms[dest];
58  this->_syms[dest] = t;
59  dest--;
60  seen++;
61  }
62  }
63  _nValueSymmetries = seen;
64  _nNonValueSymmetries = this->_nsyms - seen;
65  }
66 
67  template<class View, int n, class Val, unsigned int a,
68  class Filter, class Print>
72  : LDSBBrancher<View,n,Val,a,Filter,Print>(home,b),
73  _prevPos(b._prevPos),
74  _nNonValueSymmetries(b._nNonValueSymmetries),
75  _nValueSymmetries(b._nValueSymmetries),
76  _nCopiedSyms(b._nCopiedSyms),
77  _leftBranchValues(b._leftBranchValues),
78  _stable(b._stable) {
79  if (_nCopiedSyms > 0) {
81  for (int i = 0 ; i < _nCopiedSyms ; i++)
82  _copiedSyms[i] = static_cast<ValueSymmetryImp<View>*>(
83  b._copiedSyms[i]->copy(home));
84  } else {
85  _copiedSyms = NULL;
86  }
87  }
88 
98  template <class View>
101  // Calculate intersection and difference.
102  IntArgs intersection;
103  IntArgs difference;
104  int n = 0;
105  for (int i = s->values.next(s->values.offset()) ;
106  i <= s->values.max_bit() ; i = s->values.next(i+1)) {
107  n++;
108  if (usedValues.in(i))
109  intersection << i;
110  else
111  difference << i;
112  }
113 
114  for (IntSetValues v(usedValues) ; v() ; ++v) {
115  s->update(Literal(0, v.val()));
116  }
117 
118  if (intersection.size() < 2)
119  return NULL;
120  int *a = new int[intersection.size()];
121  for (int i = 0 ; i < intersection.size() ; i++) {
122  a[i] = intersection[i];
123  }
125  new (home) ValueSymmetryImp<View>(home, a, intersection.size());
126  delete [] a;
127  return ns;
128  }
129 
130  template<class View, int n, class Val, unsigned int a,
131  class Filter, class Print>
132  void
134  updatePart1(Space& home, int choicePos) {
135  if (_nValueSymmetries > 0) {
136  // If this is a different variable from the last commit, restore
137  // the old value symmetries and update the copy.
138  if (choicePos != _prevPos) {
139  if (_prevPos != -1) {
140  int i = 0;
141  for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
142  this->_syms[j] = _copiedSyms[i];
143  i++;
144  }
145 
146  for (int i = 0 ; i < _nCopiedSyms ; i++) {
148  specialUpdate(home, _copiedSyms[i], _leftBranchValues);
149  if (ns) {
150  this->_syms = home.realloc<SymmetryImp<View>*>(this->_syms,
151  this->_nsyms,
152  this->_nsyms+1);
153  this->_syms[this->_nsyms] = ns;
154  this->_nsyms++;
155  this->_nValueSymmetries++;
156  }
157  }
158  }
159 
160  // Reset for current variable, make copy of value symmetries
161  _leftBranchValues = IntSet::empty;
162  _prevPos = choicePos;
163  if (_nCopiedSyms > 0) home.free(_copiedSyms, _nCopiedSyms);
164  _nCopiedSyms = _nValueSymmetries;
165  _copiedSyms = home.alloc<ValueSymmetryImp<View>*>(_nCopiedSyms);
166  {
167  int i = 0;
168  for (int j = _nNonValueSymmetries ; j < this->_nsyms ; j++) {
170  static_cast<ValueSymmetryImp<View>*>(this->_syms[j]);
171  _copiedSyms[i] =
172  static_cast<ValueSymmetryImp<View>*>(vsi->copy(home));
173  i++;
174  }
175  }
176  }
177  }
178  }
179 
180  // Compute choice
181  template<class View, int n, class Val, unsigned int a,
182  class Filter, class Print>
183  const Choice*
185  // Making the PVC here is not so nice, I think.
187  const PosValChoice<Val>* pvc = static_cast<const PosValChoice<Val>* >(c);
188 
189  // Compute symmetries.
190 
191  int choicePos = pvc->pos().pos;
192  delete c;
193 
194  assert(!_stable);
195  updatePart1(home, choicePos);
196 
198  }
199 
200  template<class View, int n, class Val, unsigned int a,
201  class Filter, class Print>
202  ExecStatus
204  ::commit(Space& home, const Choice& c, unsigned int b) {
205  const LDSBChoice<Val>& pvc
206  = static_cast<const LDSBChoice<Val>&>(c);
207  int choicePos = pvc.pos().pos;
208  int choiceVal = pvc.val();
209 
210  if (!_stable)
211  updatePart1(home, choicePos);
212 
213  if (b == 0) {
214  IntArgs ia;
215  for (IntSetValues v(_leftBranchValues) ; v() ; ++v) {
216  ia << v.val();
217  }
218  ia << choiceVal;
219  _leftBranchValues = IntSet(ia);
220 
221  // Post the branching constraint.
223  ::commit(home, c, b);
224  GECODE_ES_CHECK(fromBase);
225  for (int i = 0 ; i < this->_nsyms ; i++)
226  this->_syms[i]->update(Literal(choicePos, choiceVal));
227  } else if (b == 1) {
228  // Post the branching constraint.
230  ::commit(home, c, b);
231  GECODE_ES_CHECK(fromBase);
232 
233  // Post prunings.
234  int nliterals = pvc.nliterals();
235  const Literal* literals = pvc.literals();
236  for (int i = 0 ; i < nliterals ; i++) {
237  const Literal& l = literals[i];
238  ModEvent me = prune<View>(home, this->x[l._variable], l._value);
239  GECODE_ME_CHECK(me);
240  }
241  }
242 
243  return ES_OK;
244  }
245 
246  template<class View, int n, class Val, unsigned int a,
247  class Filter, class Print>
248  Actor*
251  (home,*this);
252  }
253 
254  template<class View, int n, class Val, unsigned int a,
255  class Filter, class Print>
256  forceinline void
258  post(Home home, ViewArray<View>& x,
260  SymmetryImp<View>** syms, int nsyms,
264  (home,x,vs,vsc,syms,nsyms,bf,vvp);
265  }
266 
267  template<class View, int n, class Val, unsigned int a>
268  forceinline void
271  ViewSel<View>* vs[n],
273  SymmetryImp<View>** syms, int nsyms,
276  if (bf) {
277  if (vvp) {
279  ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
280  } else {
282  ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
283  }
284  } else {
285  if (vvp) {
287  ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
288  } else {
290  ::post(home,x,vs,vsc,syms,nsyms,bf,vvp);
291  }
292  }
293  }
294 
295 }}}
296 
297 // STATISTICS: set-branch
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl)
Post constraint .
Definition: aliases.hpp:143
std::function< bool(const Space &home, Var x, int i)> BranchFilter
Function type for branch filter functions.
Definition: filter.hpp:41
Post propagator for SetVar x
Definition: set.hh:767
bool in(int n) const
Return whether n is included in the set.
Definition: int-set-1.hpp:177
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int b)
Perform commit for choice c and alternative b.
Definition: view-val.hpp:292
Choice storing position and value, and symmetric literals to be excluded on the right branch.
Definition: ldsb.hh:301
ValueSymmetryImp< View > * specialUpdate(Space &home, ValueSymmetryImp< View > *s, IntSet usedValues)
Bulk update of a value symmetry s, using usedValues.
Definition: brancher.hpp:100
static void post(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, SymmetryImp< View > **_syms, int _nsyms, BranchFilter< Var > bf, VarValPrint< Var, Val > vvp)
Brancher post function.
Definition: brancher.hpp:258
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition: core.hpp:2863
Implementation of a value symmetry.
Definition: ldsb.hh:204
static const IntSet empty
Empty set.
Definition: int.hh:283
Class without print function.
Definition: print.hpp:73
LDSBSetBrancher(Space &home, LDSBSetBrancher &b)
Constructor for cloning b.
Definition: brancher.hpp:70
Support::BitSetOffset< Space > values
Symmetric values.
Definition: ldsb.hh:207
Symmetry-breaking brancher with generic view and value selection.
Definition: ldsb.hh:58
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Computation spaces.
Definition: core.hpp:1742
Base-class for both propagators and branchers.
Definition: core.hpp:628
ValueSymmetryImp< View > ** _copiedSyms
Copy of value symmetries from the first node where the current variable was branched on.
Definition: ldsb.hh:69
virtual Actor * copy(Space &home)
Perform cloning.
Definition: brancher.hpp:249
Class storing a print function.
Definition: print.hpp:47
Gecode toplevel namespace
Integer sets.
Definition: int.hh:174
View::VarType Var
The corresponding variable.
Definition: view-val.hpp:97
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
void update(IntSet &y, Space &home, IntSet &py)
Definition: rel.hpp:103
virtual const Choice * choice(Space &home)
Return choice.
Definition: view-val.hpp:271
virtual const Choice * choice(Space &home)
Return choice.
Definition: brancher.hpp:148
Home class for posting propagators
Definition: core.hpp:856
virtual const Choice * choice(Space &home)
Return choice.
Definition: brancher.hpp:184
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2837
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
Definition: filter.cpp:138
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
A Literal is a pair of variable index and value.
Definition: ldsb.hh:46
void updatePart1(Space &home, int choicePos)
Part one of the update phase.
Definition: brancher.hpp:134
int nliterals(void) const
Return number of literals.
Definition: brancher.hpp:76
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
int ModEvent
Type for modification events.
Definition: core.hpp:62
void postldsbsetbrancher(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, SymmetryImp< View > **syms, int nsyms, BranchFilter< typename View::VarType > bf, VarValPrint< typename View::VarType, Val > vvp)
Definition: brancher.hpp:269
const Val & val(void) const
Definition: view-val.hpp:165
const int v[7]
Definition: distinct.cpp:259
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:158
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int b)
Perform commit for choice c and alternative b.
Definition: brancher.hpp:204
Choice storing position and value
Definition: view-val.hpp:46
#define forceinline
Definition: config.hpp:192
Symmetry-breaking brancher with generic view and value selection.
Definition: ldsb.hh:332
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
int _nCopiedSyms
Number of copied symmetries.
Definition: ldsb.hh:71
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from the space heap.
Definition: core.hpp:2888
Gecode::FloatVal c(-8, 8)
View arrays.
Definition: array.hpp:253
Implementation of a single symmetry.
Definition: ldsb.hh:162
const Literal * literals(void) const
Return literals.
Definition: brancher.hpp:72
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Choice for performing commit
Definition: core.hpp:1412
Passing integer arguments.
Definition: int.hh:628
Value iterator for integer sets.
Definition: int.hh:333
Gecode::IntArgs i({1, 2, 3, 4})
std::function< void(const Space &home, const Brancher &b, unsigned int a, Var x, int i, const Val &m, std::ostream &o)> VarValPrint
Function type for printing variable and value selection.
Definition: print.hpp:43
@ ES_OK
Execution is okay.
Definition: core.hpp:476
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition: sym-imp.hpp:165
ExecStatus
Definition: core.hpp:472
const Pos & pos(void) const
Return position in array.
Definition: view.hpp:126