Generated on Sat May 25 2013 18:00:32 for Gecode by doxygen 1.8.3.1
script.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2004
8  *
9  * Last modified:
10  * $Date: 2013-03-07 20:40:42 +0100 (Thu, 07 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13462 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  *
18  * Permission is hereby granted, free of charge, to any person obtaining
19  * a copy of this software and associated documentation files (the
20  * "Software"), to deal in the Software without restriction, including
21  * without limitation the rights to use, copy, modify, merge, publish,
22  * distribute, sublicense, and/or sell copies of the Software, and to
23  * permit persons to whom the Software is furnished to do so, subject to
24  * the following conditions:
25  *
26  * The above copyright notice and this permission notice shall be
27  * included in all copies or substantial portions of the Software.
28  *
29  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36  *
37  */
38 
39 #include <iostream>
40 #include <iomanip>
41 #include <fstream>
42 #include <cstring>
43 
44 #ifndef GECODE_THREADS_WINDOWS
45 #include <csignal>
46 #endif
47 
48 namespace Gecode { namespace Driver {
49 
54  class CombinedStop : public Search::Stop {
55  private:
56  Search::NodeStop* ns;
57  Search::FailStop* fs;
58  Search::TimeStop* ts;
60  static bool sigint;
61 
62  CombinedStop(unsigned int node, unsigned int fail, unsigned int time)
63  : ns((node > 0) ? new Search::NodeStop(node) : NULL),
64  fs((fail > 0) ? new Search::FailStop(fail) : NULL),
65  ts((time > 0) ? new Search::TimeStop(time) : NULL) {
66  sigint = false;
67  }
68  public:
70  enum {
71  SR_NODE = 1 << 0,
72  SR_FAIL = 1 << 1,
73  SR_TIME = 1 << 2,
74  SR_INT = 1 << 3
75  };
77  virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
78  return
79  sigint ||
80  ((ns != NULL) && ns->stop(s,o)) ||
81  ((fs != NULL) && fs->stop(s,o)) ||
82  ((ts != NULL) && ts->stop(s,o));
83  }
85  int reason(const Search::Statistics& s, const Search::Options& o) {
86  return
87  (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
88  (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
89  (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0) |
90  (sigint ? SR_INT : 0);
91  }
93  static Search::Stop*
94  create(unsigned int node, unsigned int fail, unsigned int time,
95  bool intr) {
96  if ( (!intr) && (node == 0) && (fail == 0) && (time == 0))
97  return NULL;
98  else
99  return new CombinedStop(node,fail,time);
100  }
101 #ifdef GECODE_THREADS_WINDOWS
102 
103  static BOOL interrupt(DWORD t) {
104  if (t == CTRL_C_EVENT) {
105  sigint = true;
106  installCtrlHandler(false,true);
107  return true;
108  }
109  return false;
110  }
111 #else
112 
113  static void
114  interrupt(int) {
115  sigint = true;
116  installCtrlHandler(false,true);
117  }
118 #endif
119 
120  static void installCtrlHandler(bool install, bool force=false) {
121  if (force || !sigint) {
122 #ifdef GECODE_THREADS_WINDOWS
123  SetConsoleCtrlHandler( (PHANDLER_ROUTINE) interrupt, install);
124 #else
125  std::signal(SIGINT, install ? interrupt : SIG_DFL);
126 #endif
127  }
128  }
131  delete ns; delete fs; delete ts;
132  }
133  };
134 
140  stop(Support::Timer& t, std::ostream& os);
141 
145  GECODE_DRIVER_EXPORT double
146  am(double t[], int n);
147 
151  GECODE_DRIVER_EXPORT double
152  dev(double t[], int n);
153 
155  template<class Options>
156  inline Search::Cutoff*
157  createCutoff(const Options& o) {
158  switch (o.restart()) {
159  case RM_NONE:
160  return NULL;
161  case RM_CONSTANT:
163  case RM_LINEAR:
165  case RM_LUBY:
167  case RM_GEOMETRIC:
169  default: GECODE_NEVER;
170  }
171  return NULL;
172  }
173 
174 
175 #ifdef GECODE_HAS_GIST
176 
180  template<class Engine>
181  class GistEngine {
182  public:
183  static void explore(Space* root, const Gist::Options& opt) {
184  (void) Gist::dfs(root, opt);
185  }
186  };
187 
189  template<typename S>
190  class GistEngine<DFS<S> > {
191  public:
192  static void explore(S* root, const Gist::Options& opt) {
193  (void) Gist::dfs(root, opt);
194  }
195  };
196 
198  template<typename S>
199  class GistEngine<BAB<S> > {
200  public:
201  static void explore(S* root, const Gist::Options& opt) {
202  (void) Gist::bab(root, opt);
203  }
204  };
205 
206 #endif
207 
208 
209  template<class Space>
210  std::ostream&
211  ScriptBase<Space>::select_ostream(const char* name, std::ofstream& ofs) {
212  if (strcmp(name, "stdout") == 0) {
213  return std::cout;
214  } else if (strcmp(name, "stdlog") == 0) {
215  return std::clog;
216  } else if (strcmp(name, "stderr") == 0) {
217  return std::cerr;
218  } else {
219  ofs.open(name);
220  return ofs;
221  }
222  }
223 
227  template<template<class> class E, class T>
228  class EngineToMeta : public E<T> {
229  public:
230  EngineToMeta(T* s, const Search::Options& o) : E<T>(s,o) {}
231  };
232 
233  template<class Space>
234  template<class Script, template<class> class Engine, class Options>
235  void
237  if (o.restart()==RM_NONE) {
238  runMeta<Script,Engine,Options,EngineToMeta>(o,s);
239  } else {
240  runMeta<Script,Engine,Options,RBS>(o,s);
241  }
242  }
243 
244  template<class Space>
245  template<class Script, template<class> class Engine, class Options,
246  template<template<class> class,class> class Meta>
247  void
248  ScriptBase<Space>::runMeta(const Options& o, Script* s) {
249  using namespace std;
250 
251  ofstream sol_file, log_file;
252 
253  ostream& s_out = select_ostream(o.out_file(), sol_file);
254  ostream& l_out = select_ostream(o.log_file(), log_file);
255 
256  try {
257  switch (o.mode()) {
258  case SM_GIST:
259 #ifdef GECODE_HAS_GIST
260  {
261  Gist::Print<Script> pi(o.name());
262  Gist::VarComparator<Script> vc(o.name());
264  opt.inspect.click(&pi);
265  opt.inspect.compare(&vc);
266  opt.clone = false;
267  opt.c_d = o.c_d();
268  opt.a_d = o.a_d();
269  for (int i=0; o.inspect.click(i) != NULL; i++)
270  opt.inspect.click(o.inspect.click(i));
271  for (int i=0; o.inspect.solution(i) != NULL; i++)
272  opt.inspect.solution(o.inspect.solution(i));
273  for (int i=0; o.inspect.move(i) != NULL; i++)
274  opt.inspect.move(o.inspect.move(i));
275  for (int i=0; o.inspect.compare(i) != NULL; i++)
276  opt.inspect.compare(o.inspect.compare(i));
277  if (s == NULL)
278  s = new Script(o);
279  (void) GistEngine<Engine<Script> >::explore(s, opt);
280  }
281  break;
282  // If Gist is not available, fall through
283 #endif
284  case SM_SOLUTION:
285  {
286  l_out << o.name() << endl;
288  int i = o.solutions();
289  t.start();
290  if (s == NULL)
291  s = new Script(o);
292  unsigned int n_p = s->propagators();
293  unsigned int n_b = s->branchers();
294  Search::Options so;
295  so.threads = o.threads();
296  so.c_d = o.c_d();
297  so.a_d = o.a_d();
298  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
299  o.interrupt());
300  so.cutoff = createCutoff(o);
301  so.clone = false;
302  if (o.interrupt())
304  Meta<Engine,Script> e(s,so);
305  if (o.print_last()) {
306  Script* px = NULL;
307  do {
308  Script* ex = e.next();
309  if (ex == NULL) {
310  if (px != NULL) {
311  px->print(s_out);
312  delete px;
313  }
314  break;
315  } else {
316  delete px;
317  px = ex;
318  }
319  } while (--i != 0);
320  } else {
321  do {
322  Script* ex = e.next();
323  if (ex == NULL)
324  break;
325  ex->print(s_out);
326  delete ex;
327  } while (--i != 0);
328  }
329  if (o.interrupt())
331  Search::Statistics stat = e.statistics();
332  s_out << endl;
333  if (e.stopped()) {
334  l_out << "Search engine stopped..." << endl
335  << "\treason: ";
336  int r = static_cast<CombinedStop*>(so.stop)->reason(stat,so);
337  if (r & CombinedStop::SR_INT)
338  l_out << "user interrupt " << endl;
339  else {
340  if (r & CombinedStop::SR_NODE)
341  l_out << "node ";
342  if (r & CombinedStop::SR_FAIL)
343  l_out << "fail ";
344  if (r & CombinedStop::SR_TIME)
345  l_out << "time ";
346  l_out << "limit reached" << endl << endl;
347  }
348  }
349  l_out << "Initial" << endl
350  << "\tpropagators: " << n_p << endl
351  << "\tbranchers: " << n_b << endl
352  << endl
353  << "Summary" << endl
354  << "\truntime: ";
355  stop(t, l_out);
356  l_out << endl
357  << "\tsolutions: "
358  << ::abs(static_cast<int>(o.solutions()) - i) << endl
359  << "\tpropagations: " << stat.propagate << endl
360  << "\tnodes: " << stat.node << endl
361  << "\tfailures: " << stat.fail << endl
362  << "\trestarts: " << stat.restart << endl
363  << "\tpeak depth: " << stat.depth << endl
364  << "\tpeak memory: "
365  << static_cast<int>((stat.memory+1023) / 1024) << " KB"
366  << endl;
367  delete so.stop;
368  }
369  break;
370  case SM_STAT:
371  {
372  l_out << o.name() << endl;
374  int i = o.solutions();
375  t.start();
376  if (s == NULL)
377  s = new Script(o);
378  unsigned int n_p = s->propagators();
379  unsigned int n_b = s->branchers();
380  Search::Options so;
381  so.clone = false;
382  so.threads = o.threads();
383  so.c_d = o.c_d();
384  so.a_d = o.a_d();
385  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
386  o.interrupt());
387  so.cutoff = createCutoff(o);
388  if (o.interrupt())
390  Meta<Engine,Script> e(s,so);
391  do {
392  Script* ex = e.next();
393  if (ex == NULL)
394  break;
395  delete ex;
396  } while (--i != 0);
397  if (o.interrupt())
399  Search::Statistics stat = e.statistics();
400  l_out << endl
401  << "\tpropagators: " << n_p << endl
402  << "\tbranchers: " << n_b << endl
403  << "\truntime: ";
404  stop(t, l_out);
405  l_out << endl
406  << "\tsolutions: "
407  << ::abs(static_cast<int>(o.solutions()) - i) << endl
408  << "\tpropagations: " << stat.propagate << endl
409  << "\tnodes: " << stat.node << endl
410  << "\tfailures: " << stat.fail << endl
411  << "\trestarts: " << stat.restart << endl
412  << "\tpeak depth: " << stat.depth << endl
413  << "\tpeak memory: "
414  << static_cast<int>((stat.memory+1023) / 1024) << " KB"
415  << endl;
416  }
417  break;
418  case SM_TIME:
419  {
420  l_out << o.name() << endl;
422  double* ts = new double[o.samples()];
423  bool stopped = false;
424  for (unsigned int s = o.samples(); !stopped && s--; ) {
425  t.start();
426  for (unsigned int k = o.iterations(); !stopped && k--; ) {
427  unsigned int i = o.solutions();
428  Script* s = new Script(o);
429  Search::Options so;
430  so.clone = false;
431  so.threads = o.threads();
432  so.c_d = o.c_d();
433  so.a_d = o.a_d();
434  so.stop = CombinedStop::create(o.node(),o.fail(), o.time(),
435  false);
436  so.cutoff = createCutoff(o);
437  Meta<Engine,Script> e(s,so);
438  do {
439  Script* ex = e.next();
440  if (ex == NULL)
441  break;
442  delete ex;
443  } while (--i != 0);
444  if (e.stopped())
445  stopped = true;
446  delete so.stop;
447  }
448  ts[s] = t.stop() / o.iterations();
449  }
450  if (stopped) {
451  l_out << "\tSTOPPED" << endl;
452  } else {
453  double m = am(ts,o.samples());
454  double d = dev(ts,o.samples()) * 100.0;
455  l_out << "\truntime: "
456  << setw(20) << right
457  << showpoint << fixed
458  << setprecision(6) << m << "ms"
459  << setprecision(2) << " (" << d << "% deviation)"
460  << endl;
461  }
462  delete [] ts;
463  }
464  break;
465  }
466  } catch (Exception& e) {
467  cerr << "Exception: " << e.what() << "." << endl
468  << "Stopping..." << endl;
469  if (sol_file.is_open())
470  sol_file.close();
471  if (log_file.is_open())
472  log_file.close();
473  exit(EXIT_FAILURE);
474  }
475  if (sol_file.is_open())
476  sol_file.close();
477  if (log_file.is_open())
478  log_file.close();
479  }
480 
481 }}
482 
483 // STATISTICS: driver-any