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
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
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 delete so.stop;
00286 }
00287 break;
00288 case SM_STAT:
00289 {
00290 cout << o.name() << endl;
00291 Support::Timer t;
00292 int i = o.solutions();
00293 t.start();
00294 Script* s = new Script(o);
00295 unsigned int n_p = s->propagators();
00296 unsigned int n_b = s->branchers();
00297 Search::Options so;
00298 so.clone = false;
00299 so.threads = o.threads();
00300 so.c_d = o.c_d();
00301 so.a_d = o.a_d();
00302 so.stop = Cutoff::create(o.node(),o.fail(), o.time(),
00303 o.interrupt());
00304 if (o.interrupt())
00305 Cutoff::installCtrlHandler(true);
00306 Engine<Script> e(s,so);
00307 do {
00308 Script* ex = e.next();
00309 if (ex == NULL)
00310 break;
00311 delete ex;
00312 } while (--i != 0);
00313 if (o.interrupt())
00314 Cutoff::installCtrlHandler(false);
00315 Search::Statistics stat = e.statistics();
00316 cout << endl
00317 << "\tpropagators: " << n_p << endl
00318 << "\tbranchers: " << n_b << endl
00319 << "\truntime: ";
00320 stop(t, cout);
00321 cout << endl
00322 << "\tsolutions: "
00323 << ::abs(static_cast<int>(o.solutions()) - i) << endl
00324 << "\tpropagations: " << stat.propagate << endl
00325 << "\tnodes: " << stat.node << endl
00326 << "\tfailures: " << stat.fail << endl
00327 << "\tpeak depth: " << stat.depth << endl
00328 << "\tpeak memory: "
00329 << static_cast<int>((stat.memory+1023) / 1024) << " KB"
00330 << endl;
00331 }
00332 break;
00333 case SM_TIME:
00334 {
00335 cout << o.name() << endl;
00336 Support::Timer t;
00337 double* ts = new double[o.samples()];
00338 bool stopped = false;
00339 for (unsigned int s = o.samples(); !stopped && s--; ) {
00340 t.start();
00341 for (unsigned int k = o.iterations(); !stopped && k--; ) {
00342 unsigned int i = o.solutions();
00343 Script* s = new Script(o);
00344 Search::Options so;
00345 so.clone = false;
00346 so.threads = o.threads();
00347 so.c_d = o.c_d();
00348 so.a_d = o.a_d();
00349 so.stop = Cutoff::create(o.node(),o.fail(), o.time(), false);
00350 Engine<Script> e(s,so);
00351 do {
00352 Script* ex = e.next();
00353 if (ex == NULL)
00354 break;
00355 delete ex;
00356 } while (--i != 0);
00357 if (e.stopped())
00358 stopped = true;
00359 delete so.stop;
00360 }
00361 ts[s] = t.stop() / o.iterations();
00362 }
00363 if (stopped) {
00364 cout << "\tSTOPPED" << endl;
00365 } else {
00366 double m = am(ts,o.samples());
00367 double d = dev(ts,o.samples()) * 100.0;
00368 cout << "\tRuntime: "
00369 << setw(20) << right
00370 << showpoint << fixed
00371 << setprecision(6) << m << "ms"
00372 << setprecision(2) << " (" << d << "% deviation)"
00373 << endl;
00374 }
00375 delete [] ts;
00376 }
00377 break;
00378 }
00379 } catch (Exception e) {
00380 cerr << "Exception: " << e.what() << "." << endl
00381 << "Stopping..." << endl;
00382 exit(EXIT_FAILURE);
00383 }
00384 }
00385
00386 }}
00387
00388