Generated on Tue Jul 18 2017 18:41:42 for Gecode by doxygen 1.8.13
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: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
11  * $Revision: 14967 $
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, const Options& o);
63  Space* next(void);
65  Statistics statistics(void) const;
67  void constrain(const Space& b);
69  void reset(Space* s);
71  NoGoods& nogoods(void);
73  ~DFS(void);
74  };
75 
77  DFS::DFS(Space* s, const Options& o)
78  : opt(o), path(opt.nogoods_limit), d(0) {
79  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
80  fail++;
81  cur = NULL;
82  if (!opt.clone)
83  delete s;
84  } else {
85  cur = snapshot(s,opt);
86  }
87  }
88 
89  forceinline void
91  delete cur;
92  path.reset();
93  d = 0;
94  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
95  delete s;
96  cur = NULL;
97  } else {
98  cur = s;
99  }
100  Worker::reset();
101  }
102 
104  DFS::nogoods(void) {
105  return path;
106  }
107 
109  DFS::next(void) {
110  /*
111  * The engine maintains the following invariant:
112  * - If the current space (cur) is not NULL, the path always points
113  * to exactly that space.
114  * - If the current space (cur) is NULL, the path always points
115  * to the next space (if there is any).
116  *
117  * This invariant is needed so that no-goods can be extracted properly
118  * when the engine is stopped or has found a solution.
119  *
120  */
121  start();
122  while (true) {
123  if (stop(opt))
124  return NULL;
125  while (cur == NULL) {
126  if (path.empty())
127  return NULL;
128  cur = path.recompute(d,opt.a_d,*this);
129  if (cur != NULL)
130  break;
131  path.next();
132  }
133  node++;
134  switch (cur->status(*this)) {
135  case SS_FAILED:
136  fail++;
137  delete cur;
138  cur = NULL;
139  path.next();
140  break;
141  case SS_SOLVED:
142  {
143  // Deletes all pending branchers
144  (void) cur->choice();
145  Space* s = cur;
146  cur = NULL;
147  path.next();
148  return s;
149  }
150  case SS_BRANCH:
151  {
152  Space* c;
153  if ((d == 0) || (d >= opt.c_d)) {
154  c = cur->clone();
155  d = 1;
156  } else {
157  c = NULL;
158  d++;
159  }
160  const Choice* ch = path.push(*this,cur,c);
161  cur->commit(*ch,0);
162  break;
163  }
164  default:
165  GECODE_NEVER;
166  }
167  }
168  GECODE_NEVER;
169  return NULL;
170  }
171 
173  DFS::statistics(void) const {
174  return *this;
175  }
176 
177  forceinline void
179  (void) b;
180  assert(false);
181  }
182 
184  DFS::~DFS(void) {
185  delete cur;
186  path.reset();
187  }
188 
189 }}}
190 
191 #endif
192 
193 // STATISTICS: search-sequential
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:455
Space must be branched (at least one brancher left)
Definition: core.hpp:1691
~DFS(void)
Destructor.
Definition: dfs.hh:184
Search engine statistics
Definition: search.hh:140
Statistics statistics(void) const
Return statistics.
Definition: dfs.hh:173
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:453
Search engine options
Definition: search.hh:446
const Choice * push(Worker &stat, Space *s, Space *c)
Push space c (a clone of s or NULL)
Definition: path.hh:222
Space * next(void)
Search for next solution
Definition: dfs.hh:109
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:61
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:143
bool empty(void) const
Test whether path is empty.
Definition: path.hh:251
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3326
Computation spaces.
Definition: core.hpp:1748
void start(void)
Reset stop information.
Definition: worker.hh:78
Gecode::FloatVal c(-8, 8)
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s)
Recompute space according to path.
Definition: path.hh:290
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3334
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition: dfs.hh:178
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition: dfs.hh:77
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:449
void reset(void)
Reset stack.
Definition: path.hh:284
Search worker statistics
Definition: worker.hh:48
NoGoods & nogoods(void)
Return no-goods.
Definition: dfs.hh:104
Choice for performing commit
Definition: core.hpp:1414
No-goods recorded from restarts.
Definition: core.hpp:1595
#define forceinline
Definition: config.hpp:173
void next(void)
Generate path for next node.
Definition: path.hh:234
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:224
Space * snapshot(Space *s, const Options &o, bool share=true)
Clone space s dependening on options o.
Definition: support.hh:75
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
Definition: search.hh:145
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:127
Space is failed
Definition: core.hpp:1689
const Choice * choice(void)
Create new choice for current brancher.
Definition: core.cpp:503
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
bool stop(const Options &o)
Check whether engine must be stopped.
Definition: worker.hh:83
Depth-first search engine implementation.
Definition: dfs.hh:49
void reset(void)
Reset.
Definition: statistics.hpp:43
Space is solved (no brancher left)
Definition: core.hpp:1690