isisd/topology/spgrid.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "random.c"

#include <zebra.h>

#include "thread.h"
#include "vty.h"
#include "log.h"
#include "linklist.h"

#include "spgrid.h"


#define DASH '-'
#define VERY_FAR 100000000

#define DOUBLE_CYCLE   0
#define CYCLE          1
#define PATH           2

#define NO             0
#define YES            1

#define NODE( x, y ) (x*Y + y + 1)

/*
 * Prototypes.
 */
void free_arc(void *);
void help(struct vty *);
void print_arc(struct vty *, struct list *, long, long, long);
void hhelp(struct vty *);
void usage(struct vty *);

const char   *graph_type[] =  {
  "double cycle",
  "cycle",
  "path"
};

struct arc *arc;

char   args[30];

long   X,   /* horizontal size of grid */
       Y;   /* vertical size of grid */

long   x,
       y,
       yy1, yy2, yyp,
       dl, dx, xn, yyn, count,
       *mess;

double n;
long   n0,
       source,
       i,
       i0,
       j,
       dij;

double m;
long   m0,
       mc,
       k;

long   *p,
       p_t,
       l,
       lx;

long   seed,
       seed1,
       seed2;

int    ext=0;

/* initialized by default values */

/* variables for generating one layer */

/* variables for generating spanning graph */
int    c_f = 0, cw_f = 0, cm_f = 0, cl_f = 0;

int    cw = DOUBLE_CYCLE;  /* type of spanning graph */
long   cm = 0,             /* lower bound of the interval */
       cl = 100;           /* upper bound of the interval */

/* variables for generating additional arcs */
int    a_f = 0, ax_f = 0, am_f = 0, al_f = 0;

long   ax = 0,             /* number of additional arcs */
       am = 0,             /* lower bound of the interval */
       al = 100;           /* upper bound of the interval */

/* variables for inter-layer arcs */
int    i_f = 0, ip_f = 0, ix_f = 0, ih_f = 0,
       im_f = 0, il_f = 0, in_f = 0, is_f = 0;

int    ip = NO;       /* to mess or not to mess */
long   ix = 1,        /* number of interlayered arcs in a NODE */
       ih = 1,        /* step between two layeres */
       il = 10000,    /* upper bound of the interval */
       im = 1000;     /* lower bound of the interval */
double in = 1,        /* l *=  in * |x1-x2| */
       is = 0;        /* l *=  is * |x1-x2|^2 */

/* variables for artifical source */
int    s_f = 0, sl_f = 0, sm_f = 0;
long   sl   = VERY_FAR, /* upper bound of artifical arc */
       sm,              /* lower bound of artifical arc */
       s;

/* variables for potentials */
int    p_f = 0, pl_f = 0, pm_f = 0, pn_f = 0, ps_f = 0;

long   pl,            /* upper bound of the interval */
       pm;            /* lower bound of the interval */
double pn = 0,        /* p +=  ln * (x+1) */
       ps = 0;        /* p +=  ls * (x+1)^2 */

int np;               /* number of parameter parsing now */


void
free_arc   (void *val) {
  free(val);
}

void
print_arc (struct vty *vty, struct list *topology, long i, long j, long length)
{
  struct arc *myarc;

  l = length;
  if ( p_f ) l += ( p[i] - p[j] );
//  vty_out (vty,"a %8ld %8ld %12ld%s", i, j, l ,VTY_NEWLINE);
  myarc = malloc (sizeof(struct arc));
  myarc->from_node = i;
  myarc->to_node = j;
  myarc->distance = l;
  topology->del = free_arc;
  listnode_add (topology, myarc);
}

