Generated on Fri Oct 19 11:24:50 2018 for Gecode by doxygen 1.6.3

branch.hh

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Samuel Gagnon <samuel.gagnon92@gmail.com>
00008 
00009  *  Copyright:
00010  *     Christian Schulte, 2012
00011  *     Samuel Gagnon, 2018
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 #ifndef __GECODE_INT_BRANCH_HH__
00039 #define __GECODE_INT_BRANCH_HH__
00040 
00041 #include <gecode/int.hh>
00042 
00048 namespace Gecode { namespace Int { namespace Branch {
00049 
00068   template<class View>
00069   class MeritMin : public MeritBase<View,int> {
00070   public:
00071     using typename MeritBase<View,int>::Var;
00073     MeritMin(Space& home, const VarBranch<Var>& vb);
00075     MeritMin(Space& home, MeritMin& m);
00077     int operator ()(const Space& home, View x, int i);
00078   };
00079 
00086   template<class View>
00087   class MeritMax : public MeritBase<View,int> {
00088   public:
00089     using typename MeritBase<View,int>::Var;
00091     MeritMax(Space& home, const VarBranch<Var>& vb);
00093     MeritMax(Space& home, MeritMax& m);
00095     int operator ()(const Space& home, View x, int i);
00096   };
00097 
00104   template<class View>
00105   class MeritSize : public MeritBase<View,unsigned int> {
00106   public:
00107     using typename MeritBase<View,unsigned int>::Var;
00109     MeritSize(Space& home, const VarBranch<Var>& vb);
00111     MeritSize(Space& home, MeritSize& m);
00113     unsigned int operator ()(const Space& home, View x, int i);
00114   };
00115 
00122   template<class View>
00123   class MeritDegreeSize : public MeritBase<View,double> {
00124   public:
00125     using typename MeritBase<View,double>::Var;
00127     MeritDegreeSize(Space& home, const VarBranch<Var>& vb);
00129     MeritDegreeSize(Space& home, MeritDegreeSize& m);
00131     double operator ()(const Space& home, View x, int i);
00132   };
00133 
00140   template<class View>
00141   class MeritAFCSize : public MeritBase<View,double> {
00142     using typename MeritBase<View,double>::Var;
00143   protected:
00145     AFC afc;
00146   public:
00148     MeritAFCSize(Space& home, const VarBranch<Var>& vb);
00150     MeritAFCSize(Space& home, MeritAFCSize& m);
00152     double operator ()(const Space& home, View x, int i);
00154     bool notice(void) const;
00156     void dispose(Space& home);
00157   };
00158 
00165   template<class View>
00166   class MeritActionSize : public MeritBase<View,double> {
00167     using typename MeritBase<View,double>::Var;
00168   protected:
00170     Action action;
00171   public:
00173     MeritActionSize(Space& home, const VarBranch<Var>& vb);
00175     MeritActionSize(Space& home, MeritActionSize& m);
00177     double operator ()(const Space& home, View x, int i);
00179     bool notice(void) const;
00181     void dispose(Space& home);
00182   };
00183 
00190   template<class View>
00191   class MeritCHBSize : public MeritBase<View,double> {
00192     using typename MeritBase<View,double>::Var;
00193   protected:
00195     CHB chb;
00196   public:
00198     MeritCHBSize(Space& home, const VarBranch<Var>& vb);
00200     MeritCHBSize(Space& home, MeritCHBSize& m);
00202     double operator ()(const Space& home, View x, int i);
00204     bool notice(void) const;
00206     void dispose(Space& home);
00207   };
00208 
00215   template<class View>
00216   class MeritRegretMin : public MeritBase<View,unsigned int> {
00217   public:
00218     using typename MeritBase<View,unsigned int>::Var;
00220     MeritRegretMin(Space& home, const VarBranch<Var>& vb);
00222     MeritRegretMin(Space& home, MeritRegretMin& m);
00224     unsigned int operator ()(const Space& home, View x, int i);
00225   };
00226 
00233   template<class View>
00234   class MeritRegretMax : public MeritBase<View,unsigned int> {
00235   public:
00236     using typename MeritBase<View,unsigned int>::Var;
00238     MeritRegretMax(Space& home, const VarBranch<Var>& vb);
00240     MeritRegretMax(Space& home, MeritRegretMax& m);
00242     unsigned int operator ()(const Space& home, View x, int i);
00243   };
00244 
00245 }}}
00246 
00247 #include <gecode/int/branch/merit.hpp>
00248 
00249 namespace Gecode { namespace Int { namespace Branch {
00250 
00252   GECODE_INT_EXPORT
00253   ViewSel<IntView>* viewsel(Space& home, const IntVarBranch& ivb);
00255   GECODE_INT_EXPORT
00256   ViewSel<BoolView>* viewsel(Space& home, const BoolVarBranch& bvb);
00257 
00258 }}}
00259 
00260 namespace Gecode { namespace Int { namespace Branch {
00261 
00280   template<class View>
00281   class ValSelMin : public ValSel<View,int> {
00282   public:
00283     using typename ValSel<View,int>::Var;
00285     ValSelMin(Space& home, const ValBranch<Var>& vb);
00287     ValSelMin(Space& home, ValSelMin& vs);
00289     int val(const Space& home, View x, int i);
00290   };
00291 
00298   template<class View>
00299   class ValSelMax : public ValSel<View,int> {
00300   public:
00301     using typename ValSel<View,int>::Var;
00303     ValSelMax(Space& home, const ValBranch<Var>& vb);
00305     ValSelMax(Space& home, ValSelMax& vs);
00307     int val(const Space& home, View x, int i);
00308   };
00309 
00316   template<class View>
00317   class ValSelMed : public ValSel<View,int> {
00318   public:
00319     using typename ValSel<View,int>::Var;
00321     ValSelMed(Space& home, const ValBranch<Var>& vb);
00323     ValSelMed(Space& home, ValSelMed& vs);
00325     int val(const Space& home, View x, int i);
00326   };
00327 
00334   template<class View>
00335   class ValSelAvg : public ValSel<View,int> {
00336   public:
00337     using typename ValSel<View,int>::Var;
00339     ValSelAvg(Space& home, const ValBranch<Var>& vb);
00341     ValSelAvg(Space& home, ValSelAvg& vs);
00343     int val(const Space& home, View x, int i);
00344   };
00345 
00352   template<class View>
00353   class ValSelRnd : public ValSel<View,int> {
00354     using typename ValSel<View,int>::Var;
00355   protected:
00357     Rnd r;
00358   public:
00360     ValSelRnd(Space& home, const ValBranch<Var>& vb);
00362     ValSelRnd(Space& home, ValSelRnd& vs);
00364     int val(const Space& home, View x, int i);
00366     bool notice(void) const;
00368     void dispose(Space& home);
00369   };
00370 
00377   class ValSelRangeMin : public ValSel<IntView,int> {
00378   public:
00380     ValSelRangeMin(Space& home, const ValBranch<IntVar>& vb);
00382     ValSelRangeMin(Space& home, ValSelRangeMin& vs);
00384     int val(const Space& home, IntView x, int i);
00385   };
00386 
00393   class ValSelRangeMax : public ValSel<IntView,int> {
00394   public:
00396     ValSelRangeMax(Space& home, const ValBranch<IntVar>& vb);
00398     ValSelRangeMax(Space& home, ValSelRangeMax& vs);
00400     int val(const Space& home, IntView x, int i);
00401   };
00402 
00403 }}}
00404 
00405 #include <gecode/int/branch/val-sel.hpp>
00406 
00407 namespace Gecode { namespace Int { namespace Branch {
00408 
00410   template<class View>
00411   class EqNGL : public ViewValNGL<View,int,PC_INT_VAL> {
00412     using ViewValNGL<View,int,PC_INT_VAL>::x;
00413     using ViewValNGL<View,int,PC_INT_VAL>::n;
00414   public:
00416     EqNGL(Space& home, View x, int n);
00418     EqNGL(Space& home, EqNGL& ngl);
00420     virtual NGL::Status status(const Space& home) const;
00422     virtual ExecStatus prune(Space& home);
00424     virtual NGL* copy(Space& home);
00425   };
00426 
00428   template<class View>
00429   class NqNGL : public ViewValNGL<View,int,PC_INT_DOM> {
00430     using ViewValNGL<View,int,PC_INT_DOM>::x;
00431     using ViewValNGL<View,int,PC_INT_DOM>::n;
00432   public:
00434     NqNGL(Space& home, View x, int n);
00436     NqNGL(Space& home, NqNGL& ngl);
00438     virtual NGL::Status status(const Space& home) const;
00440     virtual ExecStatus prune(Space& home);
00442     virtual NGL* copy(Space& home);
00443   };
00444 
00446   template<class View>
00447   class LqNGL : public ViewValNGL<View,int,PC_INT_BND> {
00448     using ViewValNGL<View,int,PC_INT_BND>::x;
00449     using ViewValNGL<View,int,PC_INT_BND>::n;
00450   public:
00452     LqNGL(Space& home, View x, int n);
00454     LqNGL(Space& home, LqNGL& ngl);
00456     virtual NGL::Status status(const Space& home) const;
00458     virtual ExecStatus prune(Space& home);
00460     virtual NGL* copy(Space& home);
00461   };
00462 
00464   template<class View>
00465   class GqNGL : public ViewValNGL<View,int,PC_INT_BND> {
00466     using ViewValNGL<View,int,PC_INT_BND>::x;
00467     using ViewValNGL<View,int,PC_INT_BND>::n;
00468   public:
00470     GqNGL(Space& home, View x, int n);
00472     GqNGL(Space& home, GqNGL& ngl);
00474     virtual NGL::Status status(const Space& home) const;
00476     virtual ExecStatus prune(Space& home);
00478     virtual NGL* copy(Space& home);
00479   };
00480 
00481 }}}
00482 
00483 #include <gecode/int/branch/ngl.hpp>
00484 
00485 namespace Gecode { namespace Int { namespace Branch {
00486 
00505   template<class View>
00506   class ValCommitEq : public ValCommit<View,int> {
00507   public:
00508     using typename ValCommit<View,int>::Var;
00510     ValCommitEq(Space& home, const ValBranch<Var>& vb);
00512     ValCommitEq(Space& home, ValCommitEq& vc);
00514     ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
00516     NGL* ngl(Space& home, unsigned int a, View x, int n) const;
00518     void print(const Space& home, unsigned int a, View x, int i, int n,
00519                std::ostream& o) const;
00520   };
00521 
00528   template<class View>
00529   class ValCommitLq : public ValCommit<View,int> {
00530   public:
00531     using typename ValCommit<View,int>::Var;
00533     ValCommitLq(Space& home, const ValBranch<Var>& vb);
00535     ValCommitLq(Space& home, ValCommitLq& vc);
00537     ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
00539     NGL* ngl(Space& home, unsigned int a, View x, int n) const;
00541     void print(const Space& home, unsigned int a, View x, int i, int n,
00542                std::ostream& o) const;
00543   };
00544 
00551   template<class View>
00552   class ValCommitGq : public ValCommit<View,int> {
00553   public:
00554     using typename ValCommit<View,int>::Var;
00556     ValCommitGq(Space& home, const ValBranch<Var>& vb);
00558     ValCommitGq(Space& home, ValCommitGq& vc);
00560     ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
00562     NGL* ngl(Space& home, unsigned int a, View x, int n) const;
00564     void print(const Space& home, unsigned int a, View x, int i, int n,
00565                std::ostream& o) const;
00566   };
00567 
00574   template<class View>
00575   class ValCommitGr : public ValCommit<View,int> {
00576   public:
00577     using typename ValCommit<View,int>::Var;
00579     ValCommitGr(Space& home, const ValBranch<Var>& vb);
00581     ValCommitGr(Space& home, ValCommitGr& vc);
00583     ModEvent commit(Space& home, unsigned int a, View x, int i, int n);
00585     NGL* ngl(Space& home, unsigned int a, View x, int n) const;
00587     void print(const Space& home, unsigned int a, View x, int i, int n,
00588                std::ostream& o) const;
00589   };
00590 
00591 }}}
00592 
00593 #include <gecode/int/branch/val-commit.hpp>
00594 
00595 namespace Gecode { namespace Int { namespace Branch {
00596 
00598   GECODE_INT_EXPORT
00599   ValSelCommitBase<IntView,int>*
00600   valselcommit(Space& home, const IntValBranch& ivb);
00601 
00603   GECODE_INT_EXPORT
00604   ValSelCommitBase<BoolView,int>*
00605   valselcommit(Space& home, const BoolValBranch& bvb);
00606 
00608   GECODE_INT_EXPORT
00609   ValSelCommitBase<IntView,int>*
00610   valselcommit(Space& home, const IntAssign& ia);
00611 
00613   GECODE_INT_EXPORT
00614   ValSelCommitBase<BoolView,int>*
00615   valselcommit(Space& home, const BoolAssign& ba);
00616 
00617 }}}
00618 
00619 namespace Gecode { namespace Int { namespace Branch {
00620 
00625   template<int n, bool min, class Filter, class Print>
00626   class ViewValuesBrancher : public ViewBrancher<IntView,Filter,n> {
00627   protected:
00628     using ViewBrancher<IntView,Filter,n>::x;
00629     using ViewBrancher<IntView,Filter,n>::f;
00631     Print p;
00633     ViewValuesBrancher(Space& home, ViewValuesBrancher& b);
00635     ViewValuesBrancher(Home home, ViewArray<IntView>& x,
00636                        ViewSel<IntView>* vs[n],
00637                        IntBranchFilter bf,
00638                        IntVarValPrint vvp);
00639   public:
00641     virtual const Choice* choice(Space& home);
00643     virtual const Choice* choice(const Space& home, Archive& e);
00645     virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a);
00647     virtual NGL* ngl(Space& home, const Choice& c, unsigned int a) const;
00655     virtual void print(const Space& home, const Choice& c, unsigned int a,
00656                        std::ostream& o) const;
00658     virtual Actor* copy(Space& home);
00660     static void post(Home home, ViewArray<IntView>& x,
00661                      ViewSel<IntView>* vs[n],
00662                      IntBranchFilter bf,
00663                      IntVarValPrint vvp);
00665     virtual size_t dispose(Space& home);
00666   };
00667 
00669   template<int n, bool min>
00670   void postviewvaluesbrancher(Home home, ViewArray<IntView>& x,
00671                               ViewSel<IntView>* vs[n],
00672                               IntBranchFilter bf,
00673                               IntVarValPrint vvp);
00674 
00675 }}}
00676 
00677 #include <gecode/int/branch/view-values.hpp>
00678 
00679 #ifdef GECODE_HAS_CBS
00680 
00681 namespace Gecode { namespace Int { namespace Branch {
00682 
00687   template<class View>
00688   class CBSBrancher : public Brancher {
00689   private:
00691     ViewArray<View> x;
00692 
00700     class VarIdToPos : public SharedHandle {
00701     protected:
00702       class VarIdToPosO : public SharedHandle::Object {
00703       public:
00705         std::unordered_map<unsigned int, unsigned int> _varIdToPos;
00706       public:
00708         VarIdToPosO(void) = default;
00710         VarIdToPosO(const VarIdToPosO& o) = default;
00711       };
00712     public:
00714       VarIdToPos(void) = default;
00716       void init(void);
00718       bool isIn(unsigned int var_id) const;
00720       int operator[](unsigned int var_id) const;
00722       void insert(unsigned int var_id, unsigned int pos);
00723     } varIdToPos;
00724 
00733     struct PropInfo {
00735       unsigned int domsum;
00737       unsigned int var_id;
00739       int val;
00741       double dens;
00743       bool visited;
00744     };
00745 
00756     std::unordered_map<unsigned int, PropInfo,
00757                        std::hash<unsigned int>,
00758                        std::equal_to<unsigned int>,
00759                        space_allocator<std::pair<const unsigned int, PropInfo>>>
00760     logProp;
00761 
00762   public:
00764     CBSBrancher(Home home, ViewArray<View>& x0);
00766     CBSBrancher(Space& home, CBSBrancher& b);
00768     static void post(Home home, ViewArray<View>& x);
00770     virtual Actor* copy(Space& home);
00772     virtual size_t dispose(Space& home);
00774     virtual bool status(const Space& home) const;
00776     virtual const Choice* choice(Space& home);
00778     virtual const Choice* choice(const Space&, Archive& e);
00780     virtual ExecStatus commit(Space& home, const Choice& c, unsigned int a);
00782     virtual void print(const Space& home, const Choice& c, unsigned int a,
00783                        std::ostream& o) const;
00784   private:
00786     bool inbrancher(unsigned int varId) const;
00787   };
00788 
00789 }}}
00790 
00791 #include <gecode/int/branch/cbs.hpp>
00792 
00793 #endif
00794 
00795 #endif
00796 
00797 // STATISTICS: int-branch