isisd/topology/sprand.c

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