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 ExecStatus
00113 Dom<Card>::propagate(Space& home, const ModEventDelta&) {
00114 Region r(home);
00115
00116 int* count = r.alloc<int>(k.size());
00117 for (int i = k.size(); i--; )
00118 count[i] = 0;
00119
00120
00121 int noa = 0;
00122 for (int i = y.size(); i--; )
00123 if (y[i].assigned()) {
00124 noa++;
00125 int idx;
00126 if (!lookupValue(k,y[i].val(),idx))
00127 return ES_FAILED;
00128 count[idx]++;
00129 if (Card::propagate && (k[idx].max() == 0))
00130 return ES_FAILED;
00131 }
00132
00133 if (noa == y.size()) {
00134
00135 for (int i = k.size(); i--; ) {
00136 if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
00137 return ES_FAILED;
00138
00139 if (Card::propagate)
00140 GECODE_ME_CHECK(k[i].eq(home, count[i]));
00141 }
00142 return home.ES_SUBSUMED(*this);
00143 }
00144
00145
00146 if (Card::propagate) {
00147 if (noa > 0)
00148 for (int i = k.size(); i--; )
00149 if (!k[i].assigned()) {
00150 GECODE_ME_CHECK(k[i].lq(home, y.size() - (noa - count[i])));
00151 GECODE_ME_CHECK(k[i].gq(home, count[i]));
00152 }
00153
00154 GECODE_ES_CHECK(prop_card<Card>(home,y,k));
00155 if (!card_consistent<Card>(y,k))
00156 return ES_FAILED;
00157 }
00158
00159 if (x.size() == 0) {
00160 for (int j = k.size(); j--; )
00161 if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
00162 return ES_FAILED;
00163 return home.ES_SUBSUMED(*this);
00164 } else if ((x.size() == 1) && (x[0].assigned())) {
00165 int idx;
00166 if (!lookupValue(k,x[0].val(),idx))
00167 return ES_FAILED;
00168 GECODE_ME_CHECK(k[idx].inc());
00169 for (int j = k.size(); j--; )
00170 if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
00171 return ES_FAILED;
00172 return home.ES_SUBSUMED(*this);
00173 }
00174
00175 if (vvg == NULL) {
00176 int smin = 0;
00177 int smax = 0;
00178 for (int i=k.size(); i--; )
00179 if (k[i].counter() > k[i].max() ) {
00180 return ES_FAILED;
00181 } else {
00182 smax += (k[i].max() - k[i].counter());
00183 if (k[i].counter() < k[i].min())
00184 smin += (k[i].min() - k[i].counter());
00185 }
00186
00187 if ((x.size() < smin) || (smax < x.size()))
00188 return ES_FAILED;
00189
00190 vvg = new (home) VarValGraph<Card>(home, x, k, smin, smax);
00191 GECODE_ES_CHECK(vvg->min_require(home,x,k));
00192 GECODE_ES_CHECK(vvg->template maximum_matching<UBC>(home));
00193 if (!card_fixed)
00194 GECODE_ES_CHECK(vvg->template maximum_matching<LBC>(home));
00195 } else {
00196 GECODE_ES_CHECK(vvg->sync(home,x,k));
00197 }
00198
00199 vvg->template free_alternating_paths<UBC>(home);
00200 vvg->template strongly_connected_components<UBC>(home);
00201
00202 GECODE_ES_CHECK(vvg->template narrow<UBC>(home,x,k));
00203
00204 if (!card_fixed) {
00205 if (Card::propagate)
00206 GECODE_ES_CHECK(vvg->sync(home,x,k));
00207
00208 vvg->template free_alternating_paths<LBC>(home);
00209 vvg->template strongly_connected_components<LBC>(home);
00210
00211 GECODE_ES_CHECK(vvg->template narrow<LBC>(home,x,k));
00212 }
00213
00214 {
00215 bool card_assigned = true;
00216 if (Card::propagate) {
00217 GECODE_ES_CHECK(prop_card<Card>(home, y, k));
00218
00219 for (int i = k.size(); i--; )
00220 if (!k[i].assigned()) {
00221 card_assigned = false; break;
00222 }
00223 }
00224
00225 if (card_assigned) {
00226 if (x.size() == 0) {
00227 for (int j=k.size(); j--; )
00228 if ((k[j].min() > k[j].counter()) ||
00229 (k[j].max() < k[j].counter()))
00230 return ES_FAILED;
00231 return home.ES_SUBSUMED(*this);
00232 } else if ((x.size() == 1) && x[0].assigned()) {
00233 int idx;
00234 if (!lookupValue(k,x[0].val(),idx))
00235 return ES_FAILED;
00236 GECODE_ME_CHECK(k[idx].inc());
00237
00238 for (int j = k.size(); j--; )
00239 if ((k[j].min() > k[j].counter()) ||
00240 (k[j].max() < k[j].counter()))
00241 return ES_FAILED;
00242 return home.ES_SUBSUMED(*this);
00243 }
00244 }
00245 }
00246
00247 for (int i = k.size(); i--; )
00248 count[i] = 0;
00249
00250 bool all_assigned = true;
00251
00252 for (int i = y.size(); i--; )
00253 if (y[i].assigned()) {
00254 int idx;
00255 if (!lookupValue(k,y[i].val(),idx))
00256 return ES_FAILED;
00257 count[idx]++;
00258 if (Card::propagate && (k[idx].max() == 0))
00259 return ES_FAILED;
00260 } else {
00261 all_assigned = false;
00262 }
00263
00264 if (Card::propagate)
00265 GECODE_ES_CHECK(prop_card<Card>(home, y, k));
00266
00267 if (all_assigned) {
00268 for (int i = k.size(); i--; ) {
00269 if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
00270 return ES_FAILED;
00271
00272 if (Card::propagate)
00273 GECODE_ME_CHECK(k[i].eq(home,count[i]));
00274 }
00275 return home.ES_SUBSUMED(*this);
00276 }
00277
00278 if (Card::propagate) {
00279 int ysmax = y.size();
00280 for (int i=k.size(); i--; )
00281 ysmax -= k[i].max();
00282 int smax = 0;
00283 bool card_ass = true;
00284 for (int i = k.size(); i--; ) {
00285 GECODE_ME_CHECK(k[i].gq(home, ysmax + k[i].max()));
00286 smax += k[i].max();
00287 GECODE_ME_CHECK(k[i].lq(home, y.size() + k[i].min()));
00288 if (!k[i].assigned())
00289 card_ass = false;
00290 }
00291 if (card_ass && (smax != y.size()))
00292 return ES_FAILED;
00293 }
00294
00295 return Card::propagate ? ES_NOFIX : ES_FIX;
00296 }
00297
00298 template<class Card>
00299 inline ExecStatus
00300 Dom<Card>::post(Home home,
00301 ViewArray<IntView>& x, ViewArray<Card>& k) {
00302 GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
00303
00304 if (isDistinct<Card>(home, x, k))
00305 return Distinct::Dom<IntView>::post(home,x);
00306
00307 bool cardfix = true;
00308 for (int i = k.size(); i--; )
00309 if (!k[i].assigned()) {
00310 cardfix = false; break;
00311 }
00312
00313 (void) new (home) Dom<Card>(home,x,k,cardfix);
00314 return ES_OK;
00315 }
00316
00317 }}}
00318
00319