/* ---- help ---- */
void
help (struct vty *vty) {
//  if ( args[2] == 'h') hhelp (vty);
  vty_out (vty,"grid network generator for shortest paths problem.%s",VTY_NEWLINE);
  vty_out (vty,"Generates problems in extended DIMACS format.%s",VTY_NEWLINE);
  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);
  vty_out (vty,"#i - integer number%s",VTY_NEWLINE);
  vty_out (vty,"-cl#i - #i is the upper bound on layer arc lengths    (default 100)%s",VTY_NEWLINE);
  vty_out (vty,"-cm#i - #i is the lower bound on layer arc lengths    (default 0)%s",VTY_NEWLINE);
  vty_out (vty,"-c#t  - #t is the type of connecting graph: { c | d | p }%s",VTY_NEWLINE);
  vty_out (vty,"           c - cycle, d - double cycle, p - path      (default d)%s",VTY_NEWLINE);
  vty_out (vty,"-ip   - shuffle inter-layer arcs                     (default NO)%s",VTY_NEWLINE);
  vty_out (vty,"-il#i - #i is the upper bound on inter-layer arc lengths (default 10000)%s",VTY_NEWLINE);
  vty_out (vty,"-im#i - #i is the lower bound on inter-layer arc lengths (default 1000)%s",VTY_NEWLINE);
  vty_out (vty,"-p    - generate potentials%s",VTY_NEWLINE);
  vty_out (vty,"-pl#i - #i is the upper bound on potentials           (default il)%s",VTY_NEWLINE);
  vty_out (vty,"-pm#i - #i is the lower bound on potentials           (default im)%s",VTY_NEWLINE);
  vty_out (vty,"%s",VTY_NEWLINE);
  vty_out (vty,"-hh    - extended help%s",VTY_NEWLINE);
}

/* --------- sophisticated help ------------ */
void
hhelp (struct vty *vty) {
/*
zlog_info (
"\n'%s' - grid network generator for shortest paths problem.\n\
Generates problems in extended DIMACS format.\n\
\n\
   %s  X Y seed [ -cl#i -cm#i -c{c|d|p}\n\
                      -ax#i -al#i -am#i\n\
                      -ip   -il#i -im#i -in#i -is#i -ix#i -ih#i\n\
                      -p    -pl#i -pm#i -pn#f -ps#f\n\
                      -s    -sl#i -sm#i\n\
                    ]\n\
   %s -hh file_name\n\
\n\
                        #i - integer number   #f - real number\n\
\n\
      Parameters of connecting arcs within one layer:\n\
-cl#i - #i is the upper bound on arc lengths          (default 100)\n\
-cm#i - #i is the lower bound on arc lengths          (default 0)\n\
-c#t  - #t is the type of connecting graph: { c | d | p }\n\
           c - cycle, d - double cycle, p - path      (default d)\n\
\n\
      Parameters of additional arcs within one layer:\n\
-ax#i - #i is the number of additional arcs           (default 0)\n\
-al#i - #i is the upper bound on arc lengths          (default 100)\n\
-am#i - #i is the lower bound on arc lengths          (default 0)\n\
\n\
      Interlayerd arc parameters:\n\
-ip    - shuffle inter-layer arcs                         (default NO)\n\
-il#i  - #i is the upper bound on arc lengths          (default 10000)\n\
-im#i  - #i is the lower bound on arc lengths          (default 1000)\n\
-in#f  - multiply l(i, j) by #f * x(j)-x(i)           (default 1)\n\
         if #f=0 - don't multiply\n\
-is#f  - multiply l(i, j) by #f * (x(j)-x(i))^2       (default NO)\n\
-ix#i  - #i - is the number of arcs from a node        (default 1)\n\
-ih#i  - #i - is the step between connected layers     (default 1)\n\
\n\
      Potential parameters:\n\
-p     - generate potentials \n\
-pl#i  - #i is the upper bound on potentials           (default ll)\n\
-pm#i  - #i is the lower bound on potentials           (default lm)\n\
-pn#f  - multiply p(i) by #f * x(i)                    (default NO)\n\
-ps#f  - multiply p(i) by #f * x(i)^2                  (default NO)\n\
\n");
zlog_info (
"     Artificial source parameters:\n\
-s     - generate artificial source with default connecting arc lengths\n\
-sl#i  - #i is the upper bound on art. arc lengths    (default 100000000)\n\
-sm#i  - #i is the lower bound on art. arc lengths    (default sl)\n\"
);*/
}

/* ----- wrong usage ----- */
void
usage (struct vty *vty) {
  vty_out (vty,"usage: X Y seed [-ll#i -lm#i -cl#i -p -pl#i -pm#i ...]%s",VTY_NEWLINE);
  vty_out (vty,"help: -h or -hh%s",VTY_NEWLINE);

  if ( np > 0 )
    zlog_err ("error in parameter # %d\n\n", np );
}


