Generated on Sat Jul 28 2018 17:15:12 for Gecode by doxygen 1.8.14
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  * Last modified:
10  * $Date: 2017-04-01 20:27:10 +0200 (Sat, 01 Apr 2017) $ by $Author: schulte $
11  * $Revision: 15623 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/set/ldsb.hh>
39 #include <gecode/set/branch.hh>
40 #include <map>
41 
42 namespace Gecode {
43  using namespace Int::LDSB;
44  /*
45  * Implementation of some SymmetryHandle methods.
46  */
47 
49  ArgArray<VarImpBase*> a(x.size());
50  for (int i = 0 ; i < x.size() ; i++)
51  a[i] = x[i].varimp();
53  }
55  ArgArray<VarImpBase*> a(x.size());
56  for (int i = 0 ; i < x.size() ; i++)
57  a[i] = x[i].varimp();
59  }
60 }
61 
62 namespace Gecode { namespace Int { namespace LDSB {
63  template <>
64  ModEvent prune<Set::SetView>(Space& home, Set::SetView x, int v) {
65  return x.exclude(home, v);
66  }
67 }}}
68 
69 namespace Gecode { namespace Set { namespace LDSB {
70 
72  class VariableMap : public std::map<VarImpBase*,int> {};
73 
74  /*
75  * The createSetSym function is an almost exact copy of
76  * createIntSym/createBoolSym.
77  */
79  VariableMap variableMap) {
80  VariableSymmetryObject* varref =
81  dynamic_cast<VariableSymmetryObject*>(s.ref);
82  ValueSymmetryObject* valref =
83  dynamic_cast<ValueSymmetryObject*>(s.ref);
85  dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
86  ValueSequenceSymmetryObject* valseqref =
87  dynamic_cast<ValueSequenceSymmetryObject*>(s.ref);
88  if (varref) {
89  int n = varref->nxs;
90  int* indices = home.alloc<int>(n);
91  for (int i = 0 ; i < n ; i++) {
92  VariableMap::const_iterator index = variableMap.find(varref->xs[i]);
93  if (index == variableMap.end())
94  throw
95  Int::LDSBUnbranchedVariable("VariableSymmetryObject::createSet");
96  indices[i] = index->second;
97  }
98  return new (home) VariableSymmetryImp<SetView>(home, indices, n);
99  }
100  if (valref) {
101  int n = valref->values.size();
102  int *vs = home.alloc<int>(n);
103  int i = 0;
104  for (IntSetValues v(valref->values) ; v() ; ++v) {
105  vs[i] = v.val();
106  i++;
107  }
108  return new (home) ValueSymmetryImp<SetView>(home, vs, n);
109  }
110  if (varseqref) {
111  int n = varseqref->nxs;
112  int* indices = home.alloc<int>(n);
113  for (int i = 0 ; i < n ; i++) {
114  VariableMap::const_iterator index =
115  variableMap.find(varseqref->xs[i]);
116  if (index == variableMap.end())
117  throw
118  Int::LDSBUnbranchedVariable("VariableSequenceSymmetryObject::createSet");
119  indices[i] = index->second;
120  }
121  return new (home) VariableSequenceSymmetryImp<SetView>(home, indices, n,
122  varseqref->seq_size);
123  }
124  if (valseqref) {
125  unsigned int n = valseqref->values.size();
126  int *vs = home.alloc<int>(n);
127  for (unsigned int i = 0 ; i < n ; i++)
128  vs[i] = valseqref->values[i];
129  return new (home) ValueSequenceSymmetryImp<SetView>(home, vs, n,
130  valseqref->seq_size);
131  }
132  GECODE_NEVER;
133  return NULL;
134  }
135 }}}
136 
137 namespace Gecode {
138 
139  using namespace Set::LDSB;
140 
141  void
142  branch(Home home, const SetVarArgs& x,
143  SetVarBranch vars, SetValBranch vals,
144  const Symmetries& syms,
145  SetBranchFilter bf,
146  SetVarValPrint vvp) {
147  using namespace Set;
148  if (home.failed()) return;
149  vars.expand(home,x);
150  ViewArray<SetView> xv(home,x);
151  ViewSel<SetView>* vs[1] = {
152  Branch::viewsel(home,vars)
153  };
154 
155  // Construct mapping from each variable in the array to its index
156  // in the array.
157  VariableMap variableMap;
158  for (int i = 0 ; i < x.size() ; i++)
159  variableMap[x[i].varimp()] = i;
160 
161  // Convert the modelling-level Symmetries object into an array of
162  // SymmetryImp objects.
163  int n = syms.size();
164  SymmetryImp<SetView>** array =
165  static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
166  for (int i = 0 ; i < n ; i++) {
167  array[i] = createSetSym(home, syms[i], variableMap);
168  }
169 
170  postldsbsetbrancher<SetView,1,int,2>
171  (home,xv,vs,Branch::valselcommit(home,vals),array,n,bf,vvp);
172  }
173 
174  void
175  branch(Home home, const SetVarArgs& x,
177  const Symmetries& syms,
178  SetBranchFilter bf,
179  SetVarValPrint vvp) {
180  using namespace Set;
181  if (home.failed()) return;
182  vars.a.expand(home,x);
183  if ((vars.a.select() == SetVarBranch::SEL_NONE) ||
184  (vars.a.select() == SetVarBranch::SEL_RND))
185  vars.b = SET_VAR_NONE();
186  vars.b.expand(home,x);
187  if ((vars.b.select() == SetVarBranch::SEL_NONE) ||
188  (vars.b.select() == SetVarBranch::SEL_RND))
189  vars.c = SET_VAR_NONE();
190  vars.c.expand(home,x);
191  if ((vars.c.select() == SetVarBranch::SEL_NONE) ||
192  (vars.c.select() == SetVarBranch::SEL_RND))
193  vars.d = SET_VAR_NONE();
194  vars.d.expand(home,x);
195  if (vars.b.select() == SetVarBranch::SEL_NONE) {
196  branch(home,x,vars.a,vals,syms,bf,vvp);
197  } else {
198  // Construct mapping from each variable in the array to its index
199  // in the array.
200  VariableMap variableMap;
201  for (int i = 0 ; i < x.size() ; i++)
202  variableMap[x[i].varimp()] = i;
203 
204  // Convert the modelling-level Symmetries object into an array of
205  // SymmetryImp objects.
206  int n = syms.size();
207  SymmetryImp<SetView>** array =
208  static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
209  for (int i = 0 ; i < n ; i++) {
210  array[i] = Set::LDSB::createSetSym(home, syms[i], variableMap);
211  }
212 
213  ViewArray<SetView> xv(home,x);
215  if (vars.c.select() == SetVarBranch::SEL_NONE) {
216  ViewSel<SetView>* vs[2] = {
217  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
218  };
219  postldsbsetbrancher<SetView,2,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
220  } else if (vars.d.select() == SetVarBranch::SEL_NONE) {
221  ViewSel<SetView>* vs[3] = {
222  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
223  Branch::viewsel(home,vars.c)
224  };
225  postldsbsetbrancher<SetView,3,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
226  } else {
227  ViewSel<SetView>* vs[4] = {
228  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
229  Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
230  };
231  postldsbsetbrancher<SetView,4,int,2>(home,xv,vs,vsc,array,n,bf,vvp);
232  }
233  }
234  }
235 
236 }
237 
238 // STATISTICS: set-branch
Which values to select for branching first.
Definition: set.hh:1484
VarImpBase ** xs
Array of variables in symmetry.
Definition: ldsb.hh:123
Combine variable selection criteria for tie-breaking.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
IntSet values
Set of symmetric values.
Definition: ldsb.hh:135
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:43
IntArgs values
Array of values in symmetry.
Definition: ldsb.hh:157
First unassigned.
Definition: set.hh:1337
Implementation of a value symmetry at the modelling level.
Definition: ldsb.hh:132
Implementation of a value sequence symmetry at the modelling level.
Definition: ldsb.hh:154
Abstract class for view selection.
Collection of symmetries.
Definition: int.hh:4874
Expand and CHB void expand(Home home, const SetVarArgs &x)
Definition: var.hpp:78
int ModEvent
Type for modification events.
Definition: core.hpp:142
Implementation of a variable sequence symmetry.
Definition: ldsb.hh:227
SetVarBranch SET_VAR_NONE(void)
Definition: var.hpp:100
Computation spaces.
Definition: core.hpp:1748
Base class for value selection and commit.
int nxs
Number of variables in symmetry.
Definition: ldsb.hh:145
SymmetryImp< SetView > * createSetSym(Space &home, const SymmetryHandle &s, VariableMap variableMap)
Definition: ldsb.cpp:78
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2868
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
SymmetryHandle VariableSymmetry(const IntVarArgs &vars)
Variables in x are interchangeable.
Definition: ldsb.cpp:66
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Argument array for non-primitive types.
Definition: array.hpp:727
A reference-counted pointer to a SymmetryObject.
Definition: int.hh:4837
ViewSel< SetView > * viewsel(Space &home, const SetVarBranch &svb)
Return view selectors for set views.
Definition: view-sel.cpp:43
Implementation of a variable symmetry at the modelling level.
Definition: ldsb.hh:120
Implementation of a value symmetry.
Definition: ldsb.hh:207
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:161
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:4099
int nxs
Number of variables in symmetry.
Definition: ldsb.hh:125
int seq_size
Size of each sequence in symmetry.
Definition: ldsb.hh:147
ValSelCommitBase< SetView, int > * valselcommit(Space &home, const SetValBranch &svb)
Return value and commit for set views.
Implementation of a variable sequence symmetry at the modelling level.
Definition: ldsb.hh:140
VarImpBase ** xs
Array of variables in symmetry.
Definition: ldsb.hh:143
int seq_size
Size of each sequence in symmetry.
Definition: ldsb.hh:159
Exception: Variable in symmetry not branched on
Definition: exception.hpp:140
Function type for printing branching alternatives for set variables typedef std::function< void(const Space &home, const Brancher &b, unsigned int a, SetVar x, int i, const int &n, std::ostream &o)> SetVarValPrint
Definition: set.hh:1322
const int v[7]
Definition: distinct.cpp:263
Set view for set variables
Definition: view.hpp:60
Passing set variables.
Definition: set.hh:492
Implementation of a single symmetry.
Definition: ldsb.hh:166
Implementation of a variable symmetry.
Definition: ldsb.hh:187
Value iterator for integer sets.
Definition: int.hh:315
Int::LDSB::SymmetryObject * ref
Symmetry object that this handle refers to.
Definition: int.hh:4840
VarBranch a
Branching criteria to try in order.
std::function< bool(const Space &home, SetVar x, int i)> SetBranchFilter
Branch filter function type for set variables.
Definition: set.hh:1129
Implementation of a value sequence symmetry.
Definition: ldsb.hh:269
Post propagator for SetVar x
Definition: set.hh:784
SymmetryHandle VariableSequenceSymmetry(const IntVarArgs &vars, int ss)
Variable sequences in x of size ss are interchangeable.
Definition: ldsb.cpp:94
Random (uniform, for tie breaking)
Definition: set.hh:1338
Gecode toplevel namespace
Map from variable implementation to index.
Definition: ldsb.cpp:134
Which variable to select for branching.
Definition: set.hh:1333
Home class for posting propagators
Definition: core.hpp:922
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60