[gecode-users] staged search
Mikael Zayenz Lagerkvist
zayenz at gmail.com
Thu Oct 9 11:11:32 CEST 2008
On Thu, Oct 9, 2008 at 8:05 AM, Mikael Zayenz Lagerkvist
<zayenz at gmail.com> wrote:
> I tried it (code below), and it works just as you wanted.
Hi again,
Christian pointed out to me that I had a small problem in my posted
code - if the member-function called gave a failure, then things could
go bad. Thus I've modified the code (see below) so that the
member-function returns an ExecStatus that the MemberFunctionBranching
can return.
Cheers,
Mikael
<code>
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Mikael Lagerkvist <lagerkvist at gecode.org>
*
* Copyright:
* Mikael Lagerkvist, 2008
*
* Last modified:
* $Date: 2008-10-09 07:48:15 +0200 (Wed, 09 Oct 2008) $ by
$Author: zayenz $
* $Revision: 7912 $
*
* 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.
*
*/
#include "examples/support.hh"
#include <gecode/minimodel.hh>
/** \brief Branching for calling a space member function.
*/
template <class Model>
class MemberFunctionBranch : Branching {
public:
/// Type of the member-function to call
typedef ExecStatus (Model::*MemberFunction)();
private:
/// Member function to call
MemberFunction mf;
/// Call member function just once
bool done;
/// Minimal branching description storing no information
struct Description : public BranchingDesc {
/// Initialize description for branching \a b, number of alternatives \a a.
Description(const Branching* b, unsigned int a) : BranchingDesc(b,a) {}
/// Report size occupied
virtual size_t size(void) const { return sizeof(Description); }
};
/// Construct branching
MemberFunctionBranch(Space* home, MemberFunction mf0)
: Branching(home), mf(mf0), done(false) {}
/// Copy constructor
MemberFunctionBranch(Space* home, bool share,
MemberFunctionBranch<Model>& b)
: Branching(home, share, b), mf(b.mf), done(b.done) {}
public:
/// Check status of branching, return true if alternatives left.
virtual bool status(const Space*) const {
return !done;
}
/// Return branching description
virtual BranchingDesc* description(const Space*) const {
assert(!done);
return new Description(this, 1);
}
/// Perform commit
virtual ExecStatus commit(Space* home, const BranchingDesc*, unsigned int) {
done = true;
Model* model = static_cast<Model*>(home);
return (model->*mf)();
}
/// Copy branching
virtual Actor* copy(Space* home, bool share) {
return new (home) MemberFunctionBranch(home, share, *this);
}
/// Reflection name
virtual const char* name(void) const {
return "MemberFunctionBranch";
}
/// Post branching
static void post(Space* home, MemberFunction mf) {
(void) new (home) MemberFunctionBranch<Model>(home,mf);
}
};
/**
* \brief %Example: n-%Queens puzzle with member function branchings
*
* \ingroup ExProblem
*/
class QueensMF : public Example {
protected:
/// Position of queens on boards
IntVarArray q;
public:
ExecStatus addbranch(void) {
branch(this, q, INT_VAR_SIZE_MIN, INT_VAL_MIN);
MemberFunctionBranch<QueensMF>::post(this, &QueensMF::addprop);
return failed() ? ES_FAILED : ES_OK;
}
ExecStatus addprop(void) {
const int n = q.size();
for (int i = 0; i<n; i++)
for (int j = i+1; j<n; j++) {
post(this, q[i] != q[j]);
post(this, q[i]+i != q[j]+j);
post(this, q[i]-i != q[j]-j);
}
return failed() ? ES_FAILED : ES_OK;
}
/// The actual problem
QueensMF(const SizeOptions& opt)
: q(this,opt.size(),0,opt.size()-1) {
MemberFunctionBranch<QueensMF>::post(this, &QueensMF::addbranch);
}
/// Constructor for cloning \a s
QueensMF(bool share, QueensMF& s) : Example(share,s) {
q.update(this, share, s.q);
}
/// Perform copying during cloning
virtual Space*
copy(bool share) {
return new QueensMF(share,*this);
}
/// Print solution
virtual void
print(std::ostream& os) {
os << "\t";
for (int i = 0; i < q.size(); i++) {
os << q[i] << ", ";
if ((i+1) % 10 == 0)
os << std::endl << "\t";
}
os << std::endl;
}
/// Make variables available for visualisation
virtual void
getVars(Gecode::Reflection::VarMap& vm, bool registerOnly) {
vm.putArray(this,q,"q", registerOnly);
}
};
/** \brief Main-function
* \relates QueensMF
*/
int
main(int argc, char* argv[]) {
SizeOptions opt("QueensMF");
opt.iterations(500);
opt.size(6);
opt.parse(argc,argv);
Example::run<QueensMF,DFS,SizeOptions>(opt);
return 0;
}
// STATISTICS: example-any
</code>
--
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
More information about the gecode-users
mailing list