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