Generated on Tue Apr 18 10:22:09 2017 for Gecode by doxygen 1.6.3

nogoods.hh

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2013
00008  *
00009  *  Last modified:
00010  *     $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
00011  *     $Revision: 15137 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #ifndef __GECODE_SEARCH_META_NO_GOODS_HH__
00039 #define __GECODE_SEARCH_META_NO_GOODS_HH__
00040 
00041 #include <gecode/search.hh>
00042 
00043 namespace Gecode { namespace Search { namespace Meta {
00044 
00046   class GECODE_VTABLE_EXPORT NoNGL : public NGL {
00047   public:
00049     NoNGL(void);
00051     NoNGL(Space& home);
00053     NoNGL(Space& home, bool share, NoNGL& ngl);
00055     virtual void subscribe(Space& home, Propagator& p);
00057     virtual void reschedule(Space& home, Propagator& p);
00059     virtual void cancel(Space& home, Propagator& p);
00061     virtual NGL::Status status(const Space& home) const;
00063     virtual ExecStatus prune(Space& home);
00065     virtual NGL* copy(Space& home, bool share);
00066   };
00067 
00069   class GECODE_SEARCH_EXPORT NoGoodsProp : public Propagator {
00070   protected:
00072     NGL* root;
00074     unsigned int n;
00076     NoGoodsProp(Space& home, NGL* root);
00078     NoGoodsProp(Space& home, bool shared, NoGoodsProp& p);
00079   public:
00081     virtual Actor* copy(Space& home, bool share);
00083     virtual PropCost cost(const Space& home, const ModEventDelta& med) const;
00085     virtual void reschedule(Space& home);
00087     virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00089     template<class Path>
00090     static ExecStatus post(Space& home, const Path& p);
00092     virtual size_t dispose(Space& home);
00093   };
00094 
00095   forceinline
00096   NoNGL::NoNGL(void) {}
00097 
00098   forceinline
00099   NoNGL::NoNGL(Space& home)
00100     : NGL(home) {}
00101 
00102   forceinline
00103   NoNGL::NoNGL(Space& home, bool share, NoNGL& ngl)
00104     : NGL(home,share,ngl) {}
00105 
00106 
00107 
00108   forceinline
00109   NoGoodsProp::NoGoodsProp(Space& home, NGL* root0)
00110     : Propagator(Home(home)), root(root0), n(0U) {
00111     // Create subscriptions
00112     root->subscribe(home,*this); n++;
00113     bool notice = root->notice();
00114     NGL* l = root->next();
00115     while ((l != NULL) && l->leaf()) {
00116       l->subscribe(home,*this); n++;
00117       notice = notice || l->notice();
00118       l = l->next();
00119     }
00120     if (l != NULL) {
00121       l->subscribe(home,*this); n++;
00122     }
00123     while (!notice && (l != NULL)) {
00124       notice = notice || l->notice();
00125       l = l->next();
00126     }
00127     if (notice)
00128       home.notice(*this,AP_DISPOSE);
00129   }
00130 
00131   forceinline
00132   NoGoodsProp::NoGoodsProp(Space& home, bool shared, NoGoodsProp& p)
00133     : Propagator(home,shared,p), n(p.n) {
00134     assert(p.root != NULL);
00135     NoNGL s;
00136     NGL* c = &s;
00137     for (NGL* pc = p.root; pc != NULL; pc = pc->next()) {
00138       NGL* n = pc->copy(home,shared);
00139       n->leaf(pc->leaf());
00140       c->next(n); c=n;
00141     }
00142     root = s.next();
00143   }
00144 
00145 
00146 
00147   template<class Path>
00148   forceinline ExecStatus
00149   NoGoodsProp::post(Space& home, const Path& p) {
00150     int s = 0;
00151     int n = std::min(p.ds.entries(),static_cast<int>(p.ngdl()));
00152 
00153     unsigned long int n_nogood = 0;
00154 
00155     // Eliminate the alternatives which are not no-goods at the end
00156     while ((n > s) && (p.ds[n-1].truealt() == 0U))
00157       n--;
00158 
00159     // A sentinel element
00160     NoNGL nn;
00161     // Current no-good literal
00162     NGL* c = &nn;
00163 
00164     // Commit no-goods at the beginning
00165     while ((s < n) && (p.ds[s].truealt() > 0U))
00166       // Try whether this is a rightmost alternative
00167       if (p.ds[s].rightmost()) {
00168         // No literal needed, directly try to commit
00169         home.trycommit(*p.ds[s].choice(),p.ds[s].truealt());
00170         s++;
00171       } else {
00172         // Prune using no-good literals
00173         for (unsigned int a=0U; a<p.ds[s].truealt(); a++) {
00174           NGL* l = home.ngl(*p.ds[s].choice(),a);
00175           // Does the brancher support no-good literals?
00176           if (l == NULL)
00177             return ES_OK;
00178           GECODE_ES_CHECK(l->prune(home));
00179         }
00180         // Add literal as root if needed and stop
00181         if (NGL* l = home.ngl(*p.ds[s].choice(),p.ds[s].truealt())) {
00182           c = c->add(l,false);
00183           s++; break;
00184         }
00185       }
00186 
00187     // There are no literals
00188     if (home.failed())
00189       return ES_FAILED;
00190     if (s >= n)
00191       return ES_OK;
00192 
00193     // There must be at least two literals
00194     assert((n-s > 1) ||
00195            ((n-s == 1) && (c != &nn)));
00196 
00197     // Remember the last leaf
00198     NGL* ll = NULL;
00199 
00200     // Create literals
00201     for (int i=s; i<n; i++) {
00202       // Add leaves
00203       for (unsigned int a=0U; a<p.ds[i].truealt(); a++) {
00204         NGL* l = home.ngl(*p.ds[i].choice(),a);
00205         if (l == NULL) {
00206           // The brancher does not support no-goods
00207           if (ll == NULL)
00208             return ES_OK;
00209           ll->next(NULL);
00210           break;
00211         }
00212         c = c->add(l,true); ll = c;
00213         n_nogood++;
00214       }
00215       // Check whether to add an additional subtree
00216       if (NGL* l = home.ngl(*p.ds[i].choice(),p.ds[i].truealt())) {
00217         c = c->add(l,false);
00218       } else if (!p.ds[i].rightmost()) {
00219         // The brancher does not support no-goods
00220         if (ll == NULL)
00221           return ES_OK;
00222         ll->next(NULL);
00223         break;
00224       }
00225     }
00226 
00227     const_cast<Path&>(p).ng(n_nogood);
00228 
00229     (void) new (home) NoGoodsProp(home,nn.next());
00230     return ES_OK;
00231   }
00232 
00233 }}}
00234 
00235 #endif
00236 
00237 // STATISTICS: search-meta