Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
dom.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Contributing authors:
7 * Mikael Lagerkvist <lagerkvist@gecode.org>
8 *
9 * Copyright:
10 * Christian Schulte, 2006
11 * Mikael Lagerkvist, 2006
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
38namespace Gecode { namespace Int { namespace Channel {
39
44 template<class View, class Offset>
45 class DomInfo {
46 public:
48 View view;
50 unsigned int size;
52 int min;
54 int max;
56 void init(View x, int n);
58 void update(Space& home, DomInfo<View,Offset>& vcb);
60 bool doval(void) const;
62 bool dodom(void) const;
64 void assigned(void);
66 void removed(int i);
68 void done(Offset& o);
69 };
70
71 template<class View, class Offset>
72 forceinline void
74 view = x;
75 size = static_cast<unsigned int>(n);
76 min = 0;
77 max = n-1;
78 }
79
80 template<class View, class Offset>
81 forceinline void
83 view.update(home,di.view);
84 size = di.size;
85 min = di.min;
86 max = di.max;
87 }
88
89 template<class View, class Offset>
90 forceinline bool
92 return (size != 1) && view.assigned();
93 }
94
95 template<class View, class Offset>
96 forceinline bool
98 return size != view.size();
99 }
100
101 template<class View, class Offset>
102 forceinline void
104 size = 1;
105 }
106
107 template<class View, class Offset>
108 forceinline void
110 size--;
111 if (i == min)
112 min++;
113 else if (i == max)
114 max--;
115 }
116
117 template<class View, class Offset>
118 forceinline void
120 size = view.size();
121 min = o(view).min();
122 max = o(view).max();
123 }
124
125 // Propagate domain information from x to y
126 template<class View, class Offset>
130 for (int i=0; i<n; i++)
131 // Only views with not yet propagated missing values
132 if (x[i].dodom()) {
133 // Iterate the values in the complement of x[i]
135 xir(ox(x[i].view));
137 xirc(x[i].min,x[i].max,xir);
140 while (jv()) {
141 // j is not in the domain of x[i], so prune i from y[j]
142 int j = jv.val();
143 ModEvent me = oy(y[j].view).nq(home,i);
144 if (me_failed(me))
145 return ES_FAILED;
146 if (me_modified(me)) {
147 if (me == ME_INT_VAL) {
148 // Record that y[j] has been assigned and must be propagated
149 ya.push(j);
150 } else {
151 // Obvious as x[i] is different from j
152 y[j].removed(i);
153 }
154 }
155 ++jv;
156 }
157 // Update which values have been propagated and what are the new bounds
158 x[i].done(ox);
159 }
160 return ES_OK;
161 }
162
163 /*
164 * The actual propagator
165 *
166 */
167 template<class View, class Offset, bool shared>
170 Offset& ox, Offset& oy)
171 : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,n,xy,ox,oy) {}
172
173 template<class View, class Offset, bool shared>
176 : Base<DomInfo<View,Offset>,Offset,PC_INT_DOM>(home,p) {}
177
178 template<class View, class Offset, bool shared>
179 Actor*
181 return new (home) Dom<View,Offset,shared>(home,*this);
182 }
183
184 template<class View, class Offset, bool shared>
187 const ModEventDelta& med) const {
188 if (View::me(med) == ME_INT_VAL)
190 else
192 }
193
194 template<class View, class Offset, bool shared>
197 // MSVC in non-permissive mode needs this, no idea why...
198 const int n = this->n;
199 Region r;
200 ProcessStack xa(r,n);
201 ProcessStack ya(r,n);
202
205
206 if (View::me(med) == ME_INT_VAL) {
207 // Scan x and y for assigned but not yet propagated views
208 for (int i=0; i<n; i++) {
209 if (x[i].doval()) xa.push(i);
210 if (y[i].doval()) ya.push(i);
211 }
212
213 if (shared) {
214 do {
215 // Propagate assigned views for x
217 (home,n,x,ox,y,oy,n_na,xa,ya)));
218 // Propagate assigned views for y
220 (home,n,y,oy,x,ox,n_na,ya,xa)));
221 assert(ya.empty());
222 } while (!xa.empty() || !ya.empty());
223 return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
224 } else {
225 do {
226 // Propagate assigned views for x
228 (home,n,x,ox,y,oy,n_na,xa,ya)));
229 // Propagate assigned views for y
231 (home,n,y,oy,x,ox,n_na,ya,xa)));
232 assert(ya.empty());
233 } while (!xa.empty());
234 return home.ES_FIX_PARTIAL(*this,View::med(ME_INT_DOM));
235 }
236 }
237
238 // Process changed views for y
239 // This propagates from y to x and possibly records xs that
240 // got assigned
241 GECODE_ES_CHECK(prop_dom(home,n,y,oy,x,ox,xa));
242
243 // Process assigned views for x
245 (home,n,x,ox,y,oy,n_na,xa,ya)));
246
247 // Perform domain consistent propagation for distinct on the x views
248 if (dc.available()) {
249 GECODE_ES_CHECK(dc.sync());
250 } else {
251 ViewArray<View> xv(r,n);
252 for (int i=0; i<n; i++)
253 xv[i] = x[i].view;
254 GECODE_ES_CHECK(dc.init(home,xv));
255 }
256 bool assigned;
257 GECODE_ES_CHECK(dc.propagate(home,assigned));
258 if (assigned) {
259 // This has assigned some more views in x which goes unnoticed
260 // (that is, not recorded in xa). This must be checked and propagated
261 // to the y views, however the distinctness on x is already
262 // propagated.
263 for (int i=0; i<n; i++)
264 if (x[i].doval()) {
265 int j = ox(x[i].view).val();
266 // Assign the y variable to i (or test if already assigned!)
267 ModEvent me = oy(y[j].view).eq(home,i);
268 if (me_failed(me))
269 return ES_FAILED;
270 if (me_modified(me)) {
271 // Record that y[j] has been assigned and must be propagated
272 assert(me == ME_INT_VAL);
273 // Otherwise the modification event would not be ME_INT_VAL
274 ya.push(j);
275 }
276 x[i].assigned(); n_na--;
277 }
278 }
279
280 // Process changed views for x
281 // This propagates from x to y and possibly records ys that
282 // got assigned
283 GECODE_ES_CHECK(prop_dom(home,n,x,ox,y,oy,ya));
284
285 // Process assigned view again (some might have been found above)
286 while (!xa.empty() || !ya.empty()) {
287 // Process assigned views for x
289 (home,n,x,ox,y,oy,n_na,xa,ya)));
290 // Process assigned views for y
292 (home,n,y,oy,x,ox,n_na,ya,xa)));
293 };
294
295 if (shared) {
296 for (int i=0; i<2*n; i++)
297 if (!xy[i].view.assigned())
298 return ES_NOFIX;
299 return home.ES_SUBSUMED(*this);
300 } else {
301 return (n_na == 0) ? home.ES_SUBSUMED(*this) : ES_FIX;
302 }
303 }
304
305 template<class View, class Offset, bool shared>
308 Offset& ox, Offset& oy) {
309 assert(n > 0);
310 if (n == 1) {
311 GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
312 GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
313 return ES_OK;
314 }
315 for (int i=0; i<n; i++) {
316 GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
317 GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
318 GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
319 GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
320 }
321 (void) new (home) Dom<View,Offset,shared>(home,n,xy,ox,oy);
322 return ES_OK;
323 }
324
325}}}
326
327// STATISTICS: int-prop
328
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
Home class for posting propagators
Definition core.hpp:856
Base-class for channel propagators.
Definition channel.hh:55
Combine view with information for domain propagation.
Definition dom.hpp:45
void update(Space &home, DomInfo< View, Offset > &vcb)
Update during cloning.
Definition dom.hpp:82
unsigned int size
Last propagated size.
Definition dom.hpp:50
void removed(int i)
Record that one value got removed.
Definition dom.hpp:109
void assigned(void)
Record that view got assigned.
Definition dom.hpp:103
void done(Offset &o)
Update the size and bounds information after pruning.
Definition dom.hpp:119
int min
Last propagated minimum.
Definition dom.hpp:52
bool doval(void) const
Check whether propagation for assignment is to be done.
Definition dom.hpp:91
void init(View x, int n)
Initialize.
Definition dom.hpp:73
bool dodom(void) const
Check whether propagation for domain is to be done.
Definition dom.hpp:97
int max
Last propagated maximum.
Definition dom.hpp:54
Domain consistent channel propagator.
Definition channel.hh:134
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition dom.hpp:196
static ExecStatus post(Home home, int n, DomInfo< View, Offset > *xy, Offset &ox, Offset &oy)
Post propagator for channeling on xy.
Definition dom.hpp:307
Dom(Space &home, Dom &p)
Constructor for cloning p.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition dom.hpp:180
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition dom.hpp:186
Converter with fixed offset.
Definition view.hpp:650
Range iterator for integer views.
Definition view.hpp:54
Range iterator for computing the complement (described by values)
Value iterator from range iterator.
Propagation cost.
Definition core.hpp:486
static PropCost quadratic(PropCost::Mod m, unsigned int n)
Quadratic complexity for modifier m and size measure n.
Definition core.hpp:4787
@ HI
Expensive.
Definition core.hpp:514
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
Stack with fixed number of elements.
void push(const T &x)
Push element x on top of stack.
bool empty(void) const
Test whether stack is empty.
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
View arrays.
Definition array.hpp:253
ExecStatus ES_NOFIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has not computed partial fixpoint
Definition core.hpp:3576
ExecStatus ES_FIX_PARTIAL(Propagator &p, const ModEventDelta &med)
Propagator p has computed partial fixpoint
Definition core.hpp:3569
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
ExecStatus prop_val(Space &home, int n, Info *x, Offset &ox, Info *y, Offset &oy, int &n_na, ProcessStack &xa, ProcessStack &ya)
Definition val.hpp:169
ExecStatus prop_dom(Space &home, int n, DomInfo< View, Offset > *x, Offset &ox, DomInfo< View, Offset > *y, Offset &oy, ProcessStack &ya)
Definition dom.hpp:128
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:767
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Definition array.hpp:1466
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:187