/* Copyright 2020 Christophe Crespelle */

/* This program is an adaptation of a program written by Clemence Magnien and Matthieu Latapy*/
/* Clemence Magnien and Matthieu Latapy */
/* September 2007 */
/* http://www-rp.lip6.fr/~magnien/Diameter */
/* clemence.magnien@lip6.fr */


/* This program is a library to manipualte graphs given by semi-adjacency lists, that is adjacency lists were only neighbours with a smaller identifyer than the considered vertex are listed. */

#define MAX_LINE_LENGTH 1000


/* Graph stored by semi-adjacency lists (neighbours only with vertices with smaller identifiants) */
//
//NOTE: ce qui est fait actuellement (voir reorder_sgraph): slinks est indice par position, mais les listes contiennent les identifiants!!! scapacities et sdegrees sont indexes par position. permu[i] donne l'identifiant du sommet en position i dans la permu. Et pos[i] donne la position dans la permu du sommet dont l'identifiant est i. Cela suppose que les identifiants sont entre 0 et n-1.
//NOTE: ce qu'il aurait fallu faire c'est indexer tous les tableaux par position ET leur faire contenir les positions (dans slinks). La correspondance avec les identifiants se fait par permu. On peut peut-être même se passer de pos?
// CA A ETE FAIT
typedef struct sgraph{
  int n;
  int m;

  int *permu;
//  int *pos;

  int **slinks;
  int *sdegrees;
  int *scapacities;
} sgraph;


/******** UTILITY functions - begin *********/

void report_error(char *s){
  fprintf(stderr,"%s\n",s);
  fflush(stderr);
  exit(-1);
}

/******************************/
/* Auxiliary Random Functions */
/******************************/

/////////////////////////////////////
// INITIALISATION OF rand()
// with 2 inputs : n2 sensitive to program execution, n1 sensitive to moment of call in the execution

void init_random() {
  int n1, n2;
  struct timeval aux;
  gettimeofday(&aux,NULL);
  
  n1=(((int) clock())%100);
  n2=((int) aux.tv_usec)%1000;
  
  srand( (((((n2%10)*10+(n1%10))*10+(n2%10)%10)*10+(n1/10))*10+(n2/100))*10000+n1*100+n2 );
}

////////////////////////////////////
// A RANDOM INTEGER BETWEEN 0 AND a
// Question : uniformity guaranteed?

int rand_int(int a){
return (rand()/(float) INT_MAX)*a;
}

/////////////////////////////////////
// A RANDOM INTEGER BETWEEN 0 AND a-1
// an improved version, supposed to be as much uniform as rand() of C
// if need a-1=INT_MAX -> use directly rand()

int rand_imp(int a){
  int pas, limit, tir;
  pas=INT_MAX / a;
  if (INT_MAX % a == a-1) {
    pas++;
    limit=INT_MAX;
  }
  else limit = a * pas - 1;

  tir=rand();
  while (tir>limit) {
  tir=rand();
  }
  return tir/pas;
}

/////////////////////////////////////
// A RANDOM FLOAT IN [0,1]

float rand01(void) {
return rand()/(float) INT_MAX;
}

/////////////////////////////////////
// RANDOMLY PERMUTE THE CONTENT OF AN ARRAY OF INTEGERS
int * random_perm(const int * tab, int size){
  int *perm;
  int i,num,tmp;
  if( (perm=(int *)malloc(size*sizeof(int))) == NULL )
    report_error("random_perm: malloc() error");
  for (i=0;i<size;i++) perm[i] = tab[i];
//  init_random();
  for (i=0;i<size-1;i++) {
    num=rand_imp(size-i);

    tmp = perm[i+num];
    perm[i+num]=perm[i];
    perm[i]=tmp;
  }
  return perm;
}


/******** UTILITY functions - end *********/




/******** GRAPH MANAGEMENT functions - begin *********/

void free_sgraph_old_start(sgraph *g, int old_0){
  if (g!=NULL) {
    if (g->slinks!=NULL) {
      if (g->slinks[old_0]!=NULL)
	free(g->slinks[old_0]);
      free(g->slinks);
    }
    if (g->scapacities!=NULL)
      free(g->scapacities);
    if (g->sdegrees!=NULL)
      free(g->sdegrees);
    free(g);
  }
}

