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 * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5 *
6 * Contributing authors:
7 * Christian Schulte <schulte@gecode.org>
8 * Guido Tack <tack@gecode.org>
9 *
10 * Copyright:
11 * Patrick Pekczynski, 2004
12 * Christian Schulte, 2009
13 * Guido Tack, 2009
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40namespace Gecode { namespace Int { namespace GCC {
41
42 /*
43 * Analogously to "gcc/bnd.hpp" we split the algorithm
44 * in two parts:
45 * 1) the UBC (Upper Bound Constraint) stating that there are
46 * at most k[i].max() occurences of the value v_i
47 * 2) the LBC (Lower Bound Constraint) stating that there are
48 * at least k[i].min() occurences of the value v_i
49 *
50 * The algorithm proceeds in 5 STEPS:
51 *
52 * STEP 1:
53 * Build the bipartite value-graph G=(<X,D>,E),
54 * with X = all variable nodes (each variable forms a node)
55 * D = all value nodes (union over all domains of the variables)
56 * and (x_i,v) is an edge in G iff value v is in the domain D_i of x_i
57 *
58 * STEP 2: Compute a matching in the value graph.
59 * STEP 3: Compute all even alternating paths from unmatched nodes
60 * STEP 4: Compute strongly connected components in the merged graph
61 * STEP 5: Update the Domains according to the computed edges
62 *
63 */
64
65 template<class Card>
66 inline
68 ViewArray<Card>& k0, bool cf)
69 : Propagator(home), x(x0), y(home, x0),
70 k(k0), vvg(NULL), card_fixed(cf){
71 // y is used for bounds propagation since prop_bnd needs all variables
72 // values within the domain bounds
73 x.subscribe(home, *this, PC_INT_DOM);
74 k.subscribe(home, *this, PC_INT_DOM);
75 }
76
77 template<class Card>
80 : Propagator(home, p), vvg(NULL), card_fixed(p.card_fixed) {
81 x.update(home, p.x);
82 y.update(home, p.y);
83 k.update(home, p.k);
84 }
85
86 template<class Card>
87 forceinline size_t
89 x.cancel(home,*this, PC_INT_DOM);
90 k.cancel(home,*this, PC_INT_DOM);
91 (void) Propagator::dispose(home);
92 return sizeof(*this);
93 }
94
95 template<class Card>
96 Actor*
98 return new (home) Dom<Card>(home, *this);
99 }
100
101 template<class Card>
103 Dom<Card>::cost(const Space&, const ModEventDelta&) const {
104 return PropCost::cubic(PropCost::LO, x.size());
105 }
106
107 template<class Card>
108 void
110 x.reschedule(home, *this, PC_INT_DOM);
111 k.reschedule(home, *this, PC_INT_DOM);
112 }
113
114 template<class Card>
117 Region r;
118
119 int* count = r.alloc<int>(k.size());
120 for (int i = k.size(); i--; )
121 count[i] = 0;
122
123 // total number of assigned views
124 int noa = 0;
125 for (int i = y.size(); i--; )
126 if (y[i].assigned()) {
127 noa++;
128 int idx;
129 if (!lookupValue(k,y[i].val(),idx))
130 return ES_FAILED;
131 count[idx]++;
132 if (Card::propagate && (k[idx].max() == 0))
133 return ES_FAILED;
134 }
135
136 if (noa == y.size()) {
137 // All views are assigned
138 for (int i = k.size(); i--; ) {
139 if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
140 return ES_FAILED;
141 // the solution contains ci occurences of value k[i].card();
142 if (Card::propagate)
143 GECODE_ME_CHECK(k[i].eq(home, count[i]));
144 }
145 return home.ES_SUBSUMED(*this);
146 }
147
148 // before propagation performs inferences on cardinality variables:
149 if (Card::propagate) {
150 if (noa > 0)
151 for (int i = k.size(); i--; )
152 if (!k[i].assigned()) {
153 GECODE_ME_CHECK(k[i].lq(home, y.size() - (noa - count[i])));
154 GECODE_ME_CHECK(k[i].gq(home, count[i]));
155 }
156
158 if (!card_consistent<Card>(y,k))
159 return ES_FAILED;
160 }
161
162 if (x.size() == 0) {
163 for (int j = k.size(); j--; )
164 if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
165 return ES_FAILED;
166 return home.ES_SUBSUMED(*this);
167 } else if ((x.size() == 1) && (x[0].assigned())) {
168 int idx;
169 if (!lookupValue(k,x[0].val(),idx))
170 return ES_FAILED;
171 GECODE_ME_CHECK(k[idx].inc());
172 for (int j = k.size(); j--; )
173 if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
174 return ES_FAILED;
175 return home.ES_SUBSUMED(*this);
176 }
177
178 if (vvg == NULL) {
179 int smin = 0;
180 int smax = 0;
181 for (int i=k.size(); i--; )
182 if (k[i].counter() > k[i].max() ) {
183 return ES_FAILED;
184 } else {
185 smax += (k[i].max() - k[i].counter());
186 if (k[i].counter() < k[i].min())
187 smin += (k[i].min() - k[i].counter());
188 }
189
190 if ((x.size() < smin) || (smax < x.size()))
191 return ES_FAILED;
192
193 vvg = new (home) VarValGraph<Card>(home, x, k, smin, smax);
194 GECODE_ES_CHECK(vvg->min_require(home,x,k));
195 GECODE_ES_CHECK(vvg->template maximum_matching<UBC>());
196 if (!card_fixed)
197 GECODE_ES_CHECK(vvg->template maximum_matching<LBC>());
198 } else {
199 GECODE_ES_CHECK(vvg->sync(x,k));
200 }
201
202 vvg->template free_alternating_paths<UBC>();
203 vvg->template strongly_connected_components<UBC>();
204
205 GECODE_ES_CHECK(vvg->template narrow<UBC>(home,x,k));
206
207 if (!card_fixed) {
208 if (Card::propagate)
209 GECODE_ES_CHECK(vvg->sync(x,k));
210
211 vvg->template free_alternating_paths<LBC>();
212 vvg->template strongly_connected_components<LBC>();
213
214 GECODE_ES_CHECK(vvg->template narrow<LBC>(home,x,k));
215 }
216
217 {
218 bool card_assigned = true;
219 if (Card::propagate) {
221 card_assigned = k.assigned();
222 }
223
224 if (card_assigned) {
225 if (x.size() == 0) {
226 for (int j=k.size(); j--; )
227 if ((k[j].min() > k[j].counter()) ||
228 (k[j].max() < k[j].counter()))
229 return ES_FAILED;
230 return home.ES_SUBSUMED(*this);
231 } else if ((x.size() == 1) && x[0].assigned()) {
232 int idx;
233 if (!lookupValue(k,x[0].val(),idx))
234 return ES_FAILED;
235 GECODE_ME_CHECK(k[idx].inc());
236
237 for (int j = k.size(); j--; )
238 if ((k[j].min() > k[j].counter()) ||
239 (k[j].max() < k[j].counter()))
240 return ES_FAILED;
241 return home.ES_SUBSUMED(*this);
242 }
243 }
244 }
245
246 for (int i = k.size(); i--; )
247 count[i] = 0;
248
249 bool all_assigned = true;
250 // total number of assigned views
251 for (int i = y.size(); i--; )
252 if (y[i].assigned()) {
253 int idx;
254 if (!lookupValue(k,y[i].val(),idx))
255 return ES_FAILED;
256 count[idx]++;
257 if (Card::propagate && (k[idx].max() == 0))
258 return ES_FAILED;
259 } else {
260 all_assigned = false;
261 }
262
263 if (Card::propagate)
265
266 if (all_assigned) {
267 for (int i = k.size(); i--; ) {
268 if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
269 return ES_FAILED;
270 // the solution contains count[i] occurences of value k[i].card();
271 if (Card::propagate)
272 GECODE_ME_CHECK(k[i].eq(home,count[i]));
273 }
274 return home.ES_SUBSUMED(*this);
275 }
276
277 if (Card::propagate) {
278 int ysmax = y.size();
279 for (int i=k.size(); i--; )
280 ysmax -= k[i].max();
281 int smax = 0;
282 bool card_ass = true;
283 for (int i = k.size(); i--; ) {
284 GECODE_ME_CHECK(k[i].gq(home, ysmax + k[i].max()));
285 smax += k[i].max();
286 GECODE_ME_CHECK(k[i].lq(home, y.size() + k[i].min()));
287 if (!k[i].assigned())
288 card_ass = false;
289 }
290 if (card_ass && (smax != y.size()))
291 return ES_FAILED;
292 }
293
294 return Card::propagate ? ES_NOFIX : ES_FIX;
295 }
296
297 template<class Card>
298 inline ExecStatus
302
303 if (isDistinct<Card>(x,k))
304 return Distinct::Dom<IntView>::post(home,x);
305
306 bool cardfix = true;
307 for (int i = k.size(); i--; )
308 if (!k[i].assigned()) {
309 cardfix = false; break;
310 }
311
312 (void) new (home) Dom<Card>(home,x,k,cardfix);
313 return ES_OK;
314 }
315
316}}}
317
318// STATISTICS: int-prop
int p
Number of positive literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Home class for posting propagators
Definition core.hpp:856
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition dom.hpp:45
Domain consistent global cardinality propagator.
Definition gcc.hh:219
virtual size_t dispose(Space &home)
Destructor.
Definition dom.hpp:88
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition dom.hpp:116
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition dom.hpp:97
ViewArray< IntView > y
Views used to channel information between x and k ( ).
Definition gcc.hh:227
ViewArray< IntView > x
Views on which to perform domain-propagation.
Definition gcc.hh:222
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition dom.hpp:103
Dom(Space &home, Dom< Card > &p)
Constructor for cloning p.
Definition dom.hpp:79
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition gcc.hh:229
virtual void reschedule(Space &home)
Schedule function.
Definition dom.hpp:109
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition dom.hpp:299
Variable-value-graph used during propagation.
Definition dom-sup.hpp:387
Propagation cost.
Definition core.hpp:486
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition core.hpp:4778
Base-class for propagators.
Definition core.hpp:1064
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1742
bool assigned(void) const
Test whether view is assigned.
Definition var.hpp:111
View arrays.
Definition array.hpp:253
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition array.hpp:1328
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition array.hpp:1341
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1156
bool card_consistent(ViewArray< IntView > &x, ViewArray< Card > &k)
Consistency check, whether the cardinality values are feasible.
Definition bnd-sup.hpp:139
ExecStatus prop_card(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Bounds consistency check for cardinality variables.
Definition bnd-sup.hpp:74
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
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
bool isDistinct(ViewArray< IntView > &x, ViewArray< Card > &k)
Check if GCC is equivalent to distinct.
Definition post.hpp:138
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition view.hpp:45
ExecStatus postSideConstraints(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post side constraints for the GCC.
Definition post.hpp:60
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode toplevel namespace
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
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 .
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187