Generated on Mon Sep 17 2012 22:20:44 for Gecode by doxygen 1.8.1.1
search.hh
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  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2002
9  * Guido Tack, 2004
10  *
11  * Last modified:
12  * $Date: 2010-10-09 22:58:12 +1100 (Sat, 09 Oct 2010) $ by $Author: schulte $
13  * $Revision: 11498 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #ifndef __GECODE_SEARCH_HH__
41 #define __GECODE_SEARCH_HH__
42 
43 #include <gecode/kernel.hh>
44 
45 /*
46  * Configure linking
47  *
48  */
49 #if !defined(GECODE_STATIC_LIBS) && \
50  (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
51 
52 #ifdef GECODE_BUILD_SEARCH
53 #define GECODE_SEARCH_EXPORT __declspec( dllexport )
54 #else
55 #define GECODE_SEARCH_EXPORT __declspec( dllimport )
56 #endif
57 
58 #else
59 
60 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
61 #define GECODE_SEARCH_EXPORT __attribute__ ((visibility("default")))
62 #else
63 #define GECODE_SEARCH_EXPORT
64 #endif
65 
66 #endif
67 
68 // Configure auto-linking
69 #ifndef GECODE_BUILD_SEARCH
70 #define GECODE_LIBRARY_NAME "Search"
72 #endif
73 
74 
75 namespace Gecode {
76 
78  namespace Search {
79 
85  namespace Config {
87  const bool clone = true;
89  const double threads = 1.0;
91  const unsigned int c_d = 8;
93  const unsigned int a_d = 2;
94 
96  const unsigned int steal_limit = 3;
98  const unsigned int initial_delay = 5;
99  }
100 
105  class Statistics : public StatusStatistics {
106  public:
108  unsigned long int fail;
110  unsigned long int node;
112  unsigned long int depth;
114  size_t memory;
116  Statistics(void);
118  void reset(void);
120  Statistics operator +(const Statistics& s);
122  Statistics& operator +=(const Statistics& s);
123  };
124 
125  class Stop;
126 
164  class Options {
165  public:
167  bool clone;
169  double threads;
171  unsigned int c_d;
173  unsigned int a_d;
179  Options(void);
182  expand(void) const;
183  };
184 
200  public:
202  Stop(void);
204  virtual bool stop(const Statistics& s, const Options& o) = 0;
206  virtual ~Stop(void);
207  };
208 
215  protected:
217  size_t l;
218  public:
220  MemoryStop(size_t l);
222  size_t limit(void) const;
224  void limit(size_t l);
226  virtual bool stop(const Statistics& s, const Options& o);
227  };
228 
238  protected:
240  unsigned long int l;
241  public:
243  NodeStop(unsigned long int l);
245  unsigned long int limit(void) const;
247  void limit(unsigned long int l);
249  virtual bool stop(const Statistics& s, const Options& o);
250  };
251 
261  protected:
263  unsigned long int l;
264  public:
266  FailStop(unsigned long int l);
268  unsigned long int limit(void) const;
270  void limit(unsigned long int l);
272  virtual bool stop(const Statistics& s, const Options& o);
273  };
274 
280  protected:
284  unsigned long int l;
285  public:
287  TimeStop(unsigned long int l);
289  unsigned long int limit(void) const;
291  void limit(unsigned long int l);
293  void reset(void);
295  virtual bool stop(const Statistics& s, const Options& o);
296  };
297 
298 
302  class Engine {
303  public:
305  virtual Space* next(void) = 0;
307  virtual Search::Statistics statistics(void) const = 0;
309  virtual bool stopped(void) const = 0;
311  virtual ~Engine(void) {}
312  };
313 
315  namespace Sequential {}
316 
318  namespace Parallel {}
319 
320  }
321 
322 }
323 
325 #include <gecode/search/stop.hpp>
326 #include <gecode/search/options.hpp>
327 
328 namespace Gecode {
329 
337  template<class T>
338  class DFS {
339  private:
341  Search::Engine* e;
342  public:
344  DFS(T* s, const Search::Options& o=Search::Options::def);
346  T* next(void);
348  Search::Statistics statistics(void) const;
350  bool stopped(void) const;
352  ~DFS(void);
353  };
354 
356  template<class T>
357  T* dfs(T* s, const Search::Options& o=Search::Options::def);
358 
359 
360 
372  template<class T>
373  class BAB {
374  private:
376  Search::Engine* e;
377  public:
379  BAB(T* s, const Search::Options& o=Search::Options::def);
381  T* next(void);
383  Search::Statistics statistics(void) const;
385  bool stopped(void) const;
387  ~BAB(void);
388  };
389 
402  template<class T>
403  T* bab(T* s, const Search::Options& o=Search::Options::def);
404 
405 
406 
418  template<class T>
419  class Restart {
420  private:
422  Search::Engine* e;
423  public:
427  T* next(void);
429  Search::Statistics statistics(void) const;
431  bool stopped(void) const;
433  ~Restart(void);
434  };
435 
447  template<class T>
448  T* restart(T* s, const Search::Options& o=Search::Options::def);
449 
450 }
451 
452 #include <gecode/search/dfs.hpp>
453 #include <gecode/search/bab.hpp>
454 #include <gecode/search/restart.hpp>
455 
456 #endif
457 
458 // STATISTICS: search-other