Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
38namespace 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
58namespace Gecode { namespace Int { namespace LDSB {
59 template <>
61 return x.exclude(home, v);
62 }
63}}}
64
65namespace 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) {
77 dynamic_cast<VariableSymmetryObject*>(s.ref);
78 ValueSymmetryObject* valref =
79 dynamic_cast<ValueSymmetryObject*>(s.ref);
81 dynamic_cast<VariableSequenceSymmetryObject*>(s.ref);
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 }
129 return NULL;
130 }
131}}}
132
133namespace 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,
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
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,
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 size(void) const
Return size of array (number of elements)
Definition array.hpp:1613
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:4055
Value iterator for integer sets.
Definition int.hh:333
unsigned int size(void) const
Return size (cardinality) of set.
Exception: Variable in symmetry not branched on
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:1453
Passing set variables.
Definition set.hh:491
Which variable to select for branching.
Definition set.hh:1302
Expand and CHB void expand(Home home, const SetVarArgs &x)
Definition var.hpp:74
@ SEL_NONE
First unassigned.
Definition set.hh:1306
@ SEL_RND
Random (uniform, for tie breaking)
Definition set.hh:1307
Set view for set variables
Definition view.hpp:56
Computation spaces.
Definition core.hpp:1744
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2841
Collection of symmetries.
Definition int.hh:5307
A reference-counted pointer to a SymmetryObject.
Definition int.hh:5270
Int::LDSB::SymmetryObject * ref
Symmetry object that this handle refers to.
Definition int.hh:5273
Combine variable selection criteria for tie-breaking.
Definition tiebreak.hpp:38
VarBranch a
Branching criteria to try in order.
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
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
std::function< bool(const Space &home, SetVar x, int i)> SetBranchFilter
Branch filter function type for set variables.
Definition set.hh:1089
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition view-sel.cpp:39
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
Symmetry breaking for integer variables.
Definition int.hh:5261
ModEvent prune< Set::SetView >(Space &home, Set::SetView x, int v)
Definition ldsb.cpp:60
Finite domain integers.
Symmetry breaking for set variables.
Definition ldsb.cpp:65
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
SymmetryImp< SetView > * createSetSym(Space &home, const SymmetryHandle &s, VariableMap variableMap)
Definition ldsb.cpp:74
Finite integer sets.
Definition var-imp.hpp:137
Gecode toplevel namespace
Select first unassigned variable SetVarBranch SET_VAR_NONE(void)
Definition var.hpp:96
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:1291
SymmetryHandle VariableSymmetry(const IntVarArgs &x)
Variables in x are interchangeable.
Definition ldsb.cpp:62
SymmetryHandle VariableSequenceSymmetry(const IntVarArgs &x, int ss)
Variable sequences in x of size ss are interchangeable.
Definition ldsb.cpp:90
Post propagator for SetVar x
Definition set.hh:773
int ModEvent
Type for modification events.
Definition core.hpp:62
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56