//Generates a random K-regular graph on N vertices.

#include <stdio.h>
#include "defs.h"

#define N_ITER 100


void generate_base(base_graph G) {
  index C[N]; /*C is the collection of vertices still available*/
  index D[N]; /*D keeps track of degrees for you*/

  index i; /*counter*/
  index r; /* random number */
  index u, v; /* vertices */
  index n; /*number of vertices available (goes down) */

  for(v=0; v<N; v++)
    D[v]=0;

  for(v=0; v<N; v++)
    C[v]=v;

  for(v=0; v<N; v++) {
    for(u=0; u<K; u++)
      G[v][u]=0;
  }

  n=N;

  for(v=0; v<N; v++) {

    /* Scenario: V already has max degree.*/
    if(D[v]>=K){
   
    }
    /*i.e., don't do anything!*/

    else {
      for(; D[v]<K; D[v]++) {
	/* n should be one too large. the last one in selection isn't used */

	/* pick a random number from 0 to n */
	//do {
	r = select_vertex(n);
	u = C[r];
	if (u==v) {
	  r = (r+1) % n;
	  u = C[r];
	}

	//} while (u == v); 
	/* supposedly prevents Loops; should be checked for bugginess */

	/* make the edge */
	G[v][D[v]] = u;
	G[u][D[u]] = v;


	/* Scenario: Not a loop */
	if (u != v) {
	/* raise the degree of u */
	  D[u]++;


	/* Scenario: you filled up u */
	  if (D[u]==K) {
	    n--;

	  /* if n goes to 0, you must be done */
	    if(n <= 0) {
	      break;
	    }
	  
	  /* Anyway, replace u in Collection with the last vertex in C */
	    C[r] = C[n];
	  }
	}

	/* Scenario: LOOP! */
	else
	  ;
      }

      /* Now V is done */
	
      n--;
      if (n <= 0) {
	break;
      }

      for(i=0; i<n; i++){
	if (C[i] == v){
	  C[i]=C[n];
	}
      }
    }
  }
}