Generated on Fri Jan 28 2022 04:43:06 for Gecode by doxygen 1.8.13
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
Edge information.
Definition: search.hh:242
unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:755
Space must be branched (at least one brancher left)
Definition: core.hpp:1643
Search engine statistics
Definition: search.hh:147
Node representing a branch.
Definition: spacenode.hh:47
unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:753
Search engine options
Definition: search.hh:746
const Choice * choice(void) const
Return choice.
Definition: path.hpp:93
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
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:150
Node representing failure.
Definition: spacenode.hh:46
~DFS(void)
Destructor.
Definition: dfs.hpp:177
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:99
#define forceinline
Definition: config.hpp:185
Computation spaces.
Definition: core.hpp:1701
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:67
Gecode::IntSet d(v, 7)
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition: dfs.hpp:38
void start(void)
Reset stop information.
Definition: worker.hh:74
Gecode::FloatVal c(-8, 8)
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition: tracer.hpp:107
Options opt
The options.
Definition: test.cpp:97
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3181
NoGoods & nogoods(void)
Return no-goods.
Definition: dfs.hpp:72
Node representing a solution.
Definition: spacenode.hh:45
void constrain(const Space &b)
Constrain future solutions to be better than b (should never be called)
Definition: dfs.hpp:170
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3189
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Search tree edge for recomputation
Definition: path.hh:66
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:749
Choice for performing commit
Definition: core.hpp:1371
No-goods recorded from restarts.
Definition: core.hpp:1547
Space * next(void)
Search for next solution
Definition: dfs.hpp:78
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:232
Node information.
Definition: search.hh:282
Statistics statistics(void) const
Return statistics.
Definition: dfs.hpp:164
Gecode toplevel namespace
unsigned long int node
Number of nodes expanded.
Definition: search.hh:152
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
Space is failed
Definition: core.hpp:1641
const Choice * choice(void)
Create new choice for current brancher.
Definition: core.cpp:511
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
bool stop(const Options &o)
Check whether engine must be stopped.
Definition: worker.hh:79
void reset(void)
Reset.
Definition: statistics.hpp:39
Space is solved (no brancher left)
Definition: core.hpp:1642