main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Aug 25 2012 03:32:41 for Gecode by
doxygen
1.8.1.2
examples
bibd.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, 2004
8
*
9
* Bugfixes provided by:
10
* Olof Sivertsson <olsi0767@student.uu.se>
11
*
12
* Last modified:
13
* $Date: 2010-10-07 20:52:01 +1100 (Thu, 07 Oct 2010) $ by $Author: schulte $
14
* $Revision: 11473 $
15
*
16
* This file is part of Gecode, the generic constraint
17
* development environment:
18
* http://www.gecode.org
19
*
20
* Permission is hereby granted, free of charge, to any person obtaining
21
* a copy of this software and associated documentation files (the
22
* "Software"), to deal in the Software without restriction, including
23
* without limitation the rights to use, copy, modify, merge, publish,
24
* distribute, sublicense, and/or sell copies of the Software, and to
25
* permit persons to whom the Software is furnished to do so, subject to
26
* the following conditions:
27
*
28
* The above copyright notice and this permission notice shall be
29
* included in all copies or substantial portions of the Software.
30
*
31
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38
*
39
*/
40
41
#include <
gecode/driver.hh
>
42
#include <
gecode/int.hh
>
43
44
using namespace
Gecode;
45
50
class
BIBDOptions
:
public
Options
{
51
public
:
52
int
v
, k, lambda;
53
int
b
,
r
;
54
55
void
derive
(
void
) {
56
b
= (
v
*(
v
-1)*lambda)/(k*(k-1));
57
r
= (lambda*(
v
-1)) / (k-1);
58
}
60
BIBDOptions
(
const
char
* s,
61
int
v0,
int
k0,
int
lambda0)
62
:
Options
(s),
v
(v0), k(k0), lambda(lambda0) {
63
derive();
64
}
66
void
parse
(
int
& argc,
char
* argv[]) {
67
Options::parse
(argc,argv);
68
if
(argc < 4)
69
return
;
70
v
= atoi(argv[1]);
71
k = atoi(argv[2]);
72
lambda = atoi(argv[3]);
73
derive();
74
}
76
virtual
void
help
(
void
) {
77
Options::help
();
78
std::cerr <<
"\t(unsigned int) default: "
<<
v
<< std::endl
79
<<
"\t\tparameter v"
<< std::endl
80
<<
"\t(unsigned int) default: "
<< k << std::endl
81
<<
"\t\tparameter k"
<< std::endl
82
<<
"\t(unsigned int) default: "
<< lambda << std::endl
83
<<
"\t\tparameter lambda"
<< std::endl;
84
}
85
};
86
87
96
class
BIBD
:
public
Script
{
97
protected
:
99
const
BIBDOptions
&
opt
;
101
BoolVarArray
_p
;
102
public
:
104
BIBD
(
const
BIBDOptions
& o)
105
:
opt
(o), _p(*this,
opt
.
v
*
opt
.
b
,0,1) {
106
Matrix<BoolVarArray>
p(_p,
opt
.b,
opt
.v);
107
108
// r ones per row
109
for
(
int
i
=0;
i
<
opt
.v;
i
++)
110
linear
(*
this
, p.
row
(
i
),
IRT_EQ
,
opt
.r);
111
112
// k ones per column
113
for
(
int
j=0; j<
opt
.b; j++)
114
linear
(*
this
, p.
col
(j),
IRT_EQ
,
opt
.k);
115
116
// Exactly lambda ones in scalar product between two different rows
117
for
(
int
i1=0; i1<
opt
.v; i1++)
118
for
(
int
i2=i1+1; i2<
opt
.v; i2++) {
119
BoolVarArgs
row(
opt
.b);
120
for
(
int
j=0; j<
opt
.b; j++)
121
row[j] =
expr
(*
this
, p(j,i1) && p(j,i2));
122
linear
(*
this
, row,
IRT_EQ
,
opt
.lambda);
123
}
124
125
// Symmetry breaking
126
for
(
int
i
=1;
i
<
opt
.v;
i
++)
127
rel
(*
this
, p.
row
(
i
-1),
IRT_GQ
, p.
row
(
i
));
128
for
(
int
j=1; j<
opt
.b; j++)
129
rel
(*
this
, p.
col
(j-1),
IRT_GQ
, p.
col
(j));
130
131
branch
(*
this
, _p,
INT_VAR_NONE
,
INT_VAL_MIN
);
132
}
133
135
virtual
void
136
print
(std::ostream& os)
const
{
137
os <<
"\tBIBD("
138
<<
opt
.v <<
","
<<
opt
.k <<
","
139
<<
opt
.lambda <<
")"
<< std::endl;
140
Matrix<BoolVarArray>
p(_p,
opt
.b,
opt
.v);
141
for
(
int
i
= 0;
i
<
opt
.v;
i
++) {
142
os <<
"\t\t"
;
143
for
(
int
j = 0; j<
opt
.b; j++)
144
os << p(j,
i
) <<
" "
;
145
os << std::endl;
146
}
147
os << std::endl;
148
}
149
151
BIBD
(
bool
share,
BIBD
& s)
152
:
Script
(share,s),
opt
(s.
opt
) {
153
_p.update(*
this
,share,s.
_p
);
154
}
155
157
virtual
Space
*
158
copy
(
bool
share) {
159
return
new
BIBD
(share,*
this
);
160
}
161
162
};
163
167
int
168
main
(
int
argc,
char
* argv[]) {
169
BIBDOptions
opt
(
"BIBD"
,7,3,60);
170
opt.
parse
(argc,argv);
171
172
/*
173
* Other interesting instances:
174
* BIBD(7,3,1), BIBD(6,3,2), BIBD(7,3,20), ...
175
*/
176
177
Script::run<BIBD,DFS,BIBDOptions>(
opt
);
178
return
0;
179
}
180
181
// STATISTICS: example-any
182