gecode » int » gcc
dom.hpp

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: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00017  *     $Revision: 9878 $
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   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 ES_SUBSUMED(*this,home);
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 ES_SUBSUMED(*this,home);
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 ES_SUBSUMED(*this,home);
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 ES_SUBSUMED(*this,home);
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 ES_SUBSUMED(*this,home);
00243         }
00244       }
00245     }
00246 
00247     for (int i = k.size(); i--; )
00248       count[i] = 0;
00249 
00250     bool all_assigned = true;
00251     // total number of assigned views
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         // the solution contains count[i] occurences of value k[i].card();
00272         if (Card::propagate)
00273           GECODE_ME_CHECK(k[i].eq(home,count[i]));
00274       }
00275       return ES_SUBSUMED(*this,home);
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 // STATISTICS: int-prop