void free_sgraph(sgraph *g){
  free_sgraph_old_start(g,0);
}



/////////////// LOAD A SEMI-GRAPH FROMA FILE ////////////////////
// IN  : forder (the file containing the specified order of the vertices), n the number of vertices in the graph
// OUT : 
// ACTION : assign vertex_order with the order read in forder
//----------------------------------------------------------------------
// PREREQUISITE : the format of the input file is: number n of vertices, semi-degrees of all vertices by increasing id from 0 to n-1, list of edges with larger identifiant comes first
/////////////////////////////////////////////////////////////////////////////////////

void read_order_from_file(FILE * f, int n, int * vertex_order) {
  char line[MAX_LINE_LENGTH];
  int vertex, i;

  for(i=0;i<n;i++){

    if( fgets(line,MAX_LINE_LENGTH,f) == NULL )
      report_error("read_order_from_file; read error (fgets)");
    if( sscanf(line, "%d\n", &vertex) != 1 )
      report_error("read_order_from_file; read error (sscanf)");
    vertex_order[i]=vertex;
  }

  if( fgets(line,MAX_LINE_LENGTH,f) != NULL )
    report_error("read_order_from_file; too many lines");

}




/////////////// LOAD A SEMI-GRAPH FROMA FILE ////////////////////
// IN  : the file containing the semi-adjacency lists of the graph
// OUT : 
// RETURN : a pointer to the sgraph (permu and pos are not effected)
//----------------------------------------------------------------------
// PREREQUISITE : the format of the input file is: number n of vertices, semi-degrees of all vertices by increasing id from 0 to n-1, list of edges with larger identifiant comes first
/////////////////////////////////////////////////////////////////////////////////////

sgraph *sgraph_from_file(FILE *f){
  char line[MAX_LINE_LENGTH];
  int i, u, v;
  sgraph *g;

  if( (g=(sgraph *)malloc(sizeof(sgraph))) == NULL )
    report_error("sgraph_from_file: malloc() error 1");
  
  /* read n */
  if( fgets(line,MAX_LINE_LENGTH,f) == NULL )
    report_error("sgraph_from_file: read error (fgets) 1");
  if( sscanf(line, "%d\n", &(g->n)) != 1 )
    report_error("sgraph_from_file: read error (sscanf) 2");
  
  /* read the semi-degree sequence */
  if( (g->scapacities=(int *)malloc(g->n*sizeof(int))) == NULL )
    report_error("sgraph_from_file: malloc() error 2");
  if( (g->sdegrees=(int *)calloc(g->n,sizeof(int))) == NULL )
    report_error("sgraph_from_file: calloc() error");
  for(i=0;i<g->n;i++){
    if( fgets(line,MAX_LINE_LENGTH,f) == NULL )
      report_error("sgraph_from_file; read error (fgets) 2");
    if( sscanf(line, "%d %d\n", &v, &(g->scapacities[i])) != 2 )
      report_error("sgraph_from_file; read error (sscanf) 2");
    if( v != i ){
      fprintf(stderr,"Line just read : %s\n i = %d; v = %d\n",line,i,v);
      report_error("sgraph_from_file: error while reading degrees");
    }
  }
  
  /* compute the number of links */
  g->m=0;
  for(i=0;i<g->n;i++)
    g->m += g->scapacities[i];
  
  /* create contiguous space for links */
  if (g->n==0){
    g->slinks = NULL; g->sdegrees = NULL; g->scapacities = NULL;
  }
  else {
    if( (g->slinks=(int **)malloc(g->n*sizeof(int*))) == NULL )
      report_error("sgraph_from_file: malloc() error 3");
    if( (g->slinks[0]=(int *)malloc(g->m*sizeof(int))) == NULL )
      report_error("sgraph_from_file: malloc() error 4");
    for(i=1;i<g->n;i++)
      g->slinks[i] = g->slinks[i-1] + g->scapacities[i-1];
  }

  /* read the links */
  for(i=0;i<g->m;i++) {
    if( fgets(line,MAX_LINE_LENGTH,f) == NULL )
      report_error("sgraph_from_file; read error (fgets) 3");
    if( sscanf(line, "%d %d\n", &u, &v) != 2 ){
      fprintf(stderr,"Attempt to scan link #%d failed. Line read:%s\n", i, line);
      report_error("sgraph_from_file; read error (sscanf) 3");
    }
    if ( (u>=g->n) || (v>=g->n) || (u<0) || (v<0) ) {
      fprintf(stderr,"Line just read: %s",line);
      report_error("sgraph_from_file: bad node number");
    }
    if ( u<v ) {
      fprintf(stderr,"Line just read: %s",line);
      report_error("sgraph_from_file: edge not in order");
    }
    if (g->sdegrees[u]>=g->scapacities[u]) {
      fprintf(stderr, "reading link %s\n", line);
      report_error("sgraph_from_file: too many links for a node");
    }
    g->slinks[u][g->sdegrees[u]] = v;
    g->sdegrees[u]++;
  }
  for(i=0;i<g->n;i++)
    if (g->sdegrees[i]!=g->scapacities[i])
      report_error("sgraph_from_file: capacities <> degrees");
  if( fgets(line,MAX_LINE_LENGTH,f) != NULL )
    report_error("sgraph_from_file; too many lines");
  
  if ((g->scapacities)!=NULL) free(g->scapacities);
  g->scapacities=NULL;

  g->permu=NULL;
//  g->pos=NULL;

  return(g);
}




