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