Generated on Sun Feb 17 15:24:28 2019 for Gecode by doxygen 1.6.3

dfs.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, 2009
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 Seq {
00035 
00036   template<class Tracer>
00037   forceinline
00038   DFS<Tracer>::DFS(Space* s, const Options& o)
00039     : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0) {
00040     if (tracer) {
00041       tracer.engine(SearchTracer::EngineType::DFS, 1U);
00042       tracer.worker();
00043     }
00044     if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00045       fail++;
00046       cur = NULL;
00047       if (!opt.clone)
00048         delete s;
00049     } else {
00050       cur = snapshot(s,opt);
00051     }
00052   }
00053 
00054   template<class Tracer>
00055   forceinline void
00056   DFS<Tracer>::reset(Space* s) {
00057     tracer.round();
00058     delete cur;
00059     path.reset();
00060     d = 0;
00061     if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00062       delete s;
00063       cur = NULL;
00064     } else {
00065       cur = s;
00066     }
00067     Worker::reset();
00068   }
00069 
00070   template<class Tracer>
00071   forceinline NoGoods&
00072   DFS<Tracer>::nogoods(void) {
00073     return path;
00074   }
00075 
00076   template<class Tracer>
00077   forceinline Space*
00078   DFS<Tracer>::next(void) {
00079     /*
00080      * The engine maintains the following invariant:
00081      *  - If the current space (cur) is not NULL, the path always points
00082      *    to exactly that space.
00083      *  - If the current space (cur) is NULL, the path always points
00084      *    to the next space (if there is any).
00085      *
00086      * This invariant is needed so that no-goods can be extracted properly
00087      * when the engine is stopped or has found a solution.
00088      *
00089      */
00090     start();
00091     while (true) {
00092       if (stop(opt))
00093         return NULL;
00094       while (cur == NULL) {
00095         if (path.empty())
00096           return NULL;
00097         cur = path.recompute(d,opt.a_d,*this,tracer);
00098         if (cur != NULL)
00099           break;
00100         path.next();
00101       }
00102       node++;
00103       SearchTracer::EdgeInfo ei;
00104       if (tracer && (path.entries() > 0)) {
00105         typename Path<Tracer>::Edge& top = path.top();
00106         ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
00107       }
00108       unsigned int nid = tracer.nid();
00109       switch (cur->status(*this)) {
00110       case SS_FAILED:
00111         if (tracer) {
00112           SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
00113                                     tracer.wid(), nid, *cur);
00114           tracer.node(ei,ni);
00115         }
00116         fail++;
00117         delete cur;
00118         cur = NULL;
00119         path.next();
00120         break;
00121       case SS_SOLVED:
00122         {
00123           if (tracer) {
00124             SearchTracer::NodeInfo ni(SearchTracer::NodeType::SOLVED,
00125                                       tracer.wid(), nid, *cur);
00126             tracer.node(ei,ni);
00127           }
00128           // Deletes all pending branchers
00129           (void) cur->choice();
00130           Space* s = cur;
00131           cur = NULL;
00132           path.next();
00133           return s;
00134         }
00135       case SS_BRANCH:
00136         {
00137           Space* c;
00138           if ((d == 0) || (d >= opt.c_d)) {
00139             c = cur->clone();
00140             d = 1;
00141           } else {
00142             c = NULL;
00143             d++;
00144           }
00145           const Choice* ch = path.push(*this,cur,c,nid);
00146           if (tracer) {
00147             SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
00148                                       tracer.wid(), nid, *cur, ch);
00149             tracer.node(ei,ni);
00150           }
00151           cur->commit(*ch,0);
00152           break;
00153         }
00154       default:
00155         GECODE_NEVER;
00156       }
00157     }
00158     GECODE_NEVER;
00159     return NULL;
00160   }
00161 
00162   template<class Tracer>
00163   forceinline Statistics
00164   DFS<Tracer>::statistics(void) const {
00165     return *this;
00166   }
00167 
00168   template<class Tracer>
00169   forceinline void
00170   DFS<Tracer>::constrain(const Space& b) {
00171     (void) b;
00172     assert(false);
00173   }
00174 
00175   template<class Tracer>
00176   forceinline
00177   DFS<Tracer>::~DFS(void) {
00178     delete cur;
00179     tracer.done();
00180     path.reset();
00181   }
00182 
00183 }}}
00184 
00185 // STATISTICS: search-seq