/////////////// DISPLAY A SEMI-GRAPH IN A FILE ////////////////////
// IN  : the semi-graph g
// IN/OUT : 
// OUT : 
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE :
/////////////////////////////////////////////////////////////////////////////////////

void display_semi_graph (FILE *f, sgraph* g) {

  int i,j;
  
  fprintf(f,"Sommet \t Semi-degré\n");
  for (i=0;i<g->n;i++) fprintf(f,"%d \t%d\n",g->permu[i],g->sdegrees[i]);
  fprintf(f,"\n");

  fprintf(f,"Liste d'adjacences:\n");
  for (i=0;i<g->n;i++) {
    fprintf(f,"%d :\t",g->permu[i]);
    for (j=0;j<g->sdegrees[i];j++) { 
      fprintf(f,"%d ",g->permu[g->slinks[i][j]]);
    }
    fprintf(f,"\n");
  }
  fprintf(f,"\n");

}




/////////////// INITIALISE PERMU AND POS OF A GRAPH WITH IDENTITY ////////////////////
// IN  :
// IN/OUT : the semi-graph g
// OUT : 
// RETURN :
//----------------------------------------------------------------------
// PREREQUISITE :
/////////////////////////////////////////////////////////////////////////////////////

void init_permu(sgraph *g){
  int i;

  if (g->permu!=NULL) free(g->permu);

  if( (g->permu=(int *)malloc(g->n*sizeof(int))) == NULL )
    report_error("init_permu_pos: malloc() error");
//  if( (g->pos=(int *)malloc(g->n*sizeof(int))) == NULL )
//    report_error("init_permu_pos: malloc() error");

  for (i=0;i<g->n;i++) g->permu[i]=i;
//  for (i=0;i<g->n;i++) g->pos[i]=i;

}




/* Graph reordering */

/////////////// LOAD A SEMI-GRAPH FROMA FILE ////////////////////
// IN  : the file containing the semi-adjacency lists of the graph
// OUT : 
// RETURN : a pointer to the sgraph
//----------------------------------------------------------------------
// PREREQUISITE : g->permu is affected
/////////////////////////////////////////////////////////////////////////////////////

