Generated on Thu Mar 16 2017 03:24:15 for Gecode by doxygen 1.8.13
branch.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2012
8  *
9  * Last modified:
10  * $Date: 2016-05-26 13:44:53 +0200 (Thu, 26 May 2016) $ by $Author: schulte $
11  * $Revision: 15087 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/int/branch.hh>
39 
40 namespace Gecode {
41 
42  void
43  branch(Home home, const IntVarArgs& x,
44  IntVarBranch vars, IntValBranch vals,
46  using namespace Int;
47  if (home.failed()) return;
48  vars.expand(home,x);
49  ViewArray<IntView> xv(home,x);
50  ViewSel<IntView>* vs[1] = {
51  Branch::viewselint(home,vars)
52  };
53  switch (vals.select()) {
56  break;
59  break;
60  default:
62  (home,xv,vs,Branch::valselcommitint(home,x.size(),vals),bf,vvp);
63  break;
64  }
65  }
66 
67  void
68  branch(Home home, const IntVarArgs& x,
71  using namespace Int;
72  if (home.failed()) return;
73  vars.a.expand(home,x);
74  if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
75  (vars.a.select() == IntVarBranch::SEL_RND))
76  vars.b = INT_VAR_NONE();
77  vars.b.expand(home,x);
78  if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
79  (vars.b.select() == IntVarBranch::SEL_RND))
80  vars.c = INT_VAR_NONE();
81  vars.c.expand(home,x);
82  if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
83  (vars.c.select() == IntVarBranch::SEL_RND))
84  vars.d = INT_VAR_NONE();
85  vars.d.expand(home,x);
86  if (vars.b.select() == IntVarBranch::SEL_NONE) {
87  branch(home,x,vars.a,vals,bf,vvp);
88  } else {
89  ViewArray<IntView> xv(home,x);
90  if (vars.c.select() == IntVarBranch::SEL_NONE) {
91  ViewSel<IntView>* vs[2] = {
92  Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b)
93  };
94  switch (vals.select()) {
97  break;
100  break;
101  default:
103  ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),
104  bf,vvp);
105  }
106  } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
107  ViewSel<IntView>* vs[3] = {
108  Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b),
109  Branch::viewselint(home,vars.c)
110  };
111  switch (vals.select()) {
113  Branch::ViewValuesBrancher<3,true>::post(home,xv,vs,bf,vvp);
114  break;
117  break;
118  default:
120  ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),
121  bf,vvp);
122  }
123  } else {
124  ViewSel<IntView>* vs[4] = {
125  Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b),
126  Branch::viewselint(home,vars.c),Branch::viewselint(home,vars.d)
127  };
128  switch (vals.select()) {
130  Branch::ViewValuesBrancher<4,true>::post(home,xv,vs,bf,vvp);
131  break;
134  break;
135  default:
137  ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),
138  bf,vvp);
139  }
140  }
141  }
142  }
143 
144  void
146  IntVarArgs xv(1); xv[0]=x;
147  branch(home, xv, INT_VAR_NONE(), vals, NULL, vvp);
148  }
149 
150  void
151  assign(Home home, const IntVarArgs& x, IntAssign ia,
153  using namespace Int;
154  if (home.failed()) return;
155  ViewArray<IntView> xv(home,x);
156  ViewSel<IntView>* vs[1] = {
157  new (home) ViewSelNone<IntView>(home,INT_VAR_NONE())
158  };
160  (home,xv,vs,Branch::valselcommitint(home,ia),bf,vvp);
161  }
162 
163  void
165  IntVarArgs xv(1); xv[0]=x;
166  assign(home, xv, ia, NULL, vvp);
167  }
168 
169 
170  void
171  branch(Home home, const BoolVarArgs& x,
172  IntVarBranch vars, IntValBranch vals,
174  using namespace Int;
175  if (home.failed()) return;
176  vars.expand(home,x);
177  ViewArray<BoolView> xv(home,x);
178  ViewSel<BoolView>* vs[1] = {
179  Branch::viewselbool(home,vars)
180  };
182  (home,xv,vs,Branch::valselcommitbool(home,x.size(),vals),bf,vvp);
183  }
184 
185  void
186  branch(Home home, const BoolVarArgs& x,
189  using namespace Int;
190  if (home.failed()) return;
191  vars.a.expand(home,x);
192  if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
193  (vars.a.select() == IntVarBranch::SEL_RND))
194  vars.b = INT_VAR_NONE();
195  vars.b.expand(home,x);
196  if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
197  (vars.b.select() == IntVarBranch::SEL_RND))
198  vars.c = INT_VAR_NONE();
199  vars.c.expand(home,x);
200  if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
201  (vars.c.select() == IntVarBranch::SEL_RND))
202  vars.d = INT_VAR_NONE();
203  vars.d.expand(home,x);
204  if (vars.b.select() == IntVarBranch::SEL_NONE) {
205  branch(home,x,vars.a,vals,bf,vvp);
206  } else {
207  ViewArray<BoolView> xv(home,x);
209  vsc = Branch::valselcommitbool(home,x.size(),vals);
210  if (vars.c.select() == IntVarBranch::SEL_NONE) {
211  ViewSel<BoolView>* vs[2] = {
212  Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b)
213  };
214  ViewValBrancher<BoolView,2,int,2>::post(home,xv,vs,vsc,bf,vvp);
215  } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
216  ViewSel<BoolView>* vs[3] = {
217  Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b),
218  Branch::viewselbool(home,vars.c)
219  };
220  ViewValBrancher<BoolView,3,int,2>::post(home,xv,vs,vsc,bf,vvp);
221  } else {
222  ViewSel<BoolView>* vs[4] = {
223  Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b),
224  Branch::viewselbool(home,vars.c),Branch::viewselbool(home,vars.d)
225  };
226  ViewValBrancher<BoolView,4,int,2>::post(home,xv,vs,vsc,bf,vvp);
227  }
228  }
229  }
230 
231  void
233  BoolVarArgs xv(1); xv[0]=x;
234  branch(home, xv, INT_VAR_NONE(), vals, NULL, vvp);
235  }
236 
237  void
238  assign(Home home, const BoolVarArgs& x, IntAssign ia,
240  using namespace Int;
241  if (home.failed()) return;
242  ViewArray<BoolView> xv(home,x);
243  ViewSel<BoolView>* vs[1] = {
244  new (home) ViewSelNone<BoolView>(home,INT_VAR_NONE())
245  };
247  (home,xv,vs,Branch::valselcommitbool(home,ia),bf,vvp);
248  }
249 
250  void
252  BoolVarArgs xv(1); xv[0]=x;
253  assign(home, xv, ia, NULL, vvp);
254  }
255 
256 }
257 
258 // STATISTICS: int-post
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:108
bool(* BoolBranchFilter)(const Space &home, BoolVar x, int i)
Branch filter function type for Boolean variables.
Definition: int.hh:3749
Combine variable selection criteria for tie-breaking.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
Which values to select for branching first.
Definition: int.hh:4153
Which variable to select for branching.
Definition: int.hh:3970
static void post(Home home, ViewArray< IntView > &x, ViewSel< IntView > *vs[n], BranchFilter bf, IntVarValPrint vvp)
Constructor for creation.
First unassigned.
Definition: int.hh:3974
void(* BoolVarValPrint)(const Space &home, const Brancher &b, unsigned int a, BoolVar x, int i, const int &n, std::ostream &o)
Function type for printing branching alternatives for Boolean variables.
Definition: int.hh:3956
ViewSel< IntView > * viewselint(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition: view-sel.cpp:43
bool(* IntBranchFilter)(const Space &home, IntVar x, int i)
Branch filter function type for integer variables.
Definition: int.hh:3740
Base class for value selection and commit.
Select the first unassigned view.
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:43
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:113
Select all values starting from largest.
Definition: int.hh:4167
Select select(void) const
Return selection strategy.
Definition: val.hpp:57
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3967
static void post(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, BranchFilter bf, VarValPrint vvp)
Brancher post function.
ViewSel< BoolView > * viewselbool(Space &home, const IntVarBranch &ivb)
Return view selectors for Boolean views.
Definition: view-sel.cpp:163
Passing integer variables.
Definition: int.hh:637
Passing Boolean variables.
Definition: int.hh:691
Boolean integer variables.
Definition: int.hh:492
void expand(Home home, const IntVarArgs &x)
Expand decay factor into AFC or activity.
Definition: var.hpp:74
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
ValSelCommitBase< IntView, int > * valselcommitint(Space &home, int n, const IntValBranch &ivb)
Return value and commit for integer views.
Integer variables.
Definition: int.hh:351
Which values to select for assignment.
Definition: int.hh:4253
ValSelCommitBase< BoolView, int > * valselcommitbool(Space &home, int n, const IntValBranch &ivb)
Return value and commit for Boolean views.
void(* IntVarValPrint)(const Space &home, const Brancher &b, unsigned int a, IntVar x, int i, const int &n, std::ostream &o)
Function type for printing branching alternatives for integer variables.
Definition: int.hh:3950
Random (uniform, for tie breaking)
Definition: int.hh:3975
VarBranch a
Branching criteria to try in order.
Gecode toplevel namespace
Home class for posting propagators
Definition: core.hpp:905
Select all values starting from smallest.
Definition: int.hh:4166