Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
dfs.hpp
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 namespace Gecode { namespace Search { namespace Seq {
35 
36  template<class Tracer>
39  : tracer(o.tracer), opt(o), path(opt.nogoods_limit), d(0) {
40  if (tracer) {
41  tracer.engine(SearchTracer::EngineType::DFS, 1U);
42  tracer.worker();
43  }
44  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
45  fail++;
46  cur = NULL;
47  if (!opt.clone)
48  delete s;
49  } else {
50  cur = snapshot(s,opt);
51  }
52  }
53 
54  template<class Tracer>
55  forceinline void
57  tracer.round();
58  delete cur;
59  path.reset();
60  d = 0;
61  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
62  delete s;
63  cur = NULL;
64  } else {
65  cur = s;
66  }
67  Worker::reset();
68  }
69 
70  template<class Tracer>
73  return path;
74  }
75 
76  template<class Tracer>
79  /*
80  * The engine maintains the following invariant:
81  * - If the current space (cur) is not NULL, the path always points
82  * to exactly that space.
83  * - If the current space (cur) is NULL, the path always points
84  * to the next space (if there is any).
85  *
86  * This invariant is needed so that no-goods can be extracted properly
87  * when the engine is stopped or has found a solution.
88  *
89  */
90  start();
91  while (true) {
92  if (stop(opt))
93  return NULL;
94  while (cur == NULL) {
95  if (path.empty())
96  return NULL;
97  cur = path.recompute(d,opt.a_d,*this,tracer);
98  if (cur != NULL)
99  break;
100  path.next();
101  }
102  node++;
104  if (tracer && (path.entries() > 0)) {
105  typename Path<Tracer>::Edge& top = path.top();
106  ei.init(tracer.wid(), top.nid(), top.truealt(), *cur, *top.choice());
107  }
108  unsigned int nid = tracer.nid();
109  switch (cur->status(*this)) {
110  case SS_FAILED:
111  if (tracer) {
113  tracer.wid(), nid, *cur);
114  tracer.node(ei,ni);
115  }
116  fail++;
117  delete cur;
118  cur = NULL;
119  path.next();
120  break;
121  case SS_SOLVED:
122  {
123  if (tracer) {
125  tracer.wid(), nid, *cur);
126  tracer.node(ei,ni);
127  }
128  // Deletes all pending branchers
129  (void) cur->choice();
130  Space* s = cur;
131  cur = NULL;
132  path.next();
133  return s;
134  }
135  case SS_BRANCH:
136  {
137  Space* c;
138  if ((d == 0) || (d >= opt.c_d)) {
139  c = cur->clone();
140  d = 1;
141  } else {
142  c = NULL;
143  d++;
144  }
145  const Choice* ch = path.push(*this,cur,c,nid);
146  if (tracer) {
148  tracer.wid(), nid, *cur, ch);
149  tracer.node(ei,ni);
150  }
151  cur->commit(*ch,0);
152  break;
153  }
154  default:
155  GECODE_NEVER;
156  }
157  }
158  GECODE_NEVER;
159  return NULL;
160  }
161 
162  template<class Tracer>
165  return *this;
166  }
167 
168  template<class Tracer>
169  forceinline void
171  (void) b;
172  assert(false);
173  }
174 
175  template<class Tracer>
178  delete cur;
179  tracer.done();
180  path.reset();
181  }
182 
183 }}}
184 
185 // STATISTICS: search-seq
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Choice for performing commit
Definition: core.hpp:1412
No-goods recorded from restarts.
Definition: core.hpp:1588
Edge information.
Definition: search.hh:242
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition: tracer.hpp:107
Node information.
Definition: search.hh:282
Search engine options
Definition: search.hh:746
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:749
Space * next(void)
Search for next solution
Definition: dfs.hpp:78
Statistics statistics(void) const
Return statistics.
Definition: dfs.hpp:164
~DFS(void)
Destructor.
Definition: dfs.hpp:177
NoGoods & nogoods(void)
Return no-goods.
Definition: dfs.hpp:72
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition: dfs.hpp:170
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition: dfs.hpp:38
Search tree edge for recomputation
Definition: path.hh:66
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:67
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:99
const Choice * choice(void) const
Return choice.
Definition: path.hpp:93
Search engine statistics
Definition: search.hh:147
void reset(void)
Reset.
Definition: statistics.hpp:39
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:150
Computation spaces.
Definition: core.hpp:1742
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path.
Definition: circuit.cpp:124
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition: core.hpp:1684
@ SS_SOLVED
Space is solved (no brancher left)
Definition: core.hpp:1683
@ SS_FAILED
Space is failed
Definition: core.hpp:1682
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:42
@ FAILED
Node representing failure.
Definition: spacenode.hh:46
@ SOLVED
Node representing a solution.
Definition: spacenode.hh:45
@ BRANCH
Node representing a branch.
Definition: spacenode.hh:47
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:131
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Definition: support.hh:71
Gecode::FloatVal c(-8, 8)
Gecode::IntSet d(v, 7)
Options opt
The options.
Definition: test.cpp:97
#define forceinline
Definition: config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56