Generated on Sat May 25 2013 18:00:40 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: 2013-03-07 20:56:21 +0100 (Thu, 07 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13463 $
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  public:
61  DFS(Space* s, size_t sz, const Options& o);
63  Space* next(void);
65  Statistics statistics(void) const;
67  void reset(Space* s);
69  ~DFS(void);
70  };
71 
73  DFS::DFS(Space* s, size_t sz, const Options& o)
74  : Worker(sz), opt(o), d(0) {
75  current(s);
76  if (s->status(*this) == SS_FAILED) {
77  fail++;
78  cur = NULL;
79  if (!opt.clone)
80  delete s;
81  } else {
82  cur = snapshot(s,opt);
83  }
84  current(NULL);
85  current(cur);
86  }
87 
88  forceinline void
90  delete cur;
91  path.reset();
92  d = 0;
93  if (s->status(*this) == SS_FAILED) {
94  cur = NULL;
95  Worker::reset();
96  } else {
97  cur = s;
98  Worker::reset(cur);
99  }
100  }
101 
103  DFS::next(void) {
104  start();
105  while (true) {
106  while (cur) {
107  if (stop(opt,path.size()))
108  return NULL;
109  node++;
110  switch (cur->status(*this)) {
111  case SS_FAILED:
112  fail++;
113  delete cur;
114  cur = NULL;
115  Worker::current(NULL);
116  break;
117  case SS_SOLVED:
118  {
119  // Deletes all pending branchers
120  (void) cur->choice();
121  Space* s = cur;
122  cur = NULL;
123  Worker::current(NULL);
124  return s;
125  }
126  case SS_BRANCH:
127  {
128  Space* c;
129  if ((d == 0) || (d >= opt.c_d)) {
130  c = cur->clone();
131  d = 1;
132  } else {
133  c = NULL;
134  d++;
135  }
136  const Choice* ch = path.push(*this,cur,c);
137  Worker::push(c,ch);
138  cur->commit(*ch,0);
139  break;
140  }
141  default:
142  GECODE_NEVER;
143  }
144  }
145  do {
146  if (!path.next(*this))
147  return NULL;
148  cur = path.recompute(d,opt.a_d,*this);
149  } while (cur == NULL);
150  Worker::current(cur);
151  }
152  GECODE_NEVER;
153  return NULL;
154  }
155 
157  DFS::statistics(void) const {
158  Statistics s = *this;
159  s.memory += path.size();
160  return s;
161  }
162 
163  forceinline
164  DFS::~DFS(void) {
165  delete cur;
166  path.reset();
167  }
168 
169 }}}
170 
171 #endif
172 
173 // STATISTICS: search-sequential