Generated on Sat Feb 7 2015 02:01:23 for Gecode by doxygen 1.8.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  * Last modified:
10  * $Date: 2013-05-15 20:32:39 +0200 (Wed, 15 May 2013) $ by $Author: schulte $
11  * $Revision: 13639 $
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 
50  for (int i = 0 ; i < x.size() ; i++)
51  a[i] = x[i].varimp();
53  }
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);
84  VariableSequenceSymmetryObject* varseqref =
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  BrancherHandle
142  branch(Home home, const SetVarArgs& x,
143  SetVarBranch vars, SetValBranch vals,
144  const Symmetries& syms,
146  using namespace Set;
147  if (home.failed()) return BrancherHandle();
148  vars.expand(home,x);
149  ViewArray<SetView> xv(home,x);
150  ViewSel<SetView>* vs[1] = {
151  Branch::viewsel(home,vars)
152  };
153 
154  // Construct mapping from each variable in the array to its index
155  // in the array.
156  VariableMap variableMap;
157  for (int i = 0 ; i < x.size() ; i++)
158  variableMap[x[i].varimp()] = i;
159 
160  // Convert the modelling-level Symmetries object into an array of
161  // SymmetryImp objects.
162  int n = syms.size();
163  SymmetryImp<SetView>** array =
164  static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
165  for (int i = 0 ; i < n ; i++) {
166  array[i] = createSetSym(home, syms[i], variableMap);
167  }
168 
170  (home,xv,vs,Branch::valselcommit(home,vals),array,n,bf,vvp);
171  }
172 
173  BrancherHandle
174  branch(Home home, const SetVarArgs& x,
176  const Symmetries& syms,
178  using namespace Set;
179  if (home.failed()) return BrancherHandle();
180  vars.a.expand(home,x);
181  if ((vars.a.select() == SetVarBranch::SEL_NONE) ||
182  (vars.a.select() == SetVarBranch::SEL_RND))
183  vars.b = SET_VAR_NONE();
184  vars.b.expand(home,x);
185  if ((vars.b.select() == SetVarBranch::SEL_NONE) ||
186  (vars.b.select() == SetVarBranch::SEL_RND))
187  vars.c = SET_VAR_NONE();
188  vars.c.expand(home,x);
189  if ((vars.c.select() == SetVarBranch::SEL_NONE) ||
190  (vars.c.select() == SetVarBranch::SEL_RND))
191  vars.d = SET_VAR_NONE();
192  vars.d.expand(home,x);
193  if (vars.b.select() == SetVarBranch::SEL_NONE) {
194  return branch(home,x,vars.a,vals,syms,bf,vvp);
195  } else {
196  // Construct mapping from each variable in the array to its index
197  // in the array.
198  VariableMap variableMap;
199  for (int i = 0 ; i < x.size() ; i++)
200  variableMap[x[i].varimp()] = i;
201 
202  // Convert the modelling-level Symmetries object into an array of
203  // SymmetryImp objects.
204  int n = syms.size();
205  SymmetryImp<SetView>** array =
206  static_cast<Space&>(home).alloc<SymmetryImp<SetView>* >(n);
207  for (int i = 0 ; i < n ; i++) {
208  array[i] = Set::LDSB::createSetSym(home, syms[i], variableMap);
209  }
210 
211  ViewArray<SetView> xv(home,x);
213  if (vars.c.select() == SetVarBranch::SEL_NONE) {
214  ViewSel<SetView>* vs[2] = {
215  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
216  };
217  return
218  LDSBSetBrancher<SetView,2,int,2>::post(home,xv,vs,vsc,array,n,bf,vvp);
219  } else if (vars.d.select() == SetVarBranch::SEL_NONE) {
220  ViewSel<SetView>* vs[3] = {
221  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
222  Branch::viewsel(home,vars.c)
223  };
224  return
225  LDSBSetBrancher<SetView,3,int,2>::post(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  return
232  LDSBSetBrancher<SetView,4,int,2>::post(home,xv,vs,vsc,array,n,bf,vvp);
233  }
234  }
235  }
236 
237 }
238 
239 // STATISTICS: set-branch
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
Which values to select for branching first.
Definition: set.hh:1382
VarImpBase ** xs
Array of variables in symmetry.
Definition: ldsb.hh:123
Combine variable selection criteria for tie-breaking.
SetVarBranch SET_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:91
IntSet values
Set of symmetric values.
Definition: ldsb.hh:135
IntArgs values
Array of values in symmetry.
Definition: ldsb.hh:157
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
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
Handle for brancher.
Definition: core.hpp:1157
Abstract class for view selection.
Collection of symmetries.
Definition: int.hh:4300
int ModEvent
Type for modification events.
Definition: core.hpp:146
Implementation of a variable sequence symmetry.
Definition: ldsb.hh:225
Computation spaces.
Definition: core.hpp:1362
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:2397
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
First unassigned.
Definition: set.hh:1257
A reference-counted pointer to a SymmetryObject.
Definition: int.hh:4263
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:205
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
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:161
const int v[7]
Definition: distinct.cpp:207
Set view for set variables
Definition: view.hpp:60
Passing set variables.
Definition: set.hh:490
Random (uniform, for tie breaking)
Definition: set.hh:1258
Implementation of a single symmetry.
Definition: ldsb.hh:166
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
void expand(Home home, const SetVarArgs &x)
Expand decay factor into AFC or activity.
Definition: var.hpp:74
static BrancherHandle post(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, SymmetryImp< View > **_syms, int _nsyms, SetBranchFilter bf, VarValPrint vvp)
Brancher post function.
Definition: brancher.hpp:248
Implementation of a variable symmetry.
Definition: ldsb.hh:185
Value iterator for integer sets.
Definition: int.hh:312
void(* SetVarValPrint)(const Space &home, const BrancherHandle &bh, unsigned int a, SetVar x, int i, const int &n, std::ostream &o)
Function type for printing branching alternatives for set variables.
Definition: set.hh:1239
bool(* SetBranchFilter)(const Space &home, SetVar x, int i)
Branch filter function type for set variables.
Definition: set.hh:1102
Int::LDSB::SymmetryObject * ref
Symmetry object that this handle refers to.
Definition: int.hh:4266
VarBranch a
Branching criteria to try in order.
Implementation of a value sequence symmetry.
Definition: ldsb.hh:267
SymmetryHandle VariableSequenceSymmetry(const IntVarArgs &vars, int ss)
Variable sequences in x of size ss are interchangeable.
Definition: ldsb.cpp:94
Gecode toplevel namespace
Map from variable implementation to index.
Definition: ldsb.cpp:134
BrancherHandle 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
Which variable to select for branching.
Definition: set.hh:1253
Home class for posting propagators
Definition: core.hpp:717
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.