Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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 Par {
35
36 /*
37 * Edge for recomputation
38 *
39 */
40 template<class Tracer>
43
44 template<class Tracer>
47 : _space(c), _alt(0), _choice(s->choice()), _nid(nid) {
48 _alt_max = _choice->alternatives()-1;
49 }
50
51 template<class Tracer>
54 return _space;
55 }
56 template<class Tracer>
57 forceinline void
61
62 template<class Tracer>
63 forceinline unsigned int
65 return _alt;
66 }
67
68 template<class Tracer>
69 forceinline unsigned int
71 return _nid;
72 }
73
74 template<class Tracer>
75 forceinline unsigned int
77 return std::min(_alt,_choice->alternatives()-1);
78 }
79 template<class Tracer>
82 return _alt >= _alt_max;
83 }
84 template<class Tracer>
87 return _alt > _alt_max;
88 }
89 template<class Tracer>
92 return _alt < _alt_max;
93 }
94 template<class Tracer>
98 }
99 template<class Tracer>
100 forceinline unsigned int
102 assert(work());
103 return _alt_max--;
104 }
106 template<class Tracer>
107 forceinline const Choice*
109 return _choice;
110 }
112 template<class Tracer>
113 forceinline void
115 delete _space;
116 delete _choice;
117 }
118
119
120
121 /*
122 * Depth-first stack with recomputation
123 *
124 */
125
126 template<class Tracer>
128 Path<Tracer>::Path(unsigned int l)
129 : ds(heap), _ngdl(l), n_work(0) {}
131 template<class Tracer>
132 forceinline unsigned int
133 Path<Tracer>::ngdl(void) const {
134 return _ngdl;
135 }
137 template<class Tracer>
139 Path<Tracer>::ngdl(unsigned int l) {
140 _ngdl = l;
141 }
143 template<class Tracer>
144 forceinline const Choice*
145 Path<Tracer>::push(Worker& stat, Space* s, Space* c, unsigned int nid) {
146 if (!ds.empty() && ds.top().lao()) {
147 // Topmost stack entry was LAO -> reuse
148 ds.pop().dispose();
150 Edge sn(s,c,nid);
151 if (sn.work())
152 n_work++;
153 ds.push(sn);
154 stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
155 return sn.choice();
156 }
157
158 template<class Tracer>
159 forceinline void
161 while (!ds.empty())
162 if (ds.top().rightmost()) {
163 ds.pop().dispose();
164 } else {
165 assert(ds.top().work());
166 ds.top().next();
167 if (!ds.top().work())
168 n_work--;
169 return;
170 }
171 }
172
173 template<class Tracer>
175 Path<Tracer>::top(void) const {
176 assert(!ds.empty());
177 return ds.top();
178 }
179
180 template<class Tracer>
181 forceinline bool
183 return ds.empty();
184 }
185
186 template<class Tracer>
187 forceinline void
188 Path<Tracer>::commit(Space* s, int i) const {
189 const Edge& n = ds[i];
190 s->commit(*n.choice(),n.alt());
191 }
192
193 template<class Tracer>
194 forceinline int
195 Path<Tracer>::lc(void) const {
196 int l = ds.entries()-1;
197 while (ds[l].space() == NULL)
198 l--;
199 return l;
200 }
201
202 template<class Tracer>
203 forceinline int
205 return ds.entries();
206 }
207
208 template<class Tracer>
209 forceinline void
211 assert((ds[l].space() == NULL) || ds[l].space()->failed());
212 int n = ds.entries();
213 if (t) {
214 for (int i=l; i<n; i++) {
215 Path<Tracer>::Edge& top = ds.top();
216 unsigned int fa = (i != l) ? top.alt() + 1 : top.alt();
217 for (unsigned int a = fa; a < top.choice()->alternatives(); a++) {
218 SearchTracer::EdgeInfo ei(t.wid(), top.nid(), a);
219 t.skip(ei);
220 }
221 if (ds.top().work())
222 n_work--;
223 ds.pop().dispose();
224 }
225 } else {
226 for (int i=l; i<n; i++) {
227 if (ds.top().work())
228 n_work--;
229 ds.pop().dispose();
230 }
231 }
232 assert(ds.entries() == l);
233 }
234
235 template<class Tracer>
236 forceinline void
237 Path<Tracer>::reset(unsigned int l) {
238 n_work = 0;
239 while (!ds.empty())
240 ds.pop().dispose();
241 _ngdl = l;
242 }
243
244 template<class Tracer>
245 forceinline bool
248 }
249
250 template<class Tracer>
252 Path<Tracer>::steal(Worker& stat, unsigned long int& d,
253 Tracer& myt, Tracer& ot) {
254 // Find position to steal: leave sufficient work
255 int n = ds.entries()-1;
256 unsigned int w = 0;
257 while (n >= 0) {
258 if (ds[n].work())
259 w++;
260 if (w > Config::steal_limit) {
261 // Okay, there is sufficient work left
262 int l=n;
263 // Find last copy
264 while (ds[l].space() == NULL)
265 l--;
266 Space* c = ds[l].space()->clone();
267 // Recompute, if necessary
268 for (int i=l; i<n; i++)
269 commit(c,i);
270 unsigned int a = ds[n].steal();
271 c->commit(*ds[n].choice(),a);
272 if (!ds[n].work())
273 n_work--;
274 // No no-goods can be extracted above n
275 ngdl(std::min(ngdl(),static_cast<unsigned int>(n)));
276 d = stat.steal_depth(static_cast<unsigned long int>(n+1));
277 if (myt && ot) {
278 ot.ei()->init(myt.wid(),ds[n].nid(), a, *c, *ds[n].choice());
279 }
280 return c;
281 }
282 n--;
283 }
284 return NULL;
285 }
286
287 template<class Tracer>
289 Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
290 Tracer& t) {
291 assert(!ds.empty());
292 // Recompute space according to path
293 // Also say distance to copy (d == 0) requires immediate copying
294
295 // Check for LAO
296 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
297 Space* s = ds.top().space();
298 s->commit(*ds.top().choice(),ds.top().alt());
299 assert(ds.entries()-1 == lc());
300 ds.top().space(NULL);
301 // Mark as reusable
302 if (static_cast<unsigned int>(ds.entries()) > ngdl())
303 ds.top().next();
304 d = 0;
305 return s;
306 }
307 // General case for recomputation
308 int l = lc(); // Position of last clone
309 int n = ds.entries(); // Number of stack entries
310 // New distance, if no adaptive recomputation
311 d = static_cast<unsigned int>(n - l);
312
313 Space* s = ds[l].space()->clone(); // Last clone
314
315 if (d < a_d) {
316 // No adaptive recomputation
317 for (int i=l; i<n; i++)
318 commit(s,i);
319 } else {
320 int m = l + static_cast<int>(d >> 1); // Middle between copy and top
321 int i = l; // To iterate over all entries
322 // Recompute up to middle
323 for (; i<m; i++ )
324 commit(s,i);
325 // Skip over all rightmost branches
326 for (; (i<n) && ds[i].rightmost(); i++)
327 commit(s,i);
328 // Is there any point to make a copy?
329 if (i<n-1) {
330 // Propagate to fixpoint
331 SpaceStatus ss = s->status(stat);
332 /*
333 * Again, the space might already propagate to failure (due to
334 * weakly monotonic propagators).
335 */
336 if (ss == SS_FAILED) {
337 // s must be deleted as it is not on the stack
338 delete s;
339 stat.fail++;
340 unwind(i,t);
341 return NULL;
342 }
343 ds[i].space(s->clone());
344 d = static_cast<unsigned int>(n-i);
345 }
346 // Finally do the remaining commits
347 for (; i<n; i++)
348 commit(s,i);
349 }
350 return s;
351 }
352
353 template<class Tracer>
355 Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
356 const Space& best, int& mark,
357 Tracer& t) {
358 assert(!ds.empty());
359 // Recompute space according to path
360 // Also say distance to copy (d == 0) requires immediate copying
361
362 // Check for LAO
363 if ((ds.top().space() != NULL) && ds.top().rightmost()) {
364 Space* s = ds.top().space();
365 s->commit(*ds.top().choice(),ds.top().alt());
366 assert(ds.entries()-1 == lc());
367 if (mark > ds.entries()-1) {
368 mark = ds.entries()-1;
369 s->constrain(best);
370 }
371 ds.top().space(NULL);
372 // Mark as reusable
373 if (static_cast<unsigned int>(ds.entries()) > ngdl())
374 ds.top().next();
375 d = 0;
376 return s;
377 }
378 // General case for recomputation
379 int l = lc(); // Position of last clone
380 int n = ds.entries(); // Number of stack entries
381 // New distance, if no adaptive recomputation
382 d = static_cast<unsigned int>(n - l);
383
384 Space* s = ds[l].space(); // Last clone
385
386 if (l < mark) {
387 mark = l;
388 s->constrain(best);
389 // The space on the stack could be failed now as an additional
390 // constraint might have been added.
391 if (s->status(stat) == SS_FAILED) {
392 // s does not need deletion as it is on the stack (unwind does this)
393 stat.fail++;
394 unwind(l,t);
395 return NULL;
396 }
397 // It is important to replace the space on the stack with the
398 // copy: a copy might be much smaller due to flushed caches
399 // of propagators
400 Space* c = s->clone();
401 ds[l].space(c);
402 } else {
403 s = s->clone();
404 }
405
406 if (d < a_d) {
407 // No adaptive recomputation
408 for (int i=l; i<n; i++)
409 commit(s,i);
410 } else {
411 int m = l + static_cast<int>(d >> 1); // Middle between copy and top
412 int i = l; // To iterate over all entries
413 // Recompute up to middle
414 for (; i<m; i++ )
415 commit(s,i);
416 // Skip over all rightmost branches
417 for (; (i<n) && ds[i].rightmost(); i++)
418 commit(s,i);
419 // Is there any point to make a copy?
420 if (i<n-1) {
421 // Propagate to fixpoint
422 SpaceStatus ss = s->status(stat);
423 /*
424 * Again, the space might already propagate to failure
425 *
426 * This can be for two reasons:
427 * - constrain is true, so we fail
428 * - the space has weakly monotonic propagators
429 */
430 if (ss == SS_FAILED) {
431 // s must be deleted as it is not on the stack
432 delete s;
433 stat.fail++;
434 unwind(i,t);
435 return NULL;
436 }
437 ds[i].space(s->clone());
438 d = static_cast<unsigned int>(n-i);
439 }
440 // Finally do the remaining commits
441 for (; i<n; i++)
442 commit(s,i);
443 }
444 return s;
445 }
446
447 template<class Tracer>
448 void
451 }
452
453}}}
454
455// STATISTICS: search-par
Choice for performing commit
Definition core.hpp:1414
unsigned long int n
Number of no-goods.
Definition core.hpp:1593
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
bool work(void) const
Test whether there is an alternative that can be stolen.
Definition path.hpp:91
void dispose(void)
Free memory for edge.
Definition path.hpp:114
Edge(void)
Default constructor.
Definition path.hpp:42
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition path.hpp:76
bool lao(void) const
Test whether current alternative was LAO.
Definition path.hpp:86
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:70
const Choice * _choice
Choice.
Definition path.hh:75
unsigned int _alt_max
Number of alternatives left.
Definition path.hh:73
const Choice * choice(void) const
Return choice.
Definition path.hpp:108
Space * space(void) const
Return space for edge.
Definition path.hpp:53
unsigned int alt(void) const
Return number for alternatives.
Definition path.hpp:64
ID _nid
Node identifier.
Definition path.hh:77
unsigned int _alt
Current alternative.
Definition path.hh:71
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition path.hpp:81
unsigned int steal(void)
Steal rightmost alternative and return its number.
Definition path.hpp:101
void next(void)
Move to next alternative.
Definition path.hpp:96
Space * _space
Space corresponding to this edge (might be NULL)
Definition path.hh:69
void reset(unsigned int l)
Reset stack and set no-good depth limit to l.
Definition path.hpp:237
unsigned int ngdl(void) const
Return no-good depth limit.
Definition path.hpp:133
void unwind(int l, Tracer &t)
Unwind the stack up to position l (after failure)
Definition path.hpp:210
unsigned int n_work
Number of edges that have work for stealing.
Definition path.hh:119
const Choice * push(Worker &stat, Space *s, Space *c, unsigned int nid)
Push space c (a clone of s or NULL)
Definition path.hpp:145
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition path.hpp:128
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition path.hh:115
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition path.hpp:188
void next(void)
Generate path for next node.
Definition path.hpp:160
bool empty(void) const
Test whether path is empty.
Definition path.hpp:182
virtual void post(Space &home) const
Post no-goods.
Definition path.hpp:449
unsigned int _ngdl
Depth limit for no-good generation.
Definition path.hh:117
int lc(void) const
Return position on stack of last copy.
Definition path.hpp:195
int entries(void) const
Return number of entries on stack.
Definition path.hpp:204
Edge & top(void) const
Provide access to topmost edge.
Definition path.hpp:175
bool steal(void) const
Make a quick check whether stealing might be feasible.
Definition path.hpp:246
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s, Tracer &t)
Recompute space according to path.
Definition path.hpp:289
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
Search worker statistics
Definition worker.hh:44
unsigned long int steal_depth(unsigned long int d) const
Return steal depth.
Definition worker.hh:106
void stack_depth(unsigned long int d)
Record stack depth d.
Definition worker.hh:100
Computation spaces.
Definition core.hpp:1744
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:842
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition core.hpp:3236
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:3228
SpaceStatus
Space status
Definition core.hpp:1683
@ SS_FAILED
Space is failed
Definition core.hpp:1684
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition search.hh:118
Search engines
Gecode toplevel namespace
#define forceinline
Definition config.hpp:194