Generated on Tue May 22 09:39:40 2018 for Gecode by doxygen 1.6.3

script.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, 2004
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *
00014  *  Permission is hereby granted, free of charge, to any person obtaining
00015  *  a copy of this software and associated documentation files (the
00016  *  "Software"), to deal in the Software without restriction, including
00017  *  without limitation the rights to use, copy, modify, merge, publish,
00018  *  distribute, sublicense, and/or sell copies of the Software, and to
00019  *  permit persons to whom the Software is furnished to do so, subject to
00020  *  the following conditions:
00021  *
00022  *  The above copyright notice and this permission notice shall be
00023  *  included in all copies or substantial portions of the Software.
00024  *
00025  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00026  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00027  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00028  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00029  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00030  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00031  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00032  *
00033  */
00034 
00035 #include <iostream>
00036 #include <iomanip>
00037 #include <fstream>
00038 #include <cstring>
00039 
00040 #ifndef GECODE_THREADS_WINDOWS
00041 #include <csignal>
00042 #endif
00043 
00044 namespace Gecode { namespace Driver {
00045 
00050   class CombinedStop : public Search::Stop {
00051   private:
00052     Search::NodeStop* ns; 
00053     Search::FailStop* fs; 
00054     Search::TimeStop* ts; 
00055     GECODE_DRIVER_EXPORT
00056     static bool sigint;   
00057 
00058     CombinedStop(unsigned int node, unsigned int fail, unsigned int time)
00059       : ns((node > 0) ? new Search::NodeStop(node) : NULL),
00060         fs((fail > 0) ? new Search::FailStop(fail) : NULL),
00061         ts((time > 0) ? new Search::TimeStop(time) : NULL) {
00062       sigint = false;
00063     }
00064   public:
00066     enum {
00067       SR_NODE = 1 << 0, 
00068       SR_FAIL = 1 << 1, 
00069       SR_TIME = 1 << 2, 
00070       SR_INT  = 1 << 3  
00071     };
00073     virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
00074       return
00075         sigint ||
00076         ((ns != NULL) && ns->stop(s,o)) ||
00077         ((fs != NULL) && fs->stop(s,o)) ||
00078         ((ts != NULL) && ts->stop(s,o));
00079     }
00081     int reason(const Search::Statistics& s, const Search::Options& o) {
00082       return
00083         (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
00084         (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
00085         (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0) |
00086         (sigint                          ? SR_INT  : 0);
00087     }
00089     static Search::Stop*
00090     create(unsigned int node, unsigned int fail, unsigned int time,
00091            bool intr) {
00092       if ( (!intr) && (node == 0) && (fail == 0) && (time == 0))
00093         return NULL;
00094       else
00095         return new CombinedStop(node,fail,time);
00096     }
00097 #ifdef GECODE_THREADS_WINDOWS
00098 
00099     static BOOL interrupt(DWORD t) {
00100       if (t == CTRL_C_EVENT) {
00101         sigint = true;
00102         installCtrlHandler(false,true);
00103         return true;
00104       }
00105       return false;
00106     }
00107 #else
00108 
00109     static void
00110     interrupt(int) {
00111       sigint = true;
00112       installCtrlHandler(false,true);
00113     }
00114 #endif
00115 
00116     static void installCtrlHandler(bool install, bool force=false) {
00117       if (force || !sigint) {
00118 #ifdef GECODE_THREADS_WINDOWS
00119         SetConsoleCtrlHandler( (PHANDLER_ROUTINE) interrupt, install);
00120 #else
00121         std::signal(SIGINT, install ? interrupt : SIG_DFL);
00122 #endif
00123       }
00124     }
00126     ~CombinedStop(void) {
00127       delete ns; delete fs; delete ts;
00128     }
00129   };
00130 
00135   GECODE_DRIVER_EXPORT void
00136   stop(Support::Timer& t, std::ostream& os);
00137 
00141   GECODE_DRIVER_EXPORT double
00142   am(double t[], unsigned int n);
00143 
00147   GECODE_DRIVER_EXPORT double
00148   dev(double t[], unsigned int n);
00149 
00151   template<class Options>
00152   inline Search::Cutoff*
00153   createCutoff(const Options& o) {
00154     switch (o.restart()) {
00155     case RM_NONE:
00156       return NULL;
00157     case RM_CONSTANT:
00158       return Search::Cutoff::constant(o.restart_scale());
00159     case RM_LINEAR:
00160       return Search::Cutoff::linear(o.restart_scale());
00161     case RM_LUBY:
00162       return Search::Cutoff::luby(o.restart_scale());
00163     case RM_GEOMETRIC:
00164       return Search::Cutoff::geometric(o.restart_scale(),o.restart_base());
00165     default: GECODE_NEVER;
00166     }
00167     return NULL;
00168   }
00169 
00170 
00171 #ifdef GECODE_HAS_GIST
00172 
00176   template<class Engine>
00177   class GistEngine {
00178   public:
00179     static void explore(Space* root, const Gist::Options& opt) {
00180       (void) Gist::dfs(root, opt);
00181     }
00182   };
00183 
00185   template<typename S>
00186   class GistEngine<DFS<S> > {
00187   public:
00188     static void explore(S* root, const Gist::Options& opt) {
00189       (void) Gist::dfs(root, opt);
00190     }
00191   };
00192 
00194   template<typename S>
00195   class GistEngine<LDS<S> > {
00196   public:
00197     static void explore(S* root, const Gist::Options& opt) {
00198       (void) Gist::dfs(root, opt);
00199     }
00200   };
00201 
00203   template<typename S>
00204   class GistEngine<BAB<S> > {
00205   public:
00206     static void explore(S* root, const Gist::Options& opt) {
00207       (void) Gist::bab(root, opt);
00208     }
00209   };
00210 
00211 #endif
00212 
00213 #ifdef GECODE_HAS_CPPROFILER
00214 
00216   template<class BaseSpace>
00217   class ScriptGetInfo : public CPProfilerSearchTracer::GetInfo {
00218   public:
00220     ScriptGetInfo(void);
00222     virtual std::string getInfo(const Space& home) const;
00223   };
00224   
00225 #endif
00226 
00227   template<class BaseSpace>
00228   forceinline
00229   ScriptBase<BaseSpace>::ScriptBase(const Options& opt)
00230     : BaseSpace(opt) {}
00231 
00232   template<class BaseSpace>
00233   forceinline
00234   ScriptBase<BaseSpace>::ScriptBase(ScriptBase& e)
00235     : BaseSpace(e) {}
00236 
00237   template<class BaseSpace>
00238   void
00239   ScriptBase<BaseSpace>::print(std::ostream&) const {}
00240 
00241   template<class BaseSpace>
00242   void
00243   ScriptBase<BaseSpace>::compare(const Space&, std::ostream&) const {}
00244 
00245   template<class BaseSpace>
00246   std::ostream&
00247   ScriptBase<BaseSpace>::select_ostream(const char* sn, std::ofstream& ofs) {
00248     if (strcmp(sn, "stdout") == 0) {
00249       return std::cout;
00250     } else if (strcmp(sn, "stdlog") == 0) {
00251       return std::clog;
00252     } else if (strcmp(sn, "stderr") == 0) {
00253       return std::cerr;
00254     } else {
00255       ofs.open(sn);
00256       return ofs;
00257     }
00258   }
00259 
00260 #ifdef GECODE_HAS_CPPROFILER
00261 
00262   template<class BaseSpace>
00263   ScriptGetInfo<BaseSpace>::ScriptGetInfo(void) {}
00264 
00265   template<class BaseSpace>
00266   std::string
00267   ScriptGetInfo<BaseSpace>::getInfo(const Space& home) const {
00268     std::stringstream ss;
00269     if (const ScriptBase<BaseSpace>* sb
00270         = dynamic_cast<const ScriptBase<BaseSpace>*>(&home))
00271       sb->print(ss);
00272     return ss.str();
00273   }
00274   
00275 #endif
00276 
00277 
00281   template<class T, template<class> class E>
00282   class EngineToMeta : public E<T> {
00283   public:
00284     EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
00285   };
00286 
00287   template<class BaseSpace>
00288   template<class Script, template<class> class Engine, class Options>
00289   void
00290   ScriptBase<BaseSpace>::run(const Options& o, Script* s) {
00291     if ((o.restart() != RM_NONE) && (o.assets() > 0)) {
00292       std::cerr << "Cannot use restarts and portfolio..." << std::endl;
00293       exit(EXIT_FAILURE);
00294     }
00295     if (o.restart() != RM_NONE) {
00296       runMeta<Script,Engine,Options,RBS>(o,s);
00297     } else if (o.assets() > 0) {
00298       runMeta<Script,Engine,Options,PBS>(o,s);
00299     } else {
00300       runMeta<Script,Engine,Options,EngineToMeta>(o,s);
00301     }
00302   }
00303 
00304   template<class BaseSpace>
00305   template<class Script, template<class> class Engine, class Options,
00306            template<class, template<class> class> class Meta>
00307   void
00308   ScriptBase<BaseSpace>::runMeta(const Options& o, Script* s) {
00309     using namespace std;
00310 
00311     ofstream sol_file, log_file;
00312 
00313     ostream& s_out = select_ostream(o.out_file(), sol_file);
00314     ostream& l_out = select_ostream(o.log_file(), log_file);
00315 
00316     Search::Options so;
00317 
00318     try {
00319       switch (o.mode()) {
00320       case SM_GIST:
00321 #ifdef GECODE_HAS_GIST
00322         {
00323           Gist::Print<Script> pi(o.name());
00324           Gist::VarComparator<Script> vc(o.name());
00325           Gist::Options opt;
00326           opt.inspect.click(&pi);
00327           opt.inspect.compare(&vc);
00328           opt.clone = false;
00329           opt.c_d   = o.c_d();
00330           opt.a_d   = o.a_d();
00331           for (unsigned int i=0; o.inspect.click(i) != NULL; i++)
00332             opt.inspect.click(o.inspect.click(i));
00333           for (unsigned int i=0; o.inspect.solution(i) != NULL; i++)
00334             opt.inspect.solution(o.inspect.solution(i));
00335           for (unsigned int i=0; o.inspect.move(i) != NULL; i++)
00336             opt.inspect.move(o.inspect.move(i));
00337           for (unsigned int i=0; o.inspect.compare(i) != NULL; i++)
00338             opt.inspect.compare(o.inspect.compare(i));
00339           if (s == NULL)
00340             s = new Script(o);
00341           (void) GistEngine<Engine<Script> >::explore(s, opt);
00342         }
00343         break;
00344         // If Gist is not available, goto solution
00345 #else
00346         goto solution;
00347 #endif
00348       case SM_CPPROFILER:
00349 #ifdef GECODE_HAS_CPPROFILER
00350         {
00351           CPProfilerSearchTracer::GetInfo* getInfo = nullptr;
00352           if (o.profiler_info())
00353             getInfo = new ScriptGetInfo<BaseSpace>;
00354           so.tracer = new CPProfilerSearchTracer
00355             (o.profiler_id(), o.name(), o.profiler_port(), getInfo);
00356         }
00357         /* FALL THROUGH */
00358 #endif
00359       case SM_SOLUTION:
00360 #ifndef GECODE_HAS_GIST
00361       solution:
00362 #endif
00363         {
00364           l_out << o.name() << endl;
00365           Support::Timer t;
00366           int i = static_cast<int>(o.solutions());
00367           t.start();
00368           if (s == NULL)
00369             s = new Script(o);
00370           unsigned int n_p = PropagatorGroup::all.size(*s);
00371           unsigned int n_b = BrancherGroup::all.size(*s);
00372           so.threads = o.threads();
00373           so.c_d     = o.c_d();
00374           so.a_d     = o.a_d();
00375           so.d_l     = o.d_l();
00376           so.assets  = o.assets();
00377           so.slice   = o.slice();
00378           so.stop    = CombinedStop::create(o.node(),o.fail(), o.time(),
00379                                             o.interrupt());
00380           so.cutoff  = createCutoff(o);
00381           so.clone   = false;
00382           so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00383           if (o.interrupt())
00384             CombinedStop::installCtrlHandler(true);
00385           {
00386             Meta<Script,Engine> e(s,so);
00387             if (o.print_last()) {
00388               Script* px = NULL;
00389               do {
00390                 Script* ex = e.next();
00391                 if (ex == NULL) {
00392                   if (px != NULL) {
00393                     px->print(s_out);
00394                     delete px;
00395                   }
00396                   break;
00397                 } else {
00398                   delete px;
00399                   px = ex;
00400                 }
00401               } while (--i != 0);
00402             } else {
00403               do {
00404                 Script* ex = e.next();
00405                 if (ex == NULL)
00406                   break;
00407                 ex->print(s_out);
00408                 delete ex;
00409               } while (--i != 0);
00410             }
00411             if (o.interrupt())
00412               CombinedStop::installCtrlHandler(false);
00413             Search::Statistics stat = e.statistics();
00414             s_out << endl;
00415             if (e.stopped()) {
00416               l_out << "Search engine stopped..." << endl
00417                     << "\treason: ";
00418               int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
00419               if (r & CombinedStop::SR_INT)
00420                 l_out << "user interrupt " << endl;
00421               else {
00422                 if (r & CombinedStop::SR_NODE)
00423                   l_out << "node ";
00424                 if (r & CombinedStop::SR_FAIL)
00425                   l_out << "fail ";
00426                 if (r & CombinedStop::SR_TIME)
00427                   l_out << "time ";
00428                 l_out << "limit reached" << endl << endl;
00429               }
00430             }
00431             l_out << "Initial" << endl
00432                   << "\tpropagators: " << n_p << endl
00433                   << "\tbranchers:   " << n_b << endl
00434                   << endl
00435                   << "Summary" << endl
00436                   << "\truntime:      ";
00437             stop(t, l_out);
00438             l_out << endl
00439                   << "\tsolutions:    "
00440                   << ::abs(static_cast<int>(o.solutions()) - i) << endl
00441                   << "\tpropagations: " << stat.propagate << endl
00442                   << "\tnodes:        " << stat.node << endl
00443                   << "\tfailures:     " << stat.fail << endl
00444                   << "\trestarts:     " << stat.restart << endl
00445                   << "\tno-goods:     " << stat.nogood << endl
00446                   << "\tpeak depth:   " << stat.depth << endl
00447 #ifdef GECODE_PEAKHEAP
00448                   << "\tpeak memory:  "
00449                   << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00450                   << endl
00451 #endif
00452                   << endl;
00453           }
00454           delete so.stop;
00455           delete so.tracer;
00456         }
00457         break;
00458       case SM_STAT:
00459         {
00460           l_out << o.name() << endl;
00461           Support::Timer t;
00462           int i = static_cast<int>(o.solutions());
00463           t.start();
00464           if (s == NULL)
00465             s = new Script(o);
00466           unsigned int n_p = PropagatorGroup::all.size(*s);
00467           unsigned int n_b = BrancherGroup::all.size(*s);
00468 
00469           so.clone   = false;
00470           so.threads = o.threads();
00471           so.assets  = o.assets();
00472           so.slice   = o.slice();
00473           so.c_d     = o.c_d();
00474           so.a_d     = o.a_d();
00475           so.d_l     = o.d_l();
00476           so.stop    = CombinedStop::create(o.node(),o.fail(), o.time(),
00477                                             o.interrupt());
00478           so.cutoff  = createCutoff(o);
00479           so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00480           if (o.interrupt())
00481             CombinedStop::installCtrlHandler(true);
00482           {
00483             Meta<Script,Engine> e(s,so);
00484             do {
00485               Script* ex = e.next();
00486               if (ex == NULL)
00487                 break;
00488               delete ex;
00489             } while (--i != 0);
00490             if (o.interrupt())
00491               CombinedStop::installCtrlHandler(false);
00492             Search::Statistics stat = e.statistics();
00493             l_out << endl
00494                   << "\tpropagators:  " << n_p << endl
00495                   << "\tbranchers:    " << n_b << endl
00496                   << "\truntime:      ";
00497             stop(t, l_out);
00498             l_out << endl
00499                   << "\tsolutions:    "
00500                   << ::abs(static_cast<int>(o.solutions()) - i) << endl
00501                   << "\tpropagations: " << stat.propagate << endl
00502                   << "\tnodes:        " << stat.node << endl
00503                   << "\tfailures:     " << stat.fail << endl
00504                   << "\trestarts:     " << stat.restart << endl
00505                   << "\tno-goods:     " << stat.nogood << endl
00506                   << "\tpeak depth:   " << stat.depth << endl
00507 #ifdef GECODE_PEAKHEAP
00508                   << "\tpeak memory:  "
00509                   << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00510                   << endl
00511 #endif
00512                   << endl;
00513           }
00514           delete so.stop;
00515         }
00516         break;
00517       case SM_TIME:
00518         {
00519           l_out << o.name() << endl;
00520           Support::Timer t;
00521           double* ts = new double[o.samples()];
00522           bool stopped = false;
00523           for (unsigned int ns = o.samples(); !stopped && ns--; ) {
00524             t.start();
00525             for (unsigned int k = o.iterations(); !stopped && k--; ) {
00526               unsigned int i = o.solutions();
00527               Script* s1 = new Script(o);
00528               Search::Options so;
00529               so.clone   = false;
00530               so.threads = o.threads();
00531               so.assets  = o.assets();
00532               so.slice   = o.slice();
00533               so.c_d     = o.c_d();
00534               so.a_d     = o.a_d();
00535               so.d_l     = o.d_l();
00536               so.stop    = CombinedStop::create(o.node(),o.fail(), o.time(),
00537                                                 false);
00538               so.cutoff  = createCutoff(o);
00539               so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00540               {
00541                 Meta<Script,Engine> e(s1,so);
00542                 do {
00543                   Script* ex = e.next();
00544                   if (ex == NULL)
00545                     break;
00546                   delete ex;
00547                 } while (--i != 0);
00548                 if (e.stopped())
00549                   stopped = true;
00550               }
00551               delete so.stop;
00552             }
00553             ts[ns] = t.stop() / o.iterations();
00554           }
00555           if (stopped) {
00556             l_out << "\tSTOPPED" << endl;
00557           } else {
00558             double m = am(ts,o.samples());
00559             double d = dev(ts,o.samples()) * 100.0;
00560             l_out << "\truntime: "
00561                  << setw(20) << right
00562                  << showpoint << fixed
00563                  << setprecision(6) << m << "ms"
00564                  << setprecision(2) << " (" << d << "% deviation)"
00565                  << endl;
00566           }
00567           delete [] ts;
00568         }
00569         break;
00570       }
00571     } catch (Exception& e) {
00572       cerr << "Exception: " << e.what() << "." << endl
00573            << "Stopping..." << endl;
00574       if (sol_file.is_open())
00575         sol_file.close();
00576       if (log_file.is_open())
00577         log_file.close();
00578       exit(EXIT_FAILURE);
00579     }
00580     if (sol_file.is_open())
00581       sol_file.close();
00582     if (log_file.is_open())
00583       log_file.close();
00584   }
00585 
00586 }}
00587 
00588 // STATISTICS: driver-any