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 /*
  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,
  53        y1, y2, yp,
  54        dl, dx, xn, yn, count,
  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        {
 673          y1 = nrand ( Y );
 674          do
 675             y2 = nrand ( Y );
 676          while ( y2 == y1 );
 677          i  = NODE ( x, y1 );
 678          j  = NODE ( x, y2 );
 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             {
 714               yp = nrand(Y-y);
 715               yn = mess[ yp ];
 716                 mess[ yp ] = mess[ Y - y - 1 ];
 717             }
 718           else
 719                yn =  y;
 720           j = NODE ( xn, yn );
 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