/* 

   (Pseduo)random graph generator for CSE 417 HW 6, Au 02

   The graphs generated by this code are not truly random,
   but they will hopefully provide decent examples for the 
   HW, i.e. they should have a few biconnected components.

*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>

#define A(x,y) (adj[(x * n) + y])

long seed;

/* Park-Miller pseudorandom linear congruential generator */

int rnd( int max ) {

  const double a = 1607;
  const double m = 2147483647;  /* reasonably good values */
  double temp;

  temp = seed * a;
  seed = (temp - m * (long) (temp / m));

  return seed % max;   /* could be done better, but oh well */

}

/* random bit w/prob. p of being 1 */

char bit(double p) {

  return ((((double) rnd(LONG_MAX))/LONG_MAX) < p ? 1 : 0);

}

/* 
   actually generate the graph 

   We will select a random number of potential biconnected
   components, and generate edges between these vertices
   with significantly higher probability than others.

*/

char *makegraph(int n, int d) {

  double epr; /* epr = prob. of creating edge */
  int expbc;  /* exp. number of biconnected components (sort of) */
  char *adj;  /* adjacency matrix */
  int **partition; /* partitioning into biconnected components */
  int *partend;
  int *partdata;
  int i,j,tmp,partitions;

  adj = (char *) malloc(n * n);
  partitions = (((int) (log(n)/log(2))) > 6 ? 
		((int) (log(n)/log(2))) : 6); 
  expbc = rnd(partitions)+2;
  epr = ((double) (n * d)/2) / ((n/(expbc*2)) * (n/(expbc*2)));

  /* create partitions */
 
  partition = (int **) malloc(sizeof(int *) * expbc);
  partend = (int *) malloc(sizeof(int) * expbc);
  for (i = 0; i < expbc; i++) {
    partition[i] = (int *) malloc(sizeof(int) * n);
    partend[i] = 0;
  }

  for (i = 0; i < n; i++) {
    tmp = rnd(expbc);
    partition[tmp][partend[tmp]] = i;
    partend[tmp]++;
  }

  partdata = (int *) malloc(sizeof(int) * n);
  for (i = 0; i < expbc; i++)
    for (j = 0; j < partend[i]; j++)
      partdata[partition[i][j]] = i;


  free(partition);
  free(partend);

  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
	/* make edge only if in same partition */
      if (i < j && partdata[i] == partdata[j])
	A(i,j) = bit(epr);

  free(partdata);

  return adj;

} 

void printgraph( char *adj, int n ) {

  int i,j;
  printf("%d\n",n);
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (i < j && A(i,j) == 1)
	printf("%d %d\n",i,j);

}


/* Main program */

int main(int argc, char **argv) {

  int n,d;
  char *graph;

  if (argc < 4) {
    fprintf(stderr,"Usage: rndgraph n d seed\n\n");
    fprintf(stderr,"where n = number of vertices\n");
    fprintf(stderr,"      d = expected degree\n");
    fprintf(stderr,"      seed = initial seed\n\n");
    fprintf(stderr,"Output: First line of output contains # of vertices,\n");
    fprintf(stderr,"        succeeding lines contain pairs of vertices\n");
    fprintf(stderr,"        representing edges\n");
    return -1;
  }

  n = atoi(argv[1]);
  d = atoi(argv[2]);
  seed = atol(argv[3]);

  if (n < 1 || d < 1) {
    fprintf(stderr,"Invalid input\n");
    return -1;
  }

  graph = makegraph(n,d);
  printgraph(graph,n);
  free(graph);

  return 0;

}