Annotation of embedaddon/quagga/isisd/topology/spgrid.c, revision 1.1.1.2

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

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>