Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
ldsb.cpp
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 #include <gecode/set/ldsb.hh>
35 #include <gecode/set/branch.hh>
36 #include <map>
37 
38 namespace Gecode {
39  using namespace Int::LDSB;
40  /*
41  * Implementation of some SymmetryHandle methods.
42  */
43 
45  ArgArray<VarImpBase*> a(x.size());
46  for (int i = 0 ; i < x.size() ; i++)
47  a[i] = x[i].varimp();
49  }
51  ArgArray<VarImpBase*> a(x.size());
52  for (int i = 0 ; i < x.size() ; i++)
53  a[i] = x[i].varimp();
55  }
56 }
57 
58 namespace Gecode { namespace Int { namespace LDSB {
59  template <>
60  ModEvent prune<Set::SetView>(Space& home, Set::SetView x, int v) {
61  return x.exclude(home, v);
62  }
63 }}}
64 
65 namespace Gecode { namespace Set { namespace LDSB {
66 
68  class VariableMap : public std::map<VarImpBase*,int> {};
69 
70  /*
71  * The createSetSym function is an almost exact copy of
72  * createIntSym/createBoolSym.
73  */
75  VariableMap variableMap) {
76  VariableSymmetryObject* varref =
77  dynamic_cast<VariableSymmetryObject*>(s.ref);
78  ValueSymmetryObject* valref =
79  dynamic_cast<ValueSymmetryObject*>(s.ref);
81  dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
82  ValueSequenceSymmetryObject* valseqref =
83  dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
84  if (varref) {
85  int n = varref->nxs;
86  int* indices = home.alloc<int>(n);
87  for (int i = 0 ; i < n ; i++) {
88  VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
89  if (index == variableMap.end())
90  throw
91  Int::LDSBUnbranchedVariable("VariableSymmetryObject::createSet");
92  indices[i] = index->second;
93  }
94  return new (home) VariableSymmetryImp<SetView>(home, indices, n);
95  }
96  if (valref) {
97  int n = valref->values.size();
98  int *vs = home.alloc<int>(n);
99  int i = 0;
100  for (IntSetValues v(valref->values) ; v() ; ++v) {
101  vs[i] = v.val();
102  i++;
103  }
104  return new (home) ValueSymmetryImp<SetView>(home, vs, n);
105  }
106  if (varseqref) {
107  int n = varseqref->nxs;
108  int* indices = home.alloc<int>(n);
109  for (int i = 0 ; i < n ; i++) {
110  VariableMap::const_iterator index =
111  variableMap.find(varseqref->xs[i]);
112  if (index == variableMap.end())
113  throw
114  Int::LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createSet");
115  indices[i] = index->second;
116  }
117  return new (home) VariableSequenceSymmetryImp<SetView>(home, indices, n,
118  varseqref->seq_size);
119  }
120  if (valseqref) {
121  unsigned int n = valseqref->values.size();
122  int *vs = home.alloc<int>(n);
123  for (unsigned int i = 0 ; i < n ; i++)
124  vs[i] = valseqref->values[i];
125  return new (home) ValueSequenceSymmetryImp<SetView>(home, vs, n,
126  valseqref->seq_size);
127  }
128  GECODE_NEVER;
129  return NULL;
130  }
131 }}}
132 
133 namespace Gecode {
134 
135  using namespace Set::LDSB;
136 
137  void
138  branch(Home home, const SetVarArgs& x,
139  SetVarBranch vars, SetValBranch vals,
140  const Symmetries& syms,
141  SetBranchFilter bf,
142  SetVarValPrint vvp) {
143  using namespace Set;
144  if (home.failed()) return;
145  vars.expand(home,x);
146  ViewArray<SetView> xv(home,x);
147  ViewSel<SetView>* vs[1] = {
148  Branch::viewsel(home,vars)
149  };
150 
151  // Construct mapping from each variable in the array to its index
152  // in the array.
153  VariableMap variableMap;
154  for (int i = 0 ; i < x.size() ; i++)
155  variableMap[x[i].varimp()] = i;
156 
157  // Convert the modelling-level Symmetries object into an array of
158  // SymmetryImp objects.
159  int n = syms.size();
160  SymmetryImp<SetView>** array =
161  static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
162  for (int i = 0 ; i < n ; i++) {
163  array[i] = createSetSym(home, syms[i], variableMap);
164  }
165 
166  postldsbsetbrancher<SetView,1,int,2>
167  (home,xv,vs,Branch::valselcommit(home,vals),array,n,bf,vvp);
168  }
169 
170  void
171  branch(Home home, const SetVarArgs& x,
173  const Symmetries& syms,
174  SetBranchFilter bf,
175  SetVarValPrint vvp) {
176  using namespace Set;
177  if (home.failed()) return;
178  vars.a.expand(home,x);
179  if ((vars.a.select() == SetVarBranch::SEL_NONE) ||
180  (vars.a.select() == SetVarBranch::SEL_RND))
181  vars.b = SET_VAR_NONE();
182  vars.b.expand(home,x);
183  if ((vars.b.select() == SetVarBranch::SEL_NONE) ||
184  (vars.b.select() == SetVarBranch::SEL_RND))
185  vars.c = SET_VAR_NONE();
186  vars.c.expand(home,x);
187  if ((vars.c.select() == SetVarBranch::SEL_NONE) ||
188  (vars.c.select() == SetVarBranch::SEL_RND))
189  vars.d = SET_VAR_NONE();
190  vars.d.expand(home,x);
191  if (vars.b.select() == SetVarBranch::SEL_NONE) {
192  branch(home,x,vars.a,vals,syms,bf,vvp);
193  } else {
194  // Construct mapping from each variable in the array to its index
195  // in the array.
196  VariableMap variableMap;
197  for (int i = 0 ; i < x.size() ; i++)
198  variableMap[x[i].varimp()] = i;
199 
200  // Convert the modelling-level Symmetries object into an array of
201  // SymmetryImp objects.
202  int n = syms.size();
203  SymmetryImp<SetView>** array =
204  static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
205  for (int i = 0 ; i < n ; i++) {
206  array[i] = Set::LDSB::createSetSym(home, syms[i], variableMap);
207  }
208 
209  ViewArray<SetView> xv(home,x);
211  if (vars.c.select() == SetVarBranch::SEL_NONE) {
212  ViewSel<SetView>* vs[2] = {
213  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
214  };
215  postldsbsetbrancher<SetView,2,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
216  } else if (vars.d.select() == SetVarBranch::SEL_NONE) {
217  ViewSel<SetView>* vs[3] = {
218  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
219  Branch::viewsel(home,vars.c)
220  };
221  postldsbsetbrancher<SetView,3,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
222  } else {
223  ViewSel<SetView>* vs[4] = {
224  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
225  Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
226  };
227  postldsbsetbrancher<SetView,4,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
228  }
229  }
230  }
231 
232 }
233 
234 // STATISTICS: set-branch
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.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1607
Argument array for non-primitive types.
Definition: array.hpp:691
Home class for posting propagators
Definition: core.hpp:856
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:4048
Value iterator for integer sets.
Definition: int.hh:333
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:198
Exception: Variable in symmetry not branched on
Definition: exception.hpp:150
Implementation of a single symmetry.
Definition: ldsb.hh:162
Implementation of a value sequence symmetry.
Definition: ldsb.hh:266
Implementation of a value sequence symmetry at the modelling level.
Definition: ldsb.hh:150
IntArgs values
Array of values in symmetry.
Definition: ldsb.hh:153
int seq_size
Size of each sequence in symmetry.
Definition: ldsb.hh:155
Implementation of a value symmetry.
Definition: ldsb.hh:204
Implementation of a value symmetry at the modelling level.
Definition: ldsb.hh:128
IntSet values
Set of symmetric values.
Definition: ldsb.hh:131
Map from variable implementation to index.
Definition: ldsb.cpp:130
Implementation of a variable sequence symmetry.
Definition: ldsb.hh:224
Implementation of a variable sequence symmetry at the modelling level.
Definition: ldsb.hh:136
int seq_size
Size of each sequence in symmetry.
Definition: ldsb.hh:143
int nxs
Number of variables in symmetry.
Definition: ldsb.hh:141
VarImpBase ** xs
Array of variables in symmetry.
Definition: ldsb.hh:139
Implementation of a variable symmetry.
Definition: ldsb.hh:183
Implementation of a variable symmetry at the modelling level.
Definition: ldsb.hh:116
int nxs
Number of variables in symmetry.
Definition: ldsb.hh:121
VarImpBase ** xs
Array of variables in symmetry.
Definition: ldsb.hh:119
Which values to select for branching first.
Definition: set.hh:1447
Passing set variables.
Definition: set.hh:488
Which variable to select for branching.
Definition: set.hh:1296
Expand and CHB void expand(Home home, const SetVarArgs &x)
Definition: var.hpp:74
@ SEL_NONE
First unassigned.
Definition: set.hh:1300
@ SEL_RND
Random (uniform, for tie breaking)
Definition: set.hh:1301
Set view for set variables
Definition: view.hpp:56
Computation spaces.
Definition: core.hpp:1742
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2837
Collection of symmetries.
Definition: int.hh:5292
A reference-counted pointer to a SymmetryObject.
Definition: int.hh:5255
Int::LDSB::SymmetryObject * ref
Symmetry object that this handle refers to.
Definition: int.hh:5258
Combine variable selection criteria for tie-breaking.
Definition: tiebreak.hpp:38
VarBranch b
Definition: tiebreak.hpp:41
VarBranch a
Branching criteria to try in order.
Definition: tiebreak.hpp:41
VarBranch c
Definition: tiebreak.hpp:41
VarBranch d
Definition: tiebreak.hpp:41
Base class for value selection and commit.
View arrays.
Definition: array.hpp:253
Abstract class for view selection.
Definition: view-sel.hpp:44
int ModEvent
Type for modification events.
Definition: core.hpp:62
SymmetryHandle VariableSymmetry(const IntVarArgs &vars)
Variables in x are interchangeable.
Definition: ldsb.cpp:62
SymmetryHandle VariableSequenceSymmetry(const IntVarArgs &vars, int ss)
Variable sequences in x of size ss are interchangeable.
Definition: ldsb.cpp:90
std::function< bool(const Space &home, SetVar x, int i)> SetBranchFilter
Branch filter function type for set variables.
Definition: set.hh:1083
void branch(Home home, const SetVarArgs &x, TieBreak< SetVarBranch > vars, SetValBranch vals, const Symmetries &syms, SetBranchFilter bf, SetVarValPrint vvp)
Branch over x with tie-breaking variable selection vars and value selection vals with symmetry breaki...
Definition: ldsb.cpp:171
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
SymmetryImp< SetView > * createSetSym(Space &home, const SymmetryHandle &s, VariableMap variableMap)
Definition: ldsb.cpp:74
Gecode::IntArgs i({1, 2, 3, 4})
const int v[7]
Definition: distinct.cpp:259
SetVarBranch SET_VAR_NONE(void)
Definition: var.hpp:96
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56