Go to the documentation of this file.
38 #ifndef __GECODE_SEARCH_PARALLEL_PATH_HH__
39 #define __GECODE_SEARCH_PARALLEL_PATH_HH__
46 namespace Gecode {
namespace Search {
namespace Parallel {
90 unsigned int alt(
void)
const;
92 unsigned int truealt(
void)
const;
98 bool work(
void)
const;
102 unsigned int steal(
void);
116 Path(
unsigned int l);
118 unsigned int ngdl(
void)
const;
120 void ngdl(
unsigned int l);
128 bool empty(
void)
const;
143 void reset(
unsigned int l);
145 bool steal(
void)
const;
162 : _space(
c), _alt(0), _choice(s->choice()) {
181 assert(_alt < _choice->alternatives());
186 return _alt >= _alt_max;
190 return _alt > _alt_max;
194 return _alt < _alt_max;
240 if (!
ds.empty() &&
ds.top().lao()) {
248 stat.
stack_depth(
static_cast<unsigned long int>(
ds.entries()));
255 if (
ds.top().rightmost()) {
258 assert(
ds.top().work());
260 if (!
ds.top().work())
285 int l =
ds.entries()-1;
286 while (
ds[
l].space() == NULL)
298 assert((
ds[
l].space() == NULL) ||
ds[
l].space()->failed());
299 int n =
ds.entries();
300 for (
int i=
l;
i<
n;
i++) {
305 assert(
ds.entries() ==
l);
324 int n =
ds.entries()-1;
333 while (
ds[
l].space() == NULL)
337 for (
int i=
l;
i<
n;
i++)
359 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
362 assert(
ds.entries()-1 ==
lc());
363 ds.top().space(NULL);
365 if (
static_cast<unsigned int>(
ds.entries()) >
ngdl())
372 int n =
ds.entries();
374 d =
static_cast<unsigned int>(
n -
l);
380 for (
int i=
l;
i<
n;
i++)
383 int m =
l +
static_cast<int>(
d >> 1);
389 for (; (
i<
n) &&
ds[
i].rightmost();
i++)
407 d =
static_cast<unsigned int>(
n-
i);
424 if ((
ds.top().space() != NULL) &&
ds.top().rightmost()) {
427 assert(
ds.entries()-1 ==
lc());
428 if (
mark >
ds.entries()-1) {
432 ds.top().space(NULL);
434 if (
static_cast<unsigned int>(
ds.entries()) >
ngdl())
441 int n =
ds.entries();
443 d =
static_cast<unsigned int>(
n -
l);
469 for (
int i=
l;
i<
n;
i++)
472 int m =
l +
static_cast<int>(
d >> 1);
478 for (; (
i<
n) &&
ds[
i].rightmost();
i++)
499 d =
static_cast<unsigned int>(
n-
i);
Space * _space
Space corresponding to this edge (might be NULL)
Depth-first path (stack of edges) supporting recomputation.
bool lao(void) const
Test whether current alternative was LAO.
Path(unsigned int l)
Initialize with no-good depth limit l.
int lc(void) const
Return position on stack of last copy.
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
virtual void constrain(const Space &best)
Constrain function for best solution search.
unsigned int alternatives(void) const
Return number of alternatives.
unsigned long int fail
Number of failed nodes in search tree.
unsigned int n_work
Number of edges that have work for stealing.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Search tree edge for recomputation
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
const FloatNum min
Smallest allowed float value.
bool empty(void) const
Test whether path is empty.
unsigned int _alt_max
Number of alternatives left.
const Choice * _choice
Choice.
void dispose(void)
Free memory for edge.
Gecode toplevel namespace
unsigned int _ngdl
Depth limit for no-good generation.
No-goods recorded from restarts.
bool work(void) const
Test whether there is an alternative that can be stolen.
void next(void)
Generate path for next node.
void reset(unsigned int l)
Reset stack and set no-good depth limit to l.
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Edge & top(void) const
Provide access to topmost edge.
const unsigned int steal_limit
Minimal number of open nodes for stealing.
unsigned long int steal_depth(unsigned long int d) const
Return steal depth.
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
const Choice * push(Worker &stat, Space *s, Space *c)
Push space c (a clone of s or NULL)
void next(void)
Move to next alternative.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Heap heap
The single global heap.
const Choice * choice(void) const
Return choice.
void unwind(int l)
Unwind the stack up to position l (after failure)
int entries(void) const
Return number of entries on stack.
unsigned int steal(void)
Steal rightmost alternative and return its number.
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Edge(void)
Default constructor.
Stack with arbitrary number of elements.
void stack_depth(unsigned long int d)
Record stack depth d.
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s)
Recompute space according to path.
bool rightmost(void) const
Test whether current alternative is rightmost.
unsigned long int n
Number of no-goods.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Gecode::FloatVal c(-8, 8)
unsigned int ngdl(void) const
Return no-good depth limit.
Choice for performing commit
Space * space(void) const
Return space for edge.
@ SS_FAILED
Space is failed
unsigned int alt(void) const
Return number for alternatives.
virtual void post(Space &home) const
Post no-goods.
unsigned int _alt
Current alternative.
bool steal(void) const
Make a quick check whether stealing might be feasible.