Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/set/branch.hh>
35
36namespace Gecode {
37
38 void
39 branch(Home home, const SetVarArgs& x,
40 SetVarBranch vars, SetValBranch vals,
42 SetVarValPrint vvp) {
43 using namespace Set;
44 if (home.failed()) return;
45 vars.expand(home,x);
46 ViewArray<SetView> xv(home,x);
47 ViewSel<SetView>* vs[1] = {
48 Branch::viewsel(home,vars)
49 };
51 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
52 }
53
54 void
55 branch(Home home, const SetVarArgs& x,
58 SetVarValPrint vvp) {
59 using namespace Set;
60 if (home.failed()) return;
61 vars.a.expand(home,x);
62 if ((vars.a.select() == SetVarBranch::SEL_NONE) ||
63 (vars.a.select() == SetVarBranch::SEL_RND))
64 vars.b = SET_VAR_NONE();
65 vars.b.expand(home,x);
66 if ((vars.b.select() == SetVarBranch::SEL_NONE) ||
67 (vars.b.select() == SetVarBranch::SEL_RND))
68 vars.c = SET_VAR_NONE();
69 vars.c.expand(home,x);
70 if ((vars.c.select() == SetVarBranch::SEL_NONE) ||
71 (vars.c.select() == SetVarBranch::SEL_RND))
72 vars.d = SET_VAR_NONE();
73 vars.d.expand(home,x);
74 if (vars.b.select() == SetVarBranch::SEL_NONE) {
75 branch(home,x,vars.a,vals,bf,vvp);
76 } else {
77 ViewArray<SetView> xv(home,x);
79 if (vars.c.select() == SetVarBranch::SEL_NONE) {
80 ViewSel<SetView>* vs[2] = {
81 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
82 };
83 postviewvalbrancher<SetView,2,int,2>(home,xv,vs,vsc,bf,vvp);
84 } else if (vars.d.select() == SetVarBranch::SEL_NONE) {
85 ViewSel<SetView>* vs[3] = {
86 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
87 Branch::viewsel(home,vars.c)
88 };
89 postviewvalbrancher<SetView,3,int,2>(home,xv,vs,vsc,bf,vvp);
90 } else {
91 ViewSel<SetView>* vs[4] = {
92 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
93 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
94 };
95 postviewvalbrancher<SetView,4,int,2>(home,xv,vs,vsc,bf,vvp);
96 }
97 }
98 }
99
100 void
102 SetVarArgs xv(1); xv[0]=x;
103 branch(home, xv, SET_VAR_NONE(), vals, nullptr, vvp);
104 }
105
106
107 void
108 assign(Home home, const SetVarArgs& x,
109 SetVarBranch vars, SetAssign vals,
111 SetVarValPrint vvp) {
112 using namespace Set;
113 if (home.failed()) return;
114 ViewArray<SetView> xv(home,x);
115 ViewSel<SetView>* vs[1] = {
116 new (home) ViewSelNone<SetView>(home,vars)
117 };
119 (home,xv,vs,Branch::valselcommit(home,vals),bf,vvp);
120 }
121
122 void
123 assign(Home home, const SetVarArgs& x,
126 SetVarValPrint vvp) {
127 using namespace Set;
128 if (home.failed()) return;
129 vars.a.expand(home,x);
130 if ((vars.a.select() == SetVarBranch::SEL_NONE) ||
131 (vars.a.select() == SetVarBranch::SEL_RND))
132 vars.b = SET_VAR_NONE();
133 vars.b.expand(home,x);
134 if ((vars.b.select() == SetVarBranch::SEL_NONE) ||
135 (vars.b.select() == SetVarBranch::SEL_RND))
136 vars.c = SET_VAR_NONE();
137 vars.c.expand(home,x);
138 if ((vars.c.select() == SetVarBranch::SEL_NONE) ||
139 (vars.c.select() == SetVarBranch::SEL_RND))
140 vars.d = SET_VAR_NONE();
141 vars.d.expand(home,x);
142 if (vars.b.select() == SetVarBranch::SEL_NONE) {
143 assign(home,x,vars.a,vals,bf,vvp);
144 } else {
145 ViewArray<SetView> xv(home,x);
147 if (vars.c.select() == SetVarBranch::SEL_NONE) {
148 ViewSel<SetView>* vs[2] = {
149 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b)
150 };
151 postviewvalbrancher<SetView,2,int,1>(home,xv,vs,vsc,bf,vvp);
152 } else if (vars.d.select() == SetVarBranch::SEL_NONE) {
153 ViewSel<SetView>* vs[3] = {
154 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
155 Branch::viewsel(home,vars.c)
156 };
157 postviewvalbrancher<SetView,3,int,1>(home,xv,vs,vsc,bf,vvp);
158 } else {
159 ViewSel<SetView>* vs[4] = {
160 Branch::viewsel(home,vars.a),Branch::viewsel(home,vars.b),
161 Branch::viewsel(home,vars.c),Branch::viewsel(home,vars.d)
162 };
163 postviewvalbrancher<SetView,4,int,1>(home,xv,vs,vsc,bf,vvp);
164 }
165 }
166 }
167
168 void
170 SetVarArgs xv(1); xv[0]=x;
171 assign(home, xv, SET_VAR_NONE(), vars, nullptr, vvp);
172 }
173
174}
175
176// STATISTICS: set-post
Home class for posting propagators
Definition core.hpp:856
bool failed(void) const
Check whether corresponding space is failed.
Definition core.hpp:4055
Which value to select for assignment.
Definition set.hh:1523
Which values to select for branching first.
Definition set.hh:1453
Passing set variables.
Definition set.hh:491
Which variable to select for branching.
Definition set.hh:1302
Expand and CHB void expand(Home home, const SetVarArgs &x)
Definition var.hpp:74
@ SEL_NONE
First unassigned.
Definition set.hh:1306
@ SEL_RND
Random (uniform, for tie breaking)
Definition set.hh:1307
Set variables
Definition set.hh:127
Combine variable selection criteria for tie-breaking.
Definition tiebreak.hpp:38
VarBranch a
Branching criteria to try in order.
Definition tiebreak.hpp:41
Base class for value selection and commit.
View arrays.
Definition array.hpp:253
Select the first unassigned view.
Definition view-sel.hpp:109
Abstract class for view selection.
Definition view-sel.hpp:44
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
Definition branch.cpp:111
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
std::function< bool(const Space &home, SetVar x, int i)> SetBranchFilter
Branch filter function type for set variables.
Definition set.hh:1089
ViewSel< IntView > * viewsel(Space &home, const IntVarBranch &ivb)
Return view selectors for integer views.
Definition view-sel.cpp:39
ValSelCommitBase< IntView, int > * valselcommit(Space &home, const IntValBranch &ivb)
Return value and commit for integer views.
Finite integer sets.
Definition var-imp.hpp:137
Gecode toplevel namespace
Select first unassigned variable SetVarBranch SET_VAR_NONE(void)
Definition var.hpp:96
Function type for printing branching alternatives for set variables typedef std::function< void(const Space &home, const Brancher &b, unsigned int a, SetVar x, int i, const int &n, std::ostream &o)> SetVarValPrint
Definition set.hh:1291
void postviewvalbrancher(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, BranchFilter< typename View::VarType > bf, VarValPrint< typename View::VarType, Val > vvp)
Post view value brancher.
Definition view-val.hpp:341
Post propagator for SetVar x
Definition set.hh:773