Generated on Tue Mar 5 2013 22:37:13 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: 2011-06-16 18:27:32 +1000 (Thu, 16 Jun 2011) $ by $Author: tack $
11  * $Revision: 12052 $
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 
42 #ifndef GECODE_THREADS_WINDOWS
43 #include <csignal>
44 #endif
45 
46 namespace Gecode { namespace Driver {
47 
52  class Cutoff : public Search::Stop {
53  private:
54  Search::NodeStop* ns;
55  Search::FailStop* fs;
56  Search::TimeStop* ts;
58  static bool sigint;
59 
60  Cutoff(unsigned int node, unsigned int fail, unsigned int time)
61  : ns((node > 0) ? new Search::NodeStop(node) : NULL),
62  fs((fail > 0) ? new Search::FailStop(fail) : NULL),
63  ts((time > 0) ? new Search::TimeStop(time) : NULL) {
64  sigint = false;
65  }
66  public:
68  enum {
69  SR_NODE = 1 << 0,
70  SR_FAIL = 1 << 1,
71  SR_TIME = 1 << 2,
72  SR_INT = 1 << 3
73  };
75  virtual bool stop(const Search::Statistics& s, const Search::Options& o) {
76  return
77  sigint ||
78  ((ns != NULL) && ns->stop(s,o)) ||
79  ((fs != NULL) && fs->stop(s,o)) ||
80  ((ts != NULL) && ts->stop(s,o));
81  }
83  int reason(const Search::Statistics& s, const Search::Options& o) {
84  return
85  (((ns != NULL) && ns->stop(s,o)) ? SR_NODE : 0) |
86  (((fs != NULL) && fs->stop(s,o)) ? SR_FAIL : 0) |
87  (((ts != NULL) && ts->stop(s,o)) ? SR_TIME : 0) |
88  (sigint ? SR_INT : 0);
89  }
91  static Search::Stop*
92  create(unsigned int node, unsigned int fail, unsigned int time,
93  bool intr) {
94  if ( (!intr) && (node == 0) && (fail == 0) && (time == 0))
95  return NULL;
96  else
97  return new Cutoff(node,fail,time);
98  }
99 #ifdef GECODE_THREADS_WINDOWS
100 
101  static BOOL interrupt(DWORD t) {
102  if (t == CTRL_C_EVENT) {
103  sigint = true;
104  installCtrlHandler(false,true);
105  return true;
106  }
107  return false;
108  }
109 #else
110 
111  static void
112  interrupt(int) {
113  sigint = true;
114  installCtrlHandler(false,true);
115  }
116 #endif
117 
118  static void installCtrlHandler(bool install, bool force=false) {
119  if (force || !sigint) {
120 #ifdef GECODE_THREADS_WINDOWS
121  SetConsoleCtrlHandler( (PHANDLER_ROUTINE) interrupt, install);
122 #else
123  std::signal(SIGINT, install ? interrupt : SIG_DFL);
124 #endif
125  }
126  }
128  ~Cutoff(void) {
129  delete ns; delete fs; delete ts;
130  }
131  };
132 
138  stop(Support::Timer& t, std::ostream& os);
139 
143  GECODE_DRIVER_EXPORT double
144  am(double t[], int n);
145 
149  GECODE_DRIVER_EXPORT double
150  dev(double t[], int n);
151 
152 #ifdef GECODE_HAS_GIST
153 
157  template<class Engine>
158  class GistEngine {
159  };
160 
162  template<typename S>
163  class GistEngine<DFS<S> > {
164  public:
165  static void explore(S* root, const Gist::Options& opt) {
166  (void) Gist::dfs(root, opt);
167  }
168  };
169 
171  template<typename S>
172  class GistEngine<BAB<S> > {
173  public:
174  static void explore(S* root, const Gist::Options& opt) {
175  (void) Gist::bab(root, opt);
176  }
177  };
178 
180  template<typename S>
181  class GistEngine<Restart<S> > {
182  public:
183  static void explore(S* root, const Gist::Options& opt) {
184  (void) Gist::bab(root, opt);
185  }
186  };
187 
188 #endif
189 
190  template<class Space>
191  template<class Script, template<class> class Engine, class Options>
192  void
194  using namespace std;
195  try {
196  switch (o.mode()) {
197  case SM_GIST:
198 #ifdef GECODE_HAS_GIST
199  {
200  Gist::Print<Script> pi(o.name());
203  opt.inspect.click(&pi);
204  opt.inspect.compare(&vc);
205  opt.clone = false;
206  opt.c_d = o.c_d();
207  opt.a_d = o.a_d();
208  for (int i=0; o.inspect.click(i) != NULL; i++)
209  opt.inspect.click(o.inspect.click(i));
210  for (int i=0; o.inspect.solution(i) != NULL; i++)
211  opt.inspect.solution(o.inspect.solution(i));
212  for (int i=0; o.inspect.move(i) != NULL; i++)
213  opt.inspect.move(o.inspect.move(i));
214  for (int i=0; o.inspect.compare(i) != NULL; i++)
215  opt.inspect.compare(o.inspect.compare(i));
216  Script* s = new Script(o);
217  (void) GistEngine<Engine<Script> >::explore(s, opt);
218  }
219  break;
220  // If Gist is not available, fall through
221 #endif
222  case SM_SOLUTION:
223  {
224  cout << o.name() << endl;
225  Support::Timer t;
226  int i = o.solutions();
227  t.start();
228  Script* s = new Script(o);
229  unsigned int n_p = s->propagators();
230  unsigned int n_b = s->branchers();
231  Search::Options so;
232  so.threads = o.threads();
233  so.c_d = o.c_d();
234  so.a_d = o.a_d();
235  so.stop = Cutoff::create(o.node(),o.fail(), o.time(),
236  o.interrupt());
237  so.clone = false;
238  if (o.interrupt())
240  Engine<Script> e(s,so);
241  do {
242  Script* ex = e.next();
243  if (ex == NULL)
244  break;
245  ex->print(std::cout);
246  delete ex;
247  } while (--i != 0);
248  if (o.interrupt())
250  Search::Statistics stat = e.statistics();
251  cout << endl;
252  if (e.stopped()) {
253  cout << "Search engine stopped..." << endl
254  << "\treason: ";
255  int r = static_cast<Cutoff*>(so.stop)->reason(stat,so);
256  if (r & Cutoff::SR_INT)
257  cout << "user interrupt " << endl;
258  else {
259  if (r & Cutoff::SR_NODE)
260  cout << "node ";
261  if (r & Cutoff::SR_FAIL)
262  cout << "fail ";
263  if (r & Cutoff::SR_TIME)
264  cout << "time ";
265  cout << "limit reached" << endl << endl;
266  }
267  }
268  cout << "Initial" << endl
269  << "\tpropagators: " << n_p << endl
270  << "\tbranchers: " << n_b << endl
271  << endl
272  << "Summary" << endl
273  << "\truntime: ";
274  stop(t, cout);
275  cout << endl
276  << "\tsolutions: "
277  << ::abs(static_cast<int>(o.solutions()) - i) << endl
278  << "\tpropagations: " << stat.propagate << endl
279  << "\tnodes: " << stat.node << endl
280  << "\tfailures: " << stat.fail << endl
281  << "\tpeak depth: " << stat.depth << endl
282  << "\tpeak memory: "
283  << static_cast<int>((stat.memory+1023) / 1024) << " KB"
284  << endl;
285  delete so.stop;
286  }
287  break;
288  case SM_STAT:
289  {
290  cout << o.name() << endl;
291  Support::Timer t;
292  int i = o.solutions();
293  t.start();
294  Script* s = new Script(o);
295  unsigned int n_p = s->propagators();
296  unsigned int n_b = s->branchers();
297  Search::Options so;
298  so.clone = false;
299  so.threads = o.threads();
300  so.c_d = o.c_d();
301  so.a_d = o.a_d();
302  so.stop = Cutoff::create(o.node(),o.fail(), o.time(),
303  o.interrupt());
304  if (o.interrupt())
306  Engine<Script> e(s,so);
307  do {
308  Script* ex = e.next();
309  if (ex == NULL)
310  break;
311  delete ex;
312  } while (--i != 0);
313  if (o.interrupt())
315  Search::Statistics stat = e.statistics();
316  cout << endl
317  << "\tpropagators: " << n_p << endl
318  << "\tbranchers: " << n_b << endl
319  << "\truntime: ";
320  stop(t, cout);
321  cout << endl
322  << "\tsolutions: "
323  << ::abs(static_cast<int>(o.solutions()) - i) << endl
324  << "\tpropagations: " << stat.propagate << endl
325  << "\tnodes: " << stat.node << endl
326  << "\tfailures: " << stat.fail << endl
327  << "\tpeak depth: " << stat.depth << endl
328  << "\tpeak memory: "
329  << static_cast<int>((stat.memory+1023) / 1024) << " KB"
330  << endl;
331  }
332  break;
333  case SM_TIME:
334  {
335  cout << o.name() << endl;
336  Support::Timer t;
337  double* ts = new double[o.samples()];
338  bool stopped = false;
339  for (unsigned int s = o.samples(); !stopped && s--; ) {
340  t.start();
341  for (unsigned int k = o.iterations(); !stopped && k--; ) {
342  unsigned int i = o.solutions();
343  Script* s = new Script(o);
344  Search::Options so;
345  so.clone = false;
346  so.threads = o.threads();
347  so.c_d = o.c_d();
348  so.a_d = o.a_d();
349  so.stop = Cutoff::create(o.node(),o.fail(), o.time(), false);
350  Engine<Script> e(s,so);
351  do {
352  Script* ex = e.next();
353  if (ex == NULL)
354  break;
355  delete ex;
356  } while (--i != 0);
357  if (e.stopped())
358  stopped = true;
359  delete so.stop;
360  }
361  ts[s] = t.stop() / o.iterations();
362  }
363  if (stopped) {
364  cout << "\tSTOPPED" << endl;
365  } else {
366  double m = am(ts,o.samples());
367  double d = dev(ts,o.samples()) * 100.0;
368  cout << "\tRuntime: "
369  << setw(20) << right
370  << showpoint << fixed
371  << setprecision(6) << m << "ms"
372  << setprecision(2) << " (" << d << "% deviation)"
373  << endl;
374  }
375  delete [] ts;
376  }
377  break;
378  }
379  } catch (Exception e) {
380  cerr << "Exception: " << e.what() << "." << endl
381  << "Stopping..." << endl;
382  exit(EXIT_FAILURE);
383  }
384  }
385 
386 }}
387 
388 // STATISTICS: driver-any