Generated on Sat Feb 7 2015 02:01:15 for Gecode by doxygen 1.8.9.1
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: 2013-05-02 17:10:16 +0200 (Thu, 02 May 2013) $ by $Author: schulte $
11  * $Revision: 13603 $
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  BrancherHandle
43  branch(Home home, const IntVarArgs& x,
44  IntVarBranch vars, IntValBranch vals,
46  using namespace Int;
47  if (home.failed()) return BrancherHandle();
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()) {
55  return Branch::ViewValuesBrancher<1,true>::post(home,xv,vs,bf,vvp);
56  break;
58  return Branch::ViewValuesBrancher<1,false>::post(home,xv,vs,bf,vvp);
59  break;
60  default:
62  (home,xv,vs,Branch::valselcommitint(home,x.size(),vals),bf,vvp);
63  }
64  }
65 
66  BrancherHandle
67  branch(Home home, const IntVarArgs& x,
70  using namespace Int;
71  if (home.failed()) return BrancherHandle();
72  vars.a.expand(home,x);
73  if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
74  (vars.a.select() == IntVarBranch::SEL_RND))
75  vars.b = INT_VAR_NONE();
76  vars.b.expand(home,x);
77  if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
78  (vars.b.select() == IntVarBranch::SEL_RND))
79  vars.c = INT_VAR_NONE();
80  vars.c.expand(home,x);
81  if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
82  (vars.c.select() == IntVarBranch::SEL_RND))
83  vars.d = INT_VAR_NONE();
84  vars.d.expand(home,x);
85  if (vars.b.select() == IntVarBranch::SEL_NONE) {
86  return branch(home,x,vars.a,vals,bf,vvp);
87  } else {
88  ViewArray<IntView> xv(home,x);
89  if (vars.c.select() == IntVarBranch::SEL_NONE) {
90  ViewSel<IntView>* vs[2] = {
91  Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b)
92  };
93  switch (vals.select()) {
95  return Branch::ViewValuesBrancher<2,true>::post(home,xv,vs,bf,vvp);
96  break;
98  return Branch::ViewValuesBrancher<2,false>::post(home,xv,vs,bf,vvp);
99  break;
100  default:
102  ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),
103  bf,vvp);
104  }
105  } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
106  ViewSel<IntView>* vs[3] = {
107  Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b),
108  Branch::viewselint(home,vars.c)
109  };
110  switch (vals.select()) {
112  return Branch::ViewValuesBrancher<3,true>::post(home,xv,vs,bf,vvp);
113  break;
115  return Branch::ViewValuesBrancher<3,false>::post(home,xv,vs,bf,vvp);
116  break;
117  default:
119  ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),
120  bf,vvp);
121  }
122  } else {
123  ViewSel<IntView>* vs[4] = {
124  Branch::viewselint(home,vars.a),Branch::viewselint(home,vars.b),
125  Branch::viewselint(home,vars.c),Branch::viewselint(home,vars.d)
126  };
127  switch (vals.select()) {
129  return Branch::ViewValuesBrancher<4,true>::post(home,xv,vs,bf,vvp);
130  break;
132  return Branch::ViewValuesBrancher<4,false>::post(home,xv,vs,bf,vvp);
133  break;
134  default:
136  ::post(home,xv,vs,Branch::valselcommitint(home,x.size(),vals),
137  bf,vvp);
138  }
139  }
140  }
141  }
142 
143  BrancherHandle
145  IntVarArgs xv(1); xv[0]=x;
146  return branch(home, xv, INT_VAR_NONE(), vals, NULL, vvp);
147  }
148 
149  BrancherHandle
150  assign(Home home, const IntVarArgs& x, IntAssign ia,
152  using namespace Int;
153  if (home.failed()) return BrancherHandle();
154  ViewArray<IntView> xv(home,x);
155  ViewSel<IntView>* vs[1] = {
156  new (home) ViewSelNone<IntView>(home,INT_VAR_NONE())
157  };
159  (home,xv,vs,Branch::valselcommitint(home,ia),bf,vvp);
160  }
161 
164  IntVarArgs xv(1); xv[0]=x;
165  return assign(home, xv, ia, NULL, vvp);
166  }
167 
168 
169  BrancherHandle
170  branch(Home home, const BoolVarArgs& x,
171  IntVarBranch vars, IntValBranch vals,
173  using namespace Int;
174  if (home.failed()) return BrancherHandle();
175  vars.expand(home,x);
176  ViewArray<BoolView> xv(home,x);
177  ViewSel<BoolView>* vs[1] = {
178  Branch::viewselbool(home,vars)
179  };
181  (home,xv,vs,Branch::valselcommitbool(home,x.size(),vals),bf,vvp);
182  }
183 
184  BrancherHandle
185  branch(Home home, const BoolVarArgs& x,
188  using namespace Int;
189  if (home.failed()) return BrancherHandle();
190  vars.a.expand(home,x);
191  if ((vars.a.select() == IntVarBranch::SEL_NONE) ||
192  (vars.a.select() == IntVarBranch::SEL_RND))
193  vars.b = INT_VAR_NONE();
194  vars.b.expand(home,x);
195  if ((vars.b.select() == IntVarBranch::SEL_NONE) ||
196  (vars.b.select() == IntVarBranch::SEL_RND))
197  vars.c = INT_VAR_NONE();
198  vars.c.expand(home,x);
199  if ((vars.c.select() == IntVarBranch::SEL_NONE) ||
200  (vars.c.select() == IntVarBranch::SEL_RND))
201  vars.d = INT_VAR_NONE();
202  vars.d.expand(home,x);
203  if (vars.b.select() == IntVarBranch::SEL_NONE) {
204  return branch(home,x,vars.a,vals,bf,vvp);
205  } else {
206  ViewArray<BoolView> xv(home,x);
208  vsc = Branch::valselcommitbool(home,x.size(),vals);
209  if (vars.c.select() == IntVarBranch::SEL_NONE) {
210  ViewSel<BoolView>* vs[2] = {
211  Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b)
212  };
213  return ViewValBrancher<BoolView,2,int,2>::post(home,xv,vs,vsc,bf,vvp);
214  } else if (vars.d.select() == IntVarBranch::SEL_NONE) {
215  ViewSel<BoolView>* vs[3] = {
216  Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b),
217  Branch::viewselbool(home,vars.c)
218  };
219  return ViewValBrancher<BoolView,3,int,2>::post(home,xv,vs,vsc,bf,vvp);
220  } else {
221  ViewSel<BoolView>* vs[4] = {
222  Branch::viewselbool(home,vars.a),Branch::viewselbool(home,vars.b),
223  Branch::viewselbool(home,vars.c),Branch::viewselbool(home,vars.d)
224  };
225  return ViewValBrancher<BoolView,4,int,2>::post(home,xv,vs,vsc,bf,vvp);
226  }
227  }
228  }
229 
230  BrancherHandle
232  BoolVarArgs xv(1); xv[0]=x;
233  return branch(home, xv, INT_VAR_NONE(), vals, NULL, vvp);
234  }
235 
236  BrancherHandle
237  assign(Home home, const BoolVarArgs& x, IntAssign ia,
239  using namespace Int;
240  if (home.failed()) return BrancherHandle();
241  ViewArray<BoolView> xv(home,x);
242  ViewSel<BoolView>* vs[1] = {
243  new (home) ViewSelNone<BoolView>(home,INT_VAR_NONE())
244  };
246  (home,xv,vs,Branch::valselcommitbool(home,ia),bf,vvp);
247  }
248 
251  BoolVarArgs xv(1); xv[0]=x;
252  return assign(home, xv, ia, NULL, vvp);
253  }
254 
255 }
256 
257 // STATISTICS: int-post
bool failed(void) const
Check whether corresponding space is failed.
Definition: core.hpp:3446
static BrancherHandle post(Home home, ViewArray< IntView > &x, ViewSel< IntView > *vs[n], BranchFilter bf, IntVarValPrint vvp)
Constructor for creation.
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:3577
Combine variable selection criteria for tie-breaking.
Select all values starting from smallest.
Definition: int.hh:3994
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
Which values to select for branching first.
Definition: int.hh:3981
Which variable to select for branching.
Definition: int.hh:3798
Handle for brancher.
Definition: core.hpp:1157
Select all values starting from largest.
Definition: int.hh:3995
Select select(void) const
Return selection strategy.
Definition: val.hpp:57
static BrancherHandle post(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, BranchFilter bf, VarValPrint vvp)
Brancher post function.
void(* BoolVarValPrint)(const Space &home, const BrancherHandle &bh, 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:3784
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:3568
Base class for value selection and commit.
Select the first unassigned view.
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:636
Passing Boolean variables.
Definition: int.hh:690
Boolean integer variables.
Definition: int.hh:491
Random (uniform, for tie breaking)
Definition: int.hh:3803
BrancherHandle assign(Home home, const FloatVarArgs &x, FloatAssign fa, FloatBranchFilter bf, FloatVarValPrint vvp)
Assign all x with value selection vals.
Definition: branch.cpp:113
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.
First unassigned.
Definition: int.hh:3802
Integer variables.
Definition: int.hh:350
void(* IntVarValPrint)(const Space &home, const BrancherHandle &bh, 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:3778
Which values to select for assignment.
Definition: int.hh:4081
ValSelCommitBase< BoolView, int > * valselcommitbool(Space &home, int n, const IntValBranch &ivb)
Return value and commit for Boolean views.
VarBranch a
Branching criteria to try in order.
Gecode toplevel namespace
BrancherHandle 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
Home class for posting propagators
Definition: core.hpp:717