isisd/topology/sprand.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #include <values.h>
   5
   6 #include "random.c"
   7
   8 #define DASH '-'
   9 #define VERY_FAR 100000000
  10
  11 /* generator of random networks for the shortest paths problem;
  12    extended DIMACS format for output */
  13
  14 main ( argc, argv )
  15
  16 int argc;
  17 char* argv[];
  18
  19 {
  20
  21 char   args[30];
  22
  23 long   n,
  24        n0,
  25        source,
  26        i,
  27        i0,
  28        j,
  29        dij;
  30
  31 long   m,
  32        m0,
  33        mc,
  34        k;
  35
  36 long   *p,
  37        p_t,
  38        l,
  39        lx;
  40
  41 long   seed,
  42        seed1,
  43        seed2;
  44
  45 int    ext=0;
  46
  47 FILE   *fout;
  48
  49 /* variables for lengths generating */
  50 /* initialized by default values */
  51 int    l_f = 0, ll_f = 0, lm_f = 0, ln_f = 0, ls_f = 0;
  52 long   ll = 10000,    /* length of the interval */
  53        lm = 0;        /* minimal bound of the interval */
  54 double ln = 0,        /* l += ln * |i-j| */
  55        ls = 0;        /* l += ls * |i-j|^2 */
  56
  57 /* variables for connecting cycle(s) */
  58 int    c_f = 0, cl_f = 0, ch_f = 0, c_random = 1;
  59 long   cl = 1;        /* length of cycle arc */
  60 long   ch;            /* number of arcs in the cycle
  61                          n - by default */
  62
  63 /* variables for artifical source */
  64 int    s_f = 0, sl_f = 0, sm_f = 0;
  65 long   sl   = VERY_FAR, /* upper bound of artifical arc */
  66        sm,              /* lower bound of artifical arc */
  67        s;
  68
  69 /* variables for potentials */
  70 int    p_f = 0, pl_f = 0, pm_f = 0, pn_f = 0, ps_f = 0,
  71        pa_f = 0, pap_f = 0, pac_f = 0;
  72 long   pl,            /* length of the interval */
  73        pm;            /* minimal bound of the interval */
  74 double pn = 0,        /* l += ln * |i-j| */
  75        ps = 0,        /* l += ls * |i-j|^2 */
  76        pap = 0,       /* part of nodes with alternative dustribution */
  77        pac = -1;      /* multiplier for alternative distribution */
  78
  79 int np;               /* number of parameter parsing now */
  80
  81 #define PRINT_ARC( i, j, length )\
  82 {\
  83 l = length;\
  84 if ( p_f ) l += ( p[i] - p[j] );\
  85 printf ("a %8ld %8ld %12ld\n", i, j, l );\
  86 }
  87
  88   /* parsing  parameters */
  89
  90 if ( argc < 2 ) goto usage;
  91
  92 np = 0;
  93
  94 strcpy ( args, argv[1] );
  95
  96   if ( ( args[0] == DASH ) && ( args[1] == 'h')
  97      )
  98       goto help;
  99
 100 if ( argc < 4 ) goto usage;
 101
 102 /* first parameter - number of nodes */
 103 np = 1;
 104 if ( ( n = atoi ( argv[1] ) )  <  2  )  goto usage;
 105
 106 /* second parameter - number of arcs */
 107 np = 2;
 108 if ( ( m = atoi ( argv[2] ) )  <  n  )  goto usage;
 109
 110 /* third parameter - seed */
 111 np=3;
 112 if ( ( seed = atoi ( argv[3] ) )  <=  0  )  goto usage;
 113
 114 /* other parameters */
 115
 116 for ( np = 4; np < argc; np ++ )
 117   {
 118     strcpy ( args, argv[np] );
 119     if ( args[0] != DASH ) goto usage;
 120
 121     switch ( args[1] )
 122       {
 123
 124       case 'l' : /* an interval for arc length */
 125         l_f = 1;
 126         switch ( args[2] )
 127           {
 128           case 'l': /* length of the interval */
 129             ll_f = 1;
 130             ll  =  (long) atof ( &args[3] );
 131             break;
 132           case 'm': /* minimal bound */
 133             lm_f = 1;
 134             lm  = (long ) atof ( &args[3] );
 135             break;
 136           case 'n': /* additional length: l*|i-j| */
 137             ln_f = 1;
 138             ln  = atof ( &args[3] );
 139             break;
 140           case 's': /* additional length: l*|i-j|^2 */
 141             ls_f = 1;
 142             ls  = atof ( &args[3] );
 143             break;
 144           default:  /* unknown switch  value */
 145             goto usage;
 146           }
 147         break;
 148
 149       case 'c' : /* connecting cycle(s) */
 150         c_f = 1;
 151         switch ( args[2] )
 152           {
 153           case 'l':
 154             c_random = 0;
 155             cl_f = 1;
 156             cl  =  (long) atof ( &args[3] );
 157             if ( cl < 0 ) goto usage;
 158             break;
 159           case 'h':
 160             ch_f = 1;
 161             ch  =  (long) atof ( &args[3] );
 162             if ( ch < 2 || ch > n ) goto usage;
 163             break;
 164           default:  /* unknown switch  value */
 165             goto usage;
 166           }
 167         break;
 168
 169       case 's' : /* additional source */
 170         s_f = 1;
 171         if ( strlen ( args ) > 2 )
 172         {
 173         switch ( args[2] )
 174           {
 175           case 'l': /* upper bound of art. arc */
 176             sl_f = 1;
 177             sl  =  (long) atof ( &args[3] );
 178             break;
 179           case 'm': /* lower bound of art. arc */
 180             sm_f = 1;
 181             sm  =  (long) atof ( &args[3] );
 182             break;
 183           default:  /* unknown switch  value */
 184             goto usage;
 185           }
 186          }
 187         break;
 188
 189       case 'p' : /* potentials */
 190         p_f = 1;
 191         if ( strlen ( args ) > 2 )
 192         {
 193         switch ( args[2] )
 194           {
 195           case 'l': /* length of the interval */
 196             pl_f = 1;
 197             pl  =  (long) atof ( &args[3] );
 198             break;
 199           case 'm': /* minimal bound */
 200             pm_f = 1;
 201             pm  = (long ) atof ( &args[3] );
 202             break;
 203           case 'n': /* additional length: l*|i-j| */
 204             pn_f = 1;
 205             pn  = atof ( &args[3] );
 206             break;
 207           case 's': /* additional length: l*|i-j|^2 */
 208             ps_f = 1;
 209             ps  = atof ( &args[3] );
 210             break;
 211           case 'a': /* bipolar distribution */
 212             pa_f = 1;
 213             switch ( args[3] )
 214               {
 215               case 'p': /* % of alternative potentials */
 216                 pap_f = 1;
 217                 pap  = atof ( &args[4] );
 218                 if ( pap < 0   ) pap = 0;
 219                 if ( pap > 100 ) pap = 100;
 220                 pap /= 100;
 221                 break;
 222               case 'c': /* multiplier */
 223                 pac_f = 1;
 224                 pac = atof ( &args[4] );
 225                 break;
 226               default: /* unknown switch value */
 227                 goto usage;
 228               }
 229             break;
 230           default:  /* unknown switch  value */
 231             goto usage;
 232           }
 233       }
 234         break;
 235
 236       default  : /* unknoun case */
 237         goto usage;
 238       }
 239   }
 240
 241
 242 /* ----- ajusting parameters ----- */
 243
 244 n0 = n; m0 = m;
 245
 246 /* length parameters */
 247 if ( ll < lm ) { lx = ll; ll = lm; lm = lx; }
 248
 249 /* potential parameters */
 250 if ( p_f )
 251   {
 252    if ( ! pl_f ) pl = ll;
 253    if ( ! pm_f ) pm = lm;
 254    if ( pl < pm ) { lx = pl; pl = pm; pm = lx; }
 255   }
 256
 257 /* path(s) parameters */
 258 if ( ! ch_f ) ch = n;
 259
 260 mc = n + (n-2) / (ch-1);
 261 if ( mc > m )
 262   { fprintf ( stderr,
 263               "Error: not enough arcs for generating connecting cycle(s)\n" );
 264     exit (4);
 265   }
 266
 267  /* artifical source parameters */
 268 if ( s_f )
 269    { m0 += n; n0 ++ ;
 270      if ( ! sm_f ) sm = sl;
 271      if ( sl < sm ) { lx = sl; sl = sm; sm = lx; }
 272    }
 273
 274 /* printing title */
 275 printf ("c random network for shortest paths problem\n");
 276 printf ("c extended DIMACS format\nc\n" );
 277
 278 /* name of the problem */
 279 printf ("t rd_%ld_%ld_%ld_", n, m, seed );
 280 if ( l_f )
 281   printf ("%c", 'l');
 282 if ( c_f )
 283   printf ("%c", 'c');
 284 if ( s_f )
 285   printf ("%c", 's');
 286 if ( p_f )
 287   printf ("%c", 'p');
 288 printf ("\nc\n");
 289
 290 /* printing additional information  */
 291 if ( l_f )
 292   printf ("c length -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
 293            lm, ll, ln, ls );
 294 if ( c_f )
 295   {
 296     if ( c_random )
 297       printf ("c cycle -> number of arcs: %ld  arc length: random\n", ch);
 298     else
 299       printf ("c cycle -> number of arcs: %ld  arc length: %ld\n",
 300                ch, cl );
 301   }
 302 if ( s_f )
 303   printf ("c length of arcs from artifical source -> min: %ld max: %ld\n",
 304            sm, sl );
 305 if ( p_f )
 306   {
 307   printf ("c potentials -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
 308           pm, pl, pn, ps );
 309   if ( pa_f )
 310   printf ("c potentials -> part of alternative distribution: %.2f k: %.2f\n",
 311           pap, pac );
 312   }
 313 printf ("c\n" );
 314
 315
 316 printf ("p sp %8ld %8ld\nc\n", n0, m0 );
 317
 318 source = ( s_f ) ? n0 : 1;
 319 printf ("n %8ld\nc\n", source );
 320
 321 if ( p_f ) /* generating potentials */
 322   {
 323     p = (long*) calloc ( n+2, sizeof (long) );
 324     seed1 = 2*seed + 1;
 325     init_rand ( seed1);
 326     pl = pl - pm + 1;
 327
 328     for ( i = 0; i <= n; i ++ )
 329       {
 330         p_t = pm + nrand ( pl );
 331         if ( pn_f ) p_t += (long) ( i * pn );
 332         if ( ps_f ) p_t += (long) ( i * ( i * ps ));
 333         if ( pap_f )
 334             if ( rand01() < pap )
 335                 p_t = (long) ( p_t * pac );
 336         p[i] = p_t;
 337       }
 338     p[n+1] = 0;
 339   }
 340
 341
 342 if ( s_f ) /* additional arcs from artifical source */
 343   {
 344     seed2 = 3*seed + 1;
 345     init_rand ( seed2 );
 346     sl = sl - sm + 1;
 347
 348     for ( i = n; i > 1; i -- )
 349       {
 350         s = sm + nrand ( sl );
 351         PRINT_ARC ( n0, i, s )
 352       }
 353
 354     PRINT_ARC ( n0, 1, 0 )
 355   }
 356
 357 /* initialize random number generator */
 358 init_rand ( seed );
 359 ll = ll - lm + 1;
 360
 361 /* generating connecting cycle(s) */
 362 if (c_random)
 363   cl = lm + nrand ( ll );
 364 PRINT_ARC ( 1, 2, cl )
 365 if (c_random)
 366   cl = lm + nrand ( ll );
 367 PRINT_ARC ( n, 1, cl )
 368
 369 for ( i = 2; i < n; i ++ )
 370   {
 371     if (c_random)
 372       cl = lm + nrand ( ll );
 373
 374     if ( ( (i-1) % (ch-1) ) != 0 )
 375         PRINT_ARC ( i, i+1, cl )
 376     else
 377       { PRINT_ARC ( i,   1, cl )
 378         if (c_random)
 379           cl = lm + nrand ( ll );
 380         PRINT_ARC ( 1, i+1, cl )
 381       }
 382   }
 383
 384 /* generating random arcs */
 385
 386 for ( k = 1; k <= m - mc; k ++ )
 387   {
 388     i = 1 + nrand ( n );
 389
 390     do
 391     j = 1 + nrand ( n );
 392     while ( j == i );
 393
 394     dij = ( i > j ) ? ( i - j ) : ( j - i );
 395     l = lm + nrand ( ll );
 396     if ( ln_f ) l += (long) ( dij * ln );
 397     if ( ls_f ) l += (long) ( dij * ( dij * ls ) );
 398     PRINT_ARC ( i, j, l );
 399   }
 400
 401 /* all is done */
 402 exit (ext);
 403
 404 /* ----- wrong usage ----- */
 405
 406  usage:
 407 fprintf ( stderr,
 408 "\nusage: %s  n  m  seed  [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
 409 help:  %s -h\n\n", argv[0], argv[0] );
 410
 411 if ( np > 0 )
 412   fprintf ( stderr, "error in parameter # %d\n\n", np );
 413 exit (4);
 414
 415 /* ---- help ---- */
 416
 417  help:
 418
 419 if ( args[2] == 'h') goto hhelp;
 420
 421 fprintf ( stderr,
 422 "\n'%s' - random network generator for shortest paths problem.\n\
 423 Generates problems in extended DIMACS format.\n\
 424 \n\
 425    %s  n m seed [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
 426    %s -hh\n\
 427 \n\
 428                         #i - integer number   #f - real number\n\
 429 \n\
 430 -ll#i  - #i is the upper bound on arc lengths          (default 10000)\n\
 431 -lm#i  - #i is the lower bound on arc lengths          (default 0)\n\
 432 -cl#i  - #i is length of arcs in connecting cycle(s)   (default random)\n\
 433 -p     - generate potentials \n\
 434 -pl#i  - #i is the upper bound on potentials           (default ll)\n\
 435 -pm#i  - #i is the lower bound on potentials           (default lm)\n\
 436 \n\
 437 -hh    - extended help \n\n",
 438 argv[0], argv[0], argv[0] );
 439
 440 exit (0);
 441
 442 /* --------- sophisticated help ------------ */
 443  hhelp:
 444
 445 if ( argc < 3 )
 446      fout = stderr;
 447 else
 448      fout = fopen ( argv[2], "w" );
 449
 450 if ( fout == NULL )
 451 { fprintf ( stderr, "\nCan't open file  '%s' for writing help\n\n", argv[2] );
 452   exit ( 2 );
 453 }
 454
 455 fprintf (fout,
 456 "\n'%s' - random network generator for shortest paths problem.\n\
 457 Generates problems in extended DIMACS format.\n\
 458 \n\
 459    %s  n m seed [ -ll#i -lm#i -ln#f -ls#f\n\
 460                       -p  -pl#i -pm#i -pn#f -ps#f -pap#i -pac#f\n\
 461                       -cl#i -ch#i\n\
 462                       -s -sl#i -sm#i\n\
 463                     ]\n\
 464    %s -hh file_name\n\
 465 \n\
 466                         #i - integer number   #f - real number\n\
 467 \n\
 468       Arc length parameters:\n\
 469 -ll#i  - #i is the upper bound on arc lengths          (default 10000)\n\
 470 -lm#i  - #i is the lower bound on arc lengths          (default 0)\n\
 471 -ln#f  - multipliy l(i, j) by #f * |i-j|               (default 0)\n\
 472 -ls#f  - multipliy l(i, j) by #f * |i-j|^2             (default 0)\n\
 473 \n\
 474       Potential parameters:\n\
 475 -p     - generate potentials \n\
 476 -pl#i  - #i is the upper bound on potentials           (default ll)\n\
 477 -pm#i  - #i is the lower bound on potentials           (default lm)\n\
 478 -pn#f  - multiply p(i) by #f * i                       (default 0)\n\
 479 -ps#f  - multiply p(i) by #f * i^2                     (default 0)\n\
 480 -pap#i - percentage of alternative potential nodes     (default 0)\n\
 481 -pac#f - if i is alternative, multiply  p(i) by #f     (default -1)\n\
 482 \n\
 483       Connecting cycle(s) parameters:\n\
 484 -cl#i  - #i is length of arcs in connecting cycle(s)   (default random)\n\
 485 -ch#i  - #i is length of connecting cycles             (default n)\n\
 486 \n\
 487       Artificial source parameters:\n\
 488 -s     - generate artificial source with default connecting arc lengths\n\
 489 -sl#i  - #i is the upper bound on art. arc lengths    (default 100000000)\n\
 490 -sm#i  - #i is the lower bound on art. arc lengths    (default sl)\n\
 491 \n\
 492 -hh file_name  - save this help in the file 'file_name'\n\n",
 493 argv[0], argv[0], argv[0] );
 494
 495 exit (0);
 496 }
 497
 498
 499