Generated on Tue Jul 27 2010 21:59:09 for Gecode by doxygen 1.7.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: 2010-06-01 13:59:14 +0200 (Tue, 01 Jun 2010) $ by $Author: tack $
00011  *     $Revision: 10996 $
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 
00042 #ifndef GECODE_THREADS_WINDOWS
00043 #include <csignal>
00044 #endif
00045 
00046 namespace Gecode { namespace Driver {
00047 
00052   class Cutoff : public Search::Stop {
00053   private:
00054     Search::NodeStop* ns; 
00055     Search::FailStop* fs; 
00056     Search::TimeStop* ts; 
00057     GECODE_DRIVER_EXPORT
00058     static bool sigint;   
00059 
00060     Cutoff(unsigned int node, unsigned int fail, unsigned int time)
00061       : ns((node > 0) ? new Search::NodeStop(node) : NULL),
00062         fs((fail > 0) ? new Search::FailStop(fail) : NULL),
00063         ts((time > 0) ? new Search::TimeStop(time) : NULL) {
00064       sigint = false;
00065     }
00066   public:
00068     enum {
00069       SR_NODE = 1 << 0, 
00070       SR_FAIL = 1 << 1, 
00071       SR_TIME = 1 << 2, 
00072       SR_INT  = 1 << 3  
00073     };
00075     virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
00076       return
00077         sigint ||
00078         ((ns != NULL) && ns->stop(s,o)) ||
00079         ((fs != NULL) && fs->stop(s,o)) ||
00080         ((ts != NULL) && ts->stop(s,o));
00081     }
00083     int reason(const Search::Statistics& s, const Search::Options& o) {
00084       return 
00085         (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
00086         (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
00087         (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0) |
00088         (sigint                          ? SR_INT  : 0);
00089     }
00091     static Search::Stop*
00092     create(unsigned int node, unsigned int fail, unsigned int time,
00093            bool intr) {
00094       if ( (!intr) && (node == 0) && (fail == 0) && (time == 0))
00095         return NULL;
00096       else
00097         return new Cutoff(node,fail,time);
00098     }
00099 #ifdef GECODE_THREADS_WINDOWS
00100 
00101     static BOOL interrupt(DWORD t) {
00102       if (t == CTRL_C_EVENT) {
00103         sigint = true;
00104         installCtrlHandler(false,true);
00105         return true;
00106       }
00107       return false;
00108     }
00109 #else
00110 
00111     static void
00112     interrupt(int) {
00113       sigint = true;
00114       installCtrlHandler(false,true);
00115     }
00116 #endif
00117 
00118     static void installCtrlHandler(bool install, bool force=false) {
00119       if (force || !sigint) {
00120 #ifdef GECODE_THREADS_WINDOWS
00121         SetConsoleCtrlHandler( (PHANDLER_ROUTINE) interrupt, install);
00122 #else
00123         std::signal(SIGINT, install ? interrupt : SIG_DFL);
00124 #endif
00125       }
00126     }
00128     ~Cutoff(void) {
00129       delete ns; delete fs; delete ts;
00130     }
00131   };
00132 
00137   GECODE_DRIVER_EXPORT void 
00138   stop(Support::Timer& t, std::ostream& os);
00139 
00143   GECODE_DRIVER_EXPORT double
00144   am(double t[], int n);
00145   
00149   GECODE_DRIVER_EXPORT double
00150   dev(double t[], int n);
00151   
00152 #ifdef GECODE_HAS_GIST
00153   
00157   template<class Engine>
00158   class GistEngine {
00159   };
00160   
00162   template<typename S>
00163   class GistEngine<DFS<S> > {
00164   public:
00165     static void explore(S* root, const Gist::Options& opt) {
00166       (void) Gist::dfs(root, opt);
00167     }
00168   };
00169   
00171   template<typename S>
00172   class GistEngine<LDS<S> > {
00173   public:
00174     static void explore(S* root, const Gist::Options& opt) {
00175       (void) Gist::dfs(root, opt);
00176     }
00177   };
00178   
00180   template<typename S>
00181   class GistEngine<BAB<S> > {
00182   public:
00183     static void explore(S* root, const Gist::Options& opt) {
00184       (void) Gist::bab(root, opt);
00185     }
00186   };
00187   
00189   template<typename S>
00190   class GistEngine<Restart<S> > {
00191   public:
00192     static void explore(S* root, const Gist::Options& opt) {
00193       (void) Gist::bab(root, opt);
00194     }
00195   };
00196   
00197 #endif
00198 
00199   template<class Space>
00200   template<class Script, template<class> class Engine, class Options>
00201   void
00202   ScriptBase<Space>::run(const Options& o) {
00203     using namespace std;
00204     try {
00205       switch (o.mode()) {
00206       case SM_GIST:
00207 #ifdef GECODE_HAS_GIST
00208         {
00209           Gist::Print<Script> pi(o.name());
00210           Gist::VarComparator<Script> vc(o.name());
00211           Gist::Options opt;
00212           opt.inspect.click(&pi);
00213           opt.inspect.compare(&vc);
00214           opt.clone = false;
00215           opt.c_d   = o.c_d();
00216           opt.a_d   = o.a_d();
00217           for (int i=0; o.inspect.click(i) != NULL; i++)
00218             opt.inspect.click(o.inspect.click(i));
00219           for (int i=0; o.inspect.solution(i) != NULL; i++)
00220             opt.inspect.solution(o.inspect.solution(i));
00221           for (int i=0; o.inspect.move(i) != NULL; i++)
00222             opt.inspect.move(o.inspect.move(i));
00223           for (int i=0; o.inspect.compare(i) != NULL; i++)
00224             opt.inspect.compare(o.inspect.compare(i));
00225           Script* s = new Script(o);
00226           (void) GistEngine<Engine<Script> >::explore(s, opt);
00227         }
00228         break;
00229         // If Gist is not available, fall through
00230 #endif
00231       case SM_SOLUTION:
00232         {
00233           cout << o.name() << endl;
00234           Support::Timer t;
00235           int i = o.solutions();
00236           t.start();
00237           Script* s = new Script(o);
00238           unsigned int n_p = s->propagators();
00239           unsigned int n_b = s->branchers();
00240           Search::Options so;
00241           so.threads = o.threads();
00242           so.c_d     = o.c_d();
00243           so.a_d     = o.a_d();
00244           so.stop    = Cutoff::create(o.node(),o.fail(), o.time(), 
00245                                       o.interrupt());
00246           so.clone   = false;
00247           if (o.interrupt())
00248             Cutoff::installCtrlHandler(true);
00249           Engine<Script> e(s,so);
00250           do {
00251             Script* ex = e.next();
00252             if (ex == NULL)
00253               break;
00254             ex->print(std::cout);
00255             delete ex;
00256           } while (--i != 0);
00257           if (o.interrupt())
00258             Cutoff::installCtrlHandler(false);
00259           Search::Statistics stat = e.statistics();
00260           cout << endl;
00261           if (e.stopped()) {
00262             cout << "Search engine stopped..." << endl
00263                  << "\treason: ";
00264             int r = static_cast<Cutoff*>(so.stop)->reason(stat,so);
00265             if (r & Cutoff::SR_INT)
00266               cout << "user interrupt " << endl;
00267             else {
00268               if (r & Cutoff::SR_NODE)
00269                 cout << "node ";
00270               if (r & Cutoff::SR_FAIL)
00271                 cout << "fail ";
00272               if (r & Cutoff::SR_TIME)
00273                 cout << "time ";
00274               cout << "limit reached" << endl << endl;
00275             }
00276           }
00277           cout << "Initial" << endl
00278                << "\tpropagators: " << n_p << endl
00279                << "\tbranchers:   " << n_b << endl
00280                << endl
00281                << "Summary" << endl
00282                << "\truntime:      ";
00283           stop(t, cout);
00284           cout << endl
00285                << "\tsolutions:    "
00286                << ::abs(static_cast<int>(o.solutions()) - i) << endl
00287                << "\tpropagations: " << stat.propagate << endl
00288                << "\tnodes:        " << stat.node << endl
00289                << "\tfailures:     " << stat.fail << endl
00290                << "\tpeak depth:   " << stat.depth << endl
00291                << "\tpeak memory:  "
00292                << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00293                << endl;
00294         }
00295         break;
00296       case SM_STAT:
00297         {
00298           cout << o.name() << endl;
00299           Support::Timer t;
00300           int i = o.solutions();
00301           t.start();
00302           Script* s = new Script(o);
00303           unsigned int n_p = s->propagators();
00304           unsigned int n_b = s->branchers();
00305           Search::Options so;
00306           so.clone   = false;
00307           so.threads = o.threads();
00308           so.c_d     = o.c_d();
00309           so.a_d     = o.a_d();
00310           so.stop    = Cutoff::create(o.node(),o.fail(), o.time(),
00311                                       o.interrupt());
00312           if (o.interrupt())
00313             Cutoff::installCtrlHandler(true);
00314           Engine<Script> e(s,so);
00315           do {
00316             Script* ex = e.next();
00317             if (ex == NULL)
00318               break;
00319             delete ex;
00320           } while (--i != 0);
00321           if (o.interrupt())
00322             Cutoff::installCtrlHandler(false);
00323           Search::Statistics stat = e.statistics();
00324           cout << endl
00325                << "\tpropagators:  " << n_p << endl
00326                << "\tbranchers:    " << n_b << endl
00327                << "\truntime:      ";
00328           stop(t, cout);
00329           cout << endl
00330                << "\tsolutions:    "
00331                << ::abs(static_cast<int>(o.solutions()) - i) << endl
00332                << "\tpropagations: " << stat.propagate << endl
00333                << "\tnodes:        " << stat.node << endl
00334                << "\tfailures:     " << stat.fail << endl
00335                << "\tpeak depth:   " << stat.depth << endl
00336                << "\tpeak memory:  "
00337                << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00338                << endl;
00339         }
00340         break;
00341       case SM_TIME:
00342         {
00343           cout << o.name() << endl;
00344           Support::Timer t;
00345           double* ts = new double[o.samples()];
00346           bool stopped = false;
00347           for (unsigned int s = o.samples(); !stopped && s--; ) {
00348             t.start();
00349             for (unsigned int k = o.iterations(); !stopped && k--; ) {
00350               unsigned int i = o.solutions();
00351               Script* s = new Script(o);
00352               Search::Options so;
00353               so.clone   = false;
00354               so.threads = o.threads();
00355               so.c_d     = o.c_d();
00356               so.a_d     = o.a_d();
00357               so.stop    = Cutoff::create(o.node(),o.fail(), o.time(), false);
00358               Engine<Script> e(s,so);
00359               do {
00360                 Script* ex = e.next();
00361                 if (ex == NULL)
00362                   break;
00363                 delete ex;
00364               } while (--i != 0);
00365               if (e.stopped())
00366                 stopped = true;
00367             }
00368             ts[s] = t.stop() / o.iterations();
00369           }
00370           if (stopped) {
00371             cout << "\tSTOPPED" << endl;
00372           } else {
00373             double m = am(ts,o.samples());
00374             double d = dev(ts,o.samples()) * 100.0;
00375             cout << "\tRuntime: "
00376                  << setw(20) << right
00377                  << showpoint << fixed
00378                  << setprecision(6) << m << "ms"
00379                  << setprecision(2) << " (" << d << "% deviation)"
00380                  << endl;
00381           }
00382           delete [] ts;
00383         }
00384         break;
00385       }
00386     } catch (Exception e) {
00387       cerr << "Exception: " << e.what() << "." << endl
00388            << "Stopping..." << endl;
00389       exit(EXIT_FAILURE);
00390     }
00391   }
00392 
00393 }}
00394 
00395 // STATISTICS: driver-any