/*$Id: rndgraph.c,v 1.6 2005/02/24 06:10:36 ruzzo Exp $*/
/* 

   (Pseudo)random graph generator for CSE 417 

   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.
   
   Original by Bill Pentney,  March 2002
   Revisions by WLR, Feb 2005

   Goal is to produce a connected graph with a specified number of
   vertices, approximately a specified number of edges, and having a 
   modest number of biconnected components.
   
*/

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

#define DEBUG 0
#define min(x,y) (((x) < (y)) ? (x) : (y))
#define max(x,y) (((x) > (y)) ? (x) : (y))

/* treat the 1-d vactor adj as an n x n array */
#define A(x,y) (adj[((x) * n) + (y)])

//define A(x,y) (((x<0)||(y<0)||(x>=n)||(y>=n))?printf("!! %d %d %d\n",n,x,y),adj[0]: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);

}

/* sort length n array a of integers (insertion sort) */

sort(int* a, int n){
  int i, j, temp;
  
  for(i=1; i<n; i++){
    temp = a[i];
    for(j=i-1;  j>=0 && temp < a[j]; j--){
      a[j+1] = a[j];
    }
    a[j+1] = temp;
  }
}

/* 
   Actually generate the graph.

   Select a random number, uniform between 1 and log-base-2(n).
   Partition the vertices into this many blocks; each will
   (probably) become a biconnected component.  Within each
   component, all vertices are connected in one or two simple cycles
   (to make sure it's biconnected), plus we generate edges between
   these vertices with probability approximately
   2(d-1)/component-size. (d-1 instead of d since cycle present.)
   Additionally, each component is connected to exactly one earlier
   one by one or two edges, thus making the graph connected (usually
   without merging any of the components).  The single-edge case
   makes a bridge (which becomes a one-edge biconnected component);
   the 2-edge case leaves an articulation point (except in the rare
   case of a size one component connected by two edges; merged in
   this case).  Thus, the final number of bcc's should be about .75
   log n, on average -- .5 log n blocks, half joined by bridges.
   
*/
char *makegraph(int n, int d) {
  
  int bcs;	        /* number of biconnected components (roughlyf) */
  char *adj;  	        /* adjacency matrix */
  int *cs;		/* array showing _S_tart node in each _C_omponent */
  int i,j,k, ii,jj;
  int dup;
  int ni;		/* n sub i: size of ith component */
  int mynode, prevnode, prevbc,bridge;

  adj = (char *) malloc(n * n);
  bcs = ((int) (log(n)/log(2))); 
  bcs = max(bcs,1);
  bcs = min(bcs,n);
  bcs = rnd(bcs)+1;

  /* create components  */
  cs = (int *) malloc(sizeof(int) * (bcs+1));
  cs[0] = 0;			/* 1st component starts at node zero */
  for (i = 1; i < bcs; i++) {
    cs[i] = rnd(n);		/* others start at bcs-1 random positions */
  }
  cs[bcs] = n;  		/* dummy last entry */
  
  /* sort list of starts; replace duplicates as needed */
  do {
    dup = 0;
    sort(cs, bcs);
    for(i=0; i<bcs-1; i++){
      if(cs[i]==cs[i+1]){
        if(DEBUG){printf("dup\n");}
        dup = 1;
        cs[i]=rnd(n);
      }
    }
  } while(dup);

  for(i=0; i<bcs; i++){
  
    /* gen a cycle thru each component, so definitely biconnected. */
    ni = cs[i+1] - cs[i];		/* size of component */
    if(DEBUG){printf("i=%d, ni=%d\n", i, ni);}
    if(ni>1){
        for(j=0; j<ni; j++){
          A(cs[i]+j,cs[i]+(j+1)%ni) = 1;/* j to j+1, wrapped */
        }
        if(ni>=6 && bit(.7)){           /* bisect most big cycles */
            j = rnd(ni-4)+3;
            assert(3 <= j && j < ni-1);
            A(cs[i]+j,cs[i]+j+1) = 0;   /* shorten original cycle */
            A(cs[i]+j,cs[i])     = 1;
            k = rnd(j-2)+2;             /* graft remainder @ k-2 & k */
            assert(2 <= k && k < j);
            A(cs[i]+ni-1,cs[i])  = 0;
            A(cs[i]+ni-1,cs[i]+k-2) = 1;
            A(cs[i]+k,cs[i]+j+1) = 1;
            if(DEBUG){printf("split %d %d %d\n", i, j, k);}
        }
    }

    /* connect each component but the first to a previous one */
    if(i>0){
      mynode = cs[i]+rnd(ni);		/* pick a random node in my component */
      prevbc = rnd(i);			/* pick a random previous component */
      bridge = bit(.5);			/* make connection a bridge half the time */
      for(j=0; j<=bridge; j++){
        prevnode = cs[prevbc]+rnd(cs[prevbc+1]-cs[prevbc]);
        A(prevnode,mynode) = 1;
        if(DEBUG){printf("joining=%d(%d) and %d(%d), bridge=%d\n", mynode, i, prevnode, prevbc, bridge);} 
      }
    }
    
    /* now add some random edges */
    for (j = 0; j < ni; j++) 
      for (k = j+1; k < ni; k++)
	A(cs[i]+j,cs[i]+k) |= bit(2.0*(d-1)/ni);
  }
  
  if(DEBUG) {
     printf("n=%d, d=%d, bcs=%d\n", n, d, bcs);
     for (i=0; i<n; i++) {
       printf("%3d",i);
    }
    printf("\n");
    for(i=0; i<=bcs; i++){
      printf("%3d",cs[i]);
    }
    printf("\n");
    for(i=0; i<n; i++){
      for(j=0; j<n; j++){
        printf("%3d",A(i,j));
      }
      printf("\n");
    }
  }

  if(DEBUG){printf("free cs\n");}
  free(cs);

  return adj;

} 

