00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 namespace Gecode { namespace Int { namespace GCC {
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047 template <class View, class Card, bool isView>
00048 forceinline
00049 Dom<View, Card, isView>::Dom(Space* home, ViewArray<View>& x0, Card& k0)
00050 : Propagator(home, true), x(x0), y(home, x0),
00051 k(k0), l(home, k0), vvg(NULL) {
00052
00053
00054
00055 x.subscribe(home, this, PC_INT_DOM);
00056 k.subscribe(home, this, PC_INT_DOM);
00057 }
00058
00059 template <class View, class Card, bool isView>
00060 forceinline
00061 Dom<View, Card, isView>::Dom(Space* home, bool share, Dom<View, VarCard, isView>& p)
00062 : Propagator(home, share, p), vvg(NULL) {
00063 x.update(home, share, p.x);
00064 y.update(home, share, p.y);
00065 k.update(home, share, p.k);
00066 l.update(home, share, p.l);
00067 }
00068
00069 template <class View, class Card, bool isView>
00070 forceinline
00071 Dom<View, Card, isView>::Dom(Space* home, bool share, Dom<View, FixCard, isView>& p)
00072 : Propagator(home, share, p), k(p.k.size()), l(p.l.size()), vvg(NULL) {
00073 x.update(home, share, p.x);
00074 y.update(home, share, p.y);
00075 k.update(home, share, p.k);
00076 l.update(home, share, p.l);
00077 }
00078
00079 template <class View, class Card, bool isView>
00080 Dom<View, Card, isView>::~Dom(void) {
00081 x.cancel(this, PC_INT_DOM);
00082 k.cancel(this, PC_INT_DOM);
00083 delete vvg;
00084 }
00085
00086 template <class View, class Card, bool isView>
00087 forceinline void
00088 Dom<View, Card, isView>::flush(void) {
00089 delete vvg;
00090 vvg = NULL;
00091 }
00092
00093 template <class View, class Card, bool isView>
00094 forceinline Actor*
00095 Dom<View, Card, isView>::copy(Space* home, bool share) {
00096 return new (home) Dom<View, Card, isView>(home, share, *this);
00097 }
00098
00099 template <class View, class Card, bool isView>
00100 forceinline PropCost
00101 Dom<View, Card, isView>::cost (void) const {
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111 PropCost pc;
00112 switch (View::pme(this)) {
00113 case ME_INT_VAL:
00114 pc = PC_LINEAR_LO; break;
00115 case ME_INT_BND:
00116 pc = PC_LINEAR_HI; break;
00117 default:
00118 pc = PC_CUBIC_LO; break;
00119 }
00120
00121 return cost_lo(x.size(), pc);
00122 }
00123
00124 template <class View, class Card, bool isView>
00125 ExecStatus
00126 Dom<View, Card, isView>::propagate(Space* home) {
00127
00128 if (View::pme(this) == ME_INT_VAL) {
00129
00130 ExecStatus es = prop_val<View, Card, isView>(home, x, k);
00131 if ((es == ES_FAILED) || (es == ES_SUBSUMED)) {
00132 return es;
00133 }
00134 if (es == ES_FIX) {
00135 return ES_FIX_PARTIAL(View::pme(ME_INT_DOM));
00136 }
00137 if (es == ES_NOFIX) {
00138 return ES_NOFIX;
00139 }
00140 }
00141
00142 if (View::pme(this) == ME_INT_BND) {
00143
00144 for (int i = 0; i < l.size(); i++) {
00145 int kidx = 0;
00146 while (k[kidx].card() != l[i].card()) {
00147 kidx++;
00148 }
00149 int max = std::max(k[kidx].counter(), l[i].counter());
00150 k[kidx].counter(max);
00151 l[i].counter(max);
00152 }
00153
00154 int cmin = y[y.size() - 1].min();
00155 int cmax = y[y.size() - 1].max();
00156
00157 for (int i = y.size() - 1; i--; ) {
00158 if (y[i].min() < cmin) {
00159 cmin = y[i].min();
00160 }
00161 if (y[i].max() > cmax) {
00162 cmax = y[i].max();
00163 }
00164 }
00165
00166 reduce_card(cmin, cmax, l);
00167
00168 PartialSum<Card>* lps = new PartialSum<Card>(cmin, l.size(), l, false);
00169 PartialSum<Card>* ups = new PartialSum<Card>(cmin, l.size(), l, true);
00170
00171 ExecStatus es =
00172 prop_bnd<View, Card, false, isView>(home, y, l, lps, ups);
00173
00174 delete lps;
00175 lps = NULL;
00176 delete ups;
00177 ups = NULL;
00178
00179 for (int i = 0; i < l.size(); i++) {
00180 int kidx = 0;
00181 while (k[kidx].card() != l[i].card()) {
00182 kidx++;
00183 }
00184 int max = std::max(k[kidx].counter(), l[i].counter());
00185 k[kidx].counter(max);
00186 l[i].counter(max);
00187 }
00188
00189 if ((es == ES_FAILED) || (es == ES_SUBSUMED)) {
00190 return es;
00191 }
00192 if (es == ES_FIX) {
00193 return ES_FIX_PARTIAL(View::pme(ME_INT_DOM));
00194 }
00195 }
00196
00197 GECODE_AUTOARRAY(int, count, k.size());
00198 for (int i = k.size(); i--; ) {
00199 count[i] = 0;
00200 }
00201
00202 bool all_assigned = true;
00203
00204 int noa = 0;
00205 for (int i = y.size(); i--; ) {
00206 bool b = y[i].assigned();
00207 all_assigned &= b;
00208 if (b) {
00209 noa++;
00210 int idx = k.lookup(y[i].val());
00211 if (idx == -1) {
00212 return ES_FAILED;
00213 }
00214 count[idx]++;
00215 }
00216 }
00217
00218 if (all_assigned) {
00219 for (int i = k.size(); i--; ) {
00220 int ci = count[i];
00221 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00222 return ES_FAILED;
00223 }
00224
00225 if (isView) {
00226 ModEvent me = k[i].eq(home, ci);
00227 if (me_failed(me)) {
00228 return ES_FAILED;
00229 }
00230 }
00231 }
00232 return ES_SUBSUMED;
00233 }
00234
00235
00236 if (isView) {
00237 int n = y.size();
00238 int ks = k.size();
00239
00240 for (int i = ks; i--; ) {
00241 if (!k[i].assigned()) {
00242 ModEvent melq = k[i].lq(home, n - (noa - count[i]));
00243 if (me_failed(melq)) {
00244 return ES_FAILED;
00245 }
00246
00247 ModEvent megq = k[i].gq(home, count[i]);
00248 if (me_failed(megq)) {
00249 return ES_FAILED;
00250 }
00251 }
00252 }
00253 }
00254
00255 if (x.size() < 2) {
00256 assert(x.size() >= 0);
00257 if (x.size() == 0) {
00258 for (int j = k.size(); j--; ) {
00259 if (k[j].min() > k[j].counter() || k[j].max() < k[j].counter()) {
00260 return ES_FAILED;
00261 }
00262 }
00263 return ES_SUBSUMED;
00264 } else {
00265 if (x.size() == 1) {
00266 if (x[0].assigned()) {
00267 int v = x[0].val();
00268 int idx = k.lookup(v);
00269 if (idx == -1) {
00270 return ES_FAILED;
00271 }
00272 ModEvent me = k[idx].inc();
00273 if (me_failed(me)) {
00274 return ES_FAILED;
00275 }
00276 for (int j = k.size(); j--; ) {
00277 if (k[j].min() > k[j].counter() || k[j].max() < k[j].counter()) {
00278 return ES_FAILED;
00279 }
00280 }
00281 return ES_SUBSUMED;
00282 }
00283 }
00284 }
00285 }
00286
00287
00288 bool min_req_mod = false;
00289 int noe = 0;
00290 int smin = 0;
00291 int smax = 0;
00292 for (int i = x.size(); i--; ) {
00293 noe +=x[i].size();
00294 }
00295
00296 for (int i = k.size(); i--; ) {
00297 int ci = k[i].counter();
00298 if (ci > k[i].max() ) {
00299 return ES_FAILED;
00300 } else {
00301 smax += (k[i].max() - ci);
00302 if (ci < k[i].min()) {
00303 smin += (k[i].min() - ci);
00304 }
00305 }
00306 }
00307
00308 if (smin > x.size() || x.size() > smax ) {
00309 return ES_FAILED;
00310 }
00311
00312
00313 if (vvg == NULL) {
00314
00315 vvg = new VarValGraph<View, Card, isView> (x, y, k, noe, smin, smax);
00316
00317 min_req_mod = vvg->min_require(home);
00318
00319 bool init_ubm = vvg->template maximum_matching<UBC>();
00320 if (!init_ubm) {
00321 return ES_FAILED;
00322 }
00323
00324 bool init_lbm = vvg->template maximum_matching<LBC>();
00325 if (!init_lbm) {
00326 return ES_FAILED;
00327 }
00328 } else {
00329 if (!vvg->sync()) {
00330 return ES_FAILED;
00331 }
00332 }
00333
00334 vvg->template free_alternating_paths<UBC>();
00335 vvg->template strongly_connected_components<UBC>();
00336
00337 bool filter_ubc = vvg->template narrow<UBC>(home);
00338 if (vvg->failed()) {
00339 return ES_FAILED;
00340 }
00341
00342 if (!vvg->sync()) {
00343 return ES_FAILED;
00344 }
00345
00346 vvg->template free_alternating_paths<LBC>();
00347 vvg->template strongly_connected_components<LBC>();
00348
00349 bool filter_lbc = vvg->template narrow<LBC>(home);
00350 if (vvg->failed()) {
00351 return ES_FAILED;
00352 }
00353
00354 if (x.size() < 2) {
00355 assert(x.size() >= 0);
00356 if (x.size() == 0) {
00357 for (int j = k.size(); j--; ) {
00358 if (k[j].min() > k[j].counter() ||
00359 k[j].max() < k[j].counter()) {
00360 return ES_FAILED;
00361 }
00362 }
00363 return ES_SUBSUMED;
00364 } else {
00365 if (x.size() == 1) {
00366 if (x[0].assigned()) {
00367 int v = x[0].val();
00368 int idx = k.lookup(v);
00369 if (idx == -1) {
00370 return ES_FAILED;
00371 }
00372
00373 ModEvent me = k[idx].inc();
00374 if (me_failed(me)) {
00375 return ES_FAILED;
00376 }
00377 for (int j = k.size(); j--; ) {
00378 if (k[j].min() > k[j].counter() ||
00379 k[j].max() < k[j].counter()) {
00380 return ES_FAILED;
00381 }
00382 }
00383 return ES_SUBSUMED;
00384 }
00385 }
00386 }
00387 }
00388
00389 for (int i = k.size(); i--; ) {
00390 count[i] = 0;
00391 }
00392
00393 all_assigned = true;
00394
00395 for (int i = y.size(); i--; ) {
00396 bool b = y[i].assigned();
00397 all_assigned &= b;
00398 if (b) {
00399 int idx = k.lookup(y[i].val());
00400 if (idx == -1) {
00401 return ES_FAILED;
00402 }
00403 count[idx]++;
00404 }
00405 }
00406
00407 if (all_assigned) {
00408 for (int i = k.size(); i--; ) {
00409 int ci = count[i];
00410 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00411 return ES_FAILED;
00412 }
00413
00414 if (isView) {
00415 ModEvent me = k[i].eq(home, ci);
00416 if (me_failed(me)) {
00417 return ES_FAILED;
00418 }
00419 }
00420 }
00421 return ES_SUBSUMED;
00422 }
00423
00424 if (filter_ubc || filter_lbc || min_req_mod) {
00425 return ES_NOFIX;
00426 } else {
00427 return ES_FIX;
00428 }
00429 }
00430
00431 template <class View, class Card, bool isView>
00432 forceinline
00433 ExecStatus Dom<View, Card, isView>:: post(Space* home,
00434 ViewArray<View>& x0, Card& k0){
00435
00436 (void) new (home) Dom<View, Card, isView>(home, x0, k0);
00437 return ES_OK;
00438 }
00439
00440 }}}
00441
00442
00443
00444
00445