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 }
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