Generated on Sat Jan 20 2018 22:21:11 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: 2017-04-01 20:27:10 +0200 (Sat, 01 Apr 2017) $ by $Author: schulte $
11  * $Revision: 15623 $
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,
45  IntBranchFilter bf,
46  IntVarValPrint vvp) {
47  using namespace Int;
48  if (home.failed()) return;
49  vars.expand(home,x);
50  ViewArray<IntView> xv(home,x);
51  ViewSel<IntView>* vs[1] = {
52  Branch::viewsel(home,vars)
53  };
54  switch (vals.select()) {
56  Branch::postviewvaluesbrancher<1,true>(home,xv,vs,bf,vvp);
57  break;
59  Branch::postviewvaluesbrancher<1,false>(home,xv,vs,bf,vvp);
60  break;
61  default:
62  postviewvalbrancher<IntView,1,int,2>
63  (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
64  break;
65  }
66  }
67 
68  void
69  branch(Home home, const IntVarArgs& x,
71  IntBranchFilter bf,
72  IntVarValPrint vvp) {
73  using namespace Int;
74  if (home.failed()) return;
75  vars.a.expand(home,x);
76  if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
77  (vars.a.select() == IntVarBranch::SEL_RND))
78  vars.b = INT_VAR_NONE();
79  vars.b.expand(home,x);
80  if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
81  (vars.b.select() == IntVarBranch::SEL_RND))
82  vars.c = INT_VAR_NONE();
83  vars.c.expand(home,x);
84  if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
85  (vars.c.select() == IntVarBranch::SEL_RND))
86  vars.d = INT_VAR_NONE();
87  vars.d.expand(home,x);
88  if (vars.b.select() == IntVarBranch::SEL_NONE) {
89  branch(home,x,vars.a,vals,bf,vvp);
90  } else {
91  ViewArray<IntView> xv(home,x);
92  if (vars.c.select() == IntVarBranch::SEL_NONE) {
93  ViewSel<IntView>* vs[2] = {
94  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
95  };
96  switch (vals.select()) {
98  Branch::postviewvaluesbrancher<2,true>(home,xv,vs,bf,vvp);
99  break;
101  Branch::postviewvaluesbrancher<2,false>(home,xv,vs,bf,vvp);
102  break;
103  default:
104  postviewvalbrancher<IntView,2,int,2>
105  (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
106  }
107  } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
108  ViewSel<IntView>* vs[3] = {
109  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
110  Branch::viewsel(home,vars.c)
111  };
112  switch (vals.select()) {
114  Branch::postviewvaluesbrancher<3,true>(home,xv,vs,bf,vvp);
115  break;
117  Branch::postviewvaluesbrancher<3,false>(home,xv,vs,bf,vvp);
118  break;
119  default:
120  postviewvalbrancher<IntView,3,int,2>
121  (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
122  }
123  } else {
124  ViewSel<IntView>* vs[4] = {
125  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
126  Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
127  };
128  switch (vals.select()) {
130  Branch::postviewvaluesbrancher<4,true>(home,xv,vs,bf,vvp);
131  break;
133  Branch::postviewvaluesbrancher<4,false>(home,xv,vs,bf,vvp);
134  break;
135  default:
136  postviewvalbrancher<IntView,4,int,2>
137  (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
138  }
139  }
140  }
141  }
142 
143  void
145  IntVarArgs xv(1); xv[0]=x;
146  branch(home, xv, INT_VAR_NONE(), vals, nullptr, vvp);
147  }
148 
149  void
150  assign(Home home, const IntVarArgs& x, IntAssign ia,
151  IntBranchFilter bf,
152  IntVarValPrint vvp) {
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  };
159  postviewvalbrancher<IntView,1,int,1>
160  (home,xv,vs,Branch::valselcommit(home,ia),bf,vvp);
161  }
162 
163  void
165  IntVarArgs xv(1); xv[0]=x;
166  assign(home, xv, ia, nullptr, vvp);
167  }
168 
169 
170  void
171  branch(Home home, const BoolVarArgs& x,
172  BoolVarBranch vars, BoolValBranch vals,
173  BoolBranchFilter bf,
174  BoolVarValPrint vvp) {
175  using namespace Int;
176  if (home.failed()) return;
177  vars.expand(home,x);
178  ViewArray<BoolView> xv(home,x);
179  ViewSel<BoolView>* vs[1] = {
180  Branch::viewsel(home,vars)
181  };
182  postviewvalbrancher<BoolView,1,int,2>
183  (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
184  }
185 
186  void
187  branch(Home home, const BoolVarArgs& x,
189  BoolBranchFilter bf,
190  BoolVarValPrint vvp) {
191  using namespace Int;
192  if (home.failed()) return;
193  vars.a.expand(home,x);
194  if ((vars.a.select() == BoolVarBranch::SEL_NONE) ||
195  (vars.a.select() == BoolVarBranch::SEL_RND))
196  vars.b = BOOL_VAR_NONE();
197  vars.b.expand(home,x);
198  if ((vars.b.select() == BoolVarBranch::SEL_NONE) ||
199  (vars.b.select() == BoolVarBranch::SEL_RND))
200  vars.c = BOOL_VAR_NONE();
201  vars.c.expand(home,x);
202  if ((vars.c.select() == BoolVarBranch::SEL_NONE) ||
203  (vars.c.select() == BoolVarBranch::SEL_RND))
204  vars.d = BOOL_VAR_NONE();
205  vars.d.expand(home,x);
206  if (vars.b.select() == BoolVarBranch::SEL_NONE) {
207  branch(home,x,vars.a,vals,bf,vvp);
208  } else {
209  ViewArray<BoolView> xv(home,x);
211  vsc = Branch::valselcommit(home,vals);
212  if (vars.c.select() == BoolVarBranch::SEL_NONE) {
213  ViewSel<BoolView>* vs[2] = {
214  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
215  };
216  postviewvalbrancher<BoolView,2,int,2>(home,xv,vs,vsc,bf,vvp);
217  } else if (vars.d.select() == BoolVarBranch::SEL_NONE) {
218  ViewSel<BoolView>* vs[3] = {
219  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
220  Branch::viewsel(home,vars.c)
221  };
222  postviewvalbrancher<BoolView,3,int,2>(home,xv,vs,vsc,bf,vvp);
223  } else {
224  ViewSel<BoolView>* vs[4] = {
225  Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
226  Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
227  };
228  postviewvalbrancher<BoolView,4,int,2>(home,xv,vs,vsc,bf,vvp);
229  }
230  }
231  }
232 
233  void
235  BoolVarArgs xv(1); xv[0]=x;
236  branch(home, xv, BOOL_VAR_NONE(), vals, nullptr, vvp);
237  }
238 
239  void
241  BoolBranchFilter bf,
242  BoolVarValPrint vvp) {
243  using namespace Int;
244  if (home.failed()) return;
245  ViewArray<BoolView> xv(home,x);
246  ViewSel<BoolView>* vs[1] = {
247  new (home) ViewSelNone<BoolView>(home,BOOL_VAR_NONE())
248  };
249  postviewvalbrancher<BoolView,1,int,1>
250  (home,xv,vs,Branch::valselcommit(home,ba),bf,vvp);
251  }
252 
253  void
255  BoolVarArgs xv(1); xv[0]=x;
256  assign(home, xv, ba, nullptr, vvp);
257  }
258 
259 }
260 
261 // STATISTICS: int-post
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition: view-sel.cpp:43
IntVarBranch INT_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:100
Combine variable selection criteria for tie-breaking.
BoolVarBranch BOOL_VAR_NONE(void)
Select first unassigned variable.
Definition: var.hpp:368
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
Which values to select for branching first.
Definition: int.hh:4538
Which values to select for branching first.
Definition: int.hh:4503
Which integer variable to select for branching.
Definition: int.hh:4219
First unassigned.
Definition: int.hh:4223
Which values to select for assignment.
Definition: int.hh:4649
Base class for value selection and commit.
Select the first unassigned view.
Random (uniform, for tie breaking)
Definition: int.hh:4310
Select all values starting from largest.
Definition: int.hh:4517
Select select(void) const
Return selection strategy.
Definition: val.hpp:53
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:4099
Which Boolean variable to select for branching.
Definition: int.hh:4305
std::function< bool(const Space &home, IntVar x, int i)> IntBranchFilter
Branch filter function type for integer variables.
Definition: int.hh:3843
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
Passing integer variables.
Definition: int.hh:639
Passing Boolean variables.
Definition: int.hh:693
Boolean integer variables.
Definition: int.hh:494
std::function< void(const Space &home, const Brancher &b, unsigned int a, IntVar x, int i, const int &n, std::ostream &o)> IntVarValPrint
Function type for printing branching alternatives for integer variables.
Definition: int.hh:4201
IntPropLevel ba(IntPropLevel ipl)
Extract basic or advanced from propagation level.
Definition: ipl.hpp:53
std::function< bool(const Space &home, BoolVar x, int i)> BoolBranchFilter
Branch filter function type for Boolean variables.
Definition: int.hh:3853
void expand(Home home, const IntVarArgs &x)
Expand AFC, action, and CHB.
Definition: var.hpp:78
Integer variables.
Definition: int.hh:353
Which values to select for assignment.
Definition: int.hh:4620
Random (uniform, for tie breaking)
Definition: int.hh:4224
VarBranch a
Branching criteria to try in order.
Post propagator for SetVar x
Definition: set.hh:784
First unassigned.
Definition: int.hh:4309
std::function< void(const Space &home, const Brancher &b, unsigned int a, BoolVar x, int i, const int &n, std::ostream &o)> BoolVarValPrint
Function type for printing branching alternatives for Boolean variables.
Definition: int.hh:4208
Gecode toplevel namespace
void expand(Home home, const BoolVarArgs &x)
Expand decay factor into AFC or action.
Definition: var.hpp:349
void assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:115
Home class for posting propagators
Definition: core.hpp:922
Select all values starting from smallest.
Definition: int.hh:4516