Generated on Fri May 13 2011 22:41:13 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-10-09 13:58:12 +0200 (Sat, 09 Oct 2010) $ by $Author: schulte $
00011  *     $Revision: 11498 $
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<BAB<S> > {
00173   public:
00174     static void explore(S* root, const Gist::Options& opt) {
00175       (void) Gist::bab(root, opt);
00176     }
00177   };
00178   
00180   template<typename S>
00181   class GistEngine<Restart<S> > {
00182   public:
00183     static void explore(S* root, const Gist::Options& opt) {
00184       (void) Gist::bab(root, opt);
00185     }
00186   };
00187   
00188 #endif
00189 
00190   template<class Space>
00191   template<class Script, template<class> class Engine, class Options>
00192   void
00193   ScriptBase<Space>::run(const Options& o) {
00194     using namespace std;
00195     try {
00196       switch (o.mode()) {
00197       case SM_GIST:
00198 #ifdef GECODE_HAS_GIST
00199         {
00200           Gist::Print<Script> pi(o.name());
00201           Gist::VarComparator<Script> vc(o.name());
00202           Gist::Options opt;
00203           opt.inspect.click(&pi);
00204           opt.inspect.compare(&vc);
00205           opt.clone = false;
00206           opt.c_d   = o.c_d();
00207           opt.a_d   = o.a_d();
00208           for (int i=0; o.inspect.click(i) != NULL; i++)
00209             opt.inspect.click(o.inspect.click(i));
00210           for (int i=0; o.inspect.solution(i) != NULL; i++)
00211             opt.inspect.solution(o.inspect.solution(i));
00212           for (int i=0; o.inspect.move(i) != NULL; i++)
00213             opt.inspect.move(o.inspect.move(i));
00214           for (int i=0; o.inspect.compare(i) != NULL; i++)
00215             opt.inspect.compare(o.inspect.compare(i));
00216           Script* s = new Script(o);
00217           (void) GistEngine<Engine<Script> >::explore(s, opt);
00218         }
00219         break;
00220         // If Gist is not available, fall through
00221 #endif
00222       case SM_SOLUTION:
00223         {
00224           cout << o.name() << endl;
00225           Support::Timer t;
00226           int i = o.solutions();
00227           t.start();
00228           Script* s = new Script(o);
00229           unsigned int n_p = s->propagators();
00230           unsigned int n_b = s->branchers();
00231           Search::Options so;
00232           so.threads = o.threads();
00233           so.c_d     = o.c_d();
00234           so.a_d     = o.a_d();
00235           so.stop    = Cutoff::create(o.node(),o.fail(), o.time(), 
00236                                       o.interrupt());
00237           so.clone   = false;
00238           if (o.interrupt())
00239             Cutoff::installCtrlHandler(true);
00240           Engine<Script> e(s,so);
00241           do {
00242             Script* ex = e.next();
00243             if (ex == NULL)
00244               break;
00245             ex->print(std::cout);
00246             delete ex;
00247           } while (--i != 0);
00248           if (o.interrupt())
00249             Cutoff::installCtrlHandler(false);
00250           Search::Statistics stat = e.statistics();
00251           cout << endl;
00252           if (e.stopped()) {
00253             cout << "Search engine stopped..." << endl
00254                  << "\treason: ";
00255             int r = static_cast<Cutoff*>(so.stop)->reason(stat,so);
00256             if (r & Cutoff::SR_INT)
00257               cout << "user interrupt " << endl;
00258             else {
00259               if (r & Cutoff::SR_NODE)
00260                 cout << "node ";
00261               if (r & Cutoff::SR_FAIL)
00262                 cout << "fail ";
00263               if (r & Cutoff::SR_TIME)
00264                 cout << "time ";
00265               cout << "limit reached" << endl << endl;
00266             }
00267           }
00268           cout << "Initial" << endl
00269                << "\tpropagators: " << n_p << endl
00270                << "\tbranchers:   " << n_b << endl
00271                << endl
00272                << "Summary" << endl
00273                << "\truntime:      ";
00274           stop(t, cout);
00275           cout << endl
00276                << "\tsolutions:    "
00277                << ::abs(static_cast<int>(o.solutions()) - i) << endl
00278                << "\tpropagations: " << stat.propagate << endl
00279                << "\tnodes:        " << stat.node << endl
00280                << "\tfailures:     " << stat.fail << endl
00281                << "\tpeak depth:   " << stat.depth << endl
00282                << "\tpeak memory:  "
00283                << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00284                << endl;
00285         }
00286         break;
00287       case SM_STAT:
00288         {
00289           cout << o.name() << endl;
00290           Support::Timer t;
00291           int i = o.solutions();
00292           t.start();
00293           Script* s = new Script(o);
00294           unsigned int n_p = s->propagators();
00295           unsigned int n_b = s->branchers();
00296           Search::Options so;
00297           so.clone   = false;
00298           so.threads = o.threads();
00299           so.c_d     = o.c_d();
00300           so.a_d     = o.a_d();
00301           so.stop    = Cutoff::create(o.node(),o.fail(), o.time(),
00302                                       o.interrupt());
00303           if (o.interrupt())
00304             Cutoff::installCtrlHandler(true);
00305           Engine<Script> e(s,so);
00306           do {
00307             Script* ex = e.next();
00308             if (ex == NULL)
00309               break;
00310             delete ex;
00311           } while (--i != 0);
00312           if (o.interrupt())
00313             Cutoff::installCtrlHandler(false);
00314           Search::Statistics stat = e.statistics();
00315           cout << endl
00316                << "\tpropagators:  " << n_p << endl
00317                << "\tbranchers:    " << n_b << endl
00318                << "\truntime:      ";
00319           stop(t, cout);
00320           cout << endl
00321                << "\tsolutions:    "
00322                << ::abs(static_cast<int>(o.solutions()) - i) << endl
00323                << "\tpropagations: " << stat.propagate << endl
00324                << "\tnodes:        " << stat.node << endl
00325                << "\tfailures:     " << stat.fail << endl
00326                << "\tpeak depth:   " << stat.depth << endl
00327                << "\tpeak memory:  "
00328                << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00329                << endl;
00330         }
00331         break;
00332       case SM_TIME:
00333         {
00334           cout << o.name() << endl;
00335           Support::Timer t;
00336           double* ts = new double[o.samples()];
00337           bool stopped = false;
00338           for (unsigned int s = o.samples(); !stopped && s--; ) {
00339             t.start();
00340             for (unsigned int k = o.iterations(); !stopped && k--; ) {
00341               unsigned int i = o.solutions();
00342               Script* s = new Script(o);
00343               Search::Options so;
00344               so.clone   = false;
00345               so.threads = o.threads();
00346               so.c_d     = o.c_d();
00347               so.a_d     = o.a_d();
00348               so.stop    = Cutoff::create(o.node(),o.fail(), o.time(), false);
00349               Engine<Script> e(s,so);
00350               do {
00351                 Script* ex = e.next();
00352                 if (ex == NULL)
00353                   break;
00354                 delete ex;
00355               } while (--i != 0);
00356               if (e.stopped())
00357                 stopped = true;
00358             }
00359             ts[s] = t.stop() / o.iterations();
00360           }
00361           if (stopped) {
00362             cout << "\tSTOPPED" << endl;
00363           } else {
00364             double m = am(ts,o.samples());
00365             double d = dev(ts,o.samples()) * 100.0;
00366             cout << "\tRuntime: "
00367                  << setw(20) << right
00368                  << showpoint << fixed
00369                  << setprecision(6) << m << "ms"
00370                  << setprecision(2) << " (" << d << "% deviation)"
00371                  << endl;
00372           }
00373           delete [] ts;
00374         }
00375         break;
00376       }
00377     } catch (Exception e) {
00378       cerr << "Exception: " << e.what() << "." << endl
00379            << "Stopping..." << endl;
00380       exit(EXIT_FAILURE);
00381     }
00382   }
00383 
00384 }}
00385 
00386 // STATISTICS: driver-any