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 current(s);
00077 if (s->status(*this) == SS_FAILED) {
00078 fail++;
00079 cur = NULL;
00080 if (!o.clone)
00081 delete s;
00082 } else {
00083 cur = snapshot(s,opt);
00084 }
00085 current(NULL);
00086 current(cur);
00087 }
00088
00089 forceinline Space*
00090 DFS::reset(Space* s) {
00091 delete cur;
00092 path.reset();
00093 d = 0;
00094 if (s->status(*this) == SS_FAILED) {
00095 cur = NULL;
00096 Worker::reset();
00097 return NULL;
00098 } else {
00099 cur = s;
00100 Worker::reset(cur);
00101 return cur->clone();
00102 }
00103 }
00104
00105 forceinline Space*
00106 DFS::next(void) {
00107 start();
00108 while (true) {
00109 while (cur) {
00110 if (stop(opt,path.size()))
00111 return NULL;
00112 node++;
00113 switch (cur->status(*this)) {
00114 case SS_FAILED:
00115 fail++;
00116 delete cur;
00117 cur = NULL;
00118 Worker::current(NULL);
00119 break;
00120 case SS_SOLVED:
00121 {
00122
00123 (void) cur->choice();
00124 Space* s = cur;
00125 cur = NULL;
00126 Worker::current(NULL);
00127 return s;
00128 }
00129 case SS_BRANCH:
00130 {
00131 Space* c;
00132 if ((d == 0) || (d >= opt.c_d)) {
00133 c = cur->clone();
00134 d = 1;
00135 } else {
00136 c = NULL;
00137 d++;
00138 }
00139 const Choice* ch = path.push(*this,cur,c);
00140 Worker::push(c,ch);
00141 cur->commit(*ch,0);
00142 break;
00143 }
00144 default:
00145 GECODE_NEVER;
00146 }
00147 }
00148 do {
00149 if (!path.next(*this))
00150 return NULL;
00151 cur = path.recompute(d,opt.a_d,*this);
00152 } while (cur == NULL);
00153 Worker::current(cur);
00154 }
00155 GECODE_NEVER;
00156 return NULL;
00157 }
00158
00159 forceinline Statistics
00160 DFS::statistics(void) const {
00161 Statistics s = *this;
00162 s.memory += path.size();
00163 return s;
00164 }
00165
00166 forceinline
00167 DFS::~DFS(void) {
00168 delete cur;
00169 path.reset();
00170 }
00171
00172 }}}
00173
00174 #endif
00175
00176