Generated on Fri Oct 19 11:25:02 2018 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 namespace Gecode { namespace Int { namespace GCC {
00041 
00042   /*
00043    * Analogously to "gcc/bnd.hpp" we split the algorithm
00044    * in two parts:
00045    *   1) the UBC (Upper Bound Constraint) stating that there are
00046    *      at most k[i].max() occurences of the value v_i
00047    *   2) the LBC (Lower Bound Constraint) stating that there are
00048    *      at least k[i].min() occurences of the value v_i
00049    *
00050    * The algorithm proceeds in 5 STEPS:
00051    *
00052    * STEP 1:
00053    *    Build the bipartite value-graph G=(<X,D>,E),
00054    *    with X = all variable nodes (each variable forms a node)
00055    *         D = all value nodes (union over all domains of the variables)
00056    *    and (x_i,v) is an edge in G iff value v is in the domain D_i of x_i
00057    *
00058    * STEP 2:   Compute a matching in the value graph.
00059    * STEP 3:   Compute all even alternating paths from unmatched  nodes
00060    * STEP 4:   Compute strongly connected components in the merged graph
00061    * STEP 5:   Update the Domains according to the computed edges
00062    *
00063    */
00064 
00065   template<class Card>
00066   inline
00067   Dom<Card>::Dom(Home home, ViewArray<IntView>& x0,
00068                  ViewArray<Card>& k0, bool cf)
00069     : Propagator(home), x(x0),  y(home, x0),
00070       k(k0), vvg(NULL), card_fixed(cf){
00071     // y is used for bounds propagation since prop_bnd needs all variables
00072     // values within the domain bounds
00073     x.subscribe(home, *this, PC_INT_DOM);
00074     k.subscribe(home, *this, PC_INT_DOM);
00075   }
00076 
00077   template<class Card>
00078   forceinline
00079   Dom<Card>::Dom(Space& home, Dom<Card>& p)
00080     : Propagator(home, p), vvg(NULL), card_fixed(p.card_fixed) {
00081     x.update(home, p.x);
00082     y.update(home, p.y);
00083     k.update(home, p.k);
00084   }
00085 
00086   template<class Card>
00087   forceinline size_t
00088   Dom<Card>::dispose(Space& home) {
00089     x.cancel(home,*this, PC_INT_DOM);
00090     k.cancel(home,*this, PC_INT_DOM);
00091     (void) Propagator::dispose(home);
00092     return sizeof(*this);
00093   }
00094 
00095   template<class Card>
00096   Actor*
00097   Dom<Card>::copy(Space& home) {
00098     return new (home) Dom<Card>(home, *this);
00099   }
00100 
00101   template<class Card>
00102   PropCost
00103   Dom<Card>::cost(const Space&, const ModEventDelta&) const {
00104     return PropCost::cubic(PropCost::LO, x.size());
00105   }
00106 
00107   template<class Card>
00108   void
00109   Dom<Card>::reschedule(Space& home) {
00110     x.reschedule(home, *this, PC_INT_DOM);
00111     k.reschedule(home, *this, PC_INT_DOM);
00112   }
00113 
00114   template<class Card>
00115   ExecStatus
00116   Dom<Card>::propagate(Space& home, const ModEventDelta&) {
00117     Region r;
00118 
00119     int* count = r.alloc<int>(k.size());
00120     for (int i = k.size(); i--; )
00121       count[i] = 0;
00122 
00123     // total number of assigned views
00124     int noa = 0;
00125     for (int i = y.size(); i--; )
00126       if (y[i].assigned()) {
00127         noa++;
00128         int idx;
00129         if (!lookupValue(k,y[i].val(),idx))
00130           return ES_FAILED;
00131         count[idx]++;
00132         if (Card::propagate && (k[idx].max() == 0))
00133           return ES_FAILED;
00134       }
00135 
00136     if (noa == y.size()) {
00137       // All views are assigned
00138       for (int i = k.size(); i--; ) {
00139         if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
00140           return ES_FAILED;
00141         // the solution contains ci occurences of value k[i].card();
00142         if (Card::propagate)
00143           GECODE_ME_CHECK(k[i].eq(home, count[i]));
00144       }
00145       return home.ES_SUBSUMED(*this);
00146     }
00147 
00148     // before propagation performs inferences on cardinality variables:
00149     if (Card::propagate) {
00150       if (noa > 0)
00151         for (int i = k.size(); i--; )
00152           if (!k[i].assigned()) {
00153             GECODE_ME_CHECK(k[i].lq(home, y.size() - (noa - count[i])));
00154             GECODE_ME_CHECK(k[i].gq(home, count[i]));
00155           }
00156 
00157       GECODE_ES_CHECK(prop_card<Card>(home,y,k));
00158       if (!card_consistent<Card>(y,k))
00159         return ES_FAILED;
00160     }
00161 
00162     if (x.size() == 0) {
00163       for (int j = k.size(); j--; )
00164         if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
00165           return ES_FAILED;
00166       return home.ES_SUBSUMED(*this);
00167     } else if ((x.size() == 1) && (x[0].assigned())) {
00168       int idx;
00169       if (!lookupValue(k,x[0].val(),idx))
00170         return ES_FAILED;
00171       GECODE_ME_CHECK(k[idx].inc());
00172       for (int j = k.size(); j--; )
00173         if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
00174           return ES_FAILED;
00175       return home.ES_SUBSUMED(*this);
00176     }
00177 
00178     if (vvg == NULL) {
00179       int smin = 0;
00180       int smax = 0;
00181       for (int i=k.size(); i--; )
00182         if (k[i].counter() > k[i].max() ) {
00183           return ES_FAILED;
00184         } else {
00185           smax += (k[i].max() - k[i].counter());
00186           if (k[i].counter() < k[i].min())
00187             smin += (k[i].min() - k[i].counter());
00188         }
00189 
00190       if ((x.size() < smin) || (smax < x.size()))
00191         return ES_FAILED;
00192 
00193       vvg = new (home) VarValGraph<Card>(home, x, k, smin, smax);
00194       GECODE_ES_CHECK(vvg->min_require(home,x,k));
00195       GECODE_ES_CHECK(vvg->template maximum_matching<UBC>());
00196       if (!card_fixed)
00197         GECODE_ES_CHECK(vvg->template maximum_matching<LBC>());
00198     } else {
00199       GECODE_ES_CHECK(vvg->sync(x,k));
00200     }
00201 
00202     vvg->template free_alternating_paths<UBC>();
00203     vvg->template strongly_connected_components<UBC>();
00204 
00205     GECODE_ES_CHECK(vvg->template narrow<UBC>(home,x,k));
00206 
00207     if (!card_fixed) {
00208       if (Card::propagate)
00209         GECODE_ES_CHECK(vvg->sync(x,k));
00210 
00211       vvg->template free_alternating_paths<LBC>();
00212       vvg->template strongly_connected_components<LBC>();
00213 
00214       GECODE_ES_CHECK(vvg->template narrow<LBC>(home,x,k));
00215     }
00216 
00217     {
00218       bool card_assigned = true;
00219       if (Card::propagate) {
00220         GECODE_ES_CHECK(prop_card<Card>(home, y, k));
00221         card_assigned = k.assigned();
00222       }
00223 
00224       if (card_assigned) {
00225         if (x.size() == 0) {
00226           for (int j=k.size(); j--; )
00227             if ((k[j].min() > k[j].counter()) ||
00228                 (k[j].max() < k[j].counter()))
00229               return ES_FAILED;
00230           return home.ES_SUBSUMED(*this);
00231         } else if ((x.size() == 1) && x[0].assigned()) {
00232           int idx;
00233           if (!lookupValue(k,x[0].val(),idx))
00234             return ES_FAILED;
00235           GECODE_ME_CHECK(k[idx].inc());
00236 
00237           for (int j = k.size(); j--; )
00238             if ((k[j].min() > k[j].counter()) ||
00239                 (k[j].max() < k[j].counter()))
00240               return ES_FAILED;
00241           return home.ES_SUBSUMED(*this);
00242         }
00243       }
00244     }
00245 
00246     for (int i = k.size(); i--; )
00247       count[i] = 0;
00248 
00249     bool all_assigned = true;
00250     // total number of assigned views
00251     for (int i = y.size(); i--; )
00252       if (y[i].assigned()) {
00253         int idx;
00254         if (!lookupValue(k,y[i].val(),idx))
00255           return ES_FAILED;
00256         count[idx]++;
00257         if (Card::propagate && (k[idx].max() == 0))
00258           return ES_FAILED;
00259       } else {
00260         all_assigned = false;
00261       }
00262 
00263     if (Card::propagate)
00264       GECODE_ES_CHECK(prop_card<Card>(home, y, k));
00265 
00266     if (all_assigned) {
00267       for (int i = k.size(); i--; ) {
00268         if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
00269           return ES_FAILED;
00270         // the solution contains count[i] occurences of value k[i].card();
00271         if (Card::propagate)
00272           GECODE_ME_CHECK(k[i].eq(home,count[i]));
00273       }
00274       return home.ES_SUBSUMED(*this);
00275     }
00276 
00277     if (Card::propagate) {
00278       int ysmax = y.size();
00279       for (int i=k.size(); i--; )
00280         ysmax -= k[i].max();
00281       int smax = 0;
00282       bool card_ass = true;
00283       for (int i = k.size(); i--; ) {
00284         GECODE_ME_CHECK(k[i].gq(home, ysmax + k[i].max()));
00285         smax += k[i].max();
00286         GECODE_ME_CHECK(k[i].lq(home, y.size() + k[i].min()));
00287         if (!k[i].assigned())
00288           card_ass = false;
00289       }
00290       if (card_ass && (smax != y.size()))
00291         return ES_FAILED;
00292     }
00293 
00294     return Card::propagate ? ES_NOFIX : ES_FIX;
00295   }
00296 
00297   template<class Card>
00298   inline ExecStatus
00299   Dom<Card>::post(Home home,
00300                   ViewArray<IntView>& x, ViewArray<Card>& k) {
00301     GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
00302 
00303     if (isDistinct<Card>(x,k))
00304       return Distinct::Dom<IntView>::post(home,x);
00305 
00306     bool cardfix = true;
00307     for (int i = k.size(); i--; )
00308       if (!k[i].assigned()) {
00309         cardfix = false; break;
00310       }
00311 
00312     (void) new (home) Dom<Card>(home,x,k,cardfix);
00313     return ES_OK;
00314   }
00315 
00316 }}}
00317 
00318 // STATISTICS: int-prop