dom.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 00005 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * Guido Tack <tack@gecode.org> 00009 * 00010 * Copyright: 00011 * Patrick Pekczynski, 2004 00012 * Christian Schulte, 2009 00013 * Guido Tack, 2009 00014 * 00015 * Last modified: 00016 * $Date: 2010-05-11 10:57:01 +0200 (Tue, 11 May 2010) $ by $Author: tack $ 00017 * $Revision: 10935 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 * 00042 */ 00043 00044 namespace Gecode { namespace Int { namespace GCC { 00045 00046 /* 00047 * Analogously to "gcc/bnd.hpp" we split the algorithm 00048 * in two parts: 00049 * 1) the UBC (Upper Bound Constraint) stating that there are 00050 * at most k[i].max() occurences of the value v_i 00051 * 2) the LBC (Lower Bound Constraint) stating that there are 00052 * at least k[i].min() occurences of the value v_i 00053 * 00054 * The algorithm proceeds in 5 STEPS: 00055 * 00056 * STEP 1: 00057 * Build the bipartite value-graph G=(<X,D>,E), 00058 * with X = all variable nodes (each variable forms a node) 00059 * D = all value nodes (union over all domains of the variables) 00060 * and (x_i,v) is an edge in G iff value v is in the domain D_i of x_i 00061 * 00062 * STEP 2: Compute a matching in the value graph. 00063 * STEP 3: Compute all even alternating paths from unmatched nodes 00064 * STEP 4: Compute strongly connected components in the merged graph 00065 * STEP 5: Update the Domains according to the computed edges 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 // y is used for bounds propagation since prop_bnd needs all variables 00076 // values within the domain bounds 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 // total number of assigned views 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 // All views are assigned 00135 for (int i = k.size(); i--; ) { 00136 if ((k[i].min() > count[i]) || (count[i] > k[i].max())) 00137 return ES_FAILED; 00138 // the solution contains ci occurences of value k[i].card(); 00139 if (Card::propagate) 00140 GECODE_ME_CHECK(k[i].eq(home, count[i])); 00141 } 00142 return home.ES_SUBSUMED(*this); 00143 } 00144 00145 // before propagation performs inferences on cardinality variables: 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 card_assigned = k.assigned(); 00219 } 00220 00221 if (card_assigned) { 00222 if (x.size() == 0) { 00223 for (int j=k.size(); j--; ) 00224 if ((k[j].min() > k[j].counter()) || 00225 (k[j].max() < k[j].counter())) 00226 return ES_FAILED; 00227 return home.ES_SUBSUMED(*this); 00228 } else if ((x.size() == 1) && x[0].assigned()) { 00229 int idx; 00230 if (!lookupValue(k,x[0].val(),idx)) 00231 return ES_FAILED; 00232 GECODE_ME_CHECK(k[idx].inc()); 00233 00234 for (int j = k.size(); j--; ) 00235 if ((k[j].min() > k[j].counter()) || 00236 (k[j].max() < k[j].counter())) 00237 return ES_FAILED; 00238 return home.ES_SUBSUMED(*this); 00239 } 00240 } 00241 } 00242 00243 for (int i = k.size(); i--; ) 00244 count[i] = 0; 00245 00246 bool all_assigned = true; 00247 // total number of assigned views 00248 for (int i = y.size(); i--; ) 00249 if (y[i].assigned()) { 00250 int idx; 00251 if (!lookupValue(k,y[i].val(),idx)) 00252 return ES_FAILED; 00253 count[idx]++; 00254 if (Card::propagate && (k[idx].max() == 0)) 00255 return ES_FAILED; 00256 } else { 00257 all_assigned = false; 00258 } 00259 00260 if (Card::propagate) 00261 GECODE_ES_CHECK(prop_card<Card>(home, y, k)); 00262 00263 if (all_assigned) { 00264 for (int i = k.size(); i--; ) { 00265 if ((k[i].min() > count[i]) || (count[i] > k[i].max())) 00266 return ES_FAILED; 00267 // the solution contains count[i] occurences of value k[i].card(); 00268 if (Card::propagate) 00269 GECODE_ME_CHECK(k[i].eq(home,count[i])); 00270 } 00271 return home.ES_SUBSUMED(*this); 00272 } 00273 00274 if (Card::propagate) { 00275 int ysmax = y.size(); 00276 for (int i=k.size(); i--; ) 00277 ysmax -= k[i].max(); 00278 int smax = 0; 00279 bool card_ass = true; 00280 for (int i = k.size(); i--; ) { 00281 GECODE_ME_CHECK(k[i].gq(home, ysmax + k[i].max())); 00282 smax += k[i].max(); 00283 GECODE_ME_CHECK(k[i].lq(home, y.size() + k[i].min())); 00284 if (!k[i].assigned()) 00285 card_ass = false; 00286 } 00287 if (card_ass && (smax != y.size())) 00288 return ES_FAILED; 00289 } 00290 00291 return Card::propagate ? ES_NOFIX : ES_FIX; 00292 } 00293 00294 template<class Card> 00295 inline ExecStatus 00296 Dom<Card>::post(Home home, 00297 ViewArray<IntView>& x, ViewArray<Card>& k) { 00298 GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k))); 00299 00300 if (isDistinct<Card>(home, x, k)) 00301 return Distinct::Dom<IntView>::post(home,x); 00302 00303 bool cardfix = true; 00304 for (int i = k.size(); i--; ) 00305 if (!k[i].assigned()) { 00306 cardfix = false; break; 00307 } 00308 00309 (void) new (home) Dom<Card>(home,x,k,cardfix); 00310 return ES_OK; 00311 } 00312 00313 }}} 00314 00315 // STATISTICS: int-prop