Generated on Wed Jul 27 2011 15:08:48 for Gecode by doxygen 1.7.4
brancher-view.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main author:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2008
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-10-13 21:12:58 +0200 (Tue, 13 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9897 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode {
00039 
00046 
00047   class EmptyViewSelChoice {
00048   public:
00050     size_t size(void) const;
00051   };
00052 
00056   template<class _View>
00057   class ViewSelBase {
00058   public:
00060     typedef _View View;
00062     typedef EmptyViewSelChoice Choice;
00064     ViewSelBase(void);
00066     ViewSelBase(Space& home, const VarBranchOptions& vbo);
00068     EmptyViewSelChoice choice(Space& home);
00070     void commit(Space& home, const EmptyViewSelChoice& c, unsigned a);
00072     void update(Space& home, bool share, ViewSelBase& vs);
00074     void dispose(Space& home);
00075   };
00076 
00080   template<class View>
00081   class ViewSelNone : public ViewSelBase<View> {
00082   public:
00084     ViewSelNone(void);
00086     ViewSelNone(Space& home, const VarBranchOptions& vbo);
00088     ViewSelStatus init(Space& home, View x);
00090     ViewSelStatus select(Space& home, View x);
00091   };
00092 
00096   template<class View>
00097   class ViewSelDegreeMin : public ViewSelBase<View> {
00098   protected:
00100     unsigned int degree;
00101   public:
00103     ViewSelDegreeMin(void);
00105     ViewSelDegreeMin(Space& home, const VarBranchOptions& vbo);
00107     ViewSelStatus init(Space& home, View x);
00109     ViewSelStatus select(Space& home, View x);
00110   };
00111 
00115   template<class View>
00116   class ViewSelDegreeMax : public ViewSelBase<View> {
00117   protected:
00119     unsigned int degree;
00120   public:
00122     ViewSelDegreeMax(void);
00124     ViewSelDegreeMax(Space& home, const VarBranchOptions& vbo);
00126     ViewSelStatus init(Space& home, View x);
00128     ViewSelStatus select(Space& home, View x);
00129   };
00130 
00134   template<class View>
00135   class ViewSelAfcMin : public ViewSelBase<View> {
00136   protected:
00138     double afc;
00139   public:
00141     ViewSelAfcMin(void);
00143     ViewSelAfcMin(Space& home, const VarBranchOptions& vbo);
00145     ViewSelStatus init(Space& home, View x);
00147     ViewSelStatus select(Space& home, View x);
00148   };
00149 
00153   template<class View>
00154   class ViewSelAfcMax : public ViewSelBase<View> {
00155   protected:
00157     double afc;
00158   public:
00160     ViewSelAfcMax(void);
00162     ViewSelAfcMax(Space& home, const VarBranchOptions& vbo);
00164     ViewSelStatus init(Space& home, View x);
00166     ViewSelStatus select(Space& home, View x);
00167   };
00168 
00172   template<class _View>
00173   class ViewSelRnd {
00174   protected:
00176     Support::RandomGenerator r;
00178     unsigned int n;
00179   public:
00181     typedef _View View;
00183     typedef Support::RandomGenerator Choice;
00185     ViewSelRnd(void);
00187     ViewSelRnd(Space& home, const VarBranchOptions& vbo);
00189     ViewSelStatus init(Space& home, _View x);
00191     ViewSelStatus select(Space& home, _View x);
00193     Support::RandomGenerator choice(Space& home);
00195     void commit(Space& home, const Support::RandomGenerator& c, unsigned a);
00197     void update(Space& home, bool share, ViewSelRnd& vs);
00199     void dispose(Space& home);
00200   };
00202 
00203   // Empty view selection choice
00204   forceinline size_t
00205   EmptyViewSelChoice::size(void) const {
00206     return sizeof(EmptyViewSelChoice);
00207   }
00208 
00209   // Selection base class
00210   template<class View>
00211   forceinline
00212   ViewSelBase<View>::ViewSelBase(void) {}
00213   template<class View>
00214   forceinline
00215   ViewSelBase<View>::ViewSelBase(Space&, const VarBranchOptions&) {}
00216   template<class View>
00217   forceinline EmptyViewSelChoice
00218   ViewSelBase<View>::choice(Space&) {
00219     EmptyViewSelChoice c; return c;
00220   }
00221   template<class View>
00222   forceinline void
00223   ViewSelBase<View>::commit(Space&, const EmptyViewSelChoice&, unsigned int) {}
00224   template<class View>
00225   forceinline void
00226   ViewSelBase<View>::update(Space&, bool, ViewSelBase<View>&) {}
00227   template<class View>
00228   forceinline void
00229   ViewSelBase<View>::dispose(Space&) {}
00230 
00231 
00232   // Select first view
00233   template<class View>
00234   forceinline
00235   ViewSelNone<View>::ViewSelNone(void) {}
00236   template<class View>
00237   forceinline
00238   ViewSelNone<View>::ViewSelNone(Space& home, const VarBranchOptions& vbo)
00239     : ViewSelBase<View>(home,vbo) {}
00240   template<class View>
00241   forceinline ViewSelStatus
00242   ViewSelNone<View>::init(Space&, View) {
00243     return VSS_BEST;
00244   }
00245   template<class View>
00246   forceinline ViewSelStatus
00247   ViewSelNone<View>::select(Space&, View) {
00248     return VSS_BEST;
00249   }
00250 
00251 
00252   // Select variable with smallest degree
00253   template<class View>
00254   forceinline
00255   ViewSelDegreeMin<View>::ViewSelDegreeMin(void) : degree(0U) {}
00256   template<class View>
00257   forceinline
00258   ViewSelDegreeMin<View>::ViewSelDegreeMin(Space& home,
00259                                            const VarBranchOptions& vbo)
00260     : ViewSelBase<View>(home,vbo), degree(0U) {}
00261   template<class View>
00262   forceinline ViewSelStatus
00263   ViewSelDegreeMin<View>::init(Space&, View x) {
00264     degree = x.degree();
00265     return (degree == 0) ? VSS_BEST : VSS_BETTER;
00266   }
00267   template<class View>
00268   forceinline ViewSelStatus
00269   ViewSelDegreeMin<View>::select(Space&, View x) {
00270     if (x.degree() < degree) {
00271       degree = x.degree();
00272       return (degree == 0) ? VSS_BEST : VSS_BETTER;
00273     } else if (x.degree() > degree) {
00274       return VSS_WORSE;
00275     } else {
00276       return VSS_TIE;
00277     }
00278   }
00279 
00280 
00281   // Select variable with largest degree
00282   template<class View>
00283   forceinline
00284   ViewSelDegreeMax<View>::ViewSelDegreeMax(void) : degree(0) {}
00285   template<class View>
00286   forceinline
00287   ViewSelDegreeMax<View>::ViewSelDegreeMax(Space& home,
00288                                            const VarBranchOptions& vbo)
00289     : ViewSelBase<View>(home,vbo), degree(0U) {}
00290   template<class View>
00291   forceinline ViewSelStatus
00292   ViewSelDegreeMax<View>::init(Space&, View x) {
00293     degree = x.degree();
00294     return VSS_BETTER;
00295   }
00296   template<class View>
00297   forceinline ViewSelStatus
00298   ViewSelDegreeMax<View>::select(Space&, View x) {
00299     if (x.degree() > degree) {
00300       degree = x.degree();
00301       return VSS_BETTER;
00302     } else if (x.degree() < degree) {
00303       return VSS_WORSE;
00304     } else {
00305       return VSS_TIE;
00306     }
00307   }
00308 
00309 
00310   // Select variable with smallest afc
00311   template<class View>
00312   forceinline
00313   ViewSelAfcMin<View>::ViewSelAfcMin(void) : afc(0.0) {}
00314   template<class View>
00315   forceinline
00316   ViewSelAfcMin<View>::ViewSelAfcMin(Space& home,
00317                                      const VarBranchOptions& vbo)
00318     : ViewSelBase<View>(home,vbo), afc(0.0) {}
00319   template<class View>
00320   forceinline ViewSelStatus
00321   ViewSelAfcMin<View>::init(Space&, View x) {
00322     afc = x.afc();
00323     return (afc == 0.0) ? VSS_BEST : VSS_BETTER;
00324   }
00325   template<class View>
00326   forceinline ViewSelStatus
00327   ViewSelAfcMin<View>::select(Space&, View x) {
00328     if (x.afc() < afc) {
00329       afc = x.afc();
00330       return (afc == 0.0) ? VSS_BEST : VSS_BETTER;
00331     } else if (x.afc() > afc) {
00332       return VSS_WORSE;
00333     } else {
00334       return VSS_TIE;
00335     }
00336   }
00337 
00338 
00339   // Select variable with largest afc
00340   template<class View>
00341   forceinline
00342   ViewSelAfcMax<View>::ViewSelAfcMax(void) : afc(0.0) {}
00343   template<class View>
00344   forceinline
00345   ViewSelAfcMax<View>::ViewSelAfcMax(Space& home,
00346                                      const VarBranchOptions& vbo)
00347     : ViewSelBase<View>(home,vbo), afc(0.0) {}
00348   template<class View>
00349   forceinline ViewSelStatus
00350   ViewSelAfcMax<View>::init(Space&, View x) {
00351     afc = x.afc();
00352     return VSS_BETTER;
00353   }
00354   template<class View>
00355   forceinline ViewSelStatus
00356   ViewSelAfcMax<View>::select(Space&, View x) {
00357     double xafc = x.afc();
00358     if (xafc > afc) {
00359       afc = xafc;
00360       return VSS_BETTER;
00361     } else if (xafc < afc) {
00362       return VSS_WORSE;
00363     } else {
00364       return VSS_TIE;
00365     }
00366   }
00367 
00368 
00369   // Select variable by random
00370   template<class View>
00371   forceinline
00372   ViewSelRnd<View>::ViewSelRnd(void) : n(0) {}
00373   template<class View>
00374   forceinline
00375   ViewSelRnd<View>::ViewSelRnd(Space&, const VarBranchOptions& vbo)
00376     : r(vbo.seed), n(0) {}
00377   template<class View>
00378   forceinline ViewSelStatus
00379   ViewSelRnd<View>::init(Space&, View) {
00380     n=1;
00381     return VSS_BETTER;
00382   }
00383   template<class View>
00384   forceinline ViewSelStatus
00385   ViewSelRnd<View>::select(Space&, View) {
00386     n++;
00387     return (r(n) == (n-1)) ? VSS_BETTER : VSS_WORSE;
00388   }
00389   template<class View>
00390   forceinline Support::RandomGenerator
00391   ViewSelRnd<View>::choice(Space&) {
00392     return r;
00393   }
00394   template<class View>
00395   forceinline void
00396   ViewSelRnd<View>::commit(Space&, const Support::RandomGenerator& c,
00397                            unsigned int) {
00398     r = c;
00399   }
00400   template<class View>
00401   forceinline void
00402   ViewSelRnd<View>::update(Space&, bool, ViewSelRnd<View>& vs) {
00403     r = vs.r;
00404   }
00405   template<class View>
00406   forceinline void
00407   ViewSelRnd<View>::dispose(Space&) {
00408   }
00409 
00410 }
00411 
00412 // STATISTICS: kernel-branch