00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #include <iostream>
00040 #include <iomanip>
00041 #include <fstream>
00042 #include <cstring>
00043
00044 #ifndef GECODE_THREADS_WINDOWS
00045 #include <csignal>
00046 #endif
00047
00048 namespace Gecode { namespace Driver {
00049
00054 class CombinedStop : public Search::Stop {
00055 private:
00056 Search::NodeStop* ns;
00057 Search::FailStop* fs;
00058 Search::TimeStop* ts;
00059 GECODE_DRIVER_EXPORT
00060 static bool sigint;
00061
00062 CombinedStop(unsigned int node, unsigned int fail, unsigned int time)
00063 : ns((node > 0) ? new Search::NodeStop(node) : NULL),
00064 fs((fail > 0) ? new Search::FailStop(fail) : NULL),
00065 ts((time > 0) ? new Search::TimeStop(time) : NULL) {
00066 sigint = false;
00067 }
00068 public:
00070 enum {
00071 SR_NODE = 1 << 0,
00072 SR_FAIL = 1 << 1,
00073 SR_TIME = 1 << 2,
00074 SR_INT = 1 << 3
00075 };
00077 virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
00078 return
00079 sigint ||
00080 ((ns != NULL) && ns->stop(s,o)) ||
00081 ((fs != NULL) && fs->stop(s,o)) ||
00082 ((ts != NULL) && ts->stop(s,o));
00083 }
00085 int reason(const Search::Statistics& s, const Search::Options& o) {
00086 return
00087 (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
00088 (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
00089 (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0) |
00090 (sigint ? SR_INT : 0);
00091 }
00093 static Search::Stop*
00094 create(unsigned int node, unsigned int fail, unsigned int time,
00095 bool intr) {
00096 if ( (!intr) && (node == 0) && (fail == 0) && (time == 0))
00097 return NULL;
00098 else
00099 return new CombinedStop(node,fail,time);
00100 }
00101 #ifdef GECODE_THREADS_WINDOWS
00102
00103 static BOOL interrupt(DWORD t) {
00104 if (t == CTRL_C_EVENT) {
00105 sigint = true;
00106 installCtrlHandler(false,true);
00107 return true;
00108 }
00109 return false;
00110 }
00111 #else
00112
00113 static void
00114 interrupt(int) {
00115 sigint = true;
00116 installCtrlHandler(false,true);
00117 }
00118 #endif
00119
00120 static void installCtrlHandler(bool install, bool force=false) {
00121 if (force || !sigint) {
00122 #ifdef GECODE_THREADS_WINDOWS
00123 SetConsoleCtrlHandler( (PHANDLER_ROUTINE) interrupt, install);
00124 #else
00125 std::signal(SIGINT, install ? interrupt : SIG_DFL);
00126 #endif
00127 }
00128 }
00130 ~CombinedStop(void) {
00131 delete ns; delete fs; delete ts;
00132 }
00133 };
00134
00139 GECODE_DRIVER_EXPORT void
00140 stop(Support::Timer& t, std::ostream& os);
00141
00145 GECODE_DRIVER_EXPORT double
00146 am(double t[], int n);
00147
00151 GECODE_DRIVER_EXPORT double
00152 dev(double t[], int n);
00153
00155 template<class Options>
00156 inline Search::Cutoff*
00157 createCutoff(const Options& o) {
00158 switch (o.restart()) {
00159 case RM_NONE:
00160 return NULL;
00161 case RM_CONSTANT:
00162 return Search::Cutoff::constant(o.restart_scale());
00163 case RM_LINEAR:
00164 return Search::Cutoff::linear(o.restart_scale());
00165 case RM_LUBY:
00166 return Search::Cutoff::luby(o.restart_scale());
00167 case RM_GEOMETRIC:
00168 return Search::Cutoff::geometric(o.restart_scale(),o.restart_base());
00169 default: GECODE_NEVER;
00170 }
00171 return NULL;
00172 }
00173
00174
00175 #ifdef GECODE_HAS_GIST
00176
00180 template<class Engine>
00181 class GistEngine {
00182 public:
00183 static void explore(Space* root, const Gist::Options& opt) {
00184 (void) Gist::dfs(root, opt);
00185 }
00186 };
00187
00189 template<typename S>
00190 class GistEngine<DFS<S> > {
00191 public:
00192 static void explore(S* root, const Gist::Options& opt) {
00193 (void) Gist::dfs(root, opt);
00194 }
00195 };
00196
00198 template<typename S>
00199 class GistEngine<BAB<S> > {
00200 public:
00201 static void explore(S* root, const Gist::Options& opt) {
00202 (void) Gist::bab(root, opt);
00203 }
00204 };
00205
00206 #endif
00207
00208
00209 template<class Space>
00210 std::ostream&
00211 ScriptBase<Space>::select_ostream(const char* name, std::ofstream& ofs) {
00212 if (strcmp(name, "stdout") == 0) {
00213 return std::cout;
00214 } else if (strcmp(name, "stdlog") == 0) {
00215 return std::clog;
00216 } else if (strcmp(name, "stderr") == 0) {
00217 return std::cerr;
00218 } else {
00219 ofs.open(name);
00220 return ofs;
00221 }
00222 }
00223
00227 template<template<class> class E, class T>
00228 class EngineToMeta : public E<T> {
00229 public:
00230 EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
00231 };
00232
00233 template<class Space>
00234 template<class Script, template<class> class Engine, class Options>
00235 void
00236 ScriptBase<Space>::run(const Options& o, Script* s) {
00237 if (o.restart()==RM_NONE) {
00238 runMeta<Script,Engine,Options,EngineToMeta>(o,s);
00239 } else {
00240 runMeta<Script,Engine,Options,RBS>(o,s);
00241 }
00242 }
00243
00244 template<class Space>
00245 template<class Script, template<class> class Engine, class Options,
00246 template<template<class> class,class> class Meta>
00247 void
00248 ScriptBase<Space>::runMeta(const Options& o, Script* s) {
00249 using namespace std;
00250
00251 ofstream sol_file, log_file;
00252
00253 ostream& s_out = select_ostream(o.out_file(), sol_file);
00254 ostream& l_out = select_ostream(o.log_file(), log_file);
00255
00256 try {
00257 switch (o.mode()) {
00258 case SM_GIST:
00259 #ifdef GECODE_HAS_GIST
00260 {
00261 Gist::Print<Script> pi(o.name());
00262 Gist::VarComparator<Script> vc(o.name());
00263 Gist::Options opt;
00264 opt.inspect.click(&pi);
00265 opt.inspect.compare(&vc);
00266 opt.clone = false;
00267 opt.c_d = o.c_d();
00268 opt.a_d = o.a_d();
00269 for (int i=0; o.inspect.click(i) != NULL; i++)
00270 opt.inspect.click(o.inspect.click(i));
00271 for (int i=0; o.inspect.solution(i) != NULL; i++)
00272 opt.inspect.solution(o.inspect.solution(i));
00273 for (int i=0; o.inspect.move(i) != NULL; i++)
00274 opt.inspect.move(o.inspect.move(i));
00275 for (int i=0; o.inspect.compare(i) != NULL; i++)
00276 opt.inspect.compare(o.inspect.compare(i));
00277 if (s == NULL)
00278 s = new Script(o);
00279 (void) GistEngine<Engine<Script> >::explore(s, opt);
00280 }
00281 break;
00282
00283 #endif
00284 case SM_SOLUTION:
00285 {
00286 l_out << o.name() << endl;
00287 Support::Timer t;
00288 int i = o.solutions();
00289 t.start();
00290 if (s == NULL)
00291 s = new Script(o);
00292 unsigned int n_p = s->propagators();
00293 unsigned int n_b = s->branchers();
00294 Search::Options so;
00295 so.threads = o.threads();
00296 so.c_d = o.c_d();
00297 so.a_d = o.a_d();
00298 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
00299 o.interrupt());
00300 so.cutoff = createCutoff(o);
00301 so.clone = false;
00302 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00303 if (o.interrupt())
00304 CombinedStop::installCtrlHandler(true);
00305 {
00306 Meta<Engine,Script> e(s,so);
00307 if (o.print_last()) {
00308 Script* px = NULL;
00309 do {
00310 Script* ex = e.next();
00311 if (ex == NULL) {
00312 if (px != NULL) {
00313 px->print(s_out);
00314 delete px;
00315 }
00316 break;
00317 } else {
00318 delete px;
00319 px = ex;
00320 }
00321 } while (--i != 0);
00322 } else {
00323 do {
00324 Script* ex = e.next();
00325 if (ex == NULL)
00326 break;
00327 ex->print(s_out);
00328 delete ex;
00329 } while (--i != 0);
00330 }
00331 if (o.interrupt())
00332 CombinedStop::installCtrlHandler(false);
00333 Search::Statistics stat = e.statistics();
00334 s_out << endl;
00335 if (e.stopped()) {
00336 l_out << "Search engine stopped..." << endl
00337 << "\treason: ";
00338 int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
00339 if (r & CombinedStop::SR_INT)
00340 l_out << "user interrupt " << endl;
00341 else {
00342 if (r & CombinedStop::SR_NODE)
00343 l_out << "node ";
00344 if (r & CombinedStop::SR_FAIL)
00345 l_out << "fail ";
00346 if (r & CombinedStop::SR_TIME)
00347 l_out << "time ";
00348 l_out << "limit reached" << endl << endl;
00349 }
00350 }
00351 l_out << "Initial" << endl
00352 << "\tpropagators: " << n_p << endl
00353 << "\tbranchers: " << n_b << endl
00354 << endl
00355 << "Summary" << endl
00356 << "\truntime: ";
00357 stop(t, l_out);
00358 l_out << endl
00359 << "\tsolutions: "
00360 << ::abs(static_cast<int>(o.solutions()) - i) << endl
00361 << "\tpropagations: " << stat.propagate << endl
00362 << "\tnodes: " << stat.node << endl
00363 << "\tfailures: " << stat.fail << endl
00364 << "\trestarts: " << stat.restart << endl
00365 << "\tno-goods: " << stat.nogood << endl
00366 << "\tpeak depth: " << stat.depth << endl
00367 #ifdef GECODE_PEAKHEAP
00368 << "\tpeak memory: "
00369 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00370 << endl
00371 #endif
00372 << endl;
00373 }
00374 delete so.stop;
00375 }
00376 break;
00377 case SM_STAT:
00378 {
00379 l_out << o.name() << endl;
00380 Support::Timer t;
00381 int i = o.solutions();
00382 t.start();
00383 if (s == NULL)
00384 s = new Script(o);
00385 unsigned int n_p = s->propagators();
00386 unsigned int n_b = s->branchers();
00387 Search::Options so;
00388 so.clone = false;
00389 so.threads = o.threads();
00390 so.c_d = o.c_d();
00391 so.a_d = o.a_d();
00392 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
00393 o.interrupt());
00394 so.cutoff = createCutoff(o);
00395 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00396 if (o.interrupt())
00397 CombinedStop::installCtrlHandler(true);
00398 {
00399 Meta<Engine,Script> e(s,so);
00400 do {
00401 Script* ex = e.next();
00402 if (ex == NULL)
00403 break;
00404 delete ex;
00405 } while (--i != 0);
00406 if (o.interrupt())
00407 CombinedStop::installCtrlHandler(false);
00408 Search::Statistics stat = e.statistics();
00409 l_out << endl
00410 << "\tpropagators: " << n_p << endl
00411 << "\tbranchers: " << n_b << endl
00412 << "\truntime: ";
00413 stop(t, l_out);
00414 l_out << endl
00415 << "\tsolutions: "
00416 << ::abs(static_cast<int>(o.solutions()) - i) << endl
00417 << "\tpropagations: " << stat.propagate << endl
00418 << "\tnodes: " << stat.node << endl
00419 << "\tfailures: " << stat.fail << endl
00420 << "\trestarts: " << stat.restart << endl
00421 << "\tno-goods: " << stat.nogood << endl
00422 << "\tpeak depth: " << stat.depth << endl
00423 #ifdef GECODE_PEAKHEAP
00424 << "\tpeak memory: "
00425 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00426 << endl
00427 #endif
00428 << endl;
00429 }
00430 delete so.stop;
00431 }
00432 break;
00433 case SM_TIME:
00434 {
00435 l_out << o.name() << endl;
00436 Support::Timer t;
00437 double* ts = new double[o.samples()];
00438 bool stopped = false;
00439 for (unsigned int s = o.samples(); !stopped && s--; ) {
00440 t.start();
00441 for (unsigned int k = o.iterations(); !stopped && k--; ) {
00442 unsigned int i = o.solutions();
00443 Script* s = new Script(o);
00444 Search::Options so;
00445 so.clone = false;
00446 so.threads = o.threads();
00447 so.c_d = o.c_d();
00448 so.a_d = o.a_d();
00449 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
00450 false);
00451 so.cutoff = createCutoff(o);
00452 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00453 {
00454 Meta<Engine,Script> e(s,so);
00455 do {
00456 Script* ex = e.next();
00457 if (ex == NULL)
00458 break;
00459 delete ex;
00460 } while (--i != 0);
00461 if (e.stopped())
00462 stopped = true;
00463 }
00464 delete so.stop;
00465 }
00466 ts[s] = t.stop() / o.iterations();
00467 }
00468 if (stopped) {
00469 l_out << "\tSTOPPED" << endl;
00470 } else {
00471 double m = am(ts,o.samples());
00472 double d = dev(ts,o.samples()) * 100.0;
00473 l_out << "\truntime: "
00474 << setw(20) << right
00475 << showpoint << fixed
00476 << setprecision(6) << m << "ms"
00477 << setprecision(2) << " (" << d << "% deviation)"
00478 << endl;
00479 }
00480 delete [] ts;
00481 }
00482 break;
00483 }
00484 } catch (Exception& e) {
00485 cerr << "Exception: " << e.what() << "." << endl
00486 << "Stopping..." << endl;
00487 if (sol_file.is_open())
00488 sol_file.close();
00489 if (log_file.is_open())
00490 log_file.close();
00491 exit(EXIT_FAILURE);
00492 }
00493 if (sol_file.is_open())
00494 sol_file.close();
00495 if (log_file.is_open())
00496 log_file.close();
00497 }
00498
00499 }}
00500
00501