/* parsing  parameters */
/* checks the validity of incoming parameters */
int
spgrid_check_params ( struct vty *vty, int argc, const char **argv)
{
/* initialized by default values */
  ext=0;

/* variables for generating one layer */

/* variables for generating spanning graph */
  c_f = 0;
  cw_f = 0;
  cm_f = 0;
  cl_f = 0;

  cw = PATH;  /* type of spanning graph */
  cm = 0;             /* lower bound of the interval */
  cl = 63;           /* upper bound of the interval */

/* variables for generating additional arcs */
  a_f = 0;
  ax_f = 0;
  am_f = 0;
  al_f = 0;

  ax = 0;             /* number of additional arcs */
  am = 0;             /* lower bound of the interval */
  al = 63;           /* upper bound of the interval */

/* variables for inter-layer arcs */
  i_f = 0;
  ip_f = 0;
  ix_f = 0;
  ih_f = 0;
  im_f = 0;
  il_f = 0;
  in_f = 0;
  is_f = 0;

  ip = NO;       /* to mess or not to mess */
  ix = 1;        /* number of interlayered arcs in a NODE */
  ih = 1;        /* step between two layeres */
  il = 63; //was 10000;    /* upper bound of the interval */
  im = 0;  //was 1000;     /* lower bound of the interval */
  in = 1;        /* l *=  in * |x1-x2| */
  is = 0;        /* l *=  is * |x1-x2|^2 */

/* variables for artifical source */
  s_f = 0;
  sl_f = 0;
  sm_f = 0;
  sl   = VERY_FAR; /* upper bound of artifical arc */

/* variables for potentials */
  p_f = 0;
  pl_f = 0;
  pm_f = 0;
  pn_f = 0;
  ps_f = 0;

  pn = 0;        /* p +=  ln * (x+1) */
  ps = 0;        /* p +=  ls * (x+1)^2 */


  if ( argc < 1 ) {
    usage (vty);
    return 1;
  }

  np = 0;

  strcpy ( args, argv[0] );

  if ((args[0] == DASH) && (args[1] == 'h'))
    help (vty);

  if ( argc < 3 ) {
    usage (vty);
    return 1;
  }

  /* first parameter - horizontal size */
  np = 1;
  if ( ( X = atoi ( argv[0] ) )  <  1  ) {
    usage (vty);
    return 1;
  }

  /* second parameter - vertical size */
  np = 2;
  if ( ( Y = atoi ( argv[1] ) )  <  1  ) {
    usage (vty);
    return 1;
  }

  /* third parameter - seed */
  np=3;
  if ( ( seed = atoi ( argv[2] ) )  <=  0  ) {
    usage (vty);
    return 1;
  }

  /* other parameters */
  for ( np = 3; np < argc; np ++ ) {
    strcpy ( args, argv[np] );
    if ( args[0] != DASH )  {
      usage (vty);
      return 1;
    }

    switch ( args[1] ) {
      case 'c' : /* spanning graph in one layer */
        c_f = 1;
        switch ( args[2] ) {
          case 'l': /* upper bound of the interval */
            cl_f = 1;
            cl  =  atol ( &args[3] );
            break;
          case 'm': /* lower bound */
            cm_f = 1;
            cm  = atol ( &args[3] );
            break;
          case 'c': /* type - cycle */
            cw_f = 1;
            cw   = CYCLE;
            break;
          case 'd': /* type - double cycle */
            cw_f = 1;
            cw   = DOUBLE_CYCLE;
            break;
          case 'p': /* type - path */
            cw_f = 1;
            cw   = PATH;
            break;

          default:  /* unknown switch  value */
            usage (vty);
            return 1;
          }
        break;

      case 'a' : /* additional arcs in one layer */
         a_f = 1;
        switch ( args[2] )
          {
          case 'l': /* upper bound of the interval */
            al_f = 1;
            al  =  atol ( &args[3] );
            break;
          case 'm': /* lower bound */
            am_f = 1;
            am  = atol ( &args[3] );
            break;
          case 'x': /* number of additional arcs */
            ax_f = 1;
            ax   = atol ( &args[3] );
            if ( ax < 0 )
             {
               usage (vty);
               return 1;
             }
            break;

          default:  /* unknown switch  value */
            {
              usage (vty);
              return 1;
            }
          }
        break;


      case 'i' : /* interlayered arcs */
        i_f = 1;

        switch ( args[2] )
          {
          case 'l': /* upper bound */
            il_f = 1;
            il  =  atol ( &args[3] );
            break;
          case 'm': /* lower bound */
            im_f = 1;
            im  = atol ( &args[3] );
            break;
          case 'n': /* additional length: l *= in*|i1-i2| */
            in_f = 1;
            in  = atof ( &args[3] );
            break;
          case 's': /* additional length: l *= is*|i1-i2|^2 */
            is_f = 1;
            is  = atof ( &args[3] );
            break;
          case 'p': /* mess interlayered arcs */
            ip_f = 1;
            ip = YES;
            break;
          case 'x': /* number of interlayered arcs */
            ix_f = 1;
            ix  = atof ( &args[3] );
            if ( ix < 1 ) {
              usage (vty);
              return 1;
            }
            break;
          case 'h': /* step between two layeres */
            ih_f = 1;
            ih  = atof ( &args[3] );
            if ( ih < 1 ) {
               usage (vty);
               return 1;
             }
            break;
          default:  /* unknown switch  value */
            usage (vty);
            return 1;
          }
        break;

      case 's' : /* additional source */
        s_f = 1;
        if ( strlen ( args ) > 2 )
        {
        switch ( args[2] )
          {
          case 'l': /* upper bound of art. arc */
            sl_f = 1;
            sl  =  atol ( &args[3] );
            break;
          case 'm': /* lower bound of art. arc */
            sm_f = 1;
            sm  =  atol ( &args[3] );
            break;
          default:  /* unknown switch  value */
            usage (vty);
            return 1;
          }
         }
        break;

      case 'p' : /* potentials */
        p_f = 1;
        if ( strlen ( args ) > 2 )
        {
        switch ( args[2] )
          {
          case 'l': /* upper bound */
            pl_f = 1;
            pl  =  atol ( &args[3] );
            break;
          case 'm': /* lower bound */
            pm_f = 1;
            pm  = atol ( &args[3] );
            break;
          case 'n': /* additional: p *= pn*(x+1) */
            pn_f = 1;
            pn  = atof ( &args[3] );
            break;
          case 's': /* additional: p = ps* (x+1)^2 */
            ps_f = 1;
            ps  = atof ( &args[3] );
            break;
          default:  /* unknown switch  value */
            usage (vty);
            return 1;
          }
        }
        break;

      default: /* unknoun case */
        usage (vty);
        return 1;
      }
  }


  return 0;
}


