// quantum computing emulation: generate random graph
//
// Usage: graph [-h] [N [C [p1 [p2 [p3]]]]]
//
//   N = number of nodes, default = 20
//   C = max number of outgoing connections per node, default = N/10
//  p1 = Prob(connect to node 1), default = 0.20
//  p2 = Prob(connect to node 2), default = 0.15
//  p3 = Prob(connect to node 3), default = 0.10
//  -h   hubs connect to each other
//
// Nodes 1,2,3 are hubs and the C limit does not include connections to them
//
// output format: number_of_nodes node_1_to_list... 0 ... node_N_to_list... 0
//
// R. Perry, August 2019
//
#include <stdio.h>
#include <stdlib.h>
#include "qce.h"

// put array into random order
//
void shuffle( unsigned int a[], unsigned int n)
{
  unsigned int t, i;

  while( n > 1)
  {
    i = rand() % n;  // random position 0 ... n-1
    --n;
    t = a[i]; a[i] = a[n]; a[n] = t; // swap a[i] and a[n]
  }
}

int main( int argc, char *argv[])
{
  unsigned int i, j, node, h = 0, seed = SRAND();

 // options
 //
  if( argc > 1 && argv[1][0] == '-')
  {
    for( int i = 1; argv[1][i]; ++i) switch( argv[1][i])
    {
      case 'h': h = 1; break;
      default: error( "graph: bad option");
    }
    --argc, ++argv;
  }

  unsigned int N = 20;    if( argc > 1) N =  atoi( argv[1]);
  unsigned int C = N/10;  if( argc > 2) C =  atoi( argv[2]);

  double p[3] = { 0.20, 0.15, 0.10 };

  if( argc > 3) p[0] = atof( argv[3]);
  if( argc > 4) p[1] = atof( argv[4]);
  if( argc > 5) p[2] = atof( argv[5]);

  if( N < 4) error( "N >= 4 required");

  if( C > N-4) error( "C <= N-4 required");

  for( j = 0; j < 3; ++j) if( p[j] < 0 || p[j] > 1) error("0 <= p <= 1 required");

 // create list of node destinations, 4...N
 //
  unsigned int N3 = N-3, *D = emalloc( N3*sizeof(unsigned int));

  for( i = 0; i < N3; ++i) D[i] = i+4;

  // for( i = 0; i < N3; ++i) { printf( " %u", D[i]); } putchar('\n');

  printf( "%u\n", N);

 // for each node print destination links
 //
  for( node = 1; node <= N; ++node)
  {
    switch( node) // if h then hubs connect to each other
    {
      case 1: if( h) { printf( "2 3 "); } break;
      case 2: if( h) { printf( "1 3 "); } break;
      case 3: if( h) { printf( "1 2 "); } break;
      default: // other nodes may connect to each hub
	for( j = 0; j < 3; ++j) if( DRAND < p[j]) printf( "%u ", j+1);
	break;
    }

   // c random connectons, 0 <= c <= C, with no connections to self
   //
    unsigned int c = IRAND(C+1); shuffle( D, N3);

    for( i = j = 0; i < c; ++j) if( D[j] != node) { printf( "%u ", D[j]); ++i; }

    printf( "0\n");
  }

  printf( "\ngraph: seed = %u, h = %u, N = %u, C = %u, p1 = %g, p2 = %g, p3 = %g\n",
    seed, h, N, C, p[0], p[1], p[2]);
}