Generated on Thu Apr 11 13:59:18 2019 for Gecode by doxygen 1.6.3

path.hpp

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, 2003
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Search { namespace Par {
00035 
00036   /*
00037    * Edge for recomputation
00038    *
00039    */
00040   template<class Tracer>
00041   forceinline
00042   Path<Tracer>::Edge::Edge(void) {}
00043 
00044   template<class Tracer>
00045   forceinline
00046   Path<Tracer>::Edge::Edge(Space* s, Space* c, unsigned int nid)
00047     : _space(c), _alt(0), _choice(s->choice()), _nid(nid) {
00048     _alt_max = _choice->alternatives()-1;
00049   }
00050 
00051   template<class Tracer>
00052   forceinline Space*
00053   Path<Tracer>::Edge::space(void) const {
00054     return _space;
00055   }
00056   template<class Tracer>
00057   forceinline void
00058   Path<Tracer>::Edge::space(Space* s) {
00059     _space = s;
00060   }
00061 
00062   template<class Tracer>
00063   forceinline unsigned int
00064   Path<Tracer>::Edge::alt(void) const {
00065     return _alt;
00066   }
00067 
00068   template<class Tracer>
00069   forceinline unsigned int
00070   Path<Tracer>::Edge::nid(void) const {
00071     return _nid;
00072   }
00073 
00074   template<class Tracer>
00075   forceinline unsigned int
00076   Path<Tracer>::Edge::truealt(void) const {
00077     return std::min(_alt,_choice->alternatives()-1);
00078   }
00079   template<class Tracer>
00080   forceinline bool
00081   Path<Tracer>::Edge::rightmost(void) const {
00082     return _alt >= _alt_max;
00083   }
00084   template<class Tracer>
00085   forceinline bool
00086   Path<Tracer>::Edge::lao(void) const {
00087     return _alt > _alt_max;
00088   }
00089   template<class Tracer>
00090   forceinline bool
00091   Path<Tracer>::Edge::work(void) const {
00092     return _alt < _alt_max;
00093   }
00094   template<class Tracer>
00095   forceinline void
00096   Path<Tracer>::Edge::next(void) {
00097     _alt++;
00098   }
00099   template<class Tracer>
00100   forceinline unsigned int
00101   Path<Tracer>::Edge::steal(void) {
00102     assert(work());
00103     return _alt_max--;
00104   }
00105 
00106   template<class Tracer>
00107   forceinline const Choice*
00108   Path<Tracer>::Edge::choice(void) const {
00109     return _choice;
00110   }
00111 
00112   template<class Tracer>
00113   forceinline void
00114   Path<Tracer>::Edge::dispose(void) {
00115     delete _space;
00116     delete _choice;
00117   }
00118 
00119 
00120 
00121   /*
00122    * Depth-first stack with recomputation
00123    *
00124    */
00125 
00126   template<class Tracer>
00127   forceinline
00128   Path<Tracer>::Path(unsigned int l)
00129     : ds(heap), _ngdl(l), n_work(0) {}
00130 
00131   template<class Tracer>
00132   forceinline unsigned int
00133   Path<Tracer>::ngdl(void) const {
00134     return _ngdl;
00135   }
00136 
00137   template<class Tracer>
00138   forceinline void
00139   Path<Tracer>::ngdl(unsigned int l) {
00140     _ngdl = l;
00141   }
00142 
00143   template<class Tracer>
00144   forceinline const Choice*
00145   Path<Tracer>::push(Worker& stat, Space* s, Space* c, unsigned int nid) {
00146     if (!ds.empty() && ds.top().lao()) {
00147       // Topmost stack entry was LAO -> reuse
00148       ds.pop().dispose();
00149     }
00150     Edge sn(s,c,nid);
00151     if (sn.work())
00152       n_work++;
00153     ds.push(sn);
00154     stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
00155     return sn.choice();
00156   }
00157 
00158   template<class Tracer>
00159   forceinline void
00160   Path<Tracer>::next(void) {
00161     while (!ds.empty())
00162       if (ds.top().rightmost()) {
00163         ds.pop().dispose();
00164       } else {
00165         assert(ds.top().work());
00166         ds.top().next();
00167         if (!ds.top().work())
00168           n_work--;
00169         return;
00170       }
00171   }
00172 
00173   template<class Tracer>
00174   forceinline typename Path<Tracer>::Edge&
00175   Path<Tracer>::top(void) const {
00176     assert(!ds.empty());
00177     return ds.top();
00178   }
00179 
00180   template<class Tracer>
00181   forceinline bool
00182   Path<Tracer>::empty(void) const {
00183     return ds.empty();
00184   }
00185 
00186   template<class Tracer>
00187   forceinline void
00188   Path<Tracer>::commit(Space* s, int i) const {
00189     const Edge& n = ds[i];
00190     s->commit(*n.choice(),n.alt());
00191   }
00192 
00193   template<class Tracer>
00194   forceinline int
00195   Path<Tracer>::lc(void) const {
00196     int l = ds.entries()-1;
00197     while (ds[l].space() == NULL)
00198       l--;
00199     return l;
00200   }
00201 
00202   template<class Tracer>
00203   forceinline int
00204   Path<Tracer>::entries(void) const {
00205     return ds.entries();
00206   }
00207 
00208   template<class Tracer>
00209   forceinline void
00210   Path<Tracer>::unwind(int l, Tracer& t) {
00211     assert((ds[l].space() == NULL) || ds[l].space()->failed());
00212     int n = ds.entries();
00213     if (t) {
00214       for (int i=l; i<n; i++) {
00215         Path<Tracer>::Edge& top = ds.top();
00216         unsigned int fa = (i != l) ? top.alt() + 1 : top.alt();
00217         for (unsigned int a = fa; a < top.choice()->alternatives(); a++) {
00218           SearchTracer::EdgeInfo ei(t.wid(), top.nid(), a);
00219           t.skip(ei);
00220         }
00221         if (ds.top().work())
00222           n_work--;
00223         ds.pop().dispose();
00224       }
00225     } else {
00226       for (int i=l; i<n; i++) {
00227         if (ds.top().work())
00228           n_work--;
00229         ds.pop().dispose();
00230       }
00231     }
00232     assert(ds.entries() == l);
00233   }
00234 
00235   template<class Tracer>
00236   forceinline void
00237   Path<Tracer>::reset(unsigned int l) {
00238     n_work = 0;
00239     while (!ds.empty())
00240       ds.pop().dispose();
00241     _ngdl = l;
00242   }
00243 
00244   template<class Tracer>
00245   forceinline bool
00246   Path<Tracer>::steal(void) const {
00247     return n_work > Config::steal_limit;
00248   }
00249 
00250   template<class Tracer>
00251   forceinline Space*
00252   Path<Tracer>::steal(Worker& stat, unsigned long int& d,
00253                       Tracer& myt, Tracer& ot) {
00254     // Find position to steal: leave sufficient work
00255     int n = ds.entries()-1;
00256     unsigned int w = 0;
00257     while (n >= 0) {
00258       if (ds[n].work())
00259         w++;
00260       if (w > Config::steal_limit) {
00261         // Okay, there is sufficient work left
00262         int l=n;
00263         // Find last copy
00264         while (ds[l].space() == NULL)
00265           l--;
00266         Space* c = ds[l].space()->clone();
00267         // Recompute, if necessary
00268         for (int i=l; i<n; i++)
00269           commit(c,i);
00270         unsigned int a = ds[n].steal();
00271         c->commit(*ds[n].choice(),a);
00272         if (!ds[n].work())
00273           n_work--;
00274         // No no-goods can be extracted above n
00275         ngdl(std::min(ngdl(),static_cast<unsigned int>(n)));
00276         d = stat.steal_depth(static_cast<unsigned long int>(n+1));
00277         if (myt && ot) {
00278           ot.ei()->init(myt.wid(),ds[n].nid(), a, *c, *ds[n].choice());
00279         }
00280         return c;
00281       }
00282       n--;
00283     }
00284     return NULL;
00285   }
00286 
00287   template<class Tracer>
00288   forceinline Space*
00289   Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00290                           Tracer& t) {
00291     assert(!ds.empty());
00292     // Recompute space according to path
00293     // Also say distance to copy (d == 0) requires immediate copying
00294 
00295     // Check for LAO
00296     if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00297       Space* s = ds.top().space();
00298       s->commit(*ds.top().choice(),ds.top().alt());
00299       assert(ds.entries()-1 == lc());
00300       ds.top().space(NULL);
00301       // Mark as reusable
00302       if (static_cast<unsigned int>(ds.entries()) > ngdl())
00303         ds.top().next();
00304       d = 0;
00305       return s;
00306     }
00307     // General case for recomputation
00308     int l = lc();             // Position of last clone
00309     int n = ds.entries();     // Number of stack entries
00310     // New distance, if no adaptive recomputation
00311     d = static_cast<unsigned int>(n - l);
00312 
00313     Space* s = ds[l].space()->clone(); // Last clone
00314 
00315     if (d < a_d) {
00316       // No adaptive recomputation
00317       for (int i=l; i<n; i++)
00318         commit(s,i);
00319     } else {
00320       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00321       int i = l; // To iterate over all entries
00322       // Recompute up to middle
00323       for (; i<m; i++ )
00324         commit(s,i);
00325       // Skip over all rightmost branches
00326       for (; (i<n) && ds[i].rightmost(); i++)
00327         commit(s,i);
00328       // Is there any point to make a copy?
00329       if (i<n-1) {
00330         // Propagate to fixpoint
00331         SpaceStatus ss = s->status(stat);
00332         /*
00333          * Again, the space might already propagate to failure (due to
00334          * weakly monotonic propagators).
00335          */
00336         if (ss == SS_FAILED) {
00337           // s must be deleted as it is not on the stack
00338           delete s;
00339           stat.fail++;
00340           unwind(i,t);
00341           return NULL;
00342         }
00343         ds[i].space(s->clone());
00344         d = static_cast<unsigned int>(n-i);
00345       }
00346       // Finally do the remaining commits
00347       for (; i<n; i++)
00348         commit(s,i);
00349     }
00350     return s;
00351   }
00352 
00353   template<class Tracer>
00354   forceinline Space*
00355   Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00356                           const Space& best, int& mark,
00357                           Tracer& t) {
00358     assert(!ds.empty());
00359     // Recompute space according to path
00360     // Also say distance to copy (d == 0) requires immediate copying
00361 
00362     // Check for LAO
00363     if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00364       Space* s = ds.top().space();
00365       s->commit(*ds.top().choice(),ds.top().alt());
00366       assert(ds.entries()-1 == lc());
00367       if (mark > ds.entries()-1) {
00368         mark = ds.entries()-1;
00369         s->constrain(best);
00370       }
00371       ds.top().space(NULL);
00372       // Mark as reusable
00373       if (static_cast<unsigned int>(ds.entries()) > ngdl())
00374         ds.top().next();
00375       d = 0;
00376       return s;
00377     }
00378     // General case for recomputation
00379     int l = lc();             // Position of last clone
00380     int n = ds.entries();     // Number of stack entries
00381     // New distance, if no adaptive recomputation
00382     d = static_cast<unsigned int>(n - l);
00383 
00384     Space* s = ds[l].space(); // Last clone
00385 
00386     if (l < mark) {
00387       mark = l;
00388       s->constrain(best);
00389       // The space on the stack could be failed now as an additional
00390       // constraint might have been added.
00391       if (s->status(stat) == SS_FAILED) {
00392         // s does not need deletion as it is on the stack (unwind does this)
00393         stat.fail++;
00394         unwind(l,t);
00395         return NULL;
00396       }
00397       // It is important to replace the space on the stack with the
00398       // copy: a copy might be much smaller due to flushed caches
00399       // of propagators
00400       Space* c = s->clone();
00401       ds[l].space(c);
00402     } else {
00403       s = s->clone();
00404     }
00405 
00406     if (d < a_d) {
00407       // No adaptive recomputation
00408       for (int i=l; i<n; i++)
00409         commit(s,i);
00410     } else {
00411       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00412       int i = l;            // To iterate over all entries
00413       // Recompute up to middle
00414       for (; i<m; i++ )
00415         commit(s,i);
00416       // Skip over all rightmost branches
00417       for (; (i<n) && ds[i].rightmost(); i++)
00418         commit(s,i);
00419       // Is there any point to make a copy?
00420       if (i<n-1) {
00421         // Propagate to fixpoint
00422         SpaceStatus ss = s->status(stat);
00423         /*
00424          * Again, the space might already propagate to failure
00425          *
00426          * This can be for two reasons:
00427          *  - constrain is true, so we fail
00428          *  - the space has weakly monotonic propagators
00429          */
00430         if (ss == SS_FAILED) {
00431           // s must be deleted as it is not on the stack
00432           delete s;
00433           stat.fail++;
00434           unwind(i,t);
00435           return NULL;
00436         }
00437         ds[i].space(s->clone());
00438         d = static_cast<unsigned int>(n-i);
00439       }
00440       // Finally do the remaining commits
00441       for (; i<n; i++)
00442         commit(s,i);
00443     }
00444     return s;
00445   }
00446 
00447   template<class Tracer>
00448   void
00449   Path<Tracer>::post(Space& home) const {
00450     GECODE_ES_FAIL(NoGoodsProp::post(home,*this));
00451   }
00452 
00453 }}}
00454 
00455 // STATISTICS: search-par