Generated on Wed Jan 4 17:49:09 2006 for Gecode by doxygen 1.4.6

dom.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-12-06 07:46:40 +0100 (Tue, 06 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2696 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode { namespace Int { namespace GCC {
00023 
00024   /*
00025    * Analogously to "gcc/bnd.icc" we split the algorithm
00026    * in two parts:
00027    *   1) the UBC (Upper Bound Constraint) stating that there are
00028    *      at most k[i].max() occurences of the value v_i
00029    *   2) the LBC (Lower Bound Constraint) stating that there are
00030    *      at least k[i].min() occurences of the value v_i
00031    *
00032    * The algorithm proceeds in 5 STEPS:
00033    *
00034    * STEP 1:
00035    *    Build the bipartite value-graph G=(<X,D>,E),
00036    *    with X = all variable nodes (each variable forms a node)
00037    *         D = all value nodes (union over all domains of the variables)
00038    *    and (x_i,v) is an edge in G iff value v is in the domain D_i of x_i
00039    *
00040    * STEP 2:   Compute a matching in the value graph.
00041    * STEP 3:   Compute all even alternating paths from unmatched  nodes
00042    * STEP 4:   Compute strongly connected components in the merged graph
00043    * STEP 5:   Update the Domains according to the computed edges
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     // y is used for bounds propagation since prop_bnd needs all variables
00053     // l is used for bounds propagation since prop_bnd considers only
00054     // values within the domain bounds
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      * The domain consistent version of the Global Cardinality constraint
00104      * has a theoretical complexity of
00105      *   O(n * d) with
00106      *   n = number of variables
00107      *   d = the cardinality of the largest domain
00108      *       or as a larger bound the cardinality of the union of all domains
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     // total number of assigned views
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         // the solution contains ci occurences of value k[i].card();
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     // before propagation performs inferences on cardinality variables:
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     // total number of assigned views
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         // the solution contains ci occurences of value k[i].card();
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 // STATISTICS: int-prop
00445