On Thu, Oct 9, 2008 at 12:19 AM, Denys Duchier <[EMAIL PROTECTED]> wrote: > Ah! that would be great... but, I am afraid that I am a little too > stupid (and short on time) to figure it out on my own. Is there an > example I can look at, that would help me understand how to do this?
Hi, First of all, there are two examples in Gecode that come with custom branchings, Black hole patience and Peaceable Coexisting Armies of Queens. However, I got interested in your discussion, and started thinking about how it could be done in a nice way. By constructing a unary branching that stores a member function pointer to a function in the space, you can get you desired functionality. I tried it (code below), and it works just as you wanted. The code solves the Queens-problem, but you could modify it for any other problem, member-functions that take parameters, and so on. Searching for the first solution for Queens-6 using generate-and-test takes about 12 thousand failures. A pdf from Gist of the search-tree is at http://www.ict.kth.se/~zayenz/gentest.pdf. You can see where the two MemberFunctionBranchings kick in since they are unary (the first adds the real branching and the propagator-adding branching, the second adds the propagators). Cheers, Mikael <code> /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ /* * Main authors: * Mikael Lagerkvist <[EMAIL PROTECTED]> * * 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 void (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); (void) (model->*mf)(); return ES_OK; } /// 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: void addbranch(void) { branch(this, q, INT_VAR_SIZE_MIN, INT_VAL_MIN); MemberFunctionBranch<QueensMF>::post(this, &QueensMF::addprop); } void 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); } } /// 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/ _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
