Generated on Sat Jun 6 2015 00:39:53 for Gecode by doxygen 1.8.9.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: 2015-03-20 15:37:34 +0100 (Fri, 20 Mar 2015) $ by $Author: schulte $
11  * $Revision: 14471 $
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 reset(Space* s);
69  NoGoods& nogoods(void);
71  ~DFS(void);
72  };
73 
75  DFS::DFS(Space* s, const Options& o)
76  : opt(o), path(opt.nogoods_limit), d(0) {
77  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
78  fail++;
79  cur = NULL;
80  if (!opt.clone)
81  delete s;
82  } else {
83  cur = snapshot(s,opt);
84  }
85  }
86 
87  forceinline void
89  delete cur;
90  path.reset();
91  d = 0;
92  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
93  delete s;
94  cur = NULL;
95  } else {
96  cur = s;
97  }
98  Worker::reset();
99  }
100 
102  DFS::nogoods(void) {
103  return path;
104  }
105 
107  DFS::next(void) {
108  /*
109  * The engine maintains the following invariant:
110  * - If the current space (cur) is not NULL, the path always points
111  * to exactly that space.
112  * - If the current space (cur) is NULL, the path always points
113  * to the next space (if there is any).
114  *
115  * This invariant is needed so that no-goods can be extracted properly
116  * when the engine is stopped or has found a solution.
117  *
118  */
119  start();
120  while (true) {
121  if (stop(opt))
122  return NULL;
123  while (cur == NULL) {
124  if (path.empty())
125  return NULL;
126  cur = path.recompute(d,opt.a_d,*this);
127  if (cur != NULL)
128  break;
129  path.next();
130  }
131  node++;
132  switch (cur->status(*this)) {
133  case SS_FAILED:
134  fail++;
135  delete cur;
136  cur = NULL;
137  path.next();
138  break;
139  case SS_SOLVED:
140  {
141  // Deletes all pending branchers
142  (void) cur->choice();
143  Space* s = cur;
144  cur = NULL;
145  path.next();
146  return s;
147  }
148  case SS_BRANCH:
149  {
150  Space* c;
151  if ((d == 0) || (d >= opt.c_d)) {
152  c = cur->clone();
153  d = 1;
154  } else {
155  c = NULL;
156  d++;
157  }
158  const Choice* ch = path.push(*this,cur,c);
159  cur->commit(*ch,0);
160  break;
161  }
162  default:
163  GECODE_NEVER;
164  }
165  }
166  GECODE_NEVER;
167  return NULL;
168  }
169 
171  DFS::statistics(void) const {
172  return *this;
173  }
174 
175  forceinline
176  DFS::~DFS(void) {
177  delete cur;
178  path.reset();
179  }
180 
181 }}}
182 
183 #endif
184 
185 // STATISTICS: search-sequential
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:458
Space must be branched (at least one brancher left)
Definition: core.hpp:1303
~DFS(void)
Destructor.
Definition: dfs.hh:176
Search engine statistics
Definition: search.hh:136
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:456
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:2854
Search engine options
Definition: search.hh:449
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:107
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:139
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntConLevel icl)
Post propagator such that x forms a Hamiltonian path.
Definition: circuit.cpp:128
Computation spaces.
Definition: core.hpp:1362
Statistics statistics(void) const
Return statistics.
Definition: dfs.hh:171
Gecode::IntSet d(v, 7)
void start(void)
Reset stop information.
Definition: worker.hh:78
Gecode::FloatVal c(-8, 8)
Options opt
The options.
Definition: test.cpp:101
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:2862
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition: dfs.hh:75
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:452
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:102
Choice for performing commit
Definition: core.hpp:1036
No-goods recorded from restarts.
Definition: core.hpp:1240
#define forceinline
Definition: config.hpp:132
void next(void)
Generate path for next node.
Definition: path.hh:234
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
Space * snapshot(Space *s, const Options &o, bool share=true)
Clone space s dependening on options o.
Definition: support.hh:73
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
Definition: search.hh:141
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:107
Space is failed
Definition: core.hpp:1301
const Choice * choice(void)
Create new choice for current brancher.
Definition: core.cpp:366
#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
bool empty(void) const
Test whether path is empty.
Definition: path.hh:251
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:1302