main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 14 2013 20:59:44 for Gecode by
doxygen
1.8.3.1
gecode
kernel
branch.hpp
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, 2008
8
*
9
* Last modified:
10
* $Date: 2010-09-03 18:30:37 +1000 (Fri, 03 Sep 2010) $ by $Author: schulte $
11
* $Revision: 11386 $
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 <ctime>
39
40
namespace
Gecode {
41
54
typedef
bool (*
BranchFilter
)(
const
Space
& home,
int
i
,
const
Var
& x);
55
59
class
VarBranchOptions
{
60
public
:
62
BranchFilter
bf
;
64
unsigned
int
seed
;
66
GECODE_KERNEL_EXPORT
static
const
VarBranchOptions
def
;
68
VarBranchOptions
(
BranchFilter
bf0=NULL);
70
static
VarBranchOptions
time
(
BranchFilter
bf
=NULL);
71
};
72
76
class
ValBranchOptions
{
77
public
:
79
unsigned
int
seed
;
81
GECODE_KERNEL_EXPORT
static
const
ValBranchOptions
def
;
83
ValBranchOptions
(
void
);
85
static
ValBranchOptions
time
(
void
);
86
};
87
88
90
template
<
class
VarBranch>
91
class
TieBreakVarBranch
{
92
public
:
94
VarBranch
a
,
b
,
c
,
d
;
96
TieBreakVarBranch
(VarBranch a0 = static_cast<VarBranch>(0),
97
VarBranch b0 = static_cast<VarBranch>(0),
98
VarBranch c0 = static_cast<VarBranch>(0),
99
VarBranch d0 = static_cast<VarBranch>(0));
100
};
101
103
class
TieBreakVarBranchOptions
{
104
public
:
106
VarBranchOptions
a
,
b
,
c
,
d
;
108
GECODE_KERNEL_EXPORT
static
const
TieBreakVarBranchOptions
def
;
110
TieBreakVarBranchOptions
(
const
VarBranchOptions
& a0
111
=
VarBranchOptions::def
,
112
const
VarBranchOptions
& b0
113
=
VarBranchOptions::def
,
114
const
VarBranchOptions
& c0
115
=
VarBranchOptions::def
,
116
const
VarBranchOptions
& d0
117
=
VarBranchOptions::def
);
118
};
119
126
127
template
<
class
VarBranch>
128
TieBreakVarBranch<VarBranch>
129
tiebreak
(VarBranch
a
, VarBranch
b
);
131
template
<
class
VarBranch>
132
TieBreakVarBranch<VarBranch>
133
tiebreak
(VarBranch
a
, VarBranch
b
, VarBranch
c
);
135
template
<
class
VarBranch>
136
TieBreakVarBranch<VarBranch>
137
tiebreak
(VarBranch
a
, VarBranch
b
, VarBranch
c
, VarBranch
d
);
139
TieBreakVarBranchOptions
140
tiebreak
(
VarBranchOptions
a
,
VarBranchOptions
b
);
142
TieBreakVarBranchOptions
143
tiebreak
(
VarBranchOptions
a
,
VarBranchOptions
b
,
VarBranchOptions
c
);
145
TieBreakVarBranchOptions
146
tiebreak
(
VarBranchOptions
a
,
VarBranchOptions
b
,
VarBranchOptions
c
,
147
VarBranchOptions
d
);
149
161
162
GECODE_KERNEL_EXPORT
void
163
branch
(
Home
home,
void
(*f)(
Space
& home));
165
166
167
// Variable branch options
168
forceinline
169
VarBranchOptions::VarBranchOptions
(
BranchFilter
bf0)
170
: bf(bf0), seed(0) {}
171
172
forceinline
VarBranchOptions
173
VarBranchOptions::time
(
BranchFilter
bf) {
174
VarBranchOptions
o(bf);
175
o.
seed
=
static_cast<
unsigned
int
>
(
::time
(NULL));
176
return
o;
177
}
178
179
// Value branch options
180
forceinline
181
ValBranchOptions::ValBranchOptions
(
void
) : seed(0) {}
182
183
forceinline
ValBranchOptions
184
ValBranchOptions::time
(
void
) {
185
ValBranchOptions
o; o.
seed
=
static_cast<
unsigned
int
>
(
::time
(NULL));
186
return
o;
187
}
188
189
190
/*
191
* Combine variable selection criteria for tie-breaking
192
*/
193
template
<
class
VarBranch>
194
forceinline
195
TieBreakVarBranch<VarBranch>::TieBreakVarBranch
(VarBranch a0,
196
VarBranch b0,
197
VarBranch c0,
198
VarBranch d0)
199
:
a
(a0),
b
(b0),
c
(c0),
d
(d0) {}
200
201
template
<
class
VarBranch>
202
forceinline
TieBreakVarBranch<VarBranch>
203
tiebreak
(VarBranch
a
, VarBranch
b
) {
204
TieBreakVarBranch<VarBranch>
ab(a,b);
205
return
ab;
206
}
207
208
template
<
class
VarBranch>
209
forceinline
TieBreakVarBranch<VarBranch>
210
tiebreak
(VarBranch
a
, VarBranch
b
, VarBranch
c
) {
211
TieBreakVarBranch<VarBranch>
abc(a,b,c);
212
return
abc;
213
}
214
215
template
<
class
VarBranch>
216
forceinline
TieBreakVarBranch<VarBranch>
217
tiebreak
(VarBranch
a
, VarBranch
b
, VarBranch
c
, VarBranch
d
) {
218
TieBreakVarBranch<VarBranch>
abcd(a,b,c,d);
219
return
abcd;
220
}
221
222
/*
223
* Combine branch options for tie-breaking
224
*/
225
forceinline
226
TieBreakVarBranchOptions::
227
TieBreakVarBranchOptions
(
const
VarBranchOptions
& a0,
228
const
VarBranchOptions
& b0,
229
const
VarBranchOptions
& c0,
230
const
VarBranchOptions
& d0)
231
:
a
(a0),
b
(b0),
c
(c0),
d
(d0) {}
232
233
forceinline
TieBreakVarBranchOptions
234
tiebreak
(
VarBranchOptions
a
,
VarBranchOptions
b
) {
235
TieBreakVarBranchOptions
ab(a,b);
236
return
ab;
237
}
238
239
forceinline
TieBreakVarBranchOptions
240
tiebreak
(
VarBranchOptions
a
,
VarBranchOptions
b
,
VarBranchOptions
c
) {
241
TieBreakVarBranchOptions
abc(a,b,c);
242
return
abc;
243
}
244
245
forceinline
TieBreakVarBranchOptions
246
tiebreak
(
VarBranchOptions
a
,
VarBranchOptions
b
,
VarBranchOptions
c
,
247
VarBranchOptions
d
) {
248
TieBreakVarBranchOptions
abcd(a,b,c,d);
249
return
abcd;
250
}
251
252
}
253
254
// STATISTICS: kernel-branch