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