Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.1
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: 2015-01-08 15:07:24 +0100 (Thu, 08 Jan 2015) $ by $Author: schulte $
11  * $Revision: 14341 $
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  void 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) const;
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 void
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;
241  }
242  }
243 
245  Path::top(void) const {
246  assert(!ds.empty());
247  return ds.top();
248  }
249 
250  forceinline bool
251  Path::empty(void) const {
252  return ds.empty();
253  }
254 
255  forceinline void
256  Path::commit(Space* s, int i) const {
257  const Edge& n = ds[i];
258  s->commit(*n.choice(),n.alt());
259  }
260 
261  forceinline int
262  Path::lc(void) const {
263  int l = ds.entries()-1;
264  while (ds[l].space() == NULL)
265  l--;
266  return l;
267  }
268 
269  forceinline int
270  Path::entries(void) const {
271  return ds.entries();
272  }
273 
274  forceinline void
276  assert((ds[l].space() == NULL) || ds[l].space()->failed());
277  int n = ds.entries();
278  for (int i=l; i<n; i++)
279  ds.pop().dispose();
280  assert(ds.entries() == l);
281  }
282 
283  inline void
284  Path::reset(void) {
285  while (!ds.empty())
286  ds.pop().dispose();
287  }
288 
290  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
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 (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);
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 
354  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
355  const Space& best, int& mark) {
356  assert(!ds.empty());
357  // Recompute space according to path
358  // Also say distance to copy (d == 0) requires immediate copying
359 
360  // Check for LAO
361  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
362  Space* s = ds.top().space();
363  s->commit(*ds.top().choice(),ds.top().alt());
364  assert(ds.entries()-1 == lc());
365  if (mark > ds.entries()-1) {
366  mark = ds.entries()-1;
367  s->constrain(best);
368  }
369  ds.top().space(NULL);
370  // Mark as reusable
371  if (ds.entries() > ngdl())
372  ds.top().next();
373  d = 0;
374  return s;
375  }
376  // General case for recomputation
377  int l = lc(); // Position of last clone
378  int n = ds.entries(); // Number of stack entries
379  // New distance, if no adaptive recomputation
380  d = static_cast<unsigned int>(n - l);
381 
382  Space* s = ds[l].space(); // Last clone
383 
384  if (l < mark) {
385  mark = l;
386  s->constrain(best);
387  // The space on the stack could be failed now as an additional
388  // constraint might have been added.
389  if (s->status(stat) == SS_FAILED) {
390  // s does not need deletion as it is on the stack (unwind does this)
391  stat.fail++;
392  unwind(l);
393  return NULL;
394  }
395  // It is important to replace the space on the stack with the
396  // copy: a copy might be much smaller due to flushed caches
397  // of propagators
398  Space* c = s->clone();
399  ds[l].space(c);
400  } else {
401  s = s->clone();
402  }
403 
404  if (d < a_d) {
405  // No adaptive recomputation
406  for (int i=l; i<n; i++)
407  commit(s,i);
408  } else {
409  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
410  int i = l; // To iterate over all entries
411  // Recompute up to middle
412  for (; i<m; i++ )
413  commit(s,i);
414  // Skip over all rightmost branches
415  for (; (i<n) && ds[i].rightmost(); i++)
416  commit(s,i);
417  // Is there any point to make a copy?
418  if (i<n-1) {
419  // Propagate to fixpoint
420  SpaceStatus ss = s->status(stat);
421  /*
422  * Again, the space might already propagate to failure
423  *
424  * This can be for two reasons:
425  * - constrain is true, so we fail
426  * - the space has weakly monotonic propagators
427  */
428  if (ss == SS_FAILED) {
429  // s must be deleted as it is not on the stack
430  delete s;
431  stat.fail++;
432  unwind(i);
433  return NULL;
434  }
435  ds[i].space(s->clone());
436  d = static_cast<unsigned int>(n-i);
437  }
438  // Finally do the remaining commits
439  for (; i<n; i++)
440  commit(s,i);
441  }
442  return s;
443  }
444 
445 }}}
446 
447 #endif
448 
449 // 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:262
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:2854
SpaceStatus
Space status
Definition: core.hpp:1300
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:275
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:1362
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:270
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:290
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:2862
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:645
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:105
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hh:245
virtual void post(Space &home) const
Post no-goods.
Definition: path.cpp:43
void reset(void)
Reset stack.
Definition: path.hh:284
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:132
void next(void)
Generate path for next node.
Definition: path.hh:234
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:252
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:256
Gecode toplevel namespace
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:1301
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:251