/*



              +==================================+
              | Random Graph Generation Software |
              +==================================+




       This source code is (c) Copyright 2001 by Christopher R. Palmer
       and J. Gregory Steffan.  It may be freely redistributed and
       included in other packages provided this copyright notice is
       included.




   Version 1.0
       January 12, 2001 - Initial public release

   ----------------------------------------------------------------------

   Using the 'PLODD' generator:
   ====================

   This file is the entire distribution.  Compile it with your favorite
   C compiler and you can then run the program as follows:

        plodd <n> <alpha> <beta>

   where n is the number of nodes in the graph, and alpha and beta are as
   defined in the paper (cited below). Example values are  

       alpha=0.811392, beta=3

   Note that the authors did not do an extensive study on the impact of
   different values of alpha and beta.  You likely want to choose them to
   produce a desired slope for your log-log plots.

   For more information please see the paper that describes this
   graph generation algorithm.  A citation appears at the end of
   this document.

   Output format:
   ==============

   The output is an n x n adjacency matrix where a '1' indicates the 
   existence of an edge, and a '0' indicates the absence of an edge.  


     More Information / Etc:
     =======================

     The paper that describes this work is:

         Christopher R. Palmer and J. Gregory Steffan, Generating
         Network Topologies that Obey Power Laws, IEEE Globecom 2000,
         San Francisco, CA, November 2000.

         http://www.cs.cmu.edu/~crpalmer/pubs.html/globecom2000.ps

     please cite it when referring to this graph generation software.
     Further information, bug reports, etc. may be sent to:

         steffan@eecg.toronto.edu
         crpalmer@cs.cmu.edu


     ------------------------------------------------------------------

*/

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

#define MAX2(x,y)(((x) > (y)) ? (x) : (y))
#define MIN2(x,y)(((x) < (y)) ? (x) : (y))

#define TRUE 1
#define FALSE 0
typedef unsigned boolean;

double ALPHA;
double BETA;

double M;
int N;
int num_ones;

unsigned **adj;
unsigned *out_deg;

double get_rand(){
  return ((double)random())/(double)(RAND_MAX+1.0); 
}

int get_count(double m){
  return ceil(pow(ALPHA,m));
}


void compute_adjacency(){
  int i,j,k;
  int r,c;
  int v = 0;
  int inf_loop_ctr;

  boolean breakout;

  for (k=0;k<(num_ones/2);k++){
    /* get random starting position */
    r = floor(get_rand() * N);
    c = floor(get_rand() * N);
    breakout = FALSE;

    /* search until a one is placed */
    for (i=0;i<N;i++){
      for (j=0;j<N;j++){
	if ((i != j) && out_deg[i] && out_deg[j] && !adj[i][j]){
	  out_deg[i]--;
	  out_deg[j]--;
	  adj[i][j] = 1;
	  adj[j][i] = 1;
	  breakout = TRUE;
	  break;
	}
	c = (c + 1) % N;
      }
      r = (r + 1) % N;
      if (breakout)
	break;
    }
  }
}

void add_random_edges(){
  int i;
  int r,c;

  for (i=0;i<N/4;i++){
    r = floor(get_rand() * N);
    c = floor(get_rand() * N);
    
    if (r != c){
      adj[r][c] = 1;
      adj[c][r] = 1;
    }
  }
}

void init_adj(){
  int i;
  for (i=0;i<N;i++){
    adj[i] = malloc(sizeof(unsigned)*N);
    memset(adj[i],0,sizeof(unsigned)*N);
  }
}

void symmetrize_adjacency(){
  int i,j;

  for (i=0;i<N;i++){
    for (j=i;j<N;j++){
      adj[j][i] = adj[i][j];
    }
  }
}

void print_adjacency(){
  int i,j;
  for (i=0;i<N;i++){
    for (j=0;j<N;j++){
      printf("%d",adj[i][j]);
    }
    printf("\n");
  }
}

void assign_out_deg(){
  int i;
  
  for (i = 0; i < N; i++) {
    out_deg[i] = MAX2(floor(BETA*pow(get_rand()*((double)N),-ALPHA)),1.0);
  }
}

void
compute_num_ones(){
  int i;

  num_ones = 0;
  for (i=0;i<N;i++){
    num_ones += out_deg[i];
  }
}

#define SCALE 32

void
dumppgm(char *fname){
  FILE *f;
  int   i, j;
  int u,v;

  if ((f = fopen(fname, "w")) == NULL) {
    perror(fname);
    return;
  }

  fprintf(f, "P2\n%d %d\n1\n",N*SCALE,N*SCALE);

  for (i=0;i<N;i++){
    for (u=0;u<SCALE;u++){
      for (j=0;j<N;j++){
	for (v=0;v<SCALE;v++){
	  fprintf(f,"%d ",!adj[i][j]);
	}
      }
    }
    fprintf(f, "\n");
  }

  fclose(f);
}

void print_out_deg(){
  int i;

  for (i=0;i<N;i++){
    printf("%f ",out_deg[i]);
  }
  printf("\n");
}

/* randomly swap pairs of out degree counts */
void scramble_out_deg(){
  int i;
  int j;
  int tmp;
  for (i=0;i<N;i++){
    j = floor(((double)N)*get_rand());
    tmp = out_deg[i];
    out_deg[i] = out_deg[j];
    out_deg[j] = tmp;
  }
}



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

  if (argc != 4){
    fprintf(stderr, "usage: <n> <alpha> <beta>\n");
    exit(1);
  }

  srandom(time(NULL));

  N = atoi(argv[1]);

  ALPHA = strtod(argv[2],NULL);
  BETA = strtod(argv[3],NULL);

  adj = malloc(sizeof(unsigned *)*N);
  out_deg = malloc(sizeof(unsigned)*N);

  init_adj();
  assign_out_deg();

#if 0
  print_out_deg();
#endif

#if 0
  scramble_out_deg();
#endif
  
  compute_num_ones();
  compute_adjacency();

  add_random_edges();

#if 0
  symmetrize_adjacency();
#endif

  print_adjacency();

#if 0
  dumppgm("out.pgm");
#endif
}