Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
path.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, 2003
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
34namespace Gecode { namespace Search { namespace Seq {
35
36 /*
37 * Edge for recomputation
38 *
39 */
40 template<class Tracer>
43
44 template<class Tracer>
46 Path<Tracer>::Edge::Edge(Space* s, Space* c, unsigned int nid)
47 : _space(c), _alt(0), _choice(s->choice()), _nid(nid) {}
48
49 template<class Tracer>
52 return _space;
53 }
54 template<class Tracer>
55 forceinline void
57 _space = s;
58 }
59
60 template<class Tracer>
61 forceinline unsigned int
63 return _alt;
64 }
65 template<class Tracer>
66 forceinline unsigned int
68 return std::min(_alt,_choice->alternatives()-1);
69 }
70 template<class Tracer>
71 forceinline bool
73 return _alt == 0;
74 }
75 template<class Tracer>
76 forceinline bool
78 return _alt+1 >= _choice->alternatives();
79 }
80 template<class Tracer>
81 forceinline bool
83 return _alt >= _choice->alternatives();
84 }
85 template<class Tracer>
86 forceinline void
88 _alt++;
89 }
90
91 template<class Tracer>
92 forceinline const Choice*
94 return _choice;
95 }
96
97 template<class Tracer>
98 forceinline unsigned int
100 return _nid;
102
103 template<class Tracer>
106 delete _space;
107 delete _choice;
108 }
109
110
111
112 /*
113 * Depth-first stack with recomputation
114 *
115 */
117 template<class Tracer>
119 Path<Tracer>::Path(unsigned int l)
120 : ds(heap), _ngdl(l) {}
121
122 template<class Tracer>
123 forceinline unsigned int
124 Path<Tracer>::ngdl(void) const {
125 return _ngdl;
127
128 template<class Tracer>
129 forceinline void
130 Path<Tracer>::ngdl(unsigned int l) {
131 _ngdl = l;
133
134 template<class Tracer>
135 forceinline const Choice*
136 Path<Tracer>::push(Worker& stat, Space* s, Space* c, unsigned int nid) {
137 if (!ds.empty() && ds.top().lao()) {
138 // Topmost stack entry was LAO -> reuse
139 ds.pop().dispose();
140 }
141 Edge sn(s,c,nid);
142 ds.push(sn);
143 stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
144 return sn.choice();
146
147 template<class Tracer>
148 forceinline void
150 while (!ds.empty())
151 if (ds.top().rightmost()) {
152 ds.pop().dispose();
153 } else {
154 ds.top().next();
155 return;
156 }
157 }
158
159 template<class Tracer>
161 Path<Tracer>::top(void) const {
162 assert(!ds.empty());
163 return ds.top();
164 }
165
166 template<class Tracer>
167 forceinline bool
169 return ds.empty();
170 }
171
172 template<class Tracer>
173 forceinline void
174 Path<Tracer>::commit(Space* s, int i) const {
175 const Edge& n = ds[i];
176 s->commit(*n.choice(),n.alt());
177 }
178
179 template<class Tracer>
180 forceinline int
181 Path<Tracer>::lc(void) const {
182 int l = ds.entries()-1;
183 while (ds[l].space() == NULL)
184 l--;
185 return l;
186 }
187
188 template<class Tracer>
189 forceinline int
191 return ds.entries();
192 }
193
194 template<class Tracer>
195 forceinline void
197 assert((ds[l].space() == NULL) || ds[l].space()->failed());
198 int n = ds.entries();
199 if (t) {
200 for (int i=l; i<n; i++) {
201 Path<Tracer>::Edge& top = ds.top();
202 unsigned int fa = (i != l) ? top.alt() + 1 : top.alt();
203 for (unsigned int a = fa; a < top.choice()->alternatives(); a++) {
204 SearchTracer::EdgeInfo ei(t.wid(),top.nid(),a);
205 t.skip(ei);
206 }
207 ds.pop().dispose();
208 }
209 } else {
210 for (int i=l; i<n; i++)
211 ds.pop().dispose();
212 }
213 assert(ds.entries() == l);
214 }
215
216 template<class Tracer>
217 inline void
219 while (!ds.empty())
220 ds.pop().dispose();
221 }
222
223 template<class Tracer>
225 Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
226 Tracer& t) {
227 assert(!ds.empty());
228 // Recompute space according to path
229 // Also say distance to copy (d == 0) requires immediate copying
230
231 // Check for LAO
232 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
233 Space* s = ds.top().space();
234 s->commit(*ds.top().choice(),ds.top().alt());
235 assert(ds.entries()-1 == lc());
236 ds.top().space(NULL);
237 // Mark as reusable
238 if (static_cast<unsigned int>(ds.entries()) > ngdl())
239 ds.top().next();
240 d = 0;
241 return s;
242 }
243 // General case for recomputation
244 int l = lc(); // Position of last clone
245 int n = ds.entries(); // Number of stack entries
246 // New distance, if no adaptive recomputation
247 d = static_cast<unsigned int>(n - l);
248
249 Space* s = ds[l].space()->clone(); // Last clone
250
251 if (d < a_d) {
252 // No adaptive recomputation
253 for (int i=l; i<n; i++)
254 commit(s,i);
255 } else {
256 int m = l + static_cast<int>(d >> 1); // Middle between copy and top
257 int i = l; // To iterate over all entries
258 // Recompute up to middle
259 for (; i<m; i++ )
260 commit(s,i);
261 // Skip over all rightmost branches
262 for (; (i<n) && ds[i].rightmost(); i++)
263 commit(s,i);
264 // Is there any point to make a copy?
265 if (i<n-1) {
266 // Propagate to fixpoint
267 SpaceStatus ss = s->status(stat);
268 /*
269 * Again, the space might already propagate to failure (due to
270 * weakly monotonic propagators).
271 */
272 if (ss == SS_FAILED) {
273 // s must be deleted as it is not on the stack
274 delete s;
275 stat.fail++;
276 unwind(i,t);
277 return NULL;
278 }
279 ds[i].space(s->clone());
280 d = static_cast<unsigned int>(n-i);
281 }
282 // Finally do the remaining commits
283 for (; i<n; i++)
284 commit(s,i);
285 }
286 return s;
287 }
288
289 template<class Tracer>
291 Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
292 const Space& best, int& mark,
293 Tracer& t) {
294 assert(!ds.empty());
295 // Recompute space according to path
296 // Also say distance to copy (d == 0) requires immediate copying
297
298 // Check for LAO
299 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
300 Space* s = ds.top().space();
301 s->commit(*ds.top().choice(),ds.top().alt());
302 assert(ds.entries()-1 == lc());
303 if (mark > ds.entries()-1) {
304 mark = ds.entries()-1;
305 s->constrain(best);
306 }
307 ds.top().space(NULL);
308 // Mark as reusable
309 if (static_cast<unsigned int>(ds.entries()) > ngdl())
310 ds.top().next();
311 d = 0;
312 return s;
313 }
314 // General case for recomputation
315 int l = lc(); // Position of last clone
316 int n = ds.entries(); // Number of stack entries
317 // New distance, if no adaptive recomputation
318 d = static_cast<unsigned int>(n - l);
319
320 Space* s = ds[l].space(); // Last clone
321
322 if (l < mark) {
323 mark = l;
324 s->constrain(best);
325 // The space on the stack could be failed now as an additional
326 // constraint might have been added.
327 if (s->status(stat) == SS_FAILED) {
328 // s does not need deletion as it is on the stack (unwind does this)
329 stat.fail++;
330 unwind(l,t);
331 return NULL;
332 }
333 // It is important to replace the space on the stack with the
334 // copy: a copy might be much smaller due to flushed caches
335 // of propagators
336 Space* c = s->clone();
337 ds[l].space(c);
338 } else {
339 s = s->clone();
340 }
341
342 if (d < a_d) {
343 // No adaptive recomputation
344 for (int i=l; i<n; i++)
345 commit(s,i);
346 } else {
347 int m = l + static_cast<int>(d >> 1); // Middle between copy and top
348 int i = l; // To iterate over all entries
349 // Recompute up to middle
350 for (; i<m; i++ )
351 commit(s,i);
352 // Skip over all rightmost branches
353 for (; (i<n) && ds[i].rightmost(); i++)
354 commit(s,i);
355 // Is there any point to make a copy?
356 if (i<n-1) {
357 // Propagate to fixpoint
358 SpaceStatus ss = s->status(stat);
359 /*
360 * Again, the space might already propagate to failure
361 *
362 * This can be for two reasons:
363 * - constrain is true, so we fail
364 * - the space has weakly monotonic propagators
365 */
366 if (ss == SS_FAILED) {
367 // s must be deleted as it is not on the stack
368 delete s;
369 stat.fail++;
370 unwind(i,t);
371 return NULL;
372 }
373 ds[i].space(s->clone());
374 d = static_cast<unsigned int>(n-i);
375 }
376 // Finally do the remaining commits
377 for (; i<n; i++)
378 commit(s,i);
379 }
380 return s;
381 }
382
383 template<class Tracer>
384 void
387 }
388
389}}}
390
391// STATISTICS: search-seq
NNF * l
Left subtree.
NodeType t
Type of node.
struct Gecode::@603::NNF::@65::@67 a
For atomic nodes.
Choice for performing commit
Definition core.hpp:1412
unsigned long int n
Number of no-goods.
Definition core.hpp:1591
static ExecStatus post(Space &home, const Path &p)
Post propagator for path p.
Definition nogoods.hpp:90
Search tree edge for recomputation
Definition path.hh:66
Space * space(void) const
Return space for edge.
Definition path.hpp:51
unsigned int alt(void) const
Return number for alternatives.
Definition path.hpp:62
Edge(void)
Default constructor.
Definition path.hpp:42
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition path.hpp:77
void next(void)
Move to next alternative.
Definition path.hpp:87
bool leftmost(void) const
Test whether current alternative is leftmost.
Definition path.hpp:72
bool lao(void) const
Test whether current alternative was LAO.
Definition path.hpp:82
void dispose(void)
Free memory for edge.
Definition path.hpp:105
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
unsigned int _ngdl
Depth limit for no-good generation.
Definition path.hh:113
void unwind(int l, Tracer &t)
Unwind the stack up to position l (after failure)
Definition path.hpp:196
bool empty(void) const
Test whether path is empty.
Definition path.hpp:168
int entries(void) const
Return number of entries on stack.
Definition path.hpp:190
int lc(void) const
Return position on stack of last copy.
Definition path.hpp:181
void next(void)
Generate path for next node.
Definition path.hpp:149
virtual void post(Space &home) const
Post no-goods.
Definition path.hpp:385
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition path.hpp:174
unsigned int ngdl(void) const
Return no-good depth limit.
Definition path.hpp:124
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition path.hh:111
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition path.hpp:119
Edge & top(void) const
Provide access to topmost edge.
Definition path.hpp:161
void reset(void)
Reset stack.
Definition path.hpp:218
const Choice * push(Worker &stat, Space *s, Space *c, unsigned int nid)
Push space c (a clone of s or NULL)
Definition path.hpp:136
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s, Tracer &t)
Recompute space according to path.
Definition path.hpp:225
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
Search worker statistics
Definition worker.hh:44
void stack_depth(unsigned long int d)
Record stack depth d.
Definition worker.hh:100
Computation spaces.
Definition core.hpp:1742
Heap heap
The single global heap.
Definition heap.cpp:44
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:841
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition core.hpp:3232
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
SpaceStatus
Space status
Definition core.hpp:1681
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode toplevel namespace
#define forceinline
Definition config.hpp:187