Go to the documentation of this file.
34 namespace Gecode {
namespace Search {
namespace Par {
40 template<
class Tracer>
44 template<
class Tracer>
47 : _space(
c), _alt(0), _choice(s->choice()), _nid(nid) {
51 template<
class Tracer>
56 template<
class Tracer>
62 template<
class Tracer>
68 template<
class Tracer>
74 template<
class Tracer>
77 return std::min(_alt,_choice->alternatives()-1);
79 template<
class Tracer>
82 return _alt >= _alt_max;
84 template<
class Tracer>
87 return _alt > _alt_max;
89 template<
class Tracer>
92 return _alt < _alt_max;
94 template<
class Tracer>
99 template<
class Tracer>
106 template<
class Tracer>
112 template<
class Tracer>
126 template<
class Tracer>
131 template<
class Tracer>
137 template<
class Tracer>
143 template<
class Tracer>
146 if (!ds.empty() && ds.top().lao()) {
154 stat.
stack_depth(
static_cast<unsigned long int>(ds.entries()));
158 template<
class Tracer>
162 if (ds.top().rightmost()) {
165 assert(ds.top().work());
167 if (!ds.top().work())
173 template<
class Tracer>
180 template<
class Tracer>
186 template<
class Tracer>
189 const Edge&
n = ds[
i];
193 template<
class Tracer>
196 int l = ds.entries()-1;
197 while (ds[
l].space() == NULL)
202 template<
class Tracer>
208 template<
class Tracer>
211 assert((ds[
l].space() == NULL) || ds[
l].space()->failed());
212 int n = ds.entries();
214 for (
int i=
l;
i<
n;
i++) {
216 unsigned int fa = (
i !=
l) ? top.
alt() + 1 : top.
alt();
226 for (
int i=
l;
i<
n;
i++) {
232 assert(ds.entries() ==
l);
235 template<
class Tracer>
244 template<
class Tracer>
250 template<
class Tracer>
255 int n = ds.entries()-1;
264 while (ds[
l].space() == NULL)
266 Space*
c = ds[
l].space()->clone();
268 for (
int i=
l;
i<
n;
i++)
270 unsigned int a = ds[
n].steal();
271 c->commit(*ds[
n].choice(),
a);
275 ngdl(
std::min(ngdl(),
static_cast<unsigned int>(
n)));
278 ot.ei()->init(myt.wid(),ds[
n].nid(),
a, *
c, *ds[
n].choice());
287 template<
class Tracer>
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);
302 if (
static_cast<unsigned int>(ds.entries()) > ngdl())
309 int n = ds.entries();
311 d =
static_cast<unsigned int>(
n -
l);
317 for (
int i=
l;
i<
n;
i++)
320 int m =
l +
static_cast<int>(
d >> 1);
326 for (; (
i<
n) && ds[
i].rightmost();
i++)
344 d =
static_cast<unsigned int>(
n-
i);
353 template<
class Tracer>
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;
371 ds.top().space(NULL);
373 if (
static_cast<unsigned int>(ds.entries()) > ngdl())
380 int n = ds.entries();
382 d =
static_cast<unsigned int>(
n -
l);
408 for (
int i=
l;
i<
n;
i++)
411 int m =
l +
static_cast<int>(
d >> 1);
417 for (; (
i<
n) && ds[
i].rightmost();
i++)
438 d =
static_cast<unsigned int>(
n-
i);
447 template<
class Tracer>
unsigned int nid(void) const
Return node identifier.
bool rightmost(void) const
Test whether current alternative is rightmost.
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
bool work(void) const
Test whether there is an alternative that can be stolen.
void next(void)
Move to next alternative.
virtual void constrain(const Space &best)
Constrain function for best solution search.
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
unsigned int alternatives(void) const
Return number of alternatives.
unsigned long int fail
Number of failed nodes in search tree.
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Path(unsigned int l)
Initialize with no-good depth limit l.
Depth-first path (stack of edges) supporting recomputation.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
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.
const Choice * _choice
Choice.
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
bool lao(void) const
Test whether current alternative was LAO.
bool empty(void) const
Test whether path is empty.
unsigned int _alt_max
Number of alternatives left.
Gecode toplevel namespace
const Choice * choice(void) const
Return choice.
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Edge(void)
Default constructor.
unsigned int n_work
Number of edges that have work for stealing.
int entries(void) const
Return number of entries on stack.
const unsigned int steal_limit
Minimal number of open nodes for stealing.
unsigned int _ngdl
Depth limit for no-good generation.
unsigned long int steal_depth(unsigned long int d) const
Return steal depth.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Heap heap
The single global heap.
Space * space(void) const
Return space for edge.
void dispose(void)
Free memory for edge.
unsigned int steal(void)
Steal rightmost alternative and return its number.
void stack_depth(unsigned long int d)
Record stack depth d.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Gecode::FloatVal c(-8, 8)
int n
Number of negative literals for node type.
Choice for performing commit
unsigned int alt(void) const
Return number for alternatives.
Gecode::IntArgs i({1, 2, 3, 4})
@ SS_FAILED
Space is failed