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;
181 assert(_alt < _choice->alternatives());
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++)
344 d = stat.
steal_depth(static_cast<unsigned long int>(n+1));
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) {
429 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);
unsigned int alternatives(void) const
Return number of alternatives.
Depth-first path (stack of edges) supporting recomputation.
bool empty(void) const
Test whether path is empty.
Search tree edge for recomputation
Edge(void)
Default constructor.
unsigned long int steal_depth(unsigned long int d) const
Return steal depth.
unsigned long int fail
Number of failed nodes in search tree.
int lc(void) const
Return position on stack of last copy.
unsigned int n_work
Number of edges that have work for stealing.
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
void * mark(void *p)
Return marked pointer for p.
void reset(unsigned int l)
Reset stack and set no-good depth limit to l.
const Choice * _choice
Choice.
unsigned int alt(void) const
Return number for alternatives.
void next(void)
Move to next alternative.
Gecode::FloatVal c(-8, 8)
const FloatNum min
Smallest allowed float value.
Gecode::IntArgs i(4, 1, 2, 3, 4)
void unwind(int l)
Unwind the stack up to position l (after failure)
unsigned int steal(void)
Steal rightmost alternative and return its number.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Edge & top(void) const
Provide access to topmost edge.
int entries(void) const
Return number of entries on stack.
const Choice * push(Worker &stat, Space *s, Space *c)
Push space c (a clone of s or NULL)
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
virtual void constrain(const Space &best)
Constrain function for best solution search.
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
unsigned int _ngdl
Depth limit for no-good generation.
unsigned int _alt
Current alternative.
Space * _space
Space corresponding to this edge (might be NULL)
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s)
Recompute space according to path.
void dispose(void)
Free memory for edge.
unsigned int ngdl(void) const
Return no-good depth limit.
void next(void)
Generate path for next node.
virtual void post(Space &home) const
Post no-goods.
Choice for performing commit
No-goods recorded from restarts.
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
bool rightmost(void) const
Test whether current alternative is rightmost.
Heap heap
The single global heap.
Stack with arbitrary number of elements.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
bool steal(void) const
Make a quick check whether stealing might be feasible.
void stack_depth(unsigned long int d)
Record stack depth d.
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Path(unsigned int l)
Initialize with no-good depth limit l.
Gecode toplevel namespace
const Choice * choice(void) const
Return choice.
unsigned int _alt_max
Number of alternatives left.
unsigned long int n
Number of no-goods.
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Space * space(void) const
Return space for edge.
bool lao(void) const
Test whether current alternative was LAO.
bool work(void) const
Test whether there is an alternative that can be stolen.