Generated on Mon Nov 30 23:53:18 2009 for Gecode by doxygen 1.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: 2009-10-13 15:19:20 +0200 (Tue, 13 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9887 $
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     virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
00061       return
00062         ((ns != NULL) && ns->stop(s,o)) ||
00063         ((fs != NULL) && fs->stop(s,o)) ||
00064         ((ts != NULL) && ts->stop(s,o));
00065     }
00067     static Search::Stop*
00068     create(unsigned int node, unsigned int fail, unsigned int time) {
00069       if ((node == 0) && (fail == 0) && (time == 0))
00070         return NULL;
00071       else
00072         return new Cutoff(node,fail,time);
00073     }
00075     ~Cutoff(void) {
00076       delete ns; delete fs; delete ts;
00077     }
00078   };
00079 
00084   GECODE_DRIVER_EXPORT void 
00085   stop(Support::Timer& t, std::ostream& os);
00086 
00090   GECODE_DRIVER_EXPORT double
00091   am(double t[], int n);
00092   
00096   GECODE_DRIVER_EXPORT double
00097   dev(double t[], int n);
00098   
00099 #ifdef GECODE_HAS_GIST
00100   
00104   template<class Engine>
00105   class GistEngine {
00106   };
00107   
00109   template<typename S>
00110   class GistEngine<DFS<S> > {
00111   public:
00112     static void explore(S* root, const Gist::Options& opt) {
00113       (void) Gist::dfs(root, opt);
00114     }
00115   };
00116   
00118   template<typename S>
00119   class GistEngine<LDS<S> > {
00120   public:
00121     static void explore(S* root, const Gist::Options& opt) {
00122       (void) Gist::dfs(root, opt);
00123     }
00124   };
00125   
00127   template<typename S>
00128   class GistEngine<BAB<S> > {
00129   public:
00130     static void explore(S* root, const Gist::Options& opt) {
00131       (void) Gist::bab(root, opt);
00132     }
00133   };
00134   
00136   template<typename S>
00137   class GistEngine<Restart<S> > {
00138   public:
00139     static void explore(S* root, const Gist::Options& opt) {
00140       (void) Gist::bab(root, opt);
00141     }
00142   };
00143   
00144 #endif
00145 
00146   template<class Space>
00147   template<class Script, template<class> class Engine, class Options>
00148   void
00149   ScriptBase<Space>::run(const Options& o) {
00150     using namespace std;
00151     try {
00152       switch (o.mode()) {
00153       case SM_GIST:
00154 #ifdef GECODE_HAS_GIST
00155         {
00156           Gist::Print<Script> pi(o.name());
00157           Gist::Options opt;
00158           opt.inspect.click(&pi);
00159           opt.clone = false;
00160           opt.c_d   = o.c_d();
00161           opt.a_d   = o.a_d();
00162           Script* s = new Script(o);
00163           (void) GistEngine<Engine<Script> >::explore(s, opt);
00164         }
00165         break;
00166         // If Gist is not available, fall through
00167 #endif
00168       case SM_SOLUTION:
00169         {
00170           cout << o.name() << endl;
00171           Support::Timer t;
00172           int i = o.solutions();
00173           t.start();
00174           Script* s = new Script(o);
00175           unsigned int n_p = s->propagators();
00176           unsigned int n_b = s->branchers();
00177           Search::Options so;
00178           so.threads = o.threads();
00179           so.c_d     = o.c_d();
00180           so.a_d     = o.a_d();
00181           so.stop    = Cutoff::create(o.node(),o.fail(), o.time());
00182           so.clone   = false;
00183           Engine<Script> e(s,so);
00184           do {
00185             Script* ex = e.next();
00186             if (ex == NULL)
00187               break;
00188             ex->print(std::cout);
00189             delete ex;
00190           } while (--i != 0);
00191           Search::Statistics stat = e.statistics();
00192           cout << endl;
00193           cout << "Initial" << endl
00194                << "\tpropagators: " << n_p << endl
00195                << "\tbranchers:   " << n_b << endl
00196                << endl
00197                << "Summary" << endl
00198                << "\truntime:      ";
00199           stop(t, cout);
00200           cout << endl
00201                << "\tsolutions:    "
00202                << ::abs(static_cast<int>(o.solutions()) - i) << endl
00203                << "\tpropagations: " << stat.propagate << endl
00204                << "\tnodes:        " << stat.node << endl
00205                << "\tfailures:     " << stat.fail << endl
00206                << "\tpeak depth:   " << stat.depth << endl
00207                << "\tpeak memory:  "
00208                << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00209                << endl;
00210         }
00211         break;
00212       case SM_STAT:
00213         {
00214           cout << o.name() << endl;
00215           Support::Timer t;
00216           int i = o.solutions();
00217           t.start();
00218           Script* s = new Script(o);
00219           unsigned int n_p = s->propagators();
00220           unsigned int n_b = s->branchers();
00221           Search::Options so;
00222           so.clone   = false;
00223           so.threads = o.threads();
00224           so.c_d     = o.c_d();
00225           so.a_d     = o.a_d();
00226           so.stop    = Cutoff::create(o.node(),o.fail(), o.time());
00227           Engine<Script> e(s,so);
00228           do {
00229             Script* ex = e.next();
00230             if (ex == NULL)
00231               break;
00232             delete ex;
00233           } while (--i != 0);
00234           Search::Statistics stat = e.statistics();
00235           cout << endl
00236                << "\tpropagators: " << n_p << endl
00237                << "\tbranchers:   " << n_b << endl
00238                << "\truntime:      ";
00239           stop(t, cout);
00240           cout << endl
00241                << "\tsolutions:    "
00242                << ::abs(static_cast<int>(o.solutions()) - i) << endl
00243                << "\tpropagations: " << stat.propagate << endl
00244                << "\tnodes:        " << stat.node << endl
00245                << "\tfailures:     " << stat.fail << endl
00246                << "\tpeak depth:   " << stat.depth << endl
00247                << "\tpeak memory:  "
00248                << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00249                << endl;
00250         }
00251         break;
00252       case SM_TIME:
00253         {
00254           cout << o.name() << endl;
00255           Support::Timer t;
00256           double* ts = new double[o.samples()];
00257           for (unsigned int s = o.samples(); s--; ) {
00258             t.start();
00259             for (unsigned int k = o.iterations(); k--; ) {
00260               unsigned int i = o.solutions();
00261               Script* s = new Script(o);
00262               Search::Options so;
00263               so.clone   = false;
00264               so.threads = o.threads();
00265               so.c_d     = o.c_d();
00266               so.a_d     = o.a_d();
00267               so.stop    = Cutoff::create(o.node(),o.fail(), o.time());
00268               Engine<Script> e(s,so);
00269               do {
00270                 Script* ex = e.next();
00271                 if (ex == NULL)
00272                   break;
00273                 delete ex;
00274               } while (--i != 0);
00275             }
00276             ts[s] = t.stop() / o.iterations();
00277           }
00278           double m = am(ts,o.samples());
00279           double d = dev(ts,o.samples()) * 100.0;
00280           delete[] ts;
00281           cout << "\tRuntime: "
00282                << setw(20) << right
00283                << showpoint << fixed
00284                << setprecision(6) << m << "ms"
00285                << setprecision(2) << " (" << d << "% deviation)"
00286                << endl;
00287         }
00288         break;
00289       }
00290     } catch (Exception e) {
00291       cout << "Exception: " << e.what() << "." << endl
00292            << "Stopping..." << endl;
00293     }
00294   }
00295 
00296 }}
00297 
00298 // STATISTICS: driver-any