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