Generated on Thu Feb 14 2013 20:59:45 for Gecode by doxygen 1.8.3.1
dfs.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  *
6  * Copyright:
7  * Christian Schulte, 2009
8  *
9  * Last modified:
10  * $Date: 2011-05-04 19:27:49 +1000 (Wed, 04 May 2011) $ by $Author: tack $
11  * $Revision: 11992 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #ifndef __GECODE_SEARCH_SEQUENTIAL_DFS_HH__
39 #define __GECODE_SEARCH_SEQUENTIAL_DFS_HH__
40 
41 #include <gecode/search.hh>
42 #include <gecode/search/support.hh>
43 #include <gecode/search/worker.hh>
45 
46 namespace Gecode { namespace Search { namespace Sequential {
47 
49  class DFS : public Worker {
50  private:
52  Options opt;
54  Path path;
56  Space* cur;
58  unsigned int d;
59  protected:
61  Space* reset(Space* s);
62  public:
64  DFS(Space* s, size_t sz, const Options& o);
66  Space* next(void);
68  Statistics statistics(void) const;
70  ~DFS(void);
71  };
72 
74  DFS::DFS(Space* s, size_t sz, const Options& o)
75  : Worker(sz), opt(o), d(0) {
76  current(s);
77  if (s->status(*this) == SS_FAILED) {
78  fail++;
79  cur = NULL;
80  if (!o.clone)
81  delete s;
82  } else {
83  cur = snapshot(s,opt);
84  }
85  current(NULL);
86  current(cur);
87  }
88 
91  delete cur;
92  path.reset();
93  d = 0;
94  if (s->status(*this) == SS_FAILED) {
95  cur = NULL;
96  Worker::reset();
97  return NULL;
98  } else {
99  cur = s;
100  Worker::reset(cur);
101  return cur->clone();
102  }
103  }
104 
106  DFS::next(void) {
107  start();
108  while (true) {
109  while (cur) {
110  if (stop(opt,path.size()))
111  return NULL;
112  node++;
113  switch (cur->status(*this)) {
114  case SS_FAILED:
115  fail++;
116  delete cur;
117  cur = NULL;
118  Worker::current(NULL);
119  break;
120  case SS_SOLVED:
121  {
122  // Deletes all pending branchers
123  (void) cur->choice();
124  Space* s = cur;
125  cur = NULL;
126  Worker::current(NULL);
127  return s;
128  }
129  case SS_BRANCH:
130  {
131  Space* c;
132  if ((d == 0) || (d >= opt.c_d)) {
133  c = cur->clone();
134  d = 1;
135  } else {
136  c = NULL;
137  d++;
138  }
139  const Choice* ch = path.push(*this,cur,c);
140  Worker::push(c,ch);
141  cur->commit(*ch,0);
142  break;
143  }
144  default:
145  GECODE_NEVER;
146  }
147  }
148  do {
149  if (!path.next(*this))
150  return NULL;
151  cur = path.recompute(d,opt.a_d,*this);
152  } while (cur == NULL);
153  Worker::current(cur);
154  }
155  GECODE_NEVER;
156  return NULL;
157  }
158 
160  DFS::statistics(void) const {
161  Statistics s = *this;
162  s.memory += path.size();
163  return s;
164  }
165 
166  forceinline
167  DFS::~DFS(void) {
168  delete cur;
169  path.reset();
170  }
171 
172 }}}
173 
174 #endif
175 
176 // STATISTICS: search-sequential