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

sortedness.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-02 11:48:39 +0100 (Fri, 02 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2686 $
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 Sortedness {
00023 
00024 
00025   /* 
00026    * Summary of the propagation algorithm as implemented in the
00027    * propagate method below:
00028    *
00029    * STEP 1: Normalize the domains of the y variables
00030    * STEP 2: Sort the domains of the x variables according to their lower
00031    *         and upper endpoints
00032    * STEP 3: Compute the matchings phi and phiprime with 
00033    *         Glover's matching algorithm
00034    * STEP 4: Compute the strongly connected components in 
00035    *         the oriented intersection graph
00036    * STEP 5: Narrow the domains of the variables
00037    *
00038    */
00039 
00056   template<class View, class Tuple, bool Perm, bool shared>
00057   ExecStatus  
00058   bounds_propagation(Space* home, 
00059                      ViewArray<Tuple>& xz, 
00060                      ViewArray<View>& y, 
00061                      bool& repairpass, 
00062                      bool& nofix, 
00063                      bool& match_fixed){
00064 
00065     int n        = xz.size();
00066 
00067     GECODE_AUTOARRAY(int, tau,      n);
00068     GECODE_AUTOARRAY(int, phi,      n);
00069     GECODE_AUTOARRAY(int, phiprime, n);
00070     GECODE_AUTOARRAY(OfflineMinItem, sequence, n);
00071     GECODE_AUTOARRAY(int, vertices, n);
00072 
00073     if (match_fixed) {
00074       // sorting is determined
00075       // sigma and tau coincide
00076       for (int i = xz.size(); i--; ) {
00077         int pi = xz[i][1].val();
00078         tau[pi] = i;
00079       }
00080     } else {
00081       for (int i = n; i--; ) {
00082         tau[i] = i;
00083       }
00084     }
00085     
00086     bool yval    = true;
00087     bool ysorted = true;
00088     for (int i = n; i--; ) {
00089       yval    &= y[i].assigned();
00090       if (i) {
00091         ysorted &= (y[i].min() <= y[i - 1].min() &&
00092                     y[i].max() <= y[i - 1].max());
00093       }
00094     }
00095 
00096     if (Perm) {
00097       for (int i = n; i--; ) {
00098         if (xz[i][1].assigned()) {
00099 
00100           // if the permutation variable is determined
00101           
00102           int v = xz[i][1].val();
00103           if (xz[i][0].assigned()) {
00104             // channel equality from x to y
00105             if (shared && y[v].modified()) {
00106               return ES_NOFIX;
00107             }
00108             GECODE_ME_CHECK(y[v].eq(home, xz[i][0].val()));
00109           } else {
00110             if (y[v].assigned()) {
00111               // channel equality from y to x
00112               if (shared && xz[i][0].modified()) {
00113                 return ES_NOFIX;
00114               }
00115               GECODE_ME_CHECK(xz[i][0].eq(home, y[v].val()));
00116             } else {
00117               // constrain upper bound
00118               if (shared && xz[i][0].modified()) {
00119                 return ES_NOFIX;
00120               }
00121               ModEvent me = xz[i][0].lq(home, y[v].max());
00122               if (me_failed(me)) {
00123                 return ES_FAILED;
00124               }
00125               nofix |= (me_modified(me) && xz[i][0].max() != y[v].max());
00126 
00127               // constrain lower bound
00128               if (shared && xz[i][0].modified()) {
00129                 return ES_NOFIX;
00130               }
00131               
00132               me = xz[i][0].gq(home, y[v].min());
00133               if (me_failed(me)) {
00134                 return ES_FAILED;
00135               }
00136               nofix |= (me_modified(me) && xz[i][0].min() != y[v].min());
00137 
00138               // constrain the sorted variable
00139               // constrain upper bound
00140               if (shared && y[v].modified()) {
00141                 return ES_NOFIX;
00142               }
00143 
00144               me = y[v].lq(home, xz[i][0].max());
00145               if (me_failed(me)) {
00146                 return ES_FAILED;
00147               }
00148               nofix |= (me_modified(me) && y[v].max() != xz[i][0].max());
00149 
00150               // constrain lower bound
00151               if (shared && y[v].modified()) {
00152                 return ES_NOFIX;
00153               }
00154               
00155               me = y[v].gq(home, xz[i][0].min());
00156               if (me_failed(me)) {
00157                 return ES_FAILED;
00158               }
00159               nofix |= (me_modified(me) && y[v].min() != xz[i][0].min());
00160             }
00161           }
00162         } else {
00163           
00164           // if the permutation variable is undetermined
00165           int l = xz[i][1].min();
00166           int r = xz[i][1].max();
00167           if (xz[i][0].assigned()) {
00168             // if the x variable is determined
00169             int v = xz[i][0].val();
00170             
00171             while (y[l].max() < v) {
00172               ModEvent me = xz[i][1].gr(home, l);
00173               if (me_failed(me)) {
00174                 return ES_FAILED;
00175               }
00176               nofix  |= ( me_modified(me) && xz[i][1].min() != l + 1);
00177               l = xz[i][1].min();
00178             }
00179 
00180             while (y[r].min() > v) {
00181               ModEvent me = xz[i][1].le(home, r);
00182               if (me_failed(me)) {
00183                 return ES_FAILED;
00184               }
00185               nofix  |= ( me_modified(me) && xz[i][1].max() != r - 1);
00186               r = xz[i][1].max();
00187             }
00188           } else {
00189             // if the x variable is undetermined
00190             // upper bound
00191             if (shared && xz[i][0].modified()) {
00192               return ES_NOFIX;
00193             }
00194 
00195             ModEvent me = xz[i][0].lq(home, y[r].max());
00196             if (me_failed(me)) {
00197               return ES_FAILED;
00198             }
00199             nofix |= (me_modified(me) && xz[i][0].max() != y[r].max());
00200 
00201             // lower bound
00202             if (shared && xz[i][0].modified()) {
00203               return ES_NOFIX;
00204             }
00205             
00206             me = xz[i][0].gq(home, y[l].min());
00207             if (me_failed(me)) {
00208               return ES_FAILED;
00209             }
00210             nofix |= (me_modified(me) && xz[i][0].min() != y[l].min());
00211           }
00212         }
00213       }
00214     }
00215 
00216     // if bounds have changed we have to recreate sigma to restore
00217     // optimized dropping of variables
00218 
00219     if (!match_fixed) {
00220       sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00221     }
00222 
00223 
00224     bool subsumed   = true;
00225     bool array_subs = false;
00226     int  dropfst  = 0;
00227 
00228     if (!(check_subsumption<View, Tuple, Perm>
00229           (home, xz, y, subsumed, dropfst)) ||
00230         !(array_assigned<View, Tuple, Perm, shared>
00231           (home, xz, y, array_subs, match_fixed, nofix))) {
00232       return ES_FAILED;
00233     }
00234 
00235     if (shared && nofix) {
00236       return ES_NOFIX;
00237     }
00238 
00239     if (subsumed || array_subs) {
00240       return ES_SUBSUMED; 
00241     }
00242 
00243     /* 
00244      * STEP 1:
00245      *  normalization is implemented in "sortedness/order.icc"
00246      *    o  setting the lower bounds of the y_i domains (\lb E_i)
00247      *       to max(\lb E_{i-1},\lb E_i)
00248      *    o  setting the upper bounds of the y_i domains (\ub E_i) 
00249      *       to min(\ub E_i,\ub E_{i+1})
00250      */
00251 
00252     if (!normalize<View, Tuple, shared>(home, y, xz, nofix)) {
00253       return ES_FAILED;
00254     }
00255 
00256     if (shared && nofix) {
00257       return ES_NOFIX;
00258     }
00259 
00260     /*
00261      * STEP 2: creating tau 
00262      * Sort the domains of the x variables according 
00263      * to their lower bounds, where we use an 
00264      * intermediate array of integers for sorting
00265      */
00266     sort_tau<View, Tuple, Perm>(xz, tau);
00267 
00268     /* 
00269      * STEP 3:
00270      *  Compute the matchings \phi and \phi' between 
00271      *  the x and the y variables
00272      *  with Glover's matching algorithm.
00273      *        o  phi is computed with the glover function
00274      *        o  phiprime is computed with the revglover function
00275      *  glover and revglover are implemented in "sortedness/matching.icc"
00276      */
00277 
00278     if (!match_fixed) {
00279 
00280       if (!glover<View, Tuple, Perm>
00281           (home, xz, y, tau, phi, sequence, vertices)) {
00282         return ES_FAILED;
00283       }
00284     } else {
00285       for (int i = xz.size(); i--; ) {
00286         phi[i]      = xz[i][1].val();
00287         phiprime[i] = phi[i];
00288       }
00289     }
00290 
00291     if(!yval) {
00292       // phiprime is not needed to narrow the domains of the x-variables
00293       if (!match_fixed) {
00294         if (!revglover<View, Tuple, Perm>
00295             (home, xz, y, tau, phiprime, sequence, vertices)) {
00296           return ES_FAILED;
00297         }
00298       } 
00299       
00300       if (!narrow_domy<View, Tuple, Perm, shared>
00301           (home, xz, y, phi, phiprime, nofix)) {
00302         return ES_FAILED;
00303       }
00304 
00305       if (shared && nofix) {
00306         return ES_NOFIX;
00307       }
00308 
00309       if (nofix && !match_fixed) {
00310         // data structures (matching) destroyed by domains with holes
00311             
00312         for (int i = y.size(); i--; ) {
00313           phi[i] = 0;
00314           phiprime[i] = 0;
00315         }
00316         if (!glover<View, Tuple, Perm>
00317             (home, xz, y, tau, phi, sequence, vertices)) {
00318           return ES_FAILED;
00319         }
00320             
00321         if (!revglover<View, Tuple, Perm>
00322             (home, xz, y, tau, phiprime, sequence, vertices)) {
00323           return ES_FAILED;
00324         }
00325 
00326         if (!narrow_domy<View, Tuple, Perm, shared>
00327             (home, xz, y, phi, phiprime, nofix)) {
00328           return ES_FAILED;
00329         }
00330 
00331         if (shared && nofix) {
00332           return ES_NOFIX;
00333         }
00334 
00335       }
00336     }
00337 
00338     /* 
00339      * STEP 4:
00340      *  Compute the strongly connected components in 
00341      *  the oriented intersection graph
00342      *  the computation of the sccs is implemented in 
00343      *  "sortedness/narrowing.icc" in the function narrow_domx
00344      */
00345 
00346     GECODE_AUTOARRAY(int,          scclist, n);
00347     GECODE_AUTOARRAY(SccComponent, sinfo  , n);
00348     
00349     for(int i = n; i--; ) {
00350       sinfo[i].left       = i;
00351       sinfo[i].right      = i;
00352       sinfo[i].rightmost  = i;
00353       sinfo[i].leftmost   = i;
00354     }
00355 
00356     computesccs<View>(home, xz, y, phi, sinfo, scclist);
00357 
00358     /*
00359      * STEP 5:
00360      *  Narrow the domains of the variables
00361      *  Also implemented in "sortedness/narrowing.icc"
00362      *  in the functions narrow_domx and narrow_domy
00363      */
00364 
00365     if (!narrow_domx<View, Tuple, Perm, shared>
00366         (home, xz, y, tau, phi, scclist, sinfo, nofix)) {
00367       return ES_FAILED;
00368     }
00369 
00370     if (shared && nofix) {
00371       return ES_NOFIX;
00372     }
00373     
00374 
00375     if (Perm) {
00376       if (!perm_bc<View, Tuple, Perm, shared>
00377           (home, tau, xz, repairpass, nofix)) {
00378         return ES_FAILED;
00379       }
00380 
00381       if (shared && nofix) {
00382         return ES_NOFIX;
00383       }
00384       
00385     }
00386 
00387     return nofix ? ES_NOFIX : ES_FIX;
00388   } 
00389   
00390   template<class View, class Tuple, bool Perm, bool shared>
00391   Sortedness<View, Tuple, Perm, shared>::
00392   Sortedness(Space* home, bool share, Sortedness<View, Tuple, Perm, shared>& p):
00393     Propagator(home, share, p), 
00394     reachable(p.reachable) {
00395     xz.update(home, share, p.xz);
00396     y.update(home, share, p.y);
00397     w.update(home, share, p.w);
00398   }
00399 
00400   template<class View, class Tuple, bool Perm, bool shared>
00401   Sortedness<View, Tuple, Perm, shared>::
00402   Sortedness(Space* home, ViewArray<Tuple>& xz0, ViewArray<View>& y0):
00403     Propagator(home,true), xz(xz0), y(y0), w(home, y0), reachable(-1) {
00404     xz.subscribe(home, this, PC_INT_BND);
00405     y.subscribe(home, this, PC_INT_BND);
00406     
00407   }
00408 
00409   template<class View, class Tuple, bool Perm, bool shared>
00410   Sortedness<View, Tuple, Perm, shared>::~Sortedness(void) {
00411     xz.cancel(this, PC_INT_BND);
00412     y.cancel(this, PC_INT_BND);
00413   }
00414 
00415   template<class View, class Tuple, bool Perm, bool shared>
00416   Actor* Sortedness<View, Tuple, Perm, shared>::copy(Space* home, bool share) {
00417     return new (home) Sortedness<View, Tuple, Perm, shared>(home, share, *this);
00418   }
00419 
00420   template<class View, class Tuple, bool Perm, bool shared>
00421   PropCost Sortedness<View, Tuple, Perm, shared>::cost(void) const {
00422     return PC_LINEAR_LO;
00423   }
00424 
00425   template<class View, class Tuple, bool Perm, bool shared>
00426   ExecStatus
00427   Sortedness<View, Tuple, Perm, shared>::propagate(Space* home) {
00428 
00429     int  n           = xz.size();
00430     bool secondpass  = false; 
00431     bool nofix       = false;
00432     int  dropfst     = 0;
00433 
00434     bool subsumed    = false;
00435     bool array_subs  = false;
00436     bool match_fixed = false;
00437 
00438     // create sigma sorting
00439     sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00440 
00441     // normalization of x and y
00442     if (!normalize<View, Tuple, shared>(home, y, xz, nofix)) {
00443       return ES_FAILED;
00444     }
00445 
00446     if (shared && nofix) {
00447       return ES_NOFIX;
00448     }
00449     
00450     if (!array_assigned<View, Tuple, Perm, shared>
00451         (home, xz, y, array_subs, match_fixed, nofix)) {
00452       return ES_FAILED;
00453     }
00454 
00455     if (shared && nofix) {
00456       return ES_NOFIX;
00457     }
00458 
00459     if (array_subs) {
00460       return ES_SUBSUMED;
00461     }
00462 
00463     if (match_fixed) {
00464       sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00465     }
00466     
00467     // in this case check_subsumptions is guaranteed to find
00468     // the xs ordered by sigma
00469 
00470     if (!check_subsumption<View, Tuple, Perm>
00471         (home, xz, y, subsumed, dropfst)) {
00472       return ES_FAILED;
00473     }
00474 
00475     if (shared && nofix) {
00476       return ES_NOFIX;
00477     }
00478 
00479     if (subsumed) {
00480       return ES_SUBSUMED; 
00481     }     
00482 
00483     // If explicit permutation variables are used
00484 
00485     if (Perm) {
00486       // dropping possibly yields inconsistent indices on permvars
00487 
00488       if (dropfst) {
00489         reachable = w[dropfst - 1].max();
00490         bool unreachable = true;
00491         for (int i = xz.size(); unreachable && i-- ; ) {
00492           unreachable &= (reachable < xz[i][0].min());
00493         }
00494 
00495         if (unreachable) {
00496           xz.drop_fst(dropfst, this, PC_INT_BND);
00497           y.drop_fst (dropfst, this, PC_INT_BND);
00498         } else {
00499           dropfst = 0;
00500         }
00501       }
00502 
00503       n = xz.size();
00504 
00505       if (n < 2) {
00506         if (xz[0][0].max() < y[0].min() || y[0].max() < xz[0][0].min()) {
00507           return ES_FAILED;
00508         } else {
00509           Rel::EqBnd<View>::post(home, xz[0][0], y[0]);
00510 
00511           // in this case xz[0] is the rightmost problem variable
00512           if (shared && xz[0][1].modified()) {
00513             return ES_NOFIX;
00514           }
00515 
00516           GECODE_ME_CHECK(xz[0][1].eq(home, w.size() - 1));
00517 
00518           return ES_SUBSUMED;
00519         }
00520       }
00521 
00522       // check whether shifting the permutation variables 
00523       // is necessary after dropping x and y vars
00524 
00525       // highest reachable index
00526       int  valid = n - 1; 
00527       int  index = 0;     
00528       int  shift = 0;
00529 
00530       for (int i = n; i--; ){
00531         if (xz[i][1].max() > index) {
00532           index = xz[i][1].max();
00533         }
00534         if (index > valid) {
00535           shift = index - valid;
00536         }
00537       }
00538 
00539       if (shift) {
00540         
00541         ViewArray<ViewTuple<OffsetView,2> > oxz(home, n);
00542         ViewArray<OffsetView> oy(home, n);
00543 
00544         for (int i = n; i--; ) {
00545 
00546           GECODE_ME_CHECK(xz[i][1].gq(home, shift)); 
00547 
00548           oxz[i][1] = OffsetView(xz[i][1], -shift);
00549           oxz[i][0] = OffsetView(xz[i][0], 0);
00550           oy[i] = OffsetView(y[i], 0);
00551         }
00552 
00553         GECODE_ES_CHECK((bounds_propagation<OffsetView, 
00554                          ViewTuple<OffsetView,2>, Perm, shared >
00555                          (home, oxz, oy, secondpass, nofix, match_fixed)));
00556 
00557         if (secondpass) {
00558           GECODE_ES_CHECK((bounds_propagation<OffsetView, 
00559                            ViewTuple<OffsetView,2>, Perm, shared >
00560                            (home, oxz, oy, secondpass, nofix, match_fixed)));
00561         }
00562       } else {
00563         GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm, shared>
00564                          (home, xz, y, secondpass, nofix, match_fixed)));
00565 
00566         if (secondpass) {
00567           GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm, shared>
00568                            (home, xz, y, secondpass, nofix, match_fixed)));
00569         }
00570       }
00571     } else {
00572       // dropping has no consequences
00573 
00574       if (dropfst) {
00575         xz.drop_fst(dropfst, this, PC_INT_BND);
00576         y.drop_fst (dropfst, this, PC_INT_BND);
00577       }
00578 
00579       n = xz.size();
00580 
00581       if (n < 2) {
00582         if (xz[0][0].max() < y[0].min() || y[0].max() < xz[0][0].min()) {
00583           return ES_FAILED;
00584         } else {
00585           Rel::EqBnd<View>::post(home, xz[0][0], y[0]);
00586           return ES_SUBSUMED;
00587         }
00588       }
00589       GECODE_ES_CHECK((bounds_propagation<View, Tuple, Perm, shared>
00590                        (home, xz, y, secondpass, nofix, match_fixed)));
00591       // no second pass possible if there are no permvars
00592     }
00593 
00594     if (!normalize<View, Tuple, shared>(home, y, xz, nofix)) {
00595       return ES_FAILED;
00596     }
00597 
00598     subsumed   = true;
00599     array_subs = false;
00600 
00601     // creating sorting anew
00602     if (!match_fixed) {
00603       sort_sigma<View, Tuple, Perm>(xz, match_fixed);
00604     } 
00605 
00606     if (!array_assigned<View, Tuple, Perm, shared>
00607         (home, xz, y, array_subs, match_fixed, nofix)) {
00608       return ES_FAILED;
00609     }
00610 
00611     if (array_subs) {
00612       return ES_SUBSUMED;
00613     }
00614 
00615     if (!check_subsumption<View, Tuple, Perm>
00616         (home, xz, y, subsumed, dropfst)) {
00617       return ES_FAILED;
00618     }
00619 
00620     if (subsumed) {
00621       return ES_SUBSUMED;
00622     }
00623 
00624     return nofix ? ES_NOFIX : ES_FIX;
00625   }
00626 
00627   template<class View, class Tuple, bool Perm, bool shared>
00628   ExecStatus
00629   Sortedness<View, Tuple, Perm, shared>::
00630   post(Space* home, ViewArray<Tuple>& xz0, ViewArray<View>& y0) {
00631     int n = xz0.size();
00632     if (n < 2) {
00633       if ((xz0[0][0].max() < y0[0].min()) || (y0[0].max() < xz0[0][0].min())) {
00634         return ES_FAILED;
00635       } else {
00636         Rel::EqBnd<View>::post(home, xz0[0][0], y0[0]);
00637         if (Perm) {
00638           GECODE_ME_CHECK(xz0[0][1].eq(home, 0));
00639         }
00640       }
00641     } else { 
00642       new (home) Sortedness<View, Tuple, Perm, shared>(home, xz0, y0); 
00643     }
00644     return ES_OK;
00645   }
00646   
00647 }}}
00648 
00649 // STATISTICS: int-prop
00650 
00651   
00652