// 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 <stdlib.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include <math.h>

/**********************************************************************
  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<C; c++) {
    //generate and output a constraint.
    gout << c+1 << " " << K << " " << K << "\n";
    //Generate the constraint. First fill m with "1"'s
    for(i=0;i<K;i++)
      for(j=0;j<K;j++)
	m[i*K+j] = true;
    //Now insert  T "falses" into m at random.
    for(int t = 0; t < T; t++) {
      /* Pick a random number in remaining range */
      int num = rand() % (K * K - t);
      int cnt = 0;
      bool done = false;
      //find and flip the num'th compatiable pair.
      for(i=0; i< K && !done; i++) {
	for(j=0; j< K && !done; j++) {
	  if(cnt==num && m[i*K+j]) {
	    m[i*K+j] = false;
	    done = true;
	  }
	  else if (m[i*K+j]) {
	    cnt++;
	  }
	}
      }
    }
    //Now output it.
    for(i=0;i<K;i++) {
      for(j=0;j<K;j++) {
	if(m[i*K+j])
	  gout << "1 ";
	else
	  gout << "0 ";
      }
      gout << "\n";
    }
    gout << "\n";
  }
  
  //Now output the variables that are constrained.

  gout << "\n\n";

  //Fill a matrix of possible constraints will the randomly choosen
  //constraints. 
  int maxPairs = N * (N-1) / 2;
  m = new bool[maxPairs];
  int mindex;
  /* Initialize M matrix to record no choosen edges */
  for(i = 0; i < maxPairs; i++)
    m[i] = false;
  for(c = 0; c < C; c++)	{
    /* Pick a random number in remaining range and place in matrix */
    int num = rand() % (maxPairs - c);
    int cnt = 0;
    bool done = false;
    for (i = 0; i < maxPairs && !done; i++)
      if (cnt == num && !m[i])
	{
	  m[i] = true;
	  done = true;
	}
      else if (!m[i])
	cnt++;
  }
	
  int cnt = 1;
  mindex = 0;		
  for(i = 1; i <= N; i++)
    for(j = i+1; j <= N; j++)
      if (m[mindex++]) 
	// Variables i and j should be constrained. 
	gout << i << " " << j << " " << cnt++ << "\n";
}