Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
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 
34 namespace 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) {
49  }
50 
51  template<class Tracer>
54  return _space;
55  }
56  template<class Tracer>
57  forceinline void
59  _space = s;
60  }
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>
80  forceinline bool
82  return _alt >= _alt_max;
83  }
84  template<class Tracer>
85  forceinline bool
87  return _alt > _alt_max;
88  }
89  template<class Tracer>
90  forceinline bool
92  return _alt < _alt_max;
93  }
94  template<class Tracer>
95  forceinline void
97  _alt++;
98  }
99  template<class Tracer>
100  forceinline unsigned int
102  assert(work());
103  return _alt_max--;
104  }
105 
106  template<class Tracer>
107  forceinline const Choice*
109  return _choice;
110  }
111 
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) {}
130 
131  template<class Tracer>
132  forceinline unsigned int
133  Path<Tracer>::ngdl(void) const {
134  return _ngdl;
135  }
136 
137  template<class Tracer>
138  forceinline void
139  Path<Tracer>::ngdl(unsigned int l) {
140  _ngdl = l;
141  }
142 
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();
149  }
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
182  Path<Tracer>::empty(void) const {
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
204  Path<Tracer>::entries(void) const {
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
246  Path<Tracer>::steal(void) const {
247  return n_work > Config::steal_limit;
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
449  Path<Tracer>::post(Space& home) const {
450  GECODE_ES_FAIL(NoGoodsProp::post(home,*this));
451  }
452 
453 }}}
454 
455 // STATISTICS: search-par
Edge information.
Definition: search.hh:242
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3697
NodeType t
Type of node.
Definition: bool-expr.cpp:230
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hpp:64
bool work(void) const
Test whether there is an alternative that can be stolen.
Definition: path.hpp:91
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:238
unsigned int n_work
Number of edges that have work for stealing.
Definition: path.hh:119
SpaceStatus
Space status
Definition: core.hpp:1640
unsigned long int steal_depth(unsigned long int d) const
Return steal depth.
Definition: worker.hh:106
unsigned int _alt
Current alternative.
Definition: path.hh:71
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition: path.hpp:81
ID _nid
Node identifier.
Definition: path.hh:77
bool empty(void) const
Test whether path is empty.
Definition: path.hpp:168
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition: path.hpp:128
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:150
void dispose(void)
Free memory for edge.
Definition: path.hpp:114
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:115
Search tree edge for recomputation
Definition: path.hh:66
#define forceinline
Definition: config.hpp:185
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:70
Computation spaces.
Definition: core.hpp:1701
int entries(void) const
Return number of entries on stack.
Definition: path.hpp:190
Gecode::IntSet d(v, 7)
Gecode::FloatVal c(-8, 8)
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3181
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:115
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3189
unsigned int steal(void)
Steal rightmost alternative and return its number.
Definition: path.hpp:101
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:813
unsigned int _ngdl
Depth limit for no-good generation.
Definition: path.hh:117
const Choice * choice(void) const
Return choice.
Definition: path.hpp:108
Edge(void)
Default constructor.
Definition: path.hpp:42
Search worker statistics
Definition: worker.hh:44
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:60
void next(void)
Move to next alternative.
Definition: path.hpp:87
Choice for performing commit
Definition: core.hpp:1371
void next(void)
Move to next alternative.
Definition: path.hpp:96
unsigned int _alt_max
Number of alternatives left.
Definition: path.hh:73
Heap heap
The single global heap.
Definition: heap.cpp:44
bool lao(void) const
Test whether current alternative was LAO.
Definition: path.hpp:86
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:232
Tracer.
Definition: tracer.hpp:149
void stack_depth(unsigned long int d)
Record stack depth d.
Definition: worker.hh:100
Gecode toplevel namespace
const Choice * _choice
Choice.
Definition: path.hh:75
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:76
Space is failed
Definition: core.hpp:1641
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition: search.hh:118
struct Gecode::@593::NNF::@62::@64 a
For atomic nodes.
Space * space(void) const
Return space for edge.
Definition: path.hpp:53
Space * _space
Space corresponding to this edge (might be NULL)
Definition: path.hh:69
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hpp:161