isisd/topology/spacyc.c

   1 #include <zebra.h>
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <values.h>
   6
   7 #include "random.c"
   8
   9 #define DASH '-'
  10 #define VERY_FAR 100000000
  11
  12
  13 /* generator of acyclic 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,    /* upper bound of the interval */
  55        lm = 0;        /* lower 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 path(s) */
  60 int    c_f = 0, cl_f = 0, ch_f = 0, c_rand = 1;
  61 long   cl = 1;        /* length of path arc */
  62 long   ch;            /* number of arcs in the path
  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,            /* upper bound of the interval */
  75        pm;            /* lower 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 path(s) */
 152         c_f = 1;
 153         switch ( args[2] )
 154           {
 155           case 'l': /* length of path arc */
 156             c_rand = 0; /* fixed arc length */
 157             cl_f = 1;
 158             cl  =  (long) atof ( &args[3] );
 159             break;
 160           case 'h': /* number of arcs in connecting path */
 161             ch_f = 1;
 162             ch  =  (long) atof ( &args[3] );
 163             if ( ch < 1 || ch > n ) goto usage;
 164             break;
 165           default:  /* unknown switch  value */
 166             goto usage;
 167           }
 168         break;
 169
 170       case 's' : /* additional source */
 171         s_f = 1;
 172         if ( strlen ( args ) > 2 )
 173         {
 174         switch ( args[2] )
 175           {
 176           case 'l': /* upper bound of art. arc */
 177             sl_f = 1;
 178             sl  =  (long) atof ( &args[3] );
 179             break;
 180           case 'm': /* lower bound of art. arc */
 181             sm_f = 1;
 182             sm  =  (long) atof ( &args[3] );
 183             break;
 184           default:  /* unknown switch  value */
 185             goto usage;
 186           }
 187          }
 188         break;
 189
 190       case 'p' : /* potentials */
 191         p_f = 1;
 192         if ( strlen ( args ) > 2 )
 193         {
 194         switch ( args[2] )
 195           {
 196           case 'l': /* length of the interval */
 197             pl_f = 1;
 198             pl  =  (long) atof ( &args[3] );
 199             break;
 200           case 'm': /* minimal bound */
 201             pm_f = 1;
 202             pm  = (long ) atof ( &args[3] );
 203             break;
 204           case 'n': /* additional length: l*|i-j| */
 205             pn_f = 1;
 206             pn  = atof ( &args[3] );
 207             break;
 208           case 's': /* additional length: l*|i-j|^2 */
 209             ps_f = 1;
 210             ps  = atof ( &args[3] );
 211             break;
 212           case 'a': /* bipolar distribution */
 213             pa_f = 1;
 214             switch ( args[3] )
 215               {
 216               case 'p': /* % of alternative potentials */
 217                 pap_f = 1;
 218                 pap  = atof ( &args[4] );
 219                 if ( pap < 0   ) pap = 0;
 220                 if ( pap > 100 ) pap = 100;
 221                 pap /= 100;
 222                 break;
 223               case 'c': /* multiplier */
 224                 pac_f = 1;
 225                 pac = atof ( &args[4] );
 226                 break;
 227               default: /* unknown switch value */
 228                 goto usage;
 229               }
 230             break;
 231           default:  /* unknown switch  value */
 232             goto usage;
 233           }
 234       }
 235         break;
 236
 237       default  : /* unknoun case */
 238         goto usage;
 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 - 1;
 259 mc = n - 1;
 260
 261  /* artifical source parameters */
 262 if ( s_f )
 263    { m0 += n; n0 ++ ;
 264      if ( ! sm_f ) sm = sl;
 265      if ( sl < sm ) { lx = sl; sl = sm; sm = lx; }
 266    }
 267
 268 /*----- printing title -----*/
 269
 270 printf ("c acyclic network for shortest paths problem\n");
 271 printf ("c extended DIMACS format\nc\n" );
 272
 273
 274 /* name of the problem */
 275 printf ("t ac_%ld_%ld_%ld_", n, m, seed );
 276 if ( l_f )
 277   printf ("%c", 'l');
 278 if ( c_f )
 279   printf ("%c", 'c');
 280 if ( s_f )
 281   printf ("%c", 's');
 282 if ( p_f )
 283   printf ("%c", 'p');
 284 printf ("\nc\n");
 285
 286 /* printing additional information  */
 287 if ( l_f )
 288   printf ("c length -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
 289            lm, ll, ln, ls );
 290 if ( c_f )
 291   printf ("c path(s) -> number of arcs: %ld arc length: %ld\n",
 292            ch, cl );
 293 if ( s_f )
 294   printf ("c length of arcs from artifical source -> min: %ld max: %ld\n",
 295            sm, sl );
 296 if ( p_f )
 297   {
 298   printf ("c potentials -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
 299           pm, pl, pn, ps );
 300   if ( pa_f )
 301   printf ("c potentials -> part of alternative distribution: %.2f k: %.2f\n",
 302           pap, pac );
 303   }
 304 printf ("c\n" );
 305
 306 printf ("p sp %8ld %8ld\nc\n", n0, m0 );
 307
 308 source = ( s_f ) ? n0 : 1;
 309 printf ("n %8ld\nc\n", source );
 310
 311
 312 if ( p_f ) /* generating potentials */
 313   {
 314     seed1 = 2*seed + 1;
 315     p = (long*) calloc ( n+2, sizeof (long) );
 316     init_rand ( seed1);
 317     pl = pl - pm + 1;
 318
 319     for ( i = 0; i <= n; i ++ )
 320       {
 321         p_t = pm + nrand ( pl );
 322         if ( pn_f ) p_t += (long) ( i * pn );
 323         if ( ps_f ) p_t += (long) ( i * ( i * ps ));
 324         if ( pap_f )
 325             if ( rand01() < pap )
 326                 p_t = (long) ( p_t * pac );
 327         p[i] = p_t;
 328       }
 329     p[n+1] = 0;
 330   }
 331
 332
 333 if ( s_f ) /* additional arcs from artifical source */
 334   {
 335     seed2 = 3*seed + 1;
 336     init_rand ( seed2 );
 337     sl = sl - sm + 1;
 338
 339     for ( i = n; i > 1; i -- )
 340       {
 341         s = sm + nrand ( sl );
 342         PRINT_ARC ( n0, i, s )
 343       }
 344
 345     PRINT_ARC ( n0, 1, 0 )
 346   }
 347
 348 /* initialize random number generator */
 349 init_rand ( seed );
 350 ll = ll - lm + 1;
 351
 352 /* generating connecting path(s) */
 353 for ( i = 1; i < n; i ++ )
 354   {
 355     if ( ( (i-1) % ch ) != 0 )
 356       i0 = i;
 357     else
 358       i0 = 1;
 359
 360       if (c_rand)
 361         cl = lm + nrand(ll);
 362       PRINT_ARC ( i0, i+1, cl )
 363   }
 364
 365 /* generating random arcs */
 366
 367
 368 for ( k = 1; k <= m - mc; k ++ )
 369   {
 370     i = 1 + nrand ( n );
 371
 372     do
 373     j = 1 + nrand ( n );
 374     while ( j == i );
 375
 376     if ( i > j )
 377       { i0 = i; i = j; j = i0; }
 378
 379     dij = j - i;
 380     l = lm + nrand ( ll );
 381     if ( ln_f ) l += (long) ( dij * ln );
 382     if ( ls_f ) l += (long) ( dij * ( dij * ls ) );
 383     PRINT_ARC ( i, j, l );
 384   }
 385
 386 /* all is done */
 387 exit (ext);
 388
 389 /* ----- wrong usage ----- */
 390
 391  usage:
 392 fprintf ( stderr,
 393 "\nusage: %s  n  m  seed  [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
 394 help:  %s -h\n\n", argv[0], argv[0] );
 395
 396 if ( np > 0 )
 397   fprintf ( stderr, "error in parameter # %d\n\n", np );
 398 exit (4);
 399
 400 /* ---- help ---- */
 401
 402  help:
 403
 404 if ( args[2] == 'h') goto hhelp;
 405
 406 fprintf ( stderr,
 407 "\n'%s' - acyclic network generator for shortest paths problem.\n\
 408 Generates problems in extended DIMACS format.\n\
 409 \n\
 410    %s  n m seed [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
 411    %s -hh\n\
 412 \n\
 413                         #i - integer number   #f - real number\n\
 414 \n\
 415 -ll#i  - #i is the upper bound on arc lengths          (default 10000)\n\
 416 -lm#i  - #i is the lower bound on arc lengths          (default 0)\n\
 417 -cl#i  - #i is length of arcs in connecting path(s)    (default random)\n\
 418 -p     - generate potentials \n\
 419 -pl#i  - #i is the upper bound on potentials           (default ll)\n\
 420 -pm#i  - #i is the lower bound on potentials           (default lm)\n\
 421 \n\
 422 -hh    - extended help \n\n",
 423 argv[0], argv[0], argv[0] );
 424
 425 exit (0);
 426
 427 /* --------- sophisticated help ------------ */
 428  hhelp:
 429
 430 if ( argc < 3 )
 431      fout = stderr;
 432 else
 433      fout = fopen ( argv[2], "w" );
 434
 435 if ( fout == NULL )
 436 { fprintf ( stderr, "\nCan't open file  '%s' for writing help\n\n", argv[2] );
 437   exit ( 2 );
 438 }
 439
 440 fprintf (fout,
 441 "\n'%s' - acyclic network generator for shortest paths problem.\n\
 442 Generates problems in extended DIMACS format.\n\
 443 \n\
 444    %s  n m seed [ -ll#i -lm#i -ln#f -ls#f\n\
 445                       -p  -pl#i -pm#i -pn#f -ps#f -pap#i -pac#f\n\
 446                       -cl#i -ch#i\n\
 447                       -s  -sl#i -sm#i\n\
 448                     ]\n\
 449    %s -hh file_name\n\
 450 \n\
 451                         #i - integer number   #f - real number\n\
 452 \n\
 453       Arc length parameters:\n\
 454 -ll#i  - #i is the upper bound on arc lengths          (default 10000)\n\
 455 -lm#i  - #i is the lower bound on arc lengths          (default 0)\n\
 456 -ln#f  - multipliy l(i, j) by #f * |i-j|               (default 0)\n\
 457 -ls#f  - multipliy l(i, j) by #f * |i-j|^2             (default 0)\n\
 458 \n\
 459       Potential parameters:\n\
 460 -p     - generate potentials \n\
 461 -pl#i  - #i is the upper bound on potentials           (default ll)\n\
 462 -pm#i  - #i is the lower bound on potentials           (default lm)\n\
 463 -pn#f  - multiply p(i) by #f * i                       (default 0)\n\
 464 -ps#f  - multiply p(i) by #f * i^2                     (default 0)\n\
 465 -pap#i - percentage of alternative potential nodes     (default 0)\n\
 466 -pac#f - if i is alternative, multiply  p(i) by #f     (default -1)\n\
 467 \n\
 468       Connecting path(s) parameters:\n\
 469 -cl#i  - #i is length of arcs in connecting path(s)   (default random)\n\
 470 -ch#i  - #i is length of connecting path(s)           (default n-1)\n\
 471 \n\
 472       Artificial source parameters:\n\
 473 -s     - generate artificial source with default connecting arc lengths\n\
 474 -sl#i  - #i is the upper bound on art. arc lengths    (default 100000000)\n\
 475 -sm#i  - #i is the lower bound on art. arc lengths    (default sl)\n\
 476 \n\
 477 -hh file_name  - save this help in the file 'file_name'\n\n",
 478 argv[0], argv[0], argv[0] );
 479
 480 exit (0);
 481 }
 482
 483
 484