path.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
*
* Copyright:
* Christian Schulte, 2003
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
namespace Gecode { namespace Search { namespace Seq {
/*
* Edge for recomputation
*
*/
template<class Tracer>
forceinline
Path<Tracer>::Edge::Edge(void) {}
template<class Tracer>
forceinline
Path<Tracer>::Edge::Edge(Space* s, Space* c, unsigned int nid)
: _space(c), _alt(0), _choice(s->choice()), _nid(nid) {}
template<class Tracer>
forceinline Space*
Path<Tracer>::Edge::space(void) const {
return _space;
}
template<class Tracer>
forceinline void
Path<Tracer>::Edge::space(Space* s) {
_space = s;
}
template<class Tracer>
forceinline unsigned int
Path<Tracer>::Edge::alt(void) const {
return _alt;
}
template<class Tracer>
forceinline unsigned int
Path<Tracer>::Edge::truealt(void) const {
return std::min(_alt,_choice->alternatives()-1);
}
template<class Tracer>
forceinline bool
Path<Tracer>::Edge::leftmost(void) const {
return _alt == 0;
}
template<class Tracer>
forceinline bool
Path<Tracer>::Edge::rightmost(void) const {
return _alt+1 >= _choice->alternatives();
}
template<class Tracer>
forceinline bool
Path<Tracer>::Edge::lao(void) const {
return _alt >= _choice->alternatives();
}
template<class Tracer>
forceinline void
Path<Tracer>::Edge::next(void) {
_alt++;
}
template<class Tracer>
forceinline const Choice*
Path<Tracer>::Edge::choice(void) const {
return _choice;
}
template<class Tracer>
forceinline unsigned int
Path<Tracer>::Edge::nid(void) const {
return _nid;
}
template<class Tracer>
forceinline void
Path<Tracer>::Edge::dispose(void) {
delete _space;
delete _choice;
}
/*
* Depth-first stack with recomputation
*
*/
template<class Tracer>
forceinline
Path<Tracer>::Path(unsigned int l)
: ds(heap), _ngdl(l) {}
template<class Tracer>
forceinline unsigned int
Path<Tracer>::ngdl(void) const {
return _ngdl;
}
template<class Tracer>
forceinline void
Path<Tracer>::ngdl(unsigned int l) {
_ngdl = l;
}
template<class Tracer>
forceinline const Choice*
Path<Tracer>::push(Worker& stat, Space* s, Space* c, unsigned int nid) {
if (!ds.empty() && ds.top().lao()) {
// Topmost stack entry was LAO -> reuse
ds.pop().dispose();
}
Edge sn(s,c,nid);
ds.push(sn);
stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
return sn.choice();
}
template<class Tracer>
forceinline void
Path<Tracer>::next(void) {
while (!ds.empty())
if (ds.top().rightmost()) {
ds.pop().dispose();
} else {
ds.top().next();
return;
}
}
template<class Tracer>
forceinline typename Path<Tracer>::Edge&
Path<Tracer>::top(void) const {
assert(!ds.empty());
return ds.top();
}
template<class Tracer>
forceinline bool
Path<Tracer>::empty(void) const {
return ds.empty();
}
template<class Tracer>
forceinline void
Path<Tracer>::commit(Space* s, int i) const {
const Edge& n = ds[i];
s->commit(*n.choice(),n.alt());
}
template<class Tracer>
forceinline int
Path<Tracer>::lc(void) const {
int l = ds.entries()-1;
while (ds[l].space() == NULL)
l--;
return l;
}
template<class Tracer>
forceinline int
Path<Tracer>::entries(void) const {
return ds.entries();
}
template<class Tracer>
forceinline void
Path<Tracer>::unwind(int l, Tracer& t) {
assert((ds[l].space() == NULL) || ds[l].space()->failed());
int n = ds.entries();
if (t) {
for (int i=l; i<n; i++) {
Path<Tracer>::Edge& top = ds.top();
unsigned int fa = (i != l) ? top.alt() + 1 : top.alt();
for (unsigned int a = fa; a < top.choice()->alternatives(); a++) {
SearchTracer::EdgeInfo ei(t.wid(),top.nid(),a);
t.skip(ei);
}
ds.pop().dispose();
}
} else {
for (int i=l; i<n; i++)
ds.pop().dispose();
}
assert(ds.entries() == l);
}
template<class Tracer>
inline void
Path<Tracer>::reset(void) {
while (!ds.empty())
ds.pop().dispose();
}
template<class Tracer>
forceinline Space*
Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
Tracer& t) {
assert(!ds.empty());
// Recompute space according to path
// Also say distance to copy (d == 0) requires immediate copying
// Check for LAO
if ((ds.top().space() != NULL) && ds.top().rightmost()) {
Space* s = ds.top().space();
s->commit(*ds.top().choice(),ds.top().alt());
assert(ds.entries()-1 == lc());
ds.top().space(NULL);
// Mark as reusable
if (static_cast<unsigned int>(ds.entries()) > ngdl())
ds.top().next();
d = 0;
return s;
}
// General case for recomputation
int l = lc(); // Position of last clone
int n = ds.entries(); // Number of stack entries
// New distance, if no adaptive recomputation
d = static_cast<unsigned int>(n - l);
Space* s = ds[l].space()->clone(); // Last clone
if (d < a_d) {
// No adaptive recomputation
for (int i=l; i<n; i++)
commit(s,i);
} else {
int m = l + static_cast<int>(d >> 1); // Middle between copy and top
int i = l; // To iterate over all entries
// Recompute up to middle
for (; i<m; i++ )
commit(s,i);
// Skip over all rightmost branches
for (; (i<n) && ds[i].rightmost(); i++)
commit(s,i);
// Is there any point to make a copy?
if (i<n-1) {
// Propagate to fixpoint
SpaceStatus ss = s->status(stat);
/*
* Again, the space might already propagate to failure (due to
* weakly monotonic propagators).
*/
if (ss == SS_FAILED) {
// s must be deleted as it is not on the stack
delete s;
stat.fail++;
unwind(i,t);
return NULL;
}
ds[i].space(s->clone());
d = static_cast<unsigned int>(n-i);
}
// Finally do the remaining commits
for (; i<n; i++)
commit(s,i);
}
return s;
}
template<class Tracer>
forceinline Space*
Path<Tracer>::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
const Space& best, int& mark,
Tracer& t) {
assert(!ds.empty());
// Recompute space according to path
// Also say distance to copy (d == 0) requires immediate copying
// Check for LAO
if ((ds.top().space() != NULL) && ds.top().rightmost()) {
Space* s = ds.top().space();
s->commit(*ds.top().choice(),ds.top().alt());
assert(ds.entries()-1 == lc());
if (mark > ds.entries()-1) {
mark = ds.entries()-1;
s->constrain(best);
}
ds.top().space(NULL);
// Mark as reusable
if (static_cast<unsigned int>(ds.entries()) > ngdl())
ds.top().next();
d = 0;
return s;
}
// General case for recomputation
int l = lc(); // Position of last clone
int n = ds.entries(); // Number of stack entries
// New distance, if no adaptive recomputation
d = static_cast<unsigned int>(n - l);
Space* s = ds[l].space(); // Last clone
if (l < mark) {
mark = l;
s->constrain(best);
// The space on the stack could be failed now as an additional
// constraint might have been added.
if (s->status(stat) == SS_FAILED) {
// s does not need deletion as it is on the stack (unwind does this)
stat.fail++;
unwind(l,t);
return NULL;
}
// It is important to replace the space on the stack with the
// copy: a copy might be much smaller due to flushed caches
// of propagators
Space* c = s->clone();
ds[l].space(c);
} else {
s = s->clone();
}
if (d < a_d) {
// No adaptive recomputation
for (int i=l; i<n; i++)
commit(s,i);
} else {
int m = l + static_cast<int>(d >> 1); // Middle between copy and top
int i = l; // To iterate over all entries
// Recompute up to middle
for (; i<m; i++ )
commit(s,i);
// Skip over all rightmost branches
for (; (i<n) && ds[i].rightmost(); i++)
commit(s,i);
// Is there any point to make a copy?
if (i<n-1) {
// Propagate to fixpoint
SpaceStatus ss = s->status(stat);
/*
* Again, the space might already propagate to failure
*
* This can be for two reasons:
* - constrain is true, so we fail
* - the space has weakly monotonic propagators
*/
if (ss == SS_FAILED) {
// s must be deleted as it is not on the stack
delete s;
stat.fail++;
unwind(i,t);
return NULL;
}
ds[i].space(s->clone());
d = static_cast<unsigned int>(n-i);
}
// Finally do the remaining commits
for (; i<n; i++)
commit(s,i);
}
return s;
}
template<class Tracer>
void
Path<Tracer>::post(Space& home) const {
GECODE_ES_FAIL(NoGoodsProp::post(home,*this));
}
}}}
// STATISTICS: search-seq
Gecode::Choice
Choice for performing commit
Definition core.hpp:1412
Gecode::NoGoods::n
unsigned long int n
Number of no-goods.
Definition core.hpp:1591
Gecode::SearchTracer::EdgeInfo
Edge information.
Definition search.hh:242
Gecode::Search::NoGoodsProp::post
static ExecStatus post(Space &home, const Path &p)
Post propagator for path p.
Definition nogoods.hpp:90
Gecode::Search::Seq::Path::Edge
Search tree edge for recomputation
Definition path.hh:66
Gecode::Search::Seq::Path::Edge::space
Space * space(void) const
Return space for edge.
Definition path.hpp:51
Gecode::Search::Seq::Path::Edge::_space
Space * _space
Space corresponding to this edge (might be NULL).
Definition path.hh:69
Gecode::Search::Seq::Path::Edge::alt
unsigned int alt(void) const
Return number for alternatives.
Definition path.hpp:62
Gecode::Search::Seq::Path::Edge::Edge
Edge(void)
Default constructor.
Definition path.hpp:42
Gecode::Search::Seq::Path::Edge::rightmost
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition path.hpp:77
Gecode::Search::Seq::Path::Edge::next
void next(void)
Move to next alternative.
Definition path.hpp:87
Gecode::Search::Seq::Path::Edge::leftmost
bool leftmost(void) const
Test whether current alternative is leftmost.
Definition path.hpp:72
Gecode::Search::Seq::Path::Edge::lao
bool lao(void) const
Test whether current alternative was LAO.
Definition path.hpp:82
Gecode::Search::Seq::Path::Edge::dispose
void dispose(void)
Free memory for edge.
Definition path.hpp:105
Gecode::Search::Seq::Path::Edge::truealt
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization).
Definition path.hpp:67
Gecode::Search::Seq::Path::Edge::_nid
ID _nid
Node identifier.
Definition path.hh:75
Gecode::Search::Seq::Path::Edge::nid
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:99
Gecode::Search::Seq::Path::Edge::_choice
const Choice * _choice
Choice.
Definition path.hh:73
Gecode::Search::Seq::Path::Edge::choice
const Choice * choice(void) const
Return choice.
Definition path.hpp:93
Gecode::Search::Seq::Path::Edge::_alt
unsigned int _alt
Current alternative.
Definition path.hh:71
Gecode::Search::Seq::Path::_ngdl
unsigned int _ngdl
Depth limit for no-good generation.
Definition path.hh:113
Gecode::Search::Seq::Path::unwind
void unwind(int l, Tracer &t)
Unwind the stack up to position l (after failure).
Definition path.hpp:196
Gecode::Search::Seq::Path::empty
bool empty(void) const
Test whether path is empty.
Definition path.hpp:168
Gecode::Search::Seq::Path::entries
int entries(void) const
Return number of entries on stack.
Definition path.hpp:190
Gecode::Search::Seq::Path::lc
int lc(void) const
Return position on stack of last copy.
Definition path.hpp:181
Gecode::Search::Seq::Path::next
void next(void)
Generate path for next node.
Definition path.hpp:149
Gecode::Search::Seq::Path::post
virtual void post(Space &home) const
Post no-goods.
Definition path.hpp:385
Gecode::Search::Seq::Path::commit
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition path.hpp:174
Gecode::Search::Seq::Path::ngdl
unsigned int ngdl(void) const
Return no-good depth limit.
Definition path.hpp:124
Gecode::Search::Seq::Path::ds
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition path.hh:111
Gecode::Search::Seq::Path::Path
Path(unsigned int l)
Initialize with no-good depth limit l.
Definition path.hpp:119
Gecode::Search::Seq::Path::top
Edge & top(void) const
Provide access to topmost edge.
Definition path.hpp:161
Gecode::Search::Seq::Path::reset
void reset(void)
Reset stack.
Definition path.hpp:218
Gecode::Search::Seq::Path::push
const Choice * push(Worker &stat, Space *s, Space *c, unsigned int nid)
Push space c (a clone of s or NULL).
Definition path.hpp:136
Gecode::Search::Seq::Path::recompute
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s, Tracer &t)
Recompute space according to path.
Definition path.hpp:225
Gecode::Search::Statistics::fail
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
Gecode::Search::Worker
Search worker statistics
Definition worker.hh:44
Gecode::Search::Worker::stack_depth
void stack_depth(unsigned long int d)
Record stack depth d.
Definition worker.hh:100
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Tracer
Tracer.
Definition tracer.hpp:149
Gecode::heap
Heap heap
The single global heap.
Definition heap.cpp:44
GECODE_ES_FAIL
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition macros.hpp:103
Gecode::Space::constrain
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:841
Gecode::Space::commit
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition core.hpp:3232
Gecode::Space::status
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Gecode::Space::clone
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
Gecode::SpaceStatus
SpaceStatus
Space status
Definition core.hpp:1681
Gecode::SS_FAILED
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode::Search::Seq
Definition pbs.cpp:36
Gecode::Search
Search engines
Gecode
Gecode toplevel namespace
forceinline
#define forceinline
Definition config.hpp:187