isisd/topology/spgrid.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #include "random.c"
   6
   7 #include <zebra.h>
   8
   9 #include "thread.h"
  10 #include "vty.h"
  11 #include "log.h"
  12 #include "linklist.h"
  13
  14 #include "spgrid.h"
  15
  16
  17 #define DASH '-'
  18 #define VERY_FAR 100000000
  19
  20 #define DOUBLE_CYCLE   0
  21 #define CYCLE          1
  22 #define PATH           2
  23
  24 #define NO             0
  25 #define YES            1
  26
  27 #define NODE( x, y ) (x*Y + y + 1)
  28
  29 const char   *graph_type[] =  {
  30   "double cycle",
  31   "cycle",
  32   "path"
  33 };
  34
  35 struct arc *arc;
  36
  37 char   args[30];
  38
  39 long   X,   /* horizontal size of grid */
  40        Y;   /* vertical size of grid */
  41
  42 long   x,
  43        y,
  44        y1, y2, yp,
  45        dl, dx, xn, yn, count,
  46        *mess;
  47
  48 double n;
  49 long   n0,
  50        source,
  51        i,
  52        i0,
  53        j,
  54        dij;
  55
  56 double m;
  57 long   m0,
  58        mc,
  59        k;
  60
  61 long   *p,
  62        p_t,
  63        l,
  64        lx;
  65
  66 long   seed,
  67        seed1,
  68        seed2;
  69
  70 int    ext=0;
  71
  72 /* initialized by default values */
  73
  74 /* variables for generating one layer */
  75
  76 /* variables for generating spanning graph */
  77 int    c_f = 0, cw_f = 0, cm_f = 0, cl_f = 0;
  78
  79 int    cw = DOUBLE_CYCLE;  /* type of spanning graph */
  80 long   cm = 0,             /* lower bound of the interval */
  81        cl = 100;           /* upper bound of the interval */
  82
  83 /* variables for generating additional arcs */
  84 int    a_f = 0, ax_f = 0, am_f = 0, al_f = 0;
  85
  86 long   ax = 0,             /* number of additional arcs */
  87        am = 0,             /* lower bound of the interval */
  88        al = 100;           /* upper bound of the interval */
  89
  90 /* variables for inter-layer arcs */
  91 int    i_f = 0, ip_f = 0, ix_f = 0, ih_f = 0,
  92        im_f = 0, il_f = 0, in_f = 0, is_f = 0;
  93
  94 int    ip = NO;       /* to mess or not to mess */
  95 long   ix = 1,        /* number of interlayered arcs in a NODE */
  96        ih = 1,        /* step between two layeres */
  97        il = 10000,    /* upper bound of the interval */
  98        im = 1000;     /* lower bound of the interval */
  99 double in = 1,        /* l *=  in * |x1-x2| */
 100        is = 0;        /* l *=  is * |x1-x2|^2 */
 101
 102 /* variables for artifical source */
 103 int    s_f = 0, sl_f = 0, sm_f = 0;
 104 long   sl   = VERY_FAR, /* upper bound of artifical arc */
 105        sm,              /* lower bound of artifical arc */
 106        s;
 107
 108 /* variables for potentials */
 109 int    p_f = 0, pl_f = 0, pm_f = 0, pn_f = 0, ps_f = 0;
 110
 111 long   pl,            /* upper bound of the interval */
 112        pm;            /* lower bound of the interval */
 113 double pn = 0,        /* p +=  ln * (x+1) */
 114        ps = 0;        /* p +=  ls * (x+1)^2 */
 115
 116 int np;               /* number of parameter parsing now */
 117
 118
 119 void
 120 free_arc   (void *val) {
 121   free(val);
 122 }
 123
 124 void
 125 print_arc (struct vty *vty, struct list *topology, long i, long j, long length)
 126 {
 127   struct arc *myarc;
 128
 129   l = length;
 130   if ( p_f ) l += ( p[i] - p[j] );
 131 //  vty_out (vty,"a %8ld %8ld %12ld%s", i, j, l ,VTY_NEWLINE);
 132   myarc = malloc (sizeof(struct arc));
 133   myarc->from_node = i;
 134   myarc->to_node = j;
 135   myarc->distance = l;
 136   topology->del = free_arc;
 137   listnode_add (topology, myarc);
 138 }
 139
 140 /* ---- help ---- */
 141 void
 142 help (struct vty *vty) {
 143 //  if ( args[2] == 'h') hhelp (vty);
 144   vty_out (vty,"grid network generator for shortest paths problem.%s",VTY_NEWLINE);
 145   vty_out (vty,"Generates problems in extended DIMACS format.%s",VTY_NEWLINE);
 146   vty_out (vty,"X Y seed [ -cl#i -cm#i -c{c|d|p} -ip -il#i -im#i -p -pl#i -pm#i... ]%s",VTY_NEWLINE);
 147   vty_out (vty,"#i - integer number%s",VTY_NEWLINE);
 148   vty_out (vty,"-cl#i - #i is the upper bound on layer arc lengths    (default 100)%s",VTY_NEWLINE);
 149   vty_out (vty,"-cm#i - #i is the lower bound on layer arc lengths    (default 0)%s",VTY_NEWLINE);
 150   vty_out (vty,"-c#t  - #t is the type of connecting graph: { c | d | p }%s",VTY_NEWLINE);
 151   vty_out (vty,"           c - cycle, d - double cycle, p - path      (default d)%s",VTY_NEWLINE);
 152   vty_out (vty,"-ip   - shuffle inter-layer arcs                     (default NO)%s",VTY_NEWLINE);
 153   vty_out (vty,"-il#i - #i is the upper bound on inter-layer arc lengths (default 10000)%s",VTY_NEWLINE);
 154   vty_out (vty,"-im#i - #i is the lower bound on inter-layer arc lengths (default 1000)%s",VTY_NEWLINE);
 155   vty_out (vty,"-p    - generate potentials%s",VTY_NEWLINE);
 156   vty_out (vty,"-pl#i - #i is the upper bound on potentials           (default il)%s",VTY_NEWLINE);
 157   vty_out (vty,"-pm#i - #i is the lower bound on potentials           (default im)%s",VTY_NEWLINE);
 158   vty_out (vty,"%s",VTY_NEWLINE);
 159   vty_out (vty,"-hh    - extended help%s",VTY_NEWLINE);
 160 }
 161
 162 /* --------- sophisticated help ------------ */
 163 void
 164 hhelp (struct vty *vty) {
 165 /*
 166 zlog_info (
 167 "\n'%s' - grid network generator for shortest paths problem.\n\
 168 Generates problems in extended DIMACS format.\n\
 169 \n\
 170    %s  X Y seed [ -cl#i -cm#i -c{c|d|p}\n\
 171                       -ax#i -al#i -am#i\n\
 172                       -ip   -il#i -im#i -in#i -is#i -ix#i -ih#i\n\
 173                       -p    -pl#i -pm#i -pn#f -ps#f\n\
 174                       -s    -sl#i -sm#i\n\
 175                     ]\n\
 176    %s -hh file_name\n\
 177 \n\
 178                         #i - integer number   #f - real number\n\
 179 \n\
 180       Parameters of connecting arcs within one layer:\n\
 181 -cl#i - #i is the upper bound on arc lengths          (default 100)\n\
 182 -cm#i - #i is the lower bound on arc lengths          (default 0)\n\
 183 -c#t  - #t is the type of connecting graph: { c | d | p }\n\
 184            c - cycle, d - double cycle, p - path      (default d)\n\
 185 \n\
 186       Parameters of additional arcs within one layer:\n\
 187 -ax#i - #i is the number of additional arcs           (default 0)\n\
 188 -al#i - #i is the upper bound on arc lengths          (default 100)\n\
 189 -am#i - #i is the lower bound on arc lengths          (default 0)\n\
 190 \n\
 191       Interlayerd arc parameters:\n\
 192 -ip    - shuffle inter-layer arcs                         (default NO)\n\
 193 -il#i  - #i is the upper bound on arc lengths          (default 10000)\n\
 194 -im#i  - #i is the lower bound on arc lengths          (default 1000)\n\
 195 -in#f  - multiply l(i, j) by #f * x(j)-x(i)           (default 1)\n\
 196          if #f=0 - don't multiply\n\
 197 -is#f  - multiply l(i, j) by #f * (x(j)-x(i))^2       (default NO)\n\
 198 -ix#i  - #i - is the number of arcs from a node        (default 1)\n\
 199 -ih#i  - #i - is the step between connected layers     (default 1)\n\
 200 \n\
 201       Potential parameters:\n\
 202 -p     - generate potentials \n\
 203 -pl#i  - #i is the upper bound on potentials           (default ll)\n\
 204 -pm#i  - #i is the lower bound on potentials           (default lm)\n\
 205 -pn#f  - multiply p(i) by #f * x(i)                    (default NO)\n\
 206 -ps#f  - multiply p(i) by #f * x(i)^2                  (default NO)\n\
 207 \n");
 208 zlog_info (
 209 "     Artificial source parameters:\n\
 210 -s     - generate artificial source with default connecting arc lengths\n\
 211 -sl#i  - #i is the upper bound on art. arc lengths    (default 100000000)\n\
 212 -sm#i  - #i is the lower bound on art. arc lengths    (default sl)\n\"
 213 );*/
 214 }
 215
 216 /* ----- wrong usage ----- */
 217 void
 218 usage (struct vty *vty) {
 219   vty_out (vty,"usage: X Y seed [-ll#i -lm#i -cl#i -p -pl#i -pm#i ...]%s",VTY_NEWLINE);
 220   vty_out (vty,"help: -h or -hh%s",VTY_NEWLINE);
 221
 222   if ( np > 0 )
 223     zlog_err ("error in parameter # %d\n\n", np );
 224 }
 225
 226
 227 /* parsing  parameters */
 228 /* checks the validity of incoming parameters */
 229 int
 230 spgrid_check_params ( struct vty *vty, int argc, const char **argv)
 231 {
 232 /* initialized by default values */
 233   ext=0;
 234
 235 /* variables for generating one layer */
 236
 237 /* variables for generating spanning graph */
 238   c_f = 0;
 239   cw_f = 0;
 240   cm_f = 0;
 241   cl_f = 0;
 242
 243   cw = PATH;  /* type of spanning graph */
 244   cm = 0;             /* lower bound of the interval */
 245   cl = 63;           /* upper bound of the interval */
 246
 247 /* variables for generating additional arcs */
 248   a_f = 0;
 249   ax_f = 0;
 250   am_f = 0;
 251   al_f = 0;
 252
 253   ax = 0;             /* number of additional arcs */
 254   am = 0;             /* lower bound of the interval */
 255   al = 63;           /* upper bound of the interval */
 256
 257 /* variables for inter-layer arcs */
 258   i_f = 0;
 259   ip_f = 0;
 260   ix_f = 0;
 261   ih_f = 0;
 262   im_f = 0;
 263   il_f = 0;
 264   in_f = 0;
 265   is_f = 0;
 266
 267   ip = NO;       /* to mess or not to mess */
 268   ix = 1;        /* number of interlayered arcs in a NODE */
 269   ih = 1;        /* step between two layeres */
 270   il = 63; //was 10000;    /* upper bound of the interval */
 271   im = 0;  //was 1000;     /* lower bound of the interval */
 272   in = 1;        /* l *=  in * |x1-x2| */
 273   is = 0;        /* l *=  is * |x1-x2|^2 */
 274
 275 /* variables for artifical source */
 276   s_f = 0;
 277   sl_f = 0;
 278   sm_f = 0;
 279   sl   = VERY_FAR; /* upper bound of artifical arc */
 280
 281 /* variables for potentials */
 282   p_f = 0;
 283   pl_f = 0;
 284   pm_f = 0;
 285   pn_f = 0;
 286   ps_f = 0;
 287
 288   pn = 0;        /* p +=  ln * (x+1) */
 289   ps = 0;        /* p +=  ls * (x+1)^2 */
 290
 291
 292   if ( argc < 1 ) {
 293     usage (vty);
 294     return 1;
 295   }
 296
 297   np = 0;
 298
 299   strcpy ( args, argv[0] );
 300
 301   if ((args[0] == DASH) && (args[1] == 'h'))
 302     help (vty);
 303
 304   if ( argc < 3 ) {
 305     usage (vty);
 306     return 1;
 307   }
 308
 309   /* first parameter - horizontal size */
 310   np = 1;
 311   if ( ( X = atoi ( argv[0] ) )  <  1  ) {
 312     usage (vty);
 313     return 1;
 314   }
 315
 316   /* second parameter - vertical size */
 317   np = 2;
 318   if ( ( Y = atoi ( argv[1] ) )  <  1  ) {
 319     usage (vty);
 320     return 1;
 321   }
 322
 323   /* third parameter - seed */
 324   np=3;
 325   if ( ( seed = atoi ( argv[2] ) )  <=  0  ) {
 326     usage (vty);
 327     return 1;
 328   }
 329
 330   /* other parameters */
 331   for ( np = 3; np < argc; np ++ ) {
 332     strcpy ( args, argv[np] );
 333     if ( args[0] != DASH )  {
 334       usage (vty);
 335       return 1;
 336     }
 337
 338     switch ( args[1] ) {
 339       case 'c' : /* spanning graph in one layer */
 340         c_f = 1;
 341         switch ( args[2] ) {
 342           case 'l': /* upper bound of the interval */
 343             cl_f = 1;
 344             cl  =  atol ( &args[3] );
 345             break;
 346           case 'm': /* lower bound */
 347             cm_f = 1;
 348             cm  = atol ( &args[3] );
 349             break;
 350           case 'c': /* type - cycle */
 351             cw_f = 1;
 352             cw   = CYCLE;
 353             break;
 354           case 'd': /* type - double cycle */
 355             cw_f = 1;
 356             cw   = DOUBLE_CYCLE;
 357             break;
 358           case 'p': /* type - path */
 359             cw_f = 1;
 360             cw   = PATH;
 361             break;
 362
 363           default:  /* unknown switch  value */
 364             usage (vty);
 365             return 1;
 366           }
 367         break;
 368
 369       case 'a' : /* additional arcs in one layer */
 370          a_f = 1;
 371         switch ( args[2] )
 372           {
 373           case 'l': /* upper bound of the interval */
 374             al_f = 1;
 375             al  =  atol ( &args[3] );
 376             break;
 377           case 'm': /* lower bound */
 378             am_f = 1;
 379             am  = atol ( &args[3] );
 380             break;
 381           case 'x': /* number of additional arcs */
 382             ax_f = 1;
 383             ax   = atol ( &args[3] );
 384             if ( ax < 0 )
 385              {
 386                usage (vty);
 387                return 1;
 388              }
 389             break;
 390
 391           default:  /* unknown switch  value */
 392             {
 393               usage (vty);
 394               return 1;
 395             }
 396           }
 397         break;
 398
 399
 400       case 'i' : /* interlayered arcs */
 401         i_f = 1;
 402
 403         switch ( args[2] )
 404           {
 405           case 'l': /* upper bound */
 406             il_f = 1;
 407             il  =  atol ( &args[3] );
 408             break;
 409           case 'm': /* lower bound */
 410             im_f = 1;
 411             im  = atol ( &args[3] );
 412             break;
 413           case 'n': /* additional length: l *= in*|i1-i2| */
 414             in_f = 1;
 415             in  = atof ( &args[3] );
 416             break;
 417           case 's': /* additional length: l *= is*|i1-i2|^2 */
 418             is_f = 1;
 419             is  = atof ( &args[3] );
 420             break;
 421           case 'p': /* mess interlayered arcs */
 422             ip_f = 1;
 423             ip = YES;
 424             break;
 425           case 'x': /* number of interlayered arcs */
 426             ix_f = 1;
 427             ix  = atof ( &args[3] );
 428             if ( ix < 1 ) {
 429               usage (vty);
 430               return 1;
 431             }
 432             break;
 433           case 'h': /* step between two layeres */
 434             ih_f = 1;
 435             ih  = atof ( &args[3] );
 436             if ( ih < 1 ) {
 437                usage (vty);
 438                return 1;
 439              }
 440             break;
 441           default:  /* unknown switch  value */
 442             usage (vty);
 443             return 1;
 444           }
 445         break;
 446
 447       case 's' : /* additional source */
 448         s_f = 1;
 449         if ( strlen ( args ) > 2 )
 450         {
 451         switch ( args[2] )
 452           {
 453           case 'l': /* upper bound of art. arc */
 454             sl_f = 1;
 455             sl  =  atol ( &args[3] );
 456             break;
 457           case 'm': /* lower bound of art. arc */
 458             sm_f = 1;
 459             sm  =  atol ( &args[3] );
 460             break;
 461           default:  /* unknown switch  value */
 462             usage (vty);
 463             return 1;
 464           }
 465          }
 466         break;
 467
 468       case 'p' : /* potentials */
 469         p_f = 1;
 470         if ( strlen ( args ) > 2 )
 471         {
 472         switch ( args[2] )
 473           {
 474           case 'l': /* upper bound */
 475             pl_f = 1;
 476             pl  =  atol ( &args[3] );
 477             break;
 478           case 'm': /* lower bound */
 479             pm_f = 1;
 480             pm  = atol ( &args[3] );
 481             break;
 482           case 'n': /* additional: p *= pn*(x+1) */
 483             pn_f = 1;
 484             pn  = atof ( &args[3] );
 485             break;
 486           case 's': /* additional: p = ps* (x+1)^2 */
 487             ps_f = 1;
 488             ps  = atof ( &args[3] );
 489             break;
 490           default:  /* unknown switch  value */
 491             usage (vty);
 492             return 1;
 493           }
 494         }
 495         break;
 496
 497       default: /* unknoun case */
 498         usage (vty);
 499         return 1;
 500       }
 501   }
 502
 503
 504   return 0;
 505 }
 506
 507
 508 /* generator of layered networks for the shortest paths problem;
 509    extended DIMACS format for output */
 510 int
 511 gen_spgrid_topology (struct vty *vty, struct list *topology)
 512 {
 513   /* ----- ajusting parameters ----- */
 514
 515   /* spanning */
 516   if ( cl < cm ) { lx = cl; cl = cm; cm = lx; }
 517
 518   /* additional arcs */
 519   if ( al < am ) { lx = al; al = am; am = lx; }
 520
 521   /* interlayered arcs */
 522   if ( il < im ) { lx = il; il = im; im = lx; }
 523
 524   /* potential parameters */
 525   if ( p_f )
 526     {
 527      if ( ! pl_f ) pl = il;
 528      if ( ! pm_f ) pm = im;
 529      if ( pl < pm ) { lx = pl; pl = pm; pm = lx; }
 530     }
 531
 532   /* number of nodes and arcs */
 533
 534   n = (double)X *(double)Y + 1;
 535
 536   m  = (double)Y; /* arcs from source */
 537
 538   switch ( cw )
 539   {
 540    case PATH:
 541     mc = (double)Y - 1;
 542     break;
 543    case CYCLE:
 544     mc = (double)Y;
 545     break;
 546    case DOUBLE_CYCLE:
 547     mc = 2*(double)Y;
 548   }
 549
 550   m += (double)X * (double)mc;  /* spanning arcs */
 551   m += (double)X * (double)ax;  /* additional arcs */
 552
 553   /* interlayered arcs */
 554   for ( x = 0; x < X; x ++ )
 555   {
 556     dl = ( ( X - x - 1 ) + ( ih - 1 ) ) / ih;
 557     if ( dl > ix ) dl = ix;
 558     m += (double)Y * (double)dl;
 559   }
 560
 561    /* artifical source parameters */
 562   if ( s_f ) {
 563     m += n; n ++ ;
 564     if ( ! sm_f ) sm = sl;
 565     if ( sl < sm ) { lx = sl; sl = sm; sm = lx; }
 566   }
 567
 568   if ( n >= (double)LONG_MAX || m >= (double)LONG_MAX )
 569   {
 570     zlog_err ("Too large problem. It can't be generated\n");
 571     exit (4);
 572   }
 573    else
 574   {
 575     n0 = (long)n; m0 = (long)m;
 576   }
 577
 578   if ( ip_f )
 579      mess = (long*) calloc ( Y, sizeof ( long ) );
 580
 581   /* printing title */
 582   zlog_info ("Generating topology for ISIS");
 583
 584   source = ( s_f ) ? n0-1 : n0;
 585
 586   if ( p_f ) /* generating potentials */ {
 587     p = (long*) calloc ( n0+1, sizeof (long) );
 588     seed1 = 2*seed + 1;
 589     init_rand ( seed1);
 590     pl = pl - pm + 1;
 591
 592     for ( x = 0; x < X; x ++ )
 593       for ( y = 0; y < Y; y ++ ) {
 594         p_t = pm + nrand ( pl );
 595         if ( pn_f ) p_t *= (long) ( (1 + x) * pn );
 596         if ( ps_f ) p_t *= (long) ( (1 + x) * ( (1 + x) * ps ));
 597
 598         p[ NODE ( x, y ) ] = p_t;
 599       }
 600       p[n0] = 0;
 601       if ( s_f ) p[n0-1] = 0;
 602     }
 603
 604   if ( s_f ) /* additional arcs from artifical source */
 605     {
 606       seed2 = 3*seed + 1;
 607       init_rand ( seed2 );
 608       sl = sl - sm + 1;
 609
 610       for ( x = X - 1; x >= 0; x -- )
 611         for ( y = Y - 1; y >= 0; y -- )
 612         {
 613           i = NODE ( x, y );
 614           s = sm + nrand ( sl );
 615           print_arc (vty, topology,  n0, i, s );
 616         }
 617
 618       print_arc (vty, topology,  n0, n0-1, 0 );
 619     }
 620
 621
 622   /* ----- generating arcs within layers ----- */
 623
 624   init_rand ( seed );
 625   cl = cl - cm + 1;
 626   al = al - am + 1;
 627
 628   for ( x = 0; x < X; x ++ )
 629    {
 630   /* generating arcs within one layer */
 631     for ( y = 0; y < Y-1; y ++ )
 632     {
 633        /* generating spanning graph */
 634        i = NODE ( x, y );
 635        j = NODE ( x, y+1 );
 636        l = cm + nrand ( cl );
 637        print_arc (vty, topology,  i, j, l );
 638
 639        if ( cw == DOUBLE_CYCLE )
 640          {
 641            l = cm + nrand ( cl );
 642            print_arc (vty, topology,  j, i, l );
 643          }
 644      }
 645
 646     if ( cw <= CYCLE )
 647       {
 648         i = NODE ( x, Y-1 );
 649         j = NODE ( x, 0 );
 650         l = cm + nrand ( cl );
 651         print_arc (vty, topology,  i, j, l );
 652
 653         if ( cw == DOUBLE_CYCLE )
 654           {
 655           l = cm + nrand ( cl );
 656             print_arc (vty, topology,  j, i, l );
 657           }
 658        }
 659
 660   /* generating additional arcs */
 661
 662     for ( k = ax; k > 0; k -- )
 663        {
 664          y1 = nrand ( Y );
 665          do
 666             y2 = nrand ( Y );
 667          while ( y2 == y1 );
 668          i  = NODE ( x, y1 );
 669          j  = NODE ( x, y2 );
 670          l = am + nrand ( al );
 671          print_arc (vty, topology,  i, j, l );
 672        }
 673    }
 674
 675   /* ----- generating interlayered arcs ------ */
 676
 677   il = il - im + 1;
 678
 679   /* arcs from the source */
 680
 681     for ( y = 0; y < Y; y ++ )
 682       {
 683         l = im + nrand ( il );
 684         i = NODE ( 0, y );
 685         print_arc (vty, topology,  source, i, l );
 686       }
 687
 688   for ( x = 0; x < X-1; x ++ )
 689    {
 690   /* generating arcs from one layer */
 691      for ( count = 0, xn = x + 1;
 692            count < ix && xn < X;
 693            count ++, xn += ih )
 694       {
 695         if ( ip_f )
 696         for ( y = 0; y < Y; y ++ )
 697         mess[y] = y;
 698
 699         for ( y = 0; y < Y; y ++ )
 700          {
 701             i = NODE ( x, y );
 702           dx = xn - x;
 703           if ( ip_f )
 704             {
 705               yp = nrand(Y-y);
 706               yn = mess[ yp ];
 707                 mess[ yp ] = mess[ Y - y - 1 ];
 708             }
 709           else
 710                yn =  y;
 711           j = NODE ( xn, yn );
 712           l = im + nrand ( il );
 713           if ( in != 0 )
 714               l *= (long) ( in * dx );
 715             if ( is_f )
 716               l *= (long) ( ( is * dx ) * dx );
 717             print_arc (vty, topology,  i, j, l );
 718         }
 719       }
 720    }
 721   /* all is done */
 722   return ext;
 723
 724 return 0;
 725 }
 726
 727
 728