00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 namespace Gecode { namespace Int { namespace GCC {
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064 template <class View, class Card, bool isView>
00065 inline
00066 Dom<View, Card, isView>::Dom(Space* home, ViewArray<View>& x0,
00067 ViewArray<Card>& k0, bool cf)
00068 : Propagator(home), x(x0), y(home, x0),
00069 k(k0), vvg(NULL), card_fixed(cf){
00070
00071
00072 force(home);
00073 x.subscribe(home, this, PC_INT_DOM);
00074 k.subscribe(home, this, PC_INT_DOM);
00075 }
00076
00077 template <class View, class Card, bool isView>
00078 forceinline
00079 Dom<View, Card, isView>::Dom(Space* home, bool share,
00080 Dom<View, Card, isView>& p)
00081 : Propagator(home, share, p), vvg(NULL), card_fixed(p.card_fixed) {
00082 x.update(home, share, p.x);
00083 y.update(home, share, p.y);
00084 k.update(home, share, p.k);
00085 }
00086
00087 template <class View, class Card, bool isView>
00088 size_t
00089 Dom<View, Card, isView>::dispose(Space* home) {
00090 unforce(home);
00091 if (!home->failed()) {
00092 x.cancel(home,this, PC_INT_DOM);
00093 k.cancel(home,this, PC_INT_DOM);
00094 }
00095 delete vvg;
00096 (void) Propagator::dispose(home);
00097 return sizeof(*this);
00098 }
00099
00100 template <class View, class Card, bool isView>
00101 size_t
00102 Dom<View, Card, isView>::allocated(void) const {
00103 return (vvg == NULL) ? 0 : vvg->allocated();
00104 }
00105
00106 template <class View, class Card, bool isView>
00107 Actor*
00108 Dom<View, Card, isView>::copy(Space* home, bool share) {
00109 return new (home) Dom<View, Card, isView>(home, share, *this);
00110 }
00111
00112 template <class View, class Card, bool isView>
00113 PropCost
00114 Dom<View, Card, isView>::cost(ModEventDelta) const {
00115
00116 unsigned int n = x.size();
00117 unsigned int d = x[n - 1].size();
00118 for (int i = n; i--; ) {
00119 if (x[i].size() > d) {
00120 d = x[i].size();
00121 }
00122 }
00123
00124 PropCost pc;
00125 if (d < 6) {
00126 pc = PC_LINEAR_LO;
00127 } else {
00128 if (6 <= d && d < n/2) {
00129 pc = PC_LINEAR_HI;
00130 }
00131 else {
00132 if (n/2 <= d && d < n*n) {
00133 pc = PC_QUADRATIC_LO;
00134 } else {
00135 pc = PC_CUBIC_LO;
00136 }
00137 }
00138 }
00139 return cost_lo(x.size(), pc);
00140
00141 }
00142
00143 template <class View, class Card, bool isView>
00144 Support::Symbol
00145 Dom<View,Card,isView>::ati(void) {
00146 return Reflection::mangle<View,Card>("Gecode::Int::GCC::Dom",isView);
00147 }
00148
00149 template <class View, class Card, bool isView>
00150 Reflection::ActorSpec
00151 Dom<View,Card,isView>::spec(const Space* home,
00152 Reflection::VarMap& m) const {
00153 Reflection::ActorSpec s(ati());
00154 return s << y.spec(home, m) << k.spec(home, m) << card_fixed;
00155 }
00156
00157 template <class View, class Card, bool isView>
00158 void
00159 Dom<View,Card,isView>::post(Space* home, Reflection::VarMap& vars,
00160 const Reflection::ActorSpec& spec) {
00161 spec.checkArity(3);
00162 ViewArray<View> x(home, vars, spec[0]);
00163 ViewArray<Card> k(home, vars, spec[1]);
00164 bool card_fixed = spec[2]->toInt();
00165 (void) new (home) Dom(home, x, k, card_fixed);
00166 }
00167
00169 template <class View, class Card, bool isView>
00170 ExecStatus
00171 Dom<View, Card, isView>::propagate(Space* home, ModEventDelta) {
00172
00173 ExecStatus es = ES_NOFIX;
00174 bool card_mod = false;
00175
00176 GECODE_AUTOARRAY(int, count, k.size());
00177 for (int i = k.size(); i--; ) {
00178 count[i] = 0;
00179 }
00180 bool all_assigned = true;
00181
00182 int noa = 0;
00183 for (int i = y.size(); i--; ) {
00184 bool b = y[i].assigned();
00185 all_assigned &= b;
00186 if (b) {
00187 noa++;
00188 int idx = lookupValue(k, y[i].val());
00189 if (idx == -1) {
00190 return ES_FAILED;
00191 }
00192 count[idx]++;
00193 if (isView) {
00194 if (k[idx].max() == 0) {
00195 return ES_FAILED;
00196 }
00197 }
00198 }
00199 }
00200
00201 if (all_assigned) {
00202 for (int i = k.size(); i--; ) {
00203 int ci = count[i];
00204 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00205 return ES_FAILED;
00206 }
00207
00208 if (isView) {
00209 if (!k[i].assigned()) {
00210 ModEvent me = k[i].eq(home, ci);
00211 if (me_failed(me))
00212 return ES_FAILED;
00213 card_mod |= me_modified(me);
00214 }
00215 all_assigned &= k[i].assigned();
00216 }
00217 }
00218 if (all_assigned)
00219 return ES_SUBSUMED(this,home);
00220 }
00221
00222
00223 if (isView) {
00224 if (noa > 0) {
00225 int n = y.size();
00226 int ks = k.size();
00227
00228 for (int i = ks; i--; ) {
00229 if (!k[i].assigned()) {
00230 int ub = n - (noa - count[i]);
00231 int lb = count[i];
00232 ModEvent melq = k[i].lq(home, ub);
00233 if (me_failed(melq))
00234 return ES_FAILED;
00235 card_mod |= me_modified(melq);
00236
00237 ModEvent megq = k[i].gq(home, lb);
00238 if (me_failed(megq))
00239 return ES_FAILED;
00240 card_mod |= me_modified(megq);
00241 }
00242 }
00243 }
00244
00245 GECODE_ES_CHECK((prop_card<View, Card, true>(home, y, k, card_mod)));
00246
00247 int smin = 0;
00248 int smax = 0;
00249 if (!card_consistent<View, Card>(smin, smax, y, k)) {
00250 return ES_FAILED;
00251 }
00252 }
00253
00254 if (x.size() < 2) {
00255 assert(x.size() >= 0);
00256 if (x.size() == 0) {
00257 for (int j = k.size(); j--; ) {
00258 if (k[j].min() > k[j].counter() || k[j].max() < k[j].counter()) {
00259 return ES_FAILED;
00260 }
00261 }
00262 return ES_SUBSUMED(this,home);
00263 } else {
00264 if (x.size() == 1) {
00265 if (x[0].assigned()) {
00266 int v = x[0].val();
00267 int idx = lookupValue(k,v);
00268 if (idx == -1) {
00269 return ES_FAILED;
00270 }
00271 ModEvent me = k[idx].inc();
00272 if (me_failed(me))
00273 return ES_FAILED;
00274 card_mod |= me_modified(me);
00275 for (int j = k.size(); j--; )
00276 if (k[j].min() > k[j].counter() || k[j].max() < k[j].counter())
00277 return ES_FAILED;
00278 return ES_SUBSUMED(this,home);
00279 }
00280 }
00281 }
00282 }
00283
00284 assert(x.size() > 0);
00285
00286 bool mod = false;
00287 bool min_req_mod = false;
00288 int noe = 0;
00289 int smin = 0;
00290 int smax = 0;
00291 assert(noe >= 0);
00292 for (int i = x.size(); i--; ) {
00293 noe +=x[i].size();
00294 }
00295
00296 assert(noe > 0);
00297
00298 for (int i = k.size(); i--; ) {
00299 int ci = k[i].counter();
00300 if (ci > k[i].max() ) {
00301 return ES_FAILED;
00302 } else {
00303 smax += (k[i].max() - ci);
00304 if (ci < k[i].min()) {
00305 smin += (k[i].min() - ci);
00306 }
00307 }
00308 }
00309
00310 if (x.size() < smin) {
00311 return ES_FAILED;
00312 }
00313
00314 if (smax < x.size()) {
00315 return ES_FAILED;
00316 }
00317
00318
00319 if (vvg == NULL) {
00320 assert(noe > 0);
00321 assert(smin >= 0);
00322 assert(smax >= 0);
00323 vvg = new VarValGraph<View, Card, isView> (x, y, k, noe, smin, smax);
00324 min_req_mod = vvg->min_require(home);
00325 if (vvg->failed()) {
00326 return ES_FAILED;
00327 }
00328
00329 bool init_ubm = vvg->template maximum_matching<UBC>();
00330 if (!init_ubm) {
00331 return ES_FAILED;
00332 }
00333
00334 if (!card_fixed) {
00335 bool init_lbm = vvg->template maximum_matching<LBC>();
00336 if (!init_lbm) {
00337 return ES_FAILED;
00338 }
00339 }
00340 } else {
00341 if (!vvg->sync()) {
00342 return ES_FAILED;
00343 }
00344 }
00345
00346 bool filter_ubc = false;
00347 bool filter_lbc = false;
00348
00349 vvg->template free_alternating_paths<UBC>();
00350 vvg->template strongly_connected_components<UBC>();
00351
00352 filter_ubc = vvg->template narrow<UBC>(home);
00353 if (vvg->failed()) {
00354 return ES_FAILED;
00355 }
00356 if (!card_fixed) {
00357 if (isView) {
00358 if (!vvg->sync()) {
00359 return ES_FAILED;
00360 }
00361 }
00362 vvg->template free_alternating_paths<LBC>();
00363 vvg->template strongly_connected_components<LBC>();
00364
00365 filter_lbc = vvg->template narrow<LBC>(home);
00366 if (vvg->failed()) {
00367 return ES_FAILED;
00368 }
00369 }
00370
00371 bool card_assigned = true;
00372 if (isView) {
00373 es = prop_card<View, Card, true>(home, y, k, card_mod);
00374 if (es == ES_FAILED) {
00375 return ES_FAILED;
00376 }
00377
00378 for (int i = k.size(); i--; ) {
00379 card_assigned &= k[i].assigned();
00380 }
00381 }
00382
00383 if (card_assigned) {
00384 if (x.size() < 2) {
00385 assert(x.size() >= 0);
00386 if (x.size() == 0) {
00387 for (int j = k.size(); j--; ) {
00388 if (k[j].min() > k[j].counter() ||
00389 k[j].max() < k[j].counter()) {
00390 return ES_FAILED;
00391 }
00392 }
00393 return ES_SUBSUMED(this,home);
00394 } else {
00395 if (x.size() == 1) {
00396 if (x[0].assigned()) {
00397 int v = x[0].val();
00398 int idx = lookupValue(k,v);
00399 if (idx == -1) {
00400 return ES_FAILED;
00401 }
00402 ModEvent me = k[idx].inc();
00403 if (me_failed(me)) {
00404 return ES_FAILED;
00405 }
00406 card_mod |= me_modified(me);
00407
00408 for (int j = k.size(); j--; ) {
00409 if (k[j].min() > k[j].counter() ||
00410 k[j].max() < k[j].counter()) {
00411 return ES_FAILED;
00412 }
00413 }
00414 return ES_SUBSUMED(this,home);
00415 }
00416 }
00417 }
00418 }
00419 }
00420
00421 for (int i = k.size(); i--; ) {
00422 count[i] = 0;
00423 }
00424 all_assigned = true;
00425
00426 for (int i = y.size(); i--; ) {
00427 bool b = y[i].assigned();
00428 all_assigned &= b;
00429 if (b) {
00430 int idx = lookupValue(k,y[i].val());
00431 if (idx == -1) {
00432 return ES_FAILED;
00433 }
00434 count[idx]++;
00435 if (isView) {
00436 if (k[idx].max() == 0) {
00437 return ES_FAILED;
00438 }
00439 }
00440 }
00441 }
00442
00443 if (isView) {
00444 es = prop_card<View, Card, true>(home, y, k, card_mod);
00445 if (es == ES_FAILED) {
00446 return es;
00447 }
00448 }
00449
00450 if (all_assigned) {
00451 for (int i = k.size(); i--; ) {
00452 int ci = count[i];
00453 if (!(k[i].min() <= ci && ci <= k[i].max())) {
00454 return ES_FAILED;
00455 }
00456
00457 if (isView) {
00458 if (!k[i].assigned()) {
00459 ModEvent me = k[i].eq(home, ci);
00460 if (me_failed(me))
00461 return ES_FAILED;
00462 card_mod |= me_modified(me);
00463 }
00464 all_assigned &= k[i].assigned();
00465 }
00466 }
00467 if (all_assigned) {
00468 return ES_SUBSUMED(this,home);
00469 }
00470 }
00471
00472 if (isView) {
00473 int smax = 0;
00474 int smin = 0;
00475 for (int i = k.size(); i--; ) {
00476 smax += k[i].max();
00477 }
00478 int ysmax = y.size() - smax;
00479 int ysmin = y.size() - smin;
00480 smax = 0;
00481 smin = 0;
00482 bool card_ass = true;
00483 for (int i = k.size(); i--; ) {
00484 int lb = ysmax + k[i].max();
00485 int ub = ysmin + k[i].min();
00486 ModEvent me = k[i].gq(home, lb);
00487 if (me_failed(me))
00488 return ES_FAILED;
00489
00490 card_mod |= me_modified(me);
00491 smax += k[i].max();
00492
00493 me = k[i].lq(home, ub);
00494 if (me_failed(me))
00495 return ES_FAILED;
00496
00497 card_mod |= me_modified(me);
00498 card_ass &= k[i].assigned();
00499 }
00500 if (card_ass) {
00501 if (smax < y.size() || smax > y.size()) {
00502 return ES_FAILED;
00503 }
00504 }
00505 }
00506
00507 mod = (filter_ubc || filter_lbc || min_req_mod || card_mod);
00508
00509 return mod ? ES_NOFIX : ES_FIX;
00510
00511 }
00512
00513 template <class View, class Card, bool isView>
00514 inline ExecStatus
00515 Dom<View, Card, isView>::post(Space* home, ViewArray<View>& x0,
00516 ViewArray<Card>& k0){
00517 bool cardfix = true;
00518 for (int i = k0.size(); i--; ) {
00519 cardfix &= k0[i].assigned();
00520 }
00521
00522 (void) new (home) Dom<View, Card, isView>(home, x0, k0, cardfix);
00523 return ES_OK;
00524 }
00525
00526 }}}
00527
00528
00529
00530
00531