Generated on Sat Sep 13 2014 13:24:48 for Gecode by doxygen 1.8.7
path.hh
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: 2013-07-12 18:20:11 +0200 (Fri, 12 Jul 2013) $ by $Author: schulte $
11  * $Revision: 13877 $
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 #ifndef __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
39 #define __GECODE_SEARCH_SEQUENTIAL_PATH_HH__
40 
41 #include <gecode/search.hh>
42 #include <gecode/search/support.hh>
43 #include <gecode/search/worker.hh>
45 
46 namespace Gecode { namespace Search { namespace Sequential {
47 
61  class Path : public NoGoods {
63  public:
65  class Edge {
66  protected:
70  unsigned int _alt;
72  const Choice* _choice;
73  public:
75  Edge(void);
77  Edge(Space* s, Space* c);
78 
80  Space* space(void) const;
82  void space(Space* s);
83 
85  const Choice* choice(void) const;
86 
88  unsigned int alt(void) const;
90  unsigned int truealt(void) const;
92  bool leftmost(void) const;
94  bool rightmost(void) const;
96  void next(void);
98  bool lao(void) const;
99 
101  void dispose(void);
102  };
103  protected:
107  int _ngdl;
108  public:
110  Path(int l);
112  int ngdl(void) const;
114  void ngdl(int l);
116  const Choice* push(Worker& stat, Space* s, Space* c);
118  bool next(void);
120  Edge& top(void) const;
122  bool empty(void) const;
124  int lc(void) const;
126  void unwind(int l);
128  void commit(Space* s, int i) const;
130  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s);
132  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
133  const Space* best, int& mark);
135  int entries(void) const;
137  void reset(void);
139  void virtual post(Space& home);
140  };
141 
142 
143  /*
144  * Edge for recomputation
145  *
146  */
149 
152  : _space(c), _alt(0), _choice(s->choice()) {}
153 
155  Path::Edge::space(void) const {
156  return _space;
157  }
158  forceinline void
160  _space = s;
161  }
162 
163  forceinline unsigned int
164  Path::Edge::alt(void) const {
165  return _alt;
166  }
167  forceinline unsigned int
168  Path::Edge::truealt(void) const {
169  assert(_alt < _choice->alternatives());
170  return _alt;
171  }
172  forceinline bool
173  Path::Edge::leftmost(void) const {
174  return _alt == 0;
175  }
176  forceinline bool
177  Path::Edge::rightmost(void) const {
178  return _alt+1 >= _choice->alternatives();
179  }
180  forceinline bool
181  Path::Edge::lao(void) const {
182  return _alt >= _choice->alternatives();
183  }
184  forceinline void
186  _alt++;
187  }
188 
189  forceinline const Choice*
190  Path::Edge::choice(void) const {
191  return _choice;
192  }
193 
194  forceinline void
196  delete _space;
197  delete _choice;
198  }
199 
200 
201 
202  /*
203  * Depth-first stack with recomputation
204  *
205  */
206 
208  Path::Path(int l)
209  : ds(heap), _ngdl(l) {}
210 
211  forceinline int
212  Path::ngdl(void) const {
213  return _ngdl;
214  }
215 
216  forceinline void
217  Path::ngdl(int l) {
218  _ngdl = l;
219  }
220 
221  forceinline const Choice*
222  Path::push(Worker& stat, Space* s, Space* c) {
223  if (!ds.empty() && ds.top().lao()) {
224  // Topmost stack entry was LAO -> reuse
225  ds.pop().dispose();
226  }
227  Edge sn(s,c);
228  ds.push(sn);
229  stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
230  return sn.choice();
231  }
232 
233  forceinline bool
234  Path::next(void) {
235  while (!ds.empty())
236  if (ds.top().rightmost()) {
237  ds.pop().dispose();
238  } else {
239  ds.top().next();
240  return true;
241  }
242  return false;
243  }
244 
246  Path::top(void) const {
247  assert(!ds.empty());
248  return ds.top();
249  }
250 
251  forceinline bool
252  Path::empty(void) const {
253  return ds.empty();
254  }
255 
256  forceinline void
257  Path::commit(Space* s, int i) const {
258  const Edge& n = ds[i];
259  s->commit(*n.choice(),n.alt());
260  }
261 
262  forceinline int
263  Path::lc(void) const {
264  int l = ds.entries()-1;
265  while (ds[l].space() == NULL)
266  l--;
267  return l;
268  }
269 
270  forceinline int
271  Path::entries(void) const {
272  return ds.entries();
273  }
274 
275  forceinline void
277  assert((ds[l].space() == NULL) || ds[l].space()->failed());
278  int n = ds.entries();
279  for (int i=l; i<n; i++)
280  ds.pop().dispose();
281  assert(ds.entries() == l);
282  }
283 
284  inline void
285  Path::reset(void) {
286  while (!ds.empty())
287  ds.pop().dispose();
288  }
289 
291  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
292  assert(!ds.empty());
293  // Recompute space according to path
294  // Also say distance to copy (d == 0) requires immediate copying
295 
296  // Check for LAO
297  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
298  Space* s = ds.top().space();
299  s->commit(*ds.top().choice(),ds.top().alt());
300  assert(ds.entries()-1 == lc());
301  ds.top().space(NULL);
302  // Mark as reusable
303  if (ds.entries() > ngdl())
304  ds.top().next();
305  d = 0;
306  return s;
307  }
308  // General case for recomputation
309  int l = lc(); // Position of last clone
310  int n = ds.entries(); // Number of stack entries
311  // New distance, if no adaptive recomputation
312  d = static_cast<unsigned int>(n - l);
313 
314  Space* s = ds[l].space()->clone(); // Last clone
315 
316  if (d < a_d) {
317  // No adaptive recomputation
318  for (int i=l; i<n; i++)
319  commit(s,i);
320  } else {
321  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
322  int i = l; // To iterate over all entries
323  // Recompute up to middle
324  for (; i<m; i++ )
325  commit(s,i);
326  // Skip over all rightmost branches
327  for (; (i<n) && ds[i].rightmost(); i++)
328  commit(s,i);
329  // Is there any point to make a copy?
330  if (i<n-1) {
331  // Propagate to fixpoint
332  SpaceStatus ss = s->status(stat);
333  /*
334  * Again, the space might already propagate to failure (due to
335  * weakly monotonic propagators).
336  */
337  if (ss == SS_FAILED) {
338  // s must be deleted as it is not on the stack
339  delete s;
340  stat.fail++;
341  unwind(i);
342  return NULL;
343  }
344  ds[i].space(s->clone());
345  d = static_cast<unsigned int>(n-i);
346  }
347  // Finally do the remaining commits
348  for (; i<n; i++)
349  commit(s,i);
350  }
351  return s;
352  }
353 
355  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
356  const Space* best, int& mark) {
357  assert(!ds.empty());
358  // Recompute space according to path
359  // Also say distance to copy (d == 0) requires immediate copying
360 
361  // Check for LAO
362  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
363  Space* s = ds.top().space();
364  s->commit(*ds.top().choice(),ds.top().alt());
365  assert(ds.entries()-1 == lc());
366  if (mark > ds.entries()-1) {
367  mark = ds.entries()-1;
368  s->constrain(*best);
369  }
370  ds.top().space(NULL);
371  // Mark as reusable
372  if (ds.entries() > ngdl())
373  ds.top().next();
374  d = 0;
375  return s;
376  }
377  // General case for recomputation
378  int l = lc(); // Position of last clone
379  int n = ds.entries(); // Number of stack entries
380  // New distance, if no adaptive recomputation
381  d = static_cast<unsigned int>(n - l);
382 
383  Space* s = ds[l].space(); // Last clone
384 
385  if (l < mark) {
386  mark = l;
387  s->constrain(*best);
388  // The space on the stack could be failed now as an additional
389  // constraint might have been added.
390  if (s->status(stat) == SS_FAILED) {
391  // s does not need deletion as it is on the stack (unwind does this)
392  stat.fail++;
393  unwind(l);
394  return NULL;
395  }
396  // It is important to replace the space on the stack with the
397  // copy: a copy might be much smaller due to flushed caches
398  // of propagators
399  Space* c = s->clone();
400  ds[l].space(c);
401  } else {
402  s = s->clone();
403  }
404 
405  if (d < a_d) {
406  // No adaptive recomputation
407  for (int i=l; i<n; i++)
408  commit(s,i);
409  } else {
410  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
411  int i = l; // To iterate over all entries
412  // Recompute up to middle
413  for (; i<m; i++ )
414  commit(s,i);
415  // Skip over all rightmost branches
416  for (; (i<n) && ds[i].rightmost(); i++)
417  commit(s,i);
418  // Is there any point to make a copy?
419  if (i<n-1) {
420  // Propagate to fixpoint
421  SpaceStatus ss = s->status(stat);
422  /*
423  * Again, the space might already propagate to failure
424  *
425  * This can be for two reasons:
426  * - constrain is true, so we fail
427  * - the space has weakly monotonic propagators
428  */
429  if (ss == SS_FAILED) {
430  // s must be deleted as it is not on the stack
431  delete s;
432  stat.fail++;
433  unwind(i);
434  return NULL;
435  }
436  ds[i].space(s->clone());
437  d = static_cast<unsigned int>(n-i);
438  }
439  // Finally do the remaining commits
440  for (; i<n; i++)
441  commit(s,i);
442  }
443  return s;
444  }
445 
446 }}}
447 
448 #endif
449 
450 // STATISTICS: search-sequential
Search tree edge for recomputation
Definition: path.hh:65
Space * _space
Space corresponding to this edge (might be NULL)
Definition: path.hh:68
int lc(void) const
Return position on stack of last copy.
Definition: path.hh:263
void next(void)
Move to next alternative.
Definition: path.hh:185
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Edge(void)
Default constructor.
Definition: path.hh:148
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:2777
SpaceStatus
Space status
Definition: core.hpp:1263
const Choice * push(Worker &stat, Space *s, Space *c)
Push space c (a clone of s or NULL)
Definition: path.hh:222
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hh:164
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:61
void unwind(int l)
Unwind the stack up to position l (after failure)
Definition: path.hh:276
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:139
void * mark(void *p)
Return marked pointer for p.
Computation spaces.
Definition: core.hpp:1325
Heap heap
The single global heap.
Definition: heap.cpp:49
Gecode::IntSet d(v, 7)
int entries(void) const
Return number of entries on stack.
Definition: path.hh:271
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i(4, 1, 2, 3, 4)
const Choice * _choice
Choice.
Definition: path.hh:72
bool lao(void) const
Test whether current alternative was LAO.
Definition: path.hh:181
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:99
No-good propagator.
Definition: nogoods.hh:67
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s)
Recompute space according to path.
Definition: path.hh:291
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:2785
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:644
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:105
virtual void post(Space &home)
Post no-goods.
Definition: path.cpp:43
bool next(void)
Generate path for next node and return whether a next node exists.
Definition: path.hh:234
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hh:246
void reset(void)
Reset stack.
Definition: path.hh:285
Search worker statistics
Definition: worker.hh:48
void dispose(void)
Free memory for edge.
Definition: path.hh:195
Choice for performing commit
Definition: core.hpp:1036
No-goods recorded from restarts.
Definition: core.hpp:1240
#define forceinline
Definition: config.hpp:129
Stack with arbitrary number of elements.
Space * space(void) const
Return space for edge.
Definition: path.hh:155
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:251
void stack_depth(unsigned long int d)
Record stack depth d.
Definition: worker.hh:104
Path(int l)
Initialize with no-good depth limit l.
Definition: path.hh:208
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition: path.hh:177
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition: path.hh:257
bool leftmost(void) const
Test whether current alternative is leftmost.
Definition: path.hh:173
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hh:168
Space is failed
Definition: core.hpp:1264
unsigned long int n
Number of no-goods.
Definition: core.hpp:1243
int ngdl(void) const
Return no-good depth limit.
Definition: path.hh:212
unsigned int _alt
Current alternative.
Definition: path.hh:70
const Choice * choice(void) const
Return choice.
Definition: path.hh:190
int _ngdl
Depth limit for no-good generation.
Definition: path.hh:107
bool empty(void) const
Test whether path is empty.
Definition: path.hh:252