// CSP solver. For testing extended forward checking algorithms.
/**********************************************************************
CSP FILE FORMAT
Line 1. A string (no whitespace characters) specifying the
name of the problem (for the log file).
Line 2. N K1 K2 ... KN -1 (all integers).
N = the number of variables.
K1, ..., Ki, ..., KN the domain size of each variable. -1 is used as
a terminator. If there are less than N values the last value
specified is repeated to determine the domain size of all of the
other variables. Thus we can specify a CSP with every variable
having the same domain size by specifying only two numbers N K. K
will be repeated to determine the domain size of all of the
variables.
The next entries specify the constraints. First specify the number
of different constraints Q followed by each of the constraints in
the format
Q
cons# sizei sizej
0 1 ...
1 0 ...
cons# sizei sizej
0 1 ...
1 0 ...
where Q is the number of DISTINCT constraints (note that the CSP
might have many more constraints. Each constraint is specifed by
first giving three integers: the constraint number (each must be
distinct and numbered in the range 1 to Q), the domain size of the
first variable and the domain size of the second variable.
The next set of entries specify the rows of the constraint matrix,
(thus we have sizei "rows" with sizej entries of 0 and 1
each). These entries must all be 0 or 1.
After each of the constraints is specified we specify the
constraints that hold between particular variables. This is
specified by a sequence of triples in the format
i1 j1 h1
...
il jl hl
...
im jm hm
End of file is the terminator for this sequence.
Each triple i j h specifies that variable i is constrained with
variable j by constraint number h. We must have i < j, and also
constraint #h must be of the right size (i.e., domainsize of i X
domainsize of j).
**********************************************************************/
// Generate C-T model for CSPs.
// Output problem to file (in the format above)
// C=# of constraints
// T=tightness of each constraints (number of incompatiable pairs).
//
#include
#include
#include
#include
#include
#include
#include
#include
/**********************************************************************
Main routine.
**********************************************************************/
void main(int argc, char *argv[]) {
char* fnName = 0;
if (argc < 6) {
cerr
<< "Usage:.\n"
<< "genCT N K C T seed filename\n";
exit(1);
}
int N, K, C, T, SEED;
if(sscanf(argv[1], "%d", &N) != 1) {
cerr << "Unable to read N from \""
<< argv[1] << "\"\n";
exit(1);
}
if(sscanf(argv[2], "%d", &K) != 1) {
cerr << "Unable to read K from \""
<< argv[2] << "\"\n";
exit(1);
}
if(sscanf(argv[3], "%d", &C) != 1) {
cerr << "Unable to read N from \""
<< argv[3] << "\"\n";
exit(1);
}
if (C < 0 || C > (N*(N-1)/2)) {
cerr << "Invalid value for C, must be in range 0 to " << (N*(N-1)/2) << '\n';
exit(1);
}
if(sscanf(argv[4], "%d", &T) != 1) {
cerr << "Unable to read T from \""
<< argv[4] << "\"\n";
exit(1);
}
if (T < 0 || T > (K*K)) {
cerr << "Invalid value for T, must be in range 0 to " << K*K << '\n';
exit(1);
}
if(sscanf(argv[5], "%d", &SEED) != 1) {
cerr << "Warning Unable to read Seed from \""
<< argv[5] << "\": using 0 instead.\n";
SEED = 0;
}
ofstream gout(argv[6], ios::out);
if(!gout) {
cerr << "Unable to open output file \""
<< argv[6] << "\"\n";
exit(1);
}
srand(SEED);
//Generate a CT problem
//Problem name
gout << "CT-" << N << "-" << K << "-" << C << "-" << T << "\n";
//domain sizes;
gout << N << " " << K << " " << -1 << "\n\n";
//number of constraints.
gout << C << "\n";
//A K*K matrix for the constraint. Initially all pairs are
//compatiable.
bool* m = new bool[K*K];
int i,j, c;
for(c = 0; c