//void reorder_sgraph(sgraph *g, int *permu, int *pos) {
void reorder_sgraph(sgraph *g, const int * permu_new) {
  int i,j;
  int * pos_new_by_ident=NULL;  // indexed by ident
  int * pos_new=NULL;  //indexed by pos
  int * sdegrees_new=NULL;
  int ** slinks_new=NULL;

  if ((g->scapacities)!=NULL) free(g->scapacities);  // to save space, in case: capacities are not supposed to be allocated and we don't need them

  if( (pos_new_by_ident=(int *)malloc(g->n*sizeof(int))) == NULL )
    report_error("reorder_sgraph: malloc() error");

  if( (pos_new=(int *)malloc(g->n*sizeof(int))) == NULL )
    report_error("reorder_sgraph: malloc() error");

  for (i=0;i<g->n;i++) pos_new_by_ident[i]=-1;
  for (i=0;i<g->n;i++) {
    if (pos_new_by_ident[permu_new[i]]!=-1) report_error("reorder_sgraph: error in affectation of pos_new_by_ident, write twice in the same cell");
    else pos_new_by_ident[permu_new[i]]=i;
  }

//  for (i=0;i<g->n;i++) pos_new[i]=-1;
  for (i=0;i<g->n;i++) {
//    if (pos_new[pos_new_by_ident[g->permu[i]]]!=-1) report_error("reorder_sgraph: error in affectation of pos_new, write twice in the same cell");    else 
pos_new[i]=pos_new_by_ident[g->permu[i]];
  }

  

  // free space before allocating scapacities and sdegrees_new

  for (i=0;i<g->n;i++) g->permu[i] = permu_new[i];

  if ((pos_new_by_ident)!=NULL) free(pos_new_by_ident);


  // computes the capacities of vertices in the semi-adjacency lists with the new permu

  if( (g->scapacities=(int *)malloc(g->n*sizeof(int))) == NULL )
    report_error("reorder_sgraph: malloc() error");
  for (i=0;i<g->n;i++) g->scapacities[i]=0;

  if( (sdegrees_new=(int *)malloc(g->n*sizeof(int))) == NULL )
    report_error("reorder_sgraph: malloc() error");
  for (i=0;i<g->n;i++) sdegrees_new[i]=0;

  for (i=0;i<g->n;i++) {
    for (j=0;j<g->sdegrees[i];j++) {
      if (pos_new[i] > pos_new[g->slinks[i][j]])
        g->scapacities[pos_new[i]]++; 
      else g->scapacities[pos_new[g->slinks[i][j]]]++;
    }
  }



  // assign the correct pointers in slinks_new according to the new capacities
  if( (slinks_new=(int **)malloc(g->n*sizeof(int *))) == NULL )
    report_error("reorder_sgraph: malloc() error");
  if( (slinks_new[0]=(int *)malloc(g->m*sizeof(int))) == NULL )
    report_error("reorder_sgraph: malloc() error");

  for (i=1;i<g->n;i++) slinks_new[i]=slinks_new[i-1]+g->scapacities[i-1];
  

  // compute the new list of vertices
  for (i=0;i<g->n;i++) {
    for (j=0;j<g->sdegrees[i];j++) {
      if (pos_new[i] > pos_new[g->slinks[i][j]]) {
        if ( sdegrees_new[ pos_new[i] ] >= g->scapacities[ pos_new[i] ] ) {
          report_error("reorder_sgraph: capacity overflow");
        }
        else {
          slinks_new[ pos_new[i] ][ sdegrees_new[ pos_new[i] ] ]=pos_new[g->slinks[i][j]];
          sdegrees_new[ pos_new[i] ] += 1;
        }
      }
      if (pos_new[i] < pos_new[g->slinks[i][j]]) {
        if ( sdegrees_new[ pos_new[g->slinks[i][j]] ] >= g->scapacities[ pos_new[g->slinks[i][j]] ] )
          report_error("reorder_sgraph: capacity overflow");
        else {
          slinks_new[ pos_new[g->slinks[i][j]] ][ sdegrees_new[ pos_new[g->slinks[i][j]] ] ]=pos_new[i];
          sdegrees_new[ pos_new[g->slinks[i][j]] ] += 1;
        }
      }
    }
  }


  // final free space
  if ((g->slinks[0])!=NULL) free(g->slinks[0]);
  if ((g->slinks)!=NULL) free(g->slinks);
  g->slinks = slinks_new;

  if ((g->sdegrees)!=NULL) free(g->sdegrees);
  g->sdegrees = sdegrees_new;

  if ((g->scapacities)!=NULL) free(g->scapacities);
  g->scapacities=NULL;

  if ((pos_new)!=NULL) free(pos_new);

}





/******** GRAPH MANAGEMENT functions - end *********/