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 BaseSpace>
00210 forceinline
00211 ScriptBase<BaseSpace>::ScriptBase(const Options& opt)
00212 : BaseSpace(opt) {}
00213
00214 template<class BaseSpace>
00215 forceinline
00216 ScriptBase<BaseSpace>::ScriptBase(bool share, ScriptBase& e)
00217 : BaseSpace(share,e) {}
00218
00219 template<class BaseSpace>
00220 void
00221 ScriptBase<BaseSpace>::print(std::ostream&) const {}
00222
00223 template<class BaseSpace>
00224 void
00225 ScriptBase<BaseSpace>::compare(const Space&, std::ostream&) const {}
00226
00227 template<class BaseSpace>
00228 std::ostream&
00229 ScriptBase<BaseSpace>::select_ostream(const char* name, std::ofstream& ofs) {
00230 if (strcmp(name, "stdout") == 0) {
00231 return std::cout;
00232 } else if (strcmp(name, "stdlog") == 0) {
00233 return std::clog;
00234 } else if (strcmp(name, "stderr") == 0) {
00235 return std::cerr;
00236 } else {
00237 ofs.open(name);
00238 return ofs;
00239 }
00240 }
00241
00242
00246 template<template<class> class E, class T>
00247 class EngineToMeta : public E<T> {
00248 public:
00249 EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
00250 };
00251
00252 template<class BaseSpace>
00253 template<class Script, template<class> class Engine, class Options>
00254 void
00255 ScriptBase<BaseSpace>::run(const Options& o, Script* s) {
00256 if (o.restart()==RM_NONE) {
00257 runMeta<Script,Engine,Options,EngineToMeta>(o,s);
00258 } else {
00259 runMeta<Script,Engine,Options,RBS>(o,s);
00260 }
00261 }
00262
00263 template<class BaseSpace>
00264 template<class Script, template<class> class Engine, class Options,
00265 template<template<class> class,class> class Meta>
00266 void
00267 ScriptBase<BaseSpace>::runMeta(const Options& o, Script* s) {
00268 using namespace std;
00269
00270 ofstream sol_file, log_file;
00271
00272 ostream& s_out = select_ostream(o.out_file(), sol_file);
00273 ostream& l_out = select_ostream(o.log_file(), log_file);
00274
00275 try {
00276 switch (o.mode()) {
00277 case SM_GIST:
00278 #ifdef GECODE_HAS_GIST
00279 {
00280 Gist::Print<Script> pi(o.name());
00281 Gist::VarComparator<Script> vc(o.name());
00282 Gist::Options opt;
00283 opt.inspect.click(&pi);
00284 opt.inspect.compare(&vc);
00285 opt.clone = false;
00286 opt.c_d = o.c_d();
00287 opt.a_d = o.a_d();
00288 for (int i=0; o.inspect.click(i) != NULL; i++)
00289 opt.inspect.click(o.inspect.click(i));
00290 for (int i=0; o.inspect.solution(i) != NULL; i++)
00291 opt.inspect.solution(o.inspect.solution(i));
00292 for (int i=0; o.inspect.move(i) != NULL; i++)
00293 opt.inspect.move(o.inspect.move(i));
00294 for (int i=0; o.inspect.compare(i) != NULL; i++)
00295 opt.inspect.compare(o.inspect.compare(i));
00296 if (s == NULL)
00297 s = new Script(o);
00298 (void) GistEngine<Engine<Script> >::explore(s, opt);
00299 }
00300 break;
00301
00302 #endif
00303 case SM_SOLUTION:
00304 {
00305 l_out << o.name() << endl;
00306 Support::Timer t;
00307 int i = o.solutions();
00308 t.start();
00309 if (s == NULL)
00310 s = new Script(o);
00311 unsigned int n_p = s->propagators();
00312 unsigned int n_b = s->branchers();
00313 Search::Options so;
00314 so.threads = o.threads();
00315 so.c_d = o.c_d();
00316 so.a_d = o.a_d();
00317 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
00318 o.interrupt());
00319 so.cutoff = createCutoff(o);
00320 so.clone = false;
00321 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00322 if (o.interrupt())
00323 CombinedStop::installCtrlHandler(true);
00324 {
00325 Meta<Engine,Script> e(s,so);
00326 if (o.print_last()) {
00327 Script* px = NULL;
00328 do {
00329 Script* ex = e.next();
00330 if (ex == NULL) {
00331 if (px != NULL) {
00332 px->print(s_out);
00333 delete px;
00334 }
00335 break;
00336 } else {
00337 delete px;
00338 px = ex;
00339 }
00340 } while (--i != 0);
00341 } else {
00342 do {
00343 Script* ex = e.next();
00344 if (ex == NULL)
00345 break;
00346 ex->print(s_out);
00347 delete ex;
00348 } while (--i != 0);
00349 }
00350 if (o.interrupt())
00351 CombinedStop::installCtrlHandler(false);
00352 Search::Statistics stat = e.statistics();
00353 s_out << endl;
00354 if (e.stopped()) {
00355 l_out << "Search engine stopped..." << endl
00356 << "\treason: ";
00357 int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
00358 if (r & CombinedStop::SR_INT)
00359 l_out << "user interrupt " << endl;
00360 else {
00361 if (r & CombinedStop::SR_NODE)
00362 l_out << "node ";
00363 if (r & CombinedStop::SR_FAIL)
00364 l_out << "fail ";
00365 if (r & CombinedStop::SR_TIME)
00366 l_out << "time ";
00367 l_out << "limit reached" << endl << endl;
00368 }
00369 }
00370 l_out << "Initial" << endl
00371 << "\tpropagators: " << n_p << endl
00372 << "\tbranchers: " << n_b << endl
00373 << endl
00374 << "Summary" << endl
00375 << "\truntime: ";
00376 stop(t, l_out);
00377 l_out << endl
00378 << "\tsolutions: "
00379 << ::abs(static_cast<int>(o.solutions()) - i) << endl
00380 << "\tpropagations: " << stat.propagate << endl
00381 << "\tnodes: " << stat.node << endl
00382 << "\tfailures: " << stat.fail << endl
00383 << "\trestarts: " << stat.restart << endl
00384 << "\tno-goods: " << stat.nogood << endl
00385 << "\tpeak depth: " << stat.depth << endl
00386 #ifdef GECODE_PEAKHEAP
00387 << "\tpeak memory: "
00388 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00389 << endl
00390 #endif
00391 << endl;
00392 }
00393 delete so.stop;
00394 }
00395 break;
00396 case SM_STAT:
00397 {
00398 l_out << o.name() << endl;
00399 Support::Timer t;
00400 int i = o.solutions();
00401 t.start();
00402 if (s == NULL)
00403 s = new Script(o);
00404 unsigned int n_p = s->propagators();
00405 unsigned int n_b = s->branchers();
00406 Search::Options so;
00407 so.clone = false;
00408 so.threads = o.threads();
00409 so.c_d = o.c_d();
00410 so.a_d = o.a_d();
00411 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
00412 o.interrupt());
00413 so.cutoff = createCutoff(o);
00414 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00415 if (o.interrupt())
00416 CombinedStop::installCtrlHandler(true);
00417 {
00418 Meta<Engine,Script> e(s,so);
00419 do {
00420 Script* ex = e.next();
00421 if (ex == NULL)
00422 break;
00423 delete ex;
00424 } while (--i != 0);
00425 if (o.interrupt())
00426 CombinedStop::installCtrlHandler(false);
00427 Search::Statistics stat = e.statistics();
00428 l_out << endl
00429 << "\tpropagators: " << n_p << endl
00430 << "\tbranchers: " << n_b << endl
00431 << "\truntime: ";
00432 stop(t, l_out);
00433 l_out << endl
00434 << "\tsolutions: "
00435 << ::abs(static_cast<int>(o.solutions()) - i) << endl
00436 << "\tpropagations: " << stat.propagate << endl
00437 << "\tnodes: " << stat.node << endl
00438 << "\tfailures: " << stat.fail << endl
00439 << "\trestarts: " << stat.restart << endl
00440 << "\tno-goods: " << stat.nogood << endl
00441 << "\tpeak depth: " << stat.depth << endl
00442 #ifdef GECODE_PEAKHEAP
00443 << "\tpeak memory: "
00444 << static_cast<int>((heap.peak()+1023) / 1024) << " KB"
00445 << endl
00446 #endif
00447 << endl;
00448 }
00449 delete so.stop;
00450 }
00451 break;
00452 case SM_TIME:
00453 {
00454 l_out << o.name() << endl;
00455 Support::Timer t;
00456 double* ts = new double[o.samples()];
00457 bool stopped = false;
00458 for (unsigned int s = o.samples(); !stopped && s--; ) {
00459 t.start();
00460 for (unsigned int k = o.iterations(); !stopped && k--; ) {
00461 unsigned int i = o.solutions();
00462 Script* s = new Script(o);
00463 Search::Options so;
00464 so.clone = false;
00465 so.threads = o.threads();
00466 so.c_d = o.c_d();
00467 so.a_d = o.a_d();
00468 so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
00469 false);
00470 so.cutoff = createCutoff(o);
00471 so.nogoods_limit = o.nogoods() ? o.nogoods_limit() : 0U;
00472 {
00473 Meta<Engine,Script> e(s,so);
00474 do {
00475 Script* ex = e.next();
00476 if (ex == NULL)
00477 break;
00478 delete ex;
00479 } while (--i != 0);
00480 if (e.stopped())
00481 stopped = true;
00482 }
00483 delete so.stop;
00484 }
00485 ts[s] = t.stop() / o.iterations();
00486 }
00487 if (stopped) {
00488 l_out << "\tSTOPPED" << endl;
00489 } else {
00490 double m = am(ts,o.samples());
00491 double d = dev(ts,o.samples()) * 100.0;
00492 l_out << "\truntime: "
00493 << setw(20) << right
00494 << showpoint << fixed
00495 << setprecision(6) << m << "ms"
00496 << setprecision(2) << " (" << d << "% deviation)"
00497 << endl;
00498 }
00499 delete [] ts;
00500 }
00501 break;
00502 }
00503 } catch (Exception& e) {
00504 cerr << "Exception: " << e.what() << "." << endl
00505 << "Stopping..." << endl;
00506 if (sol_file.is_open())
00507 sol_file.close();
00508 if (log_file.is_open())
00509 log_file.close();
00510 exit(EXIT_FAILURE);
00511 }
00512 if (sol_file.is_open())
00513 sol_file.close();
00514 if (log_file.is_open())
00515 log_file.close();
00516 }
00517
00518 }}
00519
00520