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
00040
00041
00042
00043
00044 namespace Gecode { namespace Int { namespace GCC {
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069 template<class Card>
00070 inline
00071 Dom<Card>::Dom(Home home, ViewArray<IntView>& x0,
00072 ViewArray<Card>& k0, bool cf)
00073 : Propagator(home), x(x0), y(home, x0),
00074 k(k0), vvg(NULL), card_fixed(cf){
00075
00076
00077 x.subscribe(home, *this, PC_INT_DOM);
00078 k.subscribe(home, *this, PC_INT_DOM);
00079 }
00080
00081 template<class Card>
00082 forceinline
00083 Dom<Card>::Dom(Space& home, bool share, Dom<Card>& p)
00084 : Propagator(home, share, p), vvg(NULL), card_fixed(p.card_fixed) {
00085 x.update(home, share, p.x);
00086 y.update(home, share, p.y);
00087 k.update(home, share, p.k);
00088 }
00089
00090 template<class Card>
00091 forceinline size_t
00092 Dom<Card>::dispose(Space& home) {
00093 x.cancel(home,*this, PC_INT_DOM);
00094 k.cancel(home,*this, PC_INT_DOM);
00095 (void) Propagator::dispose(home);
00096 return sizeof(*this);
00097 }
00098
00099 template<class Card>
00100 Actor*
00101 Dom<Card>::copy(Space& home, bool share) {
00102 return new (home) Dom<Card>(home, share, *this);
00103 }
00104
00105 template<class Card>
00106 PropCost
00107 Dom<Card>::cost(const Space&, const ModEventDelta&) const {
00108 return PropCost::cubic(PropCost::LO, x.size());
00109 }
00110
00111 template<class Card>
00112 void
00113 Dom<Card>::reschedule(Space& home) {
00114 x.reschedule(home, *this, PC_INT_DOM);
00115 k.reschedule(home, *this, PC_INT_DOM);
00116 }
00117
00118 template<class Card>
00119 ExecStatus
00120 Dom<Card>::propagate(Space& home, const ModEventDelta&) {
00121 Region r(home);
00122
00123 int* count = r.alloc<int>(k.size());
00124 for (int i = k.size(); i--; )
00125 count[i] = 0;
00126
00127
00128 int noa = 0;
00129 for (int i = y.size(); i--; )
00130 if (y[i].assigned()) {
00131 noa++;
00132 int idx;
00133 if (!lookupValue(k,y[i].val(),idx))
00134 return ES_FAILED;
00135 count[idx]++;
00136 if (Card::propagate && (k[idx].max() == 0))
00137 return ES_FAILED;
00138 }
00139
00140 if (noa == y.size()) {
00141
00142 for (int i = k.size(); i--; ) {
00143 if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
00144 return ES_FAILED;
00145
00146 if (Card::propagate)
00147 GECODE_ME_CHECK(k[i].eq(home, count[i]));
00148 }
00149 return home.ES_SUBSUMED(*this);
00150 }
00151
00152
00153 if (Card::propagate) {
00154 if (noa > 0)
00155 for (int i = k.size(); i--; )
00156 if (!k[i].assigned()) {
00157 GECODE_ME_CHECK(k[i].lq(home, y.size() - (noa - count[i])));
00158 GECODE_ME_CHECK(k[i].gq(home, count[i]));
00159 }
00160
00161 GECODE_ES_CHECK(prop_card<Card>(home,y,k));
00162 if (!card_consistent<Card>(y,k))
00163 return ES_FAILED;
00164 }
00165
00166 if (x.size() == 0) {
00167 for (int j = k.size(); j--; )
00168 if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
00169 return ES_FAILED;
00170 return home.ES_SUBSUMED(*this);
00171 } else if ((x.size() == 1) && (x[0].assigned())) {
00172 int idx;
00173 if (!lookupValue(k,x[0].val(),idx))
00174 return ES_FAILED;
00175 GECODE_ME_CHECK(k[idx].inc());
00176 for (int j = k.size(); j--; )
00177 if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
00178 return ES_FAILED;
00179 return home.ES_SUBSUMED(*this);
00180 }
00181
00182 if (vvg == NULL) {
00183 int smin = 0;
00184 int smax = 0;
00185 for (int i=k.size(); i--; )
00186 if (k[i].counter() > k[i].max() ) {
00187 return ES_FAILED;
00188 } else {
00189 smax += (k[i].max() - k[i].counter());
00190 if (k[i].counter() < k[i].min())
00191 smin += (k[i].min() - k[i].counter());
00192 }
00193
00194 if ((x.size() < smin) || (smax < x.size()))
00195 return ES_FAILED;
00196
00197 vvg = new (home) VarValGraph<Card>(home, x, k, smin, smax);
00198 GECODE_ES_CHECK(vvg->min_require(home,x,k));
00199 GECODE_ES_CHECK(vvg->template maximum_matching<UBC>(home));
00200 if (!card_fixed)
00201 GECODE_ES_CHECK(vvg->template maximum_matching<LBC>(home));
00202 } else {
00203 GECODE_ES_CHECK(vvg->sync(home,x,k));
00204 }
00205
00206 vvg->template free_alternating_paths<UBC>(home);
00207 vvg->template strongly_connected_components<UBC>(home);
00208
00209 GECODE_ES_CHECK(vvg->template narrow<UBC>(home,x,k));
00210
00211 if (!card_fixed) {
00212 if (Card::propagate)
00213 GECODE_ES_CHECK(vvg->sync(home,x,k));
00214
00215 vvg->template free_alternating_paths<LBC>(home);
00216 vvg->template strongly_connected_components<LBC>(home);
00217
00218 GECODE_ES_CHECK(vvg->template narrow<LBC>(home,x,k));
00219 }
00220
00221 {
00222 bool card_assigned = true;
00223 if (Card::propagate) {
00224 GECODE_ES_CHECK(prop_card<Card>(home, y, k));
00225 card_assigned = k.assigned();
00226 }
00227
00228 if (card_assigned) {
00229 if (x.size() == 0) {
00230 for (int j=k.size(); j--; )
00231 if ((k[j].min() > k[j].counter()) ||
00232 (k[j].max() < k[j].counter()))
00233 return ES_FAILED;
00234 return home.ES_SUBSUMED(*this);
00235 } else if ((x.size() == 1) && x[0].assigned()) {
00236 int idx;
00237 if (!lookupValue(k,x[0].val(),idx))
00238 return ES_FAILED;
00239 GECODE_ME_CHECK(k[idx].inc());
00240
00241 for (int j = k.size(); j--; )
00242 if ((k[j].min() > k[j].counter()) ||
00243 (k[j].max() < k[j].counter()))
00244 return ES_FAILED;
00245 return home.ES_SUBSUMED(*this);
00246 }
00247 }
00248 }
00249
00250 for (int i = k.size(); i--; )
00251 count[i] = 0;
00252
00253 bool all_assigned = true;
00254
00255 for (int i = y.size(); i--; )
00256 if (y[i].assigned()) {
00257 int idx;
00258 if (!lookupValue(k,y[i].val(),idx))
00259 return ES_FAILED;
00260 count[idx]++;
00261 if (Card::propagate && (k[idx].max() == 0))
00262 return ES_FAILED;
00263 } else {
00264 all_assigned = false;
00265 }
00266
00267 if (Card::propagate)
00268 GECODE_ES_CHECK(prop_card<Card>(home, y, k));
00269
00270 if (all_assigned) {
00271 for (int i = k.size(); i--; ) {
00272 if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
00273 return ES_FAILED;
00274
00275 if (Card::propagate)
00276 GECODE_ME_CHECK(k[i].eq(home,count[i]));
00277 }
00278 return home.ES_SUBSUMED(*this);
00279 }
00280
00281 if (Card::propagate) {
00282 int ysmax = y.size();
00283 for (int i=k.size(); i--; )
00284 ysmax -= k[i].max();
00285 int smax = 0;
00286 bool card_ass = true;
00287 for (int i = k.size(); i--; ) {
00288 GECODE_ME_CHECK(k[i].gq(home, ysmax + k[i].max()));
00289 smax += k[i].max();
00290 GECODE_ME_CHECK(k[i].lq(home, y.size() + k[i].min()));
00291 if (!k[i].assigned())
00292 card_ass = false;
00293 }
00294 if (card_ass && (smax != y.size()))
00295 return ES_FAILED;
00296 }
00297
00298 return Card::propagate ? ES_NOFIX : ES_FIX;
00299 }
00300
00301 template<class Card>
00302 inline ExecStatus
00303 Dom<Card>::post(Home home,
00304 ViewArray<IntView>& x, ViewArray<Card>& k) {
00305 GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
00306
00307 if (isDistinct<Card>(home, x, k))
00308 return Distinct::Dom<IntView>::post(home,x);
00309
00310 bool cardfix = true;
00311 for (int i = k.size(); i--; )
00312 if (!k[i].assigned()) {
00313 cardfix = false; break;
00314 }
00315
00316 (void) new (home) Dom<Card>(home,x,k,cardfix);
00317 return ES_OK;
00318 }
00319
00320 }}}
00321
00322