//Generates random K-regular graphs on N vertices.
//Generates N_ITER1 random lifts of each base graph.
//Prints lambda_1 of each lift.

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


int main() {
  base_graph G; /* store base graph here */
  lift_graph H; /* store lifted graph here */

  /* some pre-built graphs */

  //base_graph G = {{1,2,3,4,5,6,7}, {0,2,3,4,5,6,7}, {0,1,3,4,5,6,7}, {0,1,2,4,5,6,7}, {0,1,2,3,5,6,7}, {0,1,2,3,4,6,7}, {0,1,2,3,4,5,7}, {0,1,2,3,4,5,6}}; /* K_8 */

  //base_graph G = {{0,4,5}, {0,6,2}, {1,3,7}, {2,4,8}, {0,3,9}, {0,7,8}, {1,8,9}, {2,5,9}, {3,5,6}, {4,6,7}}; /*Petersen graph*/
  
  index i, j;

  index iter, iter1;
  real gap_base, gap_lift;

  real Ram = 2*sqrt(K-1); /* Ramanujan bound */
  //printf("Ram is: %g\n", Ram);

  ran0_init();
    
  for (iter=0; iter<N_ITER;){
    generate_base(G); /* generate N_ITER base graphs */
    gap_base = symm_gap_base(G);
    //printf("Base: %g\n", gap_base);
    if (gap_base <= Ram && gap_base != K) { 
/* controls Ramanujan or non-Ramanujan base graphs; also avoids K as an eigenvalue of base graph, since this means non-connected */


 printf("base_graph G = {{");
    printf("%d", G[0][0]);
    for(j=1; j<K; j++)
      printf(", %d", G[0][j]);
    printf("}");
    for(i=1; i<N; i++){
      printf(", {%d", G[i][0]);
      for(j=1; j<K; j++)
	printf(", %d", G[i][j]);
      printf("}");
    }
    printf("}\n\n");

    
    for (iter1=0; iter1 < N_ITER1; iter1++){
      generate_lift (G, H); /* for each base graph, generate N_ITER lifts*/
	//print_lift(H);
      gap_lift = symm_gap(H);
	printf ("%g\n", gap_lift); /*print lambda_1 of each lift*/
    }
     iter++;
  }
}

  return 0;
}
 

void generate_lift(base_graph G, lift_graph H) {
  index D[N];  /*D keeps track of degrees for you*/
  permutation sigma;

  index u, v; /* vertices in G */
  index i;    /* index of neighbours of u */
  index l;    /* index along the fibre */
  index x, y; /* vertices in H */
  index j, k; /* index of neigbours of x,y */
 


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

  for(x=0; x<N*L; x++){
    for(j=0; j<K; j++)
      H[x][j]=0;
  }

  for(u=0; u<N; u++){ /*moving along the vertices*/
    for(i=0; i<K; i++){ /*for each of K neighbors*/
      v = G[u][i];
      if(v >= u){ /* lift each edge once */
	random_permutation (sigma);
        j = D[u]; k = D[v];
	for(l=0; l<L; l++){  /*an edge for each lift of K edges*/
	  x = u*L + l;  /*the vertex lifted*/
	  y = v*L + sigma[l];  /*the neighbor lifted with permutation*/

	  H[x][j] = y;
          H[y][k] = x;

	}

	if(u==v) { /* LOOP!!! Check this part of the code; could be buggy.*/
	  D[u]++;
	  i++;
	}
	else {
	  D[u]++; D[v]++;
	}
      }
    }
  }
}

/* Print the generated graph: */
void print_lift(lift_graph H){

  index i, j;

  for (i=0; i<N*L; i++) {
    printf("%d: ", i);
    for(j=0; j<K; j++)
      printf("%d ", H[i][j]);
    printf("\n");
  }
}