dfs.hh
Go to the documentation of this file.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 #ifndef __GECODE_SEARCH_SEQUENTIAL_DFS_HH__
00039 #define __GECODE_SEARCH_SEQUENTIAL_DFS_HH__
00040
00041 #include <gecode/search.hh>
00042 #include <gecode/search/support.hh>
00043 #include <gecode/search/worker.hh>
00044 #include <gecode/search/sequential/path.hh>
00045
00046 namespace Gecode { namespace Search { namespace Sequential {
00047
00049 class DFS : public Worker {
00050 private:
00052 Options opt;
00054 Path path;
00056 Space* cur;
00058 unsigned int d;
00059 protected:
00061 Space* reset(Space* s);
00062 public:
00064 DFS(Space* s, size_t sz, const Options& o);
00066 Space* next(void);
00068 Statistics statistics(void) const;
00070 ~DFS(void);
00071 };
00072
00073 forceinline
00074 DFS::DFS(Space* s, size_t sz, const Options& o)
00075 : Worker(sz), opt(o), d(0) {
00076 cur = (s->status(*this) == SS_FAILED) ? NULL : snapshot(s,opt);
00077 current(s);
00078 current(NULL);
00079 current(cur);
00080 if (cur == NULL)
00081 fail++;
00082 }
00083
00084 forceinline Space*
00085 DFS::reset(Space* s) {
00086 delete cur;
00087 path.reset();
00088 d = 0;
00089 if (s->status(*this) == SS_FAILED) {
00090 cur = NULL;
00091 Worker::reset();
00092 return NULL;
00093 } else {
00094 cur = s;
00095 Worker::reset(cur);
00096 return cur->clone();
00097 }
00098 }
00099
00100 forceinline Space*
00101 DFS::next(void) {
00102 start();
00103 while (true) {
00104 while (cur) {
00105 if (stop(opt,path.size()))
00106 return NULL;
00107 node++;
00108 switch (cur->status(*this)) {
00109 case SS_FAILED:
00110 fail++;
00111 delete cur;
00112 cur = NULL;
00113 Worker::current(NULL);
00114 break;
00115 case SS_SOLVED:
00116 {
00117
00118 (void) cur->choice();
00119 Space* s = cur;
00120 cur = NULL;
00121 Worker::current(NULL);
00122 return s;
00123 }
00124 case SS_BRANCH:
00125 {
00126 Space* c;
00127 if ((d == 0) || (d >= opt.c_d)) {
00128 c = cur->clone();
00129 d = 1;
00130 } else {
00131 c = NULL;
00132 d++;
00133 }
00134 const Choice* ch = path.push(*this,cur,c);
00135 Worker::push(c,ch);
00136 cur->commit(*ch,0);
00137 break;
00138 }
00139 default:
00140 GECODE_NEVER;
00141 }
00142 }
00143 do {
00144 if (!path.next(*this))
00145 return NULL;
00146 cur = path.recompute(d,opt.a_d,*this);
00147 } while (cur == NULL);
00148 Worker::current(cur);
00149 }
00150 GECODE_NEVER;
00151 return NULL;
00152 }
00153
00154 forceinline Statistics
00155 DFS::statistics(void) const {
00156 Statistics s = *this;
00157 s.memory += path.size();
00158 return s;
00159 }
00160
00161 forceinline
00162 DFS::~DFS(void) {
00163 delete cur;
00164 path.reset();
00165 }
00166
00167 }}}
00168
00169 #endif
00170
00171