/**
 *  This program is free software: you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see
 *  <http://www.gnu.org/licenses/>.
 *
 *  (c) Vincenzo Nicosia 2009-2017 -- <v.nicosia@qmul.ac.uk>
 * 
 *  This file is part of NetBunch, a package for complex network
 *  analysis and modelling. For more information please visit:
 *
 *             http://www.complex-networks.net/
 *
 *  If you use this software, please add a reference to 
 *
 *               V. Latora, V. Nicosia, G. Russo             
 *   "Complex Networks: Principles, Methods and Applications"
 *              Cambridge University Press (2017) 
 *                ISBN: 9781107103184
 *
 ***********************************************************************
 *
 *  This program implements the fitness model proposed by Bianconi and
 *  Barabasi, where the attachment probability is:
 *
 *     \Pi_{i->j} \propto a_j * k_j 
 *
 *  where a_j is the actractiveness of node j. 
 *
 *
 *  References:
 *  
 * [1] G. Bianconi, A.-L. Barabasi, " Competition and multiscaling in
 *     evolving networks". EPL-Europhys. Lett. 54 (2001), 436.
 *
 */


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "utils.h"
#include "cum_distr.h"


void usage(char *argv[]){
  printf("********************************************************************\n"
         "**                                                                **\n"
         "**                        -*- bb_fitness -*-                      **\n"
         "**                                                                **\n"
         "**   Grow a network of 'N' nodes using the fitness model proposed **\n"
         "**   by Bianconi and Barabasi.                                    **\n"
         "**                                                                **\n"
         "**   The initial network is a clique of 'n0' nodes, and each new  **\n"
         "**   node creates 'm' edges. The attachment probability is of     **\n"
         "**   the form:                                                    **\n"
         "**                                                                **\n"
         "**            P(i->j) ~ a_j * k_j                                 **\n"
         "**                                                                **\n"
         "**   where a_j is the attractiveness of node j. The values of     **\n"
         "**   node attractiveness are sampled uniformly at random in       **\n"
         "**   [0,1].                                                       **\n"
         "**                                                                **\n"
         "**   The program prints on STDOUT the edge-list of the final      **\n"
         "**   graph.                                                       **\n"
         "**                                                                **\n"
         "**   If 'FIT' is specified as a fourth parameter, the values      **\n"
         "**   of node attractiveness are printed on STDERR.                **\n"
         "**                                                                **\n"
         "********************************************************************\n"
         " This is Free Software - You can use and distribute it under \n"
         " the terms of the GNU General Public License, version 3 or later\n\n"
         " (c) Vincenzo Nicosia 2009-2017 (v.nicosia@qmul.ac.uk)\n\n"
         "********************************************************************\n\n"
         );
  printf("Usage: %s <N> <m> <n0> [SHOW]\n", argv[0]);
}




int init_network(unsigned int *I, unsigned int *J, int n0, 
                 double *a, cum_distr_t *d){
  
  unsigned int n, i,  S_num;
  
  
  S_num = 0;
  for(n=0; n<n0; n++){
    for(i=n+1; i<n0; i++){
      I[S_num] = n;
      J[S_num] = i % n0;
      S_num += 1;
    }
    cum_distr_add(d, n, n0*a[n]);
  }
  return S_num;
}

int already_neighbour(unsigned int *J, int S_num, int j, int dest){

   int i;

   for(i=S_num; i< S_num + j; i ++){
     if (J[i] == dest)
       return 1;
   }
   return 0;
}



int bb_fitness(unsigned int *I, unsigned int *J, unsigned int N, 
               unsigned int m, unsigned int n0,  double* a){
  
  cum_distr_t *d = NULL;
  unsigned int n, j, dest, S_num;
  
  d = cum_distr_init(N * m);
  
  S_num = init_network(I, J, n0, a, d);
  
  
  n = n0;
  while (n<N){
    for(j=0; j<m; j++){
      I[S_num+j] = n;
      dest = cum_distr_sample(d);
      while(already_neighbour(J, S_num, j, dest)){
        dest = cum_distr_sample(d);
      }
      J[S_num + j] = dest;
    }
    cum_distr_add(d, n, m*a[n]);
    for (j=0; j<m; j++){
      cum_distr_add(d, J[S_num + j], a[ J[S_num + j] ]);
    }
    S_num += m;
    n += 1;
  }
  cum_distr_destroy(d);
  return S_num;
}

void dump_graph(unsigned int *I, unsigned int *J, unsigned int K){
  
  unsigned int i;

  for(i=0; i<K; i++){
    printf("%d %d\n", J[i], I[i]);
  }
  
}


void init_fitness_uniform(double *a, unsigned int N){
  
  unsigned int i;

  for(i=0; i<N; i++){
    a[i] = 1.0 * rand() / RAND_MAX;
  }
  
}


void dump_fitness(double *a, unsigned int N){
  
  int i;

  for(i=0; i<N; i++){
    fprintf(stderr, "%g\n", a[i]);
  }
}


int main(int argc, char *argv[]){
  
  int N, m, n0, K;
  unsigned int *I, *J;
  double *a;
  
  if (argc < 4){
    usage(argv);
    exit(1);
  }
  
  N = atoi(argv[1]);
  m = atoi(argv[2]);
  n0 = atoi(argv[3]);
  
  a = malloc(N * sizeof(double));
  
  srand(time(NULL));

  if (N < 1){
    fprintf(stderr, "N must be positive\n");
    exit(1);
  }
  if(m > n0){
    fprintf(stderr, "n0 cannot be smaller than m\n");
    exit(1);

  }
  if (n0<1){
    fprintf(stderr, "n0 must be positive\n");
    exit(1);
  }
  
  if (m < 1){
    fprintf(stderr, "m must be positive\n");
    exit(1);
  }
  
  I = malloc(N * m * sizeof(unsigned int));
  J = malloc(N * m * sizeof(unsigned int));
  a = malloc(N * sizeof(double));

  init_fitness_uniform(a, N);
  
  K = bb_fitness(I, J, N, m, n0, a);
  
  dump_graph(I, J, K);
  if (argc > 4 && !my_strcasecmp(argv[4], "SHOW")){
    dump_fitness(a, N);
  }
  free(a);
  free(I);
  free(J);
  
}