/* ===========================================
   
   filename:  generate_poset.c
   revision:  January 30, 2006

   C Program to generate a poset and write it 
   out to a data file. Command line arguments 
   are 
    
      -n Positive integer representing the 
         number of points the poset should 
	 have. Optional, defaults to 100.
	 Must be <= 5000.

      -f Output filename. Optional, defaults 
         to poset.txt.
	 
      -d Number of linear orders to intersect.
         Optional, defaults to 10.

   Assuming that we have compiled with
   
      gcc -o generate_poset generate_poset.c

   and therefore have an executable 
   generate_poset, we can then type

       ./generate_poset -n 150 -d 12
   
   to generate a poset on 150 points formed
   from the intersection of 12 linear orders
   and stored in poset.txt.

   ========================================== */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define MAX_POSET_SIZE 5000

int main(int argc, char *argv[])
{
   int num_points = 100;
   int d = 10;
   int i,j, stime;
   char filename[100] = "poset.txt";
   int *permutation, *linear_order, *partial_order;
   long ltime;
   FILE *out_file;

   /* Parse the command line arguments */
   for (i = 1; i < argc; i++)
   {
      if (argv[i][0]== '-')
      {
	 char f = argv[i][1];
	 switch (f)
	 {
	    case 'n':
	       num_points = atoi(argv[i+1]);
	       if (num_points > MAX_POSET_SIZE)
	       {
		  printf("Error 1: Number of points is greater than ");
		  printf("%d. Exiting.\n",MAX_POSET_SIZE);
		  exit(1);
	       }
	       break;
	    case 'f':
	       strncpy(filename,argv[i+1],100);
	       break;
	    case 'd':
	       d = atoi(argv[i+1]);
	       if (d<=0)
	       {
		  printf("Error 2: Number or linear orders not positive. ");
		  printf("Exiting.\n"); 
		  exit(1);
	       }
	       break;
	    default:
	       printf("Unrecognized command line option: -%c.\n", f);
	       printf("Usage: %s [-n num_points] ",argv[0]);
	       printf("[-f output_filename] [-d num_linear_orders]\n");
	       exit(1);
	       break;
	 }
      }
   }   
   
   /* Seed the pseudorandom number generator with the current time */
   ltime = time(NULL);
   stime = (unsigned) ltime/2;
   srand(stime);

   /* Open the output file */
   out_file = fopen(filename, "w");
   if (out_file == NULL)
   {
      printf("Error 6: Failed to open %s for output.\n",filename);
      exit(1);
   }

   /* Print the first line of the output file, the number of points */
   fprintf(out_file,"%d\n",num_points);

   /* Allocate memory for the permutation, linear order, and partial 
      order we're creating */
   if ((permutation = malloc(sizeof(int) * num_points)) == NULL)
   {
      printf("Error 3: Failed to allocate memory for permutation.\n");
      exit(1);
   }

   if((partial_order = malloc(num_points*num_points*sizeof(int))) == NULL)
   {
      printf("Error 4: Failed to allocate memory for partial order.\n");
      exit(1);
   }

   if((linear_order = malloc(num_points*num_points*sizeof(int))) == NULL)
   {
      printf("Error 5: Failed to allocate memory for linear order.\n");
      exit(1);
   }

   /* Initialize the less than or equal to matrix of partial_order 
      with all 1's. At this point, partial_order isn't a legitimate 
      partial order, but this will allow our loop below to copy over 
      the first linear order without needing a special case. */
   for (i=0; i < num_points; i++)
      for (j=0; j < num_points; j++)
	 *(partial_order + num_points*i + j) = 1;

   for ( ; d > 0; d--) /* For each of the d linear orders we requested... */
   {
      /* Start with the identity permutation */
      for (i=0; i < num_points; i++)
	 permutation[i] = i;

      /* Generate a random permutation via swaps */
      for (i=0; i < num_points; i++)
      {
	 int temp = permutation[i];
	 int swap_index = i+ (rand() % (num_points-i));
	 permutation[i] = permutation[swap_index];
	 permutation[swap_index] = temp;
      }

      /* Create a linear order from the permutation, first by clearing 
	 out linear_order and then filling it in. */
   
      for (i=0; i < num_points; i++)
	 for(j=0; j < num_points; j++)
	    *(linear_order + num_points*i + j) = 0;

      for (i=0; i < num_points; i++)
	 for(j=i; j < num_points; j++)
	    *(linear_order + num_points*permutation[i] + permutation[j]) = 1;

      /* Take the intersection with the existing partial order */
      
      for (i=0; i < num_points; i++)
	 for (j=0; j < num_points; j++)
	 {
	    if ((*(linear_order + num_points*i + j) == 1) &&
		(*(partial_order + num_points*i + j) == 1))
	    {
	       /* Linear order and partial order agree */
	    }
	    else
	    {
	       /* Linear order and partial order disagree, so clear */
	       *(partial_order + num_points*i +j) = 0;
	    }
	 }
   }
   
   /* Print the partial order out to the file */
   for (i=0; i < num_points; i++)
      for (j=0; j< num_points; j++)
	 if (*(partial_order + num_points*i + j) == 1)
	    fprintf(out_file,"%d %d\n",i+1,j+1);

   /* Clean up */

   if (fclose(out_file) != 0)
   {
      printf("Error 7: Error closing output file.\n");
      exit(1);
   }
   free(partial_order);
   free(linear_order);
   free(permutation);

   return 0;
}