this repo has no description
dekker.one
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
67 Dom<Card>::Dom(Home home, ViewArray<IntView>& x0,
68 ViewArray<Card>& k0, bool cf)
69 : Propagator(home), x(x0), y(home, x0),
70 k(k0), vvg(nullptr), 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>
78 forceinline
79 Dom<Card>::Dom(Space& home, Dom<Card>& p)
80 : Propagator(home, p), vvg(nullptr), 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
88 Dom<Card>::dispose(Space& home) {
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*
97 Dom<Card>::copy(Space& home) {
98 return new (home) Dom<Card>(home, *this);
99 }
100
101 template<class Card>
102 PropCost
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
109 Dom<Card>::reschedule(Space& home) {
110 x.reschedule(home, *this, PC_INT_DOM);
111 k.reschedule(home, *this, PC_INT_DOM);
112 }
113
114 template<class Card>
115 ExecStatus
116 Dom<Card>::propagate(Space& home, const ModEventDelta&) {
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
157 GECODE_ES_CHECK(prop_card<Card>(home,y,k));
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 == nullptr) {
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) {
220 GECODE_ES_CHECK(prop_card<Card>(home, y, k));
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)
264 GECODE_ES_CHECK(prop_card<Card>(home, y, k));
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
299 Dom<Card>::post(Home home,
300 ViewArray<IntView>& x, ViewArray<Card>& k) {
301 GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
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