/* generator of layered networks for the shortest paths problem;
   extended DIMACS format for output */
int
gen_spgrid_topology (struct vty *vty, struct list *topology)
{
  /* ----- ajusting parameters ----- */

  /* spanning */
  if ( cl < cm ) { lx = cl; cl = cm; cm = lx; }

  /* additional arcs */
  if ( al < am ) { lx = al; al = am; am = lx; }

  /* interlayered arcs */
  if ( il < im ) { lx = il; il = im; im = lx; }

  /* potential parameters */
  if ( p_f )
    {
     if ( ! pl_f ) pl = il;
     if ( ! pm_f ) pm = im;
     if ( pl < pm ) { lx = pl; pl = pm; pm = lx; }
    }

  /* number of nodes and arcs */

  n = (double)X *(double)Y + 1;

  m  = (double)Y; /* arcs from source */

  switch ( cw )
  {
   case PATH:
    mc = (double)Y - 1;
    break;
   case CYCLE:
    mc = (double)Y;
    break;
   case DOUBLE_CYCLE:
    mc = 2*(double)Y;
  }

  m += (double)X * (double)mc;  /* spanning arcs */
  m += (double)X * (double)ax;  /* additional arcs */

  /* interlayered arcs */
  for ( x = 0; x < X; x ++ )
  {
    dl = ( ( X - x - 1 ) + ( ih - 1 ) ) / ih;
    if ( dl > ix ) dl = ix;
    m += (double)Y * (double)dl;
  }

   /* artifical source parameters */
  if ( s_f ) {
    m += n; n ++ ;
    if ( ! sm_f ) sm = sl;
    if ( sl < sm ) { lx = sl; sl = sm; sm = lx; }
  }

  if ( n >= (double)LONG_MAX || m >= (double)LONG_MAX )
  {
    zlog_err ("Too large problem. It can't be generated\n");
    exit (4);
  }
   else
  {
    n0 = (long)n; m0 = (long)m;
  }

  if ( ip_f )
     mess = (long*) calloc ( Y, sizeof ( long ) );

  /* printing title */
  zlog_info ("Generating topology for ISIS");

  source = ( s_f ) ? n0-1 : n0;

  if ( p_f ) /* generating potentials */ {
    p = (long*) calloc ( n0+1, sizeof (long) );
    seed1 = 2*seed + 1;
    init_rand ( seed1);
    pl = pl - pm + 1;

    for ( x = 0; x < X; x ++ )
      for ( y = 0; y < Y; y ++ ) {
        p_t = pm + nrand ( pl );
        if ( pn_f ) p_t *= (long) ( (1 + x) * pn );
        if ( ps_f ) p_t *= (long) ( (1 + x) * ( (1 + x) * ps ));

        p[ NODE ( x, y ) ] = p_t;
      }
      p[n0] = 0;
      if ( s_f ) p[n0-1] = 0;
    }

  if ( s_f ) /* additional arcs from artifical source */
    {
      seed2 = 3*seed + 1;
      init_rand ( seed2 );
      sl = sl - sm + 1;

      for ( x = X - 1; x >= 0; x -- )
        for ( y = Y - 1; y >= 0; y -- )
        {
          i = NODE ( x, y );
          s = sm + nrand ( sl );
          print_arc (vty, topology,  n0, i, s );
        }

      print_arc (vty, topology,  n0, n0-1, 0 );
    }


  /* ----- generating arcs within layers ----- */

  init_rand ( seed );
  cl = cl - cm + 1;
  al = al - am + 1;

  for ( x = 0; x < X; x ++ )
   {
  /* generating arcs within one layer */
    for ( y = 0; y < Y-1; y ++ )
    {
       /* generating spanning graph */
       i = NODE ( x, y );
       j = NODE ( x, y+1 );
       l = cm + nrand ( cl );
       print_arc (vty, topology,  i, j, l );

       if ( cw == DOUBLE_CYCLE )
         {
           l = cm + nrand ( cl );
           print_arc (vty, topology,  j, i, l );
         }
     }

    if ( cw <= CYCLE )
      {
        i = NODE ( x, Y-1 );
        j = NODE ( x, 0 );
        l = cm + nrand ( cl );
        print_arc (vty, topology,  i, j, l );

        if ( cw == DOUBLE_CYCLE )
          {
  	  l = cm + nrand ( cl );
            print_arc (vty, topology,  j, i, l );
          }
       }

  /* generating additional arcs */

    for ( k = ax; k > 0; k -- )
       {
         yy1 = nrand ( Y );
         do
            yy2 = nrand ( Y );
         while ( yy2 == yy1 );
         i  = NODE ( x, yy1 );
         j  = NODE ( x, yy2 );
         l = am + nrand ( al );
         print_arc (vty, topology,  i, j, l );
       }
   }

  /* ----- generating interlayered arcs ------ */

  il = il - im + 1;

  /* arcs from the source */

    for ( y = 0; y < Y; y ++ )
      {
        l = im + nrand ( il );
        i = NODE ( 0, y );
        print_arc (vty, topology,  source, i, l );
      }

  for ( x = 0; x < X-1; x ++ )
   {
  /* generating arcs from one layer */
     for ( count = 0, xn = x + 1;
           count < ix && xn < X;
           count ++, xn += ih )
      {
        if ( ip_f )
        for ( y = 0; y < Y; y ++ )
  	mess[y] = y;

        for ( y = 0; y < Y; y ++ )
         {
            i = NODE ( x, y );
  	  dx = xn - x;
  	  if ( ip_f )
  	    {
  	      yyp = nrand(Y-y);
  	      yyn = mess[ yyp ];
                mess[ yyp ] = mess[ Y - y - 1 ];
  	    }
  	  else
               yyn =  y;
  	  j = NODE ( xn, yyn );
  	  l = im + nrand ( il );
  	  if ( in != 0 )
              l *= (long) ( in * dx );
            if ( is_f )
              l *= (long) ( ( is * dx ) * dx );
            print_arc (vty, topology,  i, j, l );
  	}
      }
   }
  /* all is done */
  return ext;

return 0;
}