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