Generated on Thu Apr 5 2018 19:44:19 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  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Search { namespace Par {
39 
40  /*
41  * Edge for recomputation
42  *
43  */
44  template<class Tracer>
47 
48  template<class Tracer>
51  : _space(c), _alt(0), _choice(s->choice()), _nid(nid) {
53  }
54 
55  template<class Tracer>
58  return _space;
59  }
60  template<class Tracer>
61  forceinline void
63  _space = s;
64  }
65 
66  template<class Tracer>
67  forceinline unsigned int
69  return _alt;
70  }
71 
72  template<class Tracer>
73  forceinline unsigned int
75  return _nid;
76  }
77 
78  template<class Tracer>
79  forceinline unsigned int
81  return std::min(_alt,_choice->alternatives()-1);
82  }
83  template<class Tracer>
84  forceinline bool
86  return _alt >= _alt_max;
87  }
88  template<class Tracer>
89  forceinline bool
91  return _alt > _alt_max;
92  }
93  template<class Tracer>
94  forceinline bool
96  return _alt < _alt_max;
97  }
98  template<class Tracer>
99  forceinline void
101  _alt++;
102  }
103  template<class Tracer>
104  forceinline unsigned int
106  assert(work());
107  return _alt_max--;
108  }
109 
110  template<class Tracer>
111  forceinline const Choice*
113  return _choice;
114  }
115 
116  template<class Tracer>
117  forceinline void
119  delete _space;
120  delete _choice;
121  }
122 
123 
124 
125  /*
126  * Depth-first stack with recomputation
127  *
128  */
129 
130  template<class Tracer>
132  Path<Tracer>::Path(unsigned int l)
133  : ds(heap), _ngdl(l), n_work(0) {}
134 
135  template<class Tracer>
136  forceinline unsigned int
137  Path<Tracer>::ngdl(void) const {
138  return _ngdl;
139  }
140 
141  template<class Tracer>
142  forceinline void
143  Path<Tracer>::ngdl(unsigned int l) {
144  _ngdl = l;
145  }
146 
147  template<class Tracer>
148  forceinline const Choice*
149  Path<Tracer>::push(Worker& stat, Space* s, Space* c, unsigned int nid) {
150  if (!ds.empty() && ds.top().lao()) {
151  // Topmost stack entry was LAO -> reuse
152  ds.pop().dispose();
153  }
154  Edge sn(s,c,nid);
155  if (sn.work())
156  n_work++;
157  ds.push(sn);
158  stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
159  return sn.choice();
160  }
161 
162  template<class Tracer>
163  forceinline void
165  while (!ds.empty())
166  if (ds.top().rightmost()) {
167  ds.pop().dispose();
168  } else {
169  assert(ds.top().work());
170  ds.top().next();
171  if (!ds.top().work())
172  n_work--;
173  return;
174  }
175  }
176 
177  template<class Tracer>
179  Path<Tracer>::top(void) const {
180  assert(!ds.empty());
181  return ds.top();
182  }
183 
184  template<class Tracer>
185  forceinline bool
186  Path<Tracer>::empty(void) const {
187  return ds.empty();
188  }
189 
190  template<class Tracer>
191  forceinline void
192  Path<Tracer>::commit(Space* s, int i) const {
193  const Edge& n = ds[i];
194  s->commit(*n.choice(),n.alt());
195  }
196 
197  template<class Tracer>
198  forceinline int
199  Path<Tracer>::lc(void) const {
200  int l = ds.entries()-1;
201  while (ds[l].space() == NULL)
202  l--;
203  return l;
204  }
205 
206  template<class Tracer>
207  forceinline int
208  Path<Tracer>::entries(void) const {
209  return ds.entries();
210  }
211 
212  template<class Tracer>
213  forceinline void
215  assert((ds[l].space() == NULL) || ds[l].space()->failed());
216  int n = ds.entries();
217  if (t) {
218  for (int i=l; i<n; i++) {
219  Path<Tracer>::Edge& top = ds.top();
220  unsigned int fa = (i != l) ? top.alt() + 1 : top.alt();
221  for (unsigned int a = fa; a < top.choice()->alternatives(); a++) {
222  SearchTracer::EdgeInfo ei(t.wid(), top.nid(), a);
223  t.skip(ei);
224  }
225  if (ds.top().work())
226  n_work--;
227  ds.pop().dispose();
228  }
229  } else {
230  for (int i=l; i<n; i++) {
231  if (ds.top().work())
232  n_work--;
233  ds.pop().dispose();
234  }
235  }
236  assert(ds.entries() == l);
237  }
238 
239  template<class Tracer>
240  forceinline void
241  Path<Tracer>::reset(unsigned int l) {
242  n_work = 0;
243  while (!ds.empty())
244  ds.pop().dispose();
245  _ngdl = l;
246  }
247 
248  template<class Tracer>
249  forceinline bool
250  Path<Tracer>::steal(void) const {
251  return n_work > Config::steal_limit;
252  }
253 
254  template<class Tracer>
256  Path<Tracer>::steal(Worker& stat, unsigned long int& d,
257  Tracer& myt, Tracer& ot) {
258  // Find position to steal: leave sufficient work
259  int n = ds.entries()-1;
260  unsigned int w = 0;
261  while (n >= 0) {
262  if (ds[n].work())
263  w++;
264  if (w > Config::steal_limit) {
265  // Okay, there is sufficient work left
266  int l=n;
267  // Find last copy
268  while (ds[l].space() == NULL)
269  l--;
270  Space* c = ds[l].space()->clone();
271  // Recompute, if necessary
272  for (int i=l; i<n; i++)
273  commit(c,i);
274  unsigned int a = ds[n].steal();
275  c->commit(*ds[n].choice(),a);
276  if (!ds[n].work())
277  n_work--;
278  // No no-goods can be extracted above n
279  ngdl(std::min(ngdl(),static_cast<unsigned int>(n)));
280  d = stat.steal_depth(static_cast<unsigned long int>(n+1));
281  if (myt && ot) {
282  ot.ei()->init(myt.wid(),ds[n].nid(), a, *c, *ds[n].choice());
283  }
284  return c;
285  }
286  n--;
287  }
288  return NULL;
289  }
290 
291  template<class Tracer>
293  Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
294  Tracer& t) {
295  assert(!ds.empty());
296  // Recompute space according to path
297  // Also say distance to copy (d == 0) requires immediate copying
298 
299  // Check for LAO
300  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
301  Space* s = ds.top().space();
302  s->commit(*ds.top().choice(),ds.top().alt());
303  assert(ds.entries()-1 == lc());
304  ds.top().space(NULL);
305  // Mark as reusable
306  if (static_cast<unsigned int>(ds.entries()) > ngdl())
307  ds.top().next();
308  d = 0;
309  return s;
310  }
311  // General case for recomputation
312  int l = lc(); // Position of last clone
313  int n = ds.entries(); // Number of stack entries
314  // New distance, if no adaptive recomputation
315  d = static_cast<unsigned int>(n - l);
316 
317  Space* s = ds[l].space()->clone(); // Last clone
318 
319  if (d < a_d) {
320  // No adaptive recomputation
321  for (int i=l; i<n; i++)
322  commit(s,i);
323  } else {
324  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
325  int i = l; // To iterate over all entries
326  // Recompute up to middle
327  for (; i<m; i++ )
328  commit(s,i);
329  // Skip over all rightmost branches
330  for (; (i<n) && ds[i].rightmost(); i++)
331  commit(s,i);
332  // Is there any point to make a copy?
333  if (i<n-1) {
334  // Propagate to fixpoint
335  SpaceStatus ss = s->status(stat);
336  /*
337  * Again, the space might already propagate to failure (due to
338  * weakly monotonic propagators).
339  */
340  if (ss == SS_FAILED) {
341  // s must be deleted as it is not on the stack
342  delete s;
343  stat.fail++;
344  unwind(i,t);
345  return NULL;
346  }
347  ds[i].space(s->clone());
348  d = static_cast<unsigned int>(n-i);
349  }
350  // Finally do the remaining commits
351  for (; i<n; i++)
352  commit(s,i);
353  }
354  return s;
355  }
356 
357  template<class Tracer>
359  Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
360  const Space& best, int& mark,
361  Tracer& t) {
362  assert(!ds.empty());
363  // Recompute space according to path
364  // Also say distance to copy (d == 0) requires immediate copying
365 
366  // Check for LAO
367  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
368  Space* s = ds.top().space();
369  s->commit(*ds.top().choice(),ds.top().alt());
370  assert(ds.entries()-1 == lc());
371  if (mark > ds.entries()-1) {
372  mark = ds.entries()-1;
373  s->constrain(best);
374  }
375  ds.top().space(NULL);
376  // Mark as reusable
377  if (static_cast<unsigned int>(ds.entries()) > ngdl())
378  ds.top().next();
379  d = 0;
380  return s;
381  }
382  // General case for recomputation
383  int l = lc(); // Position of last clone
384  int n = ds.entries(); // Number of stack entries
385  // New distance, if no adaptive recomputation
386  d = static_cast<unsigned int>(n - l);
387 
388  Space* s = ds[l].space(); // Last clone
389 
390  if (l < mark) {
391  mark = l;
392  s->constrain(best);
393  // The space on the stack could be failed now as an additional
394  // constraint might have been added.
395  if (s->status(stat) == SS_FAILED) {
396  // s does not need deletion as it is on the stack (unwind does this)
397  stat.fail++;
398  unwind(l,t);
399  return NULL;
400  }
401  // It is important to replace the space on the stack with the
402  // copy: a copy might be much smaller due to flushed caches
403  // of propagators
404  Space* c = s->clone();
405  ds[l].space(c);
406  } else {
407  s = s->clone();
408  }
409 
410  if (d < a_d) {
411  // No adaptive recomputation
412  for (int i=l; i<n; i++)
413  commit(s,i);
414  } else {
415  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
416  int i = l; // To iterate over all entries
417  // Recompute up to middle
418  for (; i<m; i++ )
419  commit(s,i);
420  // Skip over all rightmost branches
421  for (; (i<n) && ds[i].rightmost(); i++)
422  commit(s,i);
423  // Is there any point to make a copy?
424  if (i<n-1) {
425  // Propagate to fixpoint
426  SpaceStatus ss = s->status(stat);
427  /*
428  * Again, the space might already propagate to failure
429  *
430  * This can be for two reasons:
431  * - constrain is true, so we fail
432  * - the space has weakly monotonic propagators
433  */
434  if (ss == SS_FAILED) {
435  // s must be deleted as it is not on the stack
436  delete s;
437  stat.fail++;
438  unwind(i,t);
439  return NULL;
440  }
441  ds[i].space(s->clone());
442  d = static_cast<unsigned int>(n-i);
443  }
444  // Finally do the remaining commits
445  for (; i<n; i++)
446  commit(s,i);
447  }
448  return s;
449  }
450 
451  template<class Tracer>
452  void
453  Path<Tracer>::post(Space& home) const {
454  GECODE_ES_FAIL(NoGoodsProp::post(home,*this));
455  }
456 
457 }}}
458 
459 // STATISTICS: search-par
Edge information.
Definition: search.hh:244
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3640
NodeType t
Type of node.
Definition: bool-expr.cpp:234
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hpp:68
bool work(void) const
Test whether there is an alternative that can be stolen.
Definition: path.hpp:95
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:242
unsigned int n_work
Number of edges that have work for stealing.
Definition: path.hh:123
SpaceStatus
Space status
Definition: core.hpp:1607
unsigned long int steal_depth(unsigned long int d) const
Return steal depth.
Definition: worker.hh:110
unsigned int _alt
Current alternative.
Definition: path.hh:75
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition: path.hpp:85
ID _nid
Node identifier.
Definition: path.hh:81
bool empty(void) const
Test whether path is empty.
Definition: path.hpp:172
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition: path.hpp:132
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:152
void dispose(void)
Free memory for edge.
Definition: path.hpp:118
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:119
Search tree edge for recomputation
Definition: path.hh:70
#define forceinline
Definition: config.hpp:182
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:74
Computation spaces.
Definition: core.hpp:1668
int entries(void) const
Return number of entries on stack.
Definition: path.hpp:194
Gecode::IntSet d(v, 7)
Gecode::FloatVal c(-8, 8)
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3144
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:117
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:3152
unsigned int steal(void)
Steal rightmost alternative and return its number.
Definition: path.hpp:105
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:807
unsigned int _ngdl
Depth limit for no-good generation.
Definition: path.hh:121
const Choice * choice(void) const
Return choice.
Definition: path.hpp:112
Edge(void)
Default constructor.
Definition: path.hpp:46
Search worker statistics
Definition: worker.hh:48
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:64
void next(void)
Move to next alternative.
Definition: path.hpp:91
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1338
void next(void)
Move to next alternative.
Definition: path.hpp:100
unsigned int _alt_max
Number of alternatives left.
Definition: path.hh:77
Heap heap
The single global heap.
Definition: heap.cpp:48
bool lao(void) const
Test whether current alternative was LAO.
Definition: path.hpp:90
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:229
Tracer.
Definition: tracer.hpp:153
void stack_depth(unsigned long int d)
Record stack depth d.
Definition: worker.hh:104
Gecode toplevel namespace
const Choice * _choice
Choice.
Definition: path.hh:79
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:80
Space is failed
Definition: core.hpp:1608
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:107
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition: search.hh:120
Space * space(void) const
Return space for edge.
Definition: path.hpp:57
Space * _space
Space corresponding to this edge (might be NULL)
Definition: path.hh:73
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hpp:165