Generated on Mon May 10 06:46:30 2010 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  *  Last modified:
00010  *     $Date: 2010-04-06 14:58:53 +0200 (Tue, 06 Apr 2010) $ by $Author: tack $
00011  *     $Revision: 10649 $
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 namespace Gecode { namespace Driver {
00043 
00048   class Cutoff : public Search::Stop {
00049   private:
00050     Search::NodeStop* ns; 
00051     Search::FailStop* fs; 
00052     Search::TimeStop* ts; 
00053 
00054     Cutoff(unsigned int node, unsigned int fail, unsigned int time)
00055       : ns((node > 0) ? new Search::NodeStop(node) : NULL),
00056         fs((fail > 0) ? new Search::FailStop(fail) : NULL),
00057         ts((time > 0) ? new Search::TimeStop(time) : NULL) {}
00058   public:
00060     enum {
00061       SR_NODE = 1 << 0, 
00062       SR_FAIL = 1 << 1, 
00063       SR_TIME = 1 << 2  
00064     };
00066     virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
00067       return
00068         ((ns != NULL) && ns->stop(s,o)) ||
00069         ((fs != NULL) && fs->stop(s,o)) ||
00070         ((ts != NULL) && ts->stop(s,o));
00071     }
00073     int reason(const Search::Statistics& s, const Search::Options& o) {
00074       return 
00075         (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
00076         (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
00077         (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0);
00078     }
00080     static Search::Stop*
00081     create(unsigned int node, unsigned int fail, unsigned int time) {
00082       if ((node == 0) && (fail == 0) && (time == 0))
00083         return NULL;
00084       else
00085         return new Cutoff(node,fail,time);
00086     }
00088     ~Cutoff(void) {
00089       delete ns; delete fs; delete ts;
00090     }
00091   };
00092 
00097   GECODE_DRIVER_EXPORT void 
00098   stop(Support::Timer& t, std::ostream& os);
00099 
00103   GECODE_DRIVER_EXPORT double
00104   am(double t[], int n);
00105   
00109   GECODE_DRIVER_EXPORT double
00110   dev(double t[], int n);
00111   
00112 #ifdef GECODE_HAS_GIST
00113   
00117   template<class Engine>
00118   class GistEngine {
00119   };
00120   
00122   template<typename S>
00123   class GistEngine<DFS<S> > {
00124   public:
00125     static void explore(S* root, const Gist::Options& opt) {
00126       (void) Gist::dfs(root, opt);
00127     }
00128   };
00129   
00131   template<typename S>
00132   class GistEngine<LDS<S> > {
00133   public:
00134     static void explore(S* root, const Gist::Options& opt) {
00135       (void) Gist::dfs(root, opt);
00136     }
00137   };
00138   
00140   template<typename S>
00141   class GistEngine<BAB<S> > {
00142   public:
00143     static void explore(S* root, const Gist::Options& opt) {
00144       (void) Gist::bab(root, opt);
00145     }
00146   };
00147   
00149   template<typename S>
00150   class GistEngine<Restart<S> > {
00151   public:
00152     static void explore(S* root, const Gist::Options& opt) {
00153       (void) Gist::bab(root, opt);
00154     }
00155   };
00156   
00157 #endif
00158 
00159   template<class Space>
00160   template<class Script, template<class> class Engine, class Options>
00161   void
00162   ScriptBase<Space>::run(const Options& o) {
00163     using namespace std;
00164     try {
00165       switch (o.mode()) {
00166       case SM_GIST:
00167 #ifdef GECODE_HAS_GIST
00168         {
00169           Gist::Print<Script> pi(o.name());
00170           Gist::VarComparator<Script> vc(o.name());
00171           Gist::Options opt;
00172           opt.inspect.click(&pi);
00173           opt.inspect.compare(&vc);
00174           opt.clone = false;
00175           opt.c_d   = o.c_d();
00176           opt.a_d   = o.a_d();
00177           for (int i=0; o.inspect.click(i) != NULL; i++)
00178             opt.inspect.click(o.inspect.click(i));
00179           for (int i=0; o.inspect.solution(i) != NULL; i++)
00180             opt.inspect.solution(o.inspect.solution(i));
00181           for (int i=0; o.inspect.move(i) != NULL; i++)
00182             opt.inspect.move(o.inspect.move(i));
00183           for (int i=0; o.inspect.compare(i) != NULL; i++)
00184             opt.inspect.compare(o.inspect.compare(i));
00185           Script* s = new Script(o);
00186           (void) GistEngine<Engine<Script> >::explore(s, opt);
00187         }
00188         break;
00189         // If Gist is not available, fall through
00190 #endif
00191       case SM_SOLUTION:
00192         {
00193           cout << o.name() << endl;
00194           Support::Timer t;
00195           int i = o.solutions();
00196           t.start();
00197           Script* s = new Script(o);
00198           unsigned int n_p = s->propagators();
00199           unsigned int n_b = s->branchers();
00200           Search::Options so;
00201           so.threads = o.threads();
00202           so.c_d     = o.c_d();
00203           so.a_d     = o.a_d();
00204           so.stop    = Cutoff::create(o.node(),o.fail(), o.time());
00205           so.clone   = false;
00206           Engine<Script> e(s,so);
00207           do {
00208             Script* ex = e.next();
00209             if (ex == NULL)
00210               break;
00211             ex->print(std::cout);
00212             delete ex;
00213           } while (--i != 0);
00214           Search::Statistics stat = e.statistics();
00215           cout << endl;
00216           if (e.stopped()) {
00217             cout << "Search engine stopped..." << endl
00218                  << "\treason: ";
00219             int r = static_cast<Cutoff*>(so.stop)->reason(stat,so);
00220             if (r & Cutoff::SR_NODE)
00221               cout << "node ";
00222             if (r & Cutoff::SR_FAIL)
00223               cout << "fail ";
00224             if (r & Cutoff::SR_TIME)
00225               cout << "time ";
00226             cout << "limit reached" << endl << endl;
00227           }
00228           cout << "Initial" << endl
00229                << "\tpropagators: " << n_p << endl
00230                << "\tbranchers:   " << n_b << endl
00231                << endl
00232                << "Summary" << endl
00233                << "\truntime:      ";
00234           stop(t, cout);
00235           cout << endl
00236                << "\tsolutions:    "
00237                << ::abs(static_cast<int>(o.solutions()) - i) << endl
00238                << "\tpropagations: " << stat.propagate << endl
00239                << "\tnodes:        " << stat.node << endl
00240                << "\tfailures:     " << stat.fail << endl
00241                << "\tpeak depth:   " << stat.depth << endl
00242                << "\tpeak memory:  "
00243                << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00244                << endl;
00245         }
00246         break;
00247       case SM_STAT:
00248         {
00249           cout << o.name() << endl;
00250           Support::Timer t;
00251           int i = o.solutions();
00252           t.start();
00253           Script* s = new Script(o);
00254           unsigned int n_p = s->propagators();
00255           unsigned int n_b = s->branchers();
00256           Search::Options so;
00257           so.clone   = false;
00258           so.threads = o.threads();
00259           so.c_d     = o.c_d();
00260           so.a_d     = o.a_d();
00261           so.stop    = Cutoff::create(o.node(),o.fail(), o.time());
00262           Engine<Script> e(s,so);
00263           do {
00264             Script* ex = e.next();
00265             if (ex == NULL)
00266               break;
00267             delete ex;
00268           } while (--i != 0);
00269           Search::Statistics stat = e.statistics();
00270           cout << endl
00271                << "\tpropagators: " << n_p << endl
00272                << "\tbranchers:   " << n_b << 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_TIME:
00288         {
00289           cout << o.name() << endl;
00290           Support::Timer t;
00291           double* ts = new double[o.samples()];
00292           for (unsigned int s = o.samples(); s--; ) {
00293             t.start();
00294             for (unsigned int k = o.iterations(); k--; ) {
00295               unsigned int i = o.solutions();
00296               Script* s = new Script(o);
00297               Search::Options so;
00298               so.clone   = false;
00299               so.threads = o.threads();
00300               so.c_d     = o.c_d();
00301               so.a_d     = o.a_d();
00302               so.stop    = Cutoff::create(o.node(),o.fail(), o.time());
00303               Engine<Script> e(s,so);
00304               do {
00305                 Script* ex = e.next();
00306                 if (ex == NULL)
00307                   break;
00308                 delete ex;
00309               } while (--i != 0);
00310             }
00311             ts[s] = t.stop() / o.iterations();
00312           }
00313           double m = am(ts,o.samples());
00314           double d = dev(ts,o.samples()) * 100.0;
00315           delete [] ts;
00316           cout << "\tRuntime: "
00317                << setw(20) << right
00318                << showpoint << fixed
00319                << setprecision(6) << m << "ms"
00320                << setprecision(2) << " (" << d << "% deviation)"
00321                << endl;
00322         }
00323         break;
00324       }
00325     } catch (Exception e) {
00326       cout << "Exception: " << e.what() << "." << endl
00327            << "Stopping..." << endl;
00328     }
00329   }
00330 
00331 }}
00332 
00333 // STATISTICS: driver-any