void printgraph( char *adj, int n, int shuffle, int dot ) {

  int i,j;
  int *map;     /* node label permutation   */
  char *sep;    /* edge separator in output */
  
  /* if shuffle then generate a random permutation of 0 .. n-1 else identity perm */
  map = (int*) malloc(sizeof(int)*n);
  for(i=0; i<n; i++){
    if(shuffle && i > 0) {
      j = rnd(i);
      map[i] = map[j];
    } else {
      j = i;
    }
    map[j] = i;
  }
  if(DEBUG){
    for (i=0; i<n; i++) {
      printf("%3d", map[i]);
    }
    printf("\n");
  }
  
  if(dot){
    /* print simple .dot file for graphviz:         */
    /*   one line header & edges indicated by "--". */
    printf("graph { graph [size=\"4,4\"]; node[shape=circle];\n");
    sep = "--";
  } else {
    /* hw5 input file: just numbers,    */
    /*   first being "n", rest edgees   */
    printf("%d\n",n);
    sep = " ";
  }
  for (i = 0; i < n; i++)
    for (j = i+1 ; j < n; j++)
      if ( A(map[i],map[j]) || A(map[j],map[i]) )
	printf("%2d%s%2d\n", i, sep, j);

  if(dot){ printf("\n}\n"); } 

  if(DEBUG){printf("free map\n");}
  free(map);
}


/* Main program */

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

  int i;
  int n;        /* desired # nodes      */
  int d;        /* desired avg degree   */
  int shuffle;  /* permute node labels? */
  int dot;      /* generate .dot file?  */
  char *graph;  /* the generated graph  */

  if (argc < 2) {
    fprintf(stderr,"Usage: rndgraph [--dot] n [d [seed [shuffle]]]\n\n");
    fprintf(stderr,"where n = number of vertices\n");
    fprintf(stderr,"      d = expected degree (0 or omitted => 5)\n");
    fprintf(stderr,"      seed = initial seed (0 or omitted => time-of-day)\n");
    fprintf(stderr,"      shuffle = randomize node numbers (1 or omitted => yes; 0 => no)\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");
    fprintf(stderr,"\n\n$Id: rndgraph.c,v 1.6 2005/02/24 06:10:36 ruzzo Exp $\n");
    return -1;
  }

  if(strcmp(argv[1],"--dot")){  /* print graphviz .dot file? */
    dot = 0;
    i = 0;
  } else {
    dot = 1;
    i = 1;
  }   
  n       = atoi(argv[i+1]);
  d       = (argc < i+3) ? 0 : atoi(argv[i+2]);
  seed    = (argc < i+4) ? 0 : atol(argv[i+3]);
  shuffle = (argc < i+5) ? 1 : atoi(argv[i+4]);
  if(d    == 0) d    = 5;
  if(seed == 0) seed = time(NULL);
  
  if (n < 1 || d < 1) {
    fprintf(stderr,"Invalid input\n");
    return -1;
  }

  graph = makegraph(n,d);
  printgraph(graph,n,shuffle,dot);

  if(DEBUG){printf("free graph\n");}
  free(graph);

  return 0;

}