Generated on Wed Nov 5 2014 05:18:16 for Gecode by doxygen 1.7.6.1
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  *  Last modified:
00010  *     $Date: 2013-07-15 02:49:56 +0200 (Mon, 15 Jul 2013) $ by $Author: tack $
00011  *     $Revision: 13879 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *
00018  *  Permission is hereby granted, free of charge, to any person obtaining
00019  *  a copy of this software and associated documentation files (the
00020  *  "Software"), to deal in the Software without restriction, including
00021  *  without limitation the rights to use, copy, modify, merge, publish,
00022  *  distribute, sublicense, and/or sell copies of the Software, and to
00023  *  permit persons to whom the Software is furnished to do so, subject to
00024  *  the following conditions:
00025  *
00026  *  The above copyright notice and this permission notice shall be
00027  *  included in all copies or substantial portions of the Software.
00028  *
00029  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00030  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00031  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00032  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00033  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00034  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00035  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00036  *
00037  */
00038 
00039 #include <iostream>
00040 #include <iomanip>
00041 #include <fstream>
00042 #include <cstring>
00043 
00044 #ifndef GECODE_THREADS_WINDOWS
00045 #include <csignal>
00046 #endif
00047 
00048 namespace Gecode { namespace Driver {
00049 
00054   class CombinedStop : public Search::Stop {
00055   private:
00056     Search::NodeStop* ns; 
00057     Search::FailStop* fs; 
00058     Search::TimeStop* ts; 
00059     GECODE_DRIVER_EXPORT
00060     static bool sigint;   
00061 
00062     CombinedStop(unsigned int node, unsigned int fail, unsigned int time)
00063       : ns((node > 0) ? new Search::NodeStop(node) : NULL),
00064         fs((fail > 0) ? new Search::FailStop(fail) : NULL),
00065         ts((time > 0) ? new Search::TimeStop(time) : NULL) {
00066       sigint = false;
00067     }
00068   public:
00070     enum {
00071       SR_NODE = 1 << 0, 
00072       SR_FAIL = 1 << 1, 
00073       SR_TIME = 1 << 2, 
00074       SR_INT  = 1 << 3  
00075     };
00077     virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
00078       return
00079         sigint ||
00080         ((ns != NULL) && ns->stop(s,o)) ||
00081         ((fs != NULL) && fs->stop(s,o)) ||
00082         ((ts != NULL) && ts->stop(s,o));
00083     }
00085     int reason(const Search::Statistics& s, const Search::Options& o) {
00086       return 
00087         (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
00088         (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
00089         (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0) |
00090         (sigint                          ? SR_INT  : 0);
00091     }
00093     static Search::Stop*
00094     create(unsigned int node, unsigned int fail, unsigned int time,
00095            bool intr) {
00096       if ( (!intr) && (node == 0) && (fail == 0) && (time == 0))
00097         return NULL;
00098       else
00099         return new CombinedStop(node,fail,time);
00100     }
00101 #ifdef GECODE_THREADS_WINDOWS
00102 
00103     static BOOL interrupt(DWORD t) {
00104       if (t == CTRL_C_EVENT) {
00105         sigint = true;
00106         installCtrlHandler(false,true);
00107         return true;
00108       }
00109       return false;
00110     }
00111 #else
00112 
00113     static void
00114     interrupt(int) {
00115       sigint = true;
00116       installCtrlHandler(false,true);
00117     }
00118 #endif
00119 
00120     static void installCtrlHandler(bool install, bool force=false) {
00121       if (force || !sigint) {
00122 #ifdef GECODE_THREADS_WINDOWS
00123         SetConsoleCtrlHandler( (PHANDLER_ROUTINE) interrupt, install);
00124 #else
00125         std::signal(SIGINT, install ? interrupt : SIG_DFL);
00126 #endif
00127       }
00128     }
00130     ~CombinedStop(void) {
00131       delete ns; delete fs; delete ts;
00132     }
00133   };
00134 
00139   GECODE_DRIVER_EXPORT void 
00140   stop(Support::Timer& t, std::ostream& os);
00141 
00145   GECODE_DRIVER_EXPORT double
00146   am(double t[], int n);
00147   
00151   GECODE_DRIVER_EXPORT double
00152   dev(double t[], int n);
00153   
00155   template<class Options>
00156   inline Search::Cutoff* 
00157   createCutoff(const Options& o) {
00158     switch (o.restart()) {
00159     case RM_NONE: 
00160       return NULL;
00161     case RM_CONSTANT: 
00162       return Search::Cutoff::constant(o.restart_scale());
00163     case RM_LINEAR: 
00164       return Search::Cutoff::linear(o.restart_scale());
00165     case RM_LUBY: 
00166       return Search::Cutoff::luby(o.restart_scale());
00167     case RM_GEOMETRIC: 
00168       return Search::Cutoff::geometric(o.restart_scale(),o.restart_base());
00169     default: GECODE_NEVER;
00170     }
00171     return NULL;
00172   }
00173   
00174   
00175 #ifdef GECODE_HAS_GIST
00176   
00180   template<class Engine>
00181   class GistEngine {
00182   public:
00183     static void explore(Space* root, const Gist::Options& opt) {
00184       (void) Gist::dfs(root, opt);
00185     }
00186   };
00187   
00189   template<typename S>
00190   class GistEngine<DFS<S> > {
00191   public:
00192     static void explore(S* root, const Gist::Options& opt) {
00193       (void) Gist::dfs(root, opt);
00194     }
00195   };
00196   
00198   template<typename S>
00199   class GistEngine<BAB<S> > {
00200   public:
00201     static void explore(S* root, const Gist::Options& opt) {
00202       (void) Gist::bab(root, opt);
00203     }
00204   };
00205   
00206 #endif
00207 
00208 
00209   template<class Space>
00210   std::ostream&
00211   ScriptBase<Space>::select_ostream(const char* name, std::ofstream& ofs) {
00212     if (strcmp(name, "stdout") == 0) {
00213       return std::cout;
00214     } else if (strcmp(name, "stdlog") == 0) {
00215       return std::clog;
00216     } else if (strcmp(name, "stderr") == 0) {
00217       return std::cerr;
00218     } else {
00219       ofs.open(name);
00220       return ofs;
00221     }
00222   }
00223 
00227   template<template<class> class E, class T>
00228   class EngineToMeta : public E<T> {
00229   public:
00230     EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
00231   };
00232 
00233   template<class Space>
00234   template<class Script, template<class> class Engine, class Options>
00235   void
00236   ScriptBase<Space>::run(const Options& o, Script* s) {
00237     if (o.restart()==RM_NONE) {
00238       runMeta<Script,Engine,Options,EngineToMeta>(o,s);
00239     } else {
00240       runMeta<Script,Engine,Options,RBS>(o,s);
00241     }
00242   }
00243 
00244   template<class Space>
00245   template<class Script, template<class> class Engine, class Options,
00246            template<template<class> class,class> class Meta>
00247   void
00248   ScriptBase<Space>::runMeta(const Options& o, Script* s) {
00249     using namespace std;
00250 
00251     ofstream sol_file, log_file;
00252 
00253     ostream& s_out = select_ostream(o.out_file(), sol_file);
00254     ostream& l_out = select_ostream(o.log_file(), log_file);
00255 
00256     try {
00257       switch (o.mode()) {
00258       case SM_GIST:
00259 #ifdef GECODE_HAS_GIST
00260         {
00261           Gist::Print<Script> pi(o.name());
00262           Gist::VarComparator<Script> vc(o.name());
00263           Gist::Options opt;
00264           opt.inspect.click(&pi);
00265           opt.inspect.compare(&vc);
00266           opt.clone = false;
00267           opt.c_d   = o.c_d();
00268           opt.a_d   = o.a_d();
00269           for (int i=0; o.inspect.click(i) != NULL; i++)
00270             opt.inspect.click(o.inspect.click(i));
00271           for (int i=0; o.inspect.solution(i) != NULL; i++)
00272             opt.inspect.solution(o.inspect.solution(i));
00273           for (int i=0; o.inspect.move(i) != NULL; i++)
00274             opt.inspect.move(o.inspect.move(i));
00275           for (int i=0; o.inspect.compare(i) != NULL; i++)
00276             opt.inspect.compare(o.inspect.compare(i));
00277           if (s == NULL)
00278             s = new Script(o);
00279           (void) GistEngine<Engine<Script> >::explore(s, opt);
00280         }
00281         break;
00282         // If Gist is not available, fall through
00283 #endif
00284       case SM_SOLUTION:
00285         {
00286           l_out << o.name() << endl;
00287           Support::Timer t;
00288           int i = o.solutions();
00289           t.start();
00290           if (s == NULL)
00291             s = new Script(o);
00292           unsigned int n_p = s->propagators();
00293           unsigned int n_b = s->branchers();
00294           Search::Options so;
00295           so.threads = o.threads();
00296           so.c_d     = o.c_d();
00297           so.a_d     = o.a_d();
00298           so.stop    = CombinedStop::create(o.node(),o.fail(), o.time(), 
00299                                             o.interrupt());
00300           so.cutoff  = createCutoff(o);
00301           so.clone   = false;
00302           so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00303           if (o.interrupt())
00304             CombinedStop::installCtrlHandler(true);
00305           {
00306             Meta<Engine,Script> e(s,so);
00307             if (o.print_last()) {
00308               Script* px = NULL;
00309               do {
00310                 Script* ex = e.next();
00311                 if (ex == NULL) {
00312                   if (px != NULL) {
00313                     px->print(s_out);
00314                     delete px;
00315                   }
00316                   break;
00317                 } else {
00318                   delete px;
00319                   px = ex;
00320                 }
00321               } while (--i != 0);
00322             } else {
00323               do {
00324                 Script* ex = e.next();
00325                 if (ex == NULL)
00326                   break;
00327                 ex->print(s_out);
00328                 delete ex;
00329               } while (--i != 0);
00330             }
00331             if (o.interrupt())
00332               CombinedStop::installCtrlHandler(false);
00333             Search::Statistics stat = e.statistics();
00334             s_out << endl;
00335             if (e.stopped()) {
00336               l_out << "Search engine stopped..." << endl
00337                     << "\treason: ";
00338               int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
00339               if (r & CombinedStop::SR_INT)
00340                 l_out << "user interrupt " << endl;
00341               else {
00342                 if (r & CombinedStop::SR_NODE)
00343                   l_out << "node ";
00344                 if (r & CombinedStop::SR_FAIL)
00345                   l_out << "fail ";
00346                 if (r & CombinedStop::SR_TIME)
00347                   l_out << "time ";
00348                 l_out << "limit reached" << endl << endl;
00349               }
00350             }
00351             l_out << "Initial" << endl
00352                   << "\tpropagators: " << n_p << endl
00353                   << "\tbranchers:   " << n_b << endl
00354                   << endl
00355                   << "Summary" << endl
00356                   << "\truntime:      ";
00357             stop(t, l_out);
00358             l_out << endl
00359                   << "\tsolutions:    "
00360                   << ::abs(static_cast<int>(o.solutions()) - i) << endl
00361                   << "\tpropagations: " << stat.propagate << endl
00362                   << "\tnodes:        " << stat.node << endl
00363                   << "\tfailures:     " << stat.fail << endl
00364                   << "\trestarts:     " << stat.restart << endl
00365                   << "\tno-goods:     " << stat.nogood << endl
00366                   << "\tpeak depth:   " << stat.depth << endl
00367 #ifdef GECODE_PEAKHEAP
00368                   << "\tpeak memory:  "
00369                   << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00370                   << endl
00371 #endif
00372                   << endl;
00373           }
00374           delete so.stop;
00375         }
00376         break;
00377       case SM_STAT:
00378         {
00379           l_out << o.name() << endl;
00380           Support::Timer t;
00381           int i = o.solutions();
00382           t.start();
00383           if (s == NULL)
00384             s = new Script(o);
00385           unsigned int n_p = s->propagators();
00386           unsigned int n_b = s->branchers();
00387           Search::Options so;
00388           so.clone   = false;
00389           so.threads = o.threads();
00390           so.c_d     = o.c_d();
00391           so.a_d     = o.a_d();
00392           so.stop    = CombinedStop::create(o.node(),o.fail(), o.time(),
00393                                             o.interrupt());
00394           so.cutoff  = createCutoff(o);
00395           so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00396           if (o.interrupt())
00397             CombinedStop::installCtrlHandler(true);
00398           {
00399             Meta<Engine,Script> e(s,so);
00400             do {
00401               Script* ex = e.next();
00402               if (ex == NULL)
00403                 break;
00404               delete ex;
00405             } while (--i != 0);
00406             if (o.interrupt())
00407               CombinedStop::installCtrlHandler(false);
00408             Search::Statistics stat = e.statistics();
00409             l_out << endl
00410                   << "\tpropagators:  " << n_p << endl
00411                   << "\tbranchers:    " << n_b << endl
00412                   << "\truntime:      ";
00413             stop(t, l_out);
00414             l_out << endl
00415                   << "\tsolutions:    "
00416                   << ::abs(static_cast<int>(o.solutions()) - i) << endl
00417                   << "\tpropagations: " << stat.propagate << endl
00418                   << "\tnodes:        " << stat.node << endl
00419                   << "\tfailures:     " << stat.fail << endl
00420                   << "\trestarts:     " << stat.restart << endl
00421                   << "\tno-goods:     " << stat.nogood << endl
00422                   << "\tpeak depth:   " << stat.depth << endl
00423 #ifdef GECODE_PEAKHEAP
00424                   << "\tpeak memory:  "
00425                   << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00426                   << endl
00427 #endif
00428                   << endl;
00429           }
00430           delete so.stop;
00431         }
00432         break;
00433       case SM_TIME:
00434         {
00435           l_out << o.name() << endl;
00436           Support::Timer t;
00437           double* ts = new double[o.samples()];
00438           bool stopped = false;
00439           for (unsigned int s = o.samples(); !stopped && s--; ) {
00440             t.start();
00441             for (unsigned int k = o.iterations(); !stopped && k--; ) {
00442               unsigned int i = o.solutions();
00443               Script* s = new Script(o);
00444               Search::Options so;
00445               so.clone   = false;
00446               so.threads = o.threads();
00447               so.c_d     = o.c_d();
00448               so.a_d     = o.a_d();
00449               so.stop    = CombinedStop::create(o.node(),o.fail(), o.time(), 
00450                                                 false);
00451               so.cutoff  = createCutoff(o);
00452               so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00453               {
00454                 Meta<Engine,Script> e(s,so);
00455                 do {
00456                   Script* ex = e.next();
00457                   if (ex == NULL)
00458                     break;
00459                   delete ex;
00460                 } while (--i != 0);
00461                 if (e.stopped())
00462                   stopped = true;
00463               }
00464               delete so.stop;
00465             }
00466             ts[s] = t.stop() / o.iterations();
00467           }
00468           if (stopped) {
00469             l_out << "\tSTOPPED" << endl;
00470           } else {
00471             double m = am(ts,o.samples());
00472             double d = dev(ts,o.samples()) * 100.0;
00473             l_out << "\truntime: "
00474                  << setw(20) << right
00475                  << showpoint << fixed
00476                  << setprecision(6) << m << "ms"
00477                  << setprecision(2) << " (" << d << "% deviation)"
00478                  << endl;
00479           }
00480           delete [] ts;
00481         }
00482         break;
00483       }
00484     } catch (Exception& e) {
00485       cerr << "Exception: " << e.what() << "." << endl
00486            << "Stopping..." << endl;
00487       if (sol_file.is_open())
00488         sol_file.close();
00489       if (log_file.is_open())
00490         log_file.close();
00491       exit(EXIT_FAILURE);
00492     }
00493     if (sol_file.is_open())
00494       sol_file.close();
00495     if (log_file.is_open())
00496       log_file.close();
00497   }
00498 
00499 }}
00500 
00501 // STATISTICS: driver-any