nogoods.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, 2013
*
* 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 {
forceinline
NoNGL::NoNGL(void) {}
forceinline
NoNGL::NoNGL(Space& home)
: NGL(home) {}
forceinline
NoNGL::NoNGL(Space& home, NoNGL& ngl)
: NGL(home,ngl) {}
forceinline
NoGoodsProp::NoGoodsProp(Space& home, NGL* root0)
: Propagator(Home(home)), root(root0), n(0U) {
// Create subscriptions
root->subscribe(home,*this); n++;
bool notice = root->notice();
NGL* l = root->next();
while ((l != NULL) && l->leaf()) {
l->subscribe(home,*this); n++;
notice = notice || l->notice();
l = l->next();
}
if (l != NULL) {
l->subscribe(home,*this); n++;
}
while (!notice && (l != NULL)) {
notice = notice || l->notice();
l = l->next();
}
if (notice)
home.notice(*this,AP_DISPOSE);
}
forceinline
NoGoodsProp::NoGoodsProp(Space& home, NoGoodsProp& p)
: Propagator(home,p), n(p.n) {
assert(p.root != NULL);
NoNGL s;
NGL* c = &s;
for (NGL* pc = p.root; pc != NULL; pc = pc->next()) {
NGL* n = pc->copy(home);
n->leaf(pc->leaf());
c->next(n); c=n;
}
root = s.next();
}
template<class Path>
forceinline ExecStatus
NoGoodsProp::post(Space& home, const Path& p) {
int s = 0;
int n = std::min(p.ds.entries(),static_cast<int>(p.ngdl()));
unsigned long int n_nogood = 0;
// Eliminate the alternatives which are not no-goods at the end
while ((n > s) && (p.ds[n-1].truealt() == 0U))
n--;
// A sentinel element
NoNGL nn;
// Current no-good literal
NGL* c = &nn;
// Commit no-goods at the beginning
while ((s < n) && (p.ds[s].truealt() > 0U))
// Try whether this is a rightmost alternative
if (p.ds[s].rightmost()) {
// No literal needed, directly try to commit
home.trycommit(*p.ds[s].choice(),p.ds[s].truealt());
s++;
} else {
// Prune using no-good literals
for (unsigned int a=0U; a<p.ds[s].truealt(); a++) {
NGL* l = home.ngl(*p.ds[s].choice(),a);
// Does the brancher support no-good literals?
if (l == NULL)
return ES_OK;
GECODE_ES_CHECK(l->prune(home));
}
// Add literal as root if needed and stop
if (NGL* l = home.ngl(*p.ds[s].choice(),p.ds[s].truealt())) {
c = c->add(l,false);
s++; break;
}
}
// There are no literals
if (home.failed())
return ES_FAILED;
if (s >= n)
return ES_OK;
// There must be at least two literals
assert((n-s > 1) ||
((n-s == 1) && (c != &nn)));
// Remember the last leaf
NGL* ll = NULL;
// Create literals
for (int i=s; i<n; i++) {
// Add leaves
for (unsigned int a=0U; a<p.ds[i].truealt(); a++) {
NGL* l = home.ngl(*p.ds[i].choice(),a);
if (l == NULL) {
// The brancher does not support no-goods
if (ll == NULL)
return ES_OK;
ll->next(NULL);
break;
}
c = c->add(l,true); ll = c;
n_nogood++;
}
// Check whether to add an additional subtree
if (NGL* l = home.ngl(*p.ds[i].choice(),p.ds[i].truealt())) {
c = c->add(l,false);
} else if (!p.ds[i].rightmost()) {
// The brancher does not support no-goods
if (ll == NULL)
return ES_OK;
ll->next(NULL);
break;
}
}
const_cast<Path&>(p).ng(n_nogood);
(void) new (home) NoGoodsProp(home,nn.next());
return ES_OK;
}
}}
// STATISTICS: search-other
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::NGL
No-good literal recorded during search.
Definition core.hpp:1340
Gecode::NGL::leaf
bool leaf(void) const
Test whether literal is a leaf.
Definition core.hpp:3789
Gecode::NGL::prune
virtual ExecStatus prune(Space &home)=0
Propagate the negation of the no-good literal.
Gecode::NGL::subscribe
virtual void subscribe(Space &home, Propagator &p)=0
Subscribe propagator p to all views of the no-good literal.
Gecode::NGL::NGL
NGL(void)
Constructor for creation.
Definition core.hpp:3812
Gecode::NGL::next
NGL * next(void) const
Return pointer to next literal.
Definition core.hpp:3793
Gecode::NGL::notice
virtual bool notice(void) const
Whether dispose must always be called (returns false).
Definition core.cpp:896
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Search::NoGoodsProp::post
static ExecStatus post(Space &home, const Path &p)
Post propagator for path p.
Definition nogoods.hpp:90
Gecode::Search::NoGoodsProp::n
unsigned int n
Number of no-good literals with subscriptions.
Definition nogoods.hh:70
Gecode::Search::NoGoodsProp::NoGoodsProp
NoGoodsProp(Space &home, NGL *root)
Constructor for creation.
Definition nogoods.hpp:50
Gecode::Search::NoGoodsProp::root
NGL * root
Root of no-good literal tree.
Definition nogoods.hh:68
Gecode::Search::NoNGL
Class for a sentinel no-good literal.
Definition nogoods.hh:42
Gecode::Search::NoNGL::NoNGL
NoNGL(void)
Constructor for creation.
Definition nogoods.hpp:37
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Space::failed
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4044
GECODE_ES_CHECK
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
Gecode::Space::notice
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:4059
Gecode::AP_DISPOSE
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:562
Gecode::Space::trycommit
void trycommit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
If possible, commit choice c for alternative a.
Definition core.hpp:3237
Gecode::Space::ngl
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition core.cpp:641
Gecode::Search
Search engines
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
forceinline
#define forceinline
Definition config.hpp:187