Initial revision

6 files changed, 1933 insertions, 0 deletions

diff --git a/isisd/topology/Makefile.am b/isisd/topology/Makefile.am
new file mode 100644
index 00000000..045c15c8
--- /dev/null
+++ b/isisd/topology/Makefile.am
@@ -0,0 +1,23 @@
+## Process this file with automake to produce Makefile.in.
+
+INCLUDES = @INCLUDES@ -I.. -I$(top_srcdir) -I$(top_srcdir)/lib
+DEFS = @DEFS@ -DSYSCONFDIR=\"$(sysconfdir)/\"
+
+noinst_LIBRARIES = libtopology.a
+
+libtopology_a_SOURCES = \
+	spgrid.c
+
+libtopology_a_DEPENDENCIES = @LIB_REGEX@
+
+libtopology_a_LIBADD = @LIB_REGEX@ ../../lib/libzebra.a
+
+noinst_HEADERS = \
+	spgrid.h
+
+EXTRA_DIST = regex.c regex-gnu.h
+
+depend:
+	@$(CPP) -MM $(INCLUDES) $(LDFLAGS) *.c
+
+## File dependency.
diff --git a/isisd/topology/random.c b/isisd/topology/random.c
new file mode 100644
index 00000000..d4ef9950
--- /dev/null
+++ b/isisd/topology/random.c
@@ -0,0 +1,154 @@
+/*********************************************************************/
+/*                                                                   */
+/* current processor time in seconds                                 */
+/* difference between two calls is processor time spent by your code */
+/* needs: <sys/types.h>, <sys/times.h>                               */
+/* depends on compiler and OS                                        */
+/*                                                                   */
+/*********************************************************************/
+
+#include <sys/types.h>
+#include <sys/times.h>
+
+float timer()
+   { struct tms hold;
+
+        times(&hold);
+        return  (float)(hold.tms_utime) / 60.0;
+   }
+
+
+/*********************************************************************/
+/*                                                                   */
+/*            Family of random number generators                     */
+/*                                                                   */
+/*  Initialisation:                                                  */
+/*            void init_rand ( seed );                               */
+/*                 long seed     - any positive number               */
+/*                                 if seed<=0 init_rand takes time   */
+/*                                 from timer instead of seed        */
+/*                                                                   */
+/*  Whole number uniformly distributed on [0,n):                     */
+/*            long nrand (n);                                        */
+/*                 long n                                            */
+/*                                                                   */
+/*  Real number uniformly distributed on [0,1]                       */
+/*            double rand01();                                       */
+/*                                                                   */
+/*  Real number with Gauss(0,1) disitribution:                       */
+/*            double randg01();                                      */
+/*                                                                   */
+/*  Algorithm:                                                       */
+/*            x(n+1) = (x(n) * 5^13) mod 2^31                        */
+/*                                                                   */
+/*********************************************************************/
+
+unsigned long internal_seed;
+
+void init_rand ( init_seed )
+
+long init_seed;
+
+{ internal_seed = ( init_seed > 0 )
+                 ? (unsigned long) init_seed
+                 : (unsigned long) timer(); 
+                
+
+  /* only odd numbers are acceptable */
+  if ( internal_seed % 2 == 0 ) internal_seed --;
+}
+
+/*********************************************************************/
+/*                                                                   */
+/* Internal function  irand  may depend on OS and compiler           */
+/*                                                                   */
+/* irand assumption:                                                 */
+/* unsigned long i,j;                                                */
+/*   if i*j > max(unsigned long)                                     */
+/*           1. No overflow interruption                             */
+/*           2. i*j = i*j mod max(unsigned long)                     */
+/*                                                                   */
+/* This assumption is true for a lot of computers.                   */
+/* If your computer fails:                                           */
+/*   rename: irand <---> xrand                                       */
+/*                                                                   */
+/*********************************************************************/
+ 
+#define  A   1220703125
+#define  B   2147483647
+#define  BF  2147483647.
+
+static long irand ()
+
+{ internal_seed = ( internal_seed * A ) & B;
+  return (long) internal_seed ;
+}
+
+/*********************************************************************/
+/*                                                                   */
+/*              computer independent variant of  irand               */
+/*                                                                   */
+/*********************************************************************/
+
+
+#define T15  32768 
+#define T16  65536
+#define A1   37252
+#define A2   29589
+
+static long xrand()
+
+{ unsigned long is1, is2;
+
+  is1 = internal_seed / T15;
+  is2 = internal_seed % T15;
+
+  internal_seed = ( (((is2 * A1) + (is1 * A2))% T16 )* T15 + (is2 * A2) ) & B;
+  return (long) ( internal_seed ) ;
+}
+
+
+/*********************************************************************/
+
+
+double rand01()
+
+{ return  (double) irand() / BF ;
+}
+  
+/*********************************************************************/
+
+#define NK  12
+
+double randg01()
+
+{ int i;
+  double sum = 0;
+
+  for ( i = 0; i < NK; i++ ) sum += rand01();
+  return sum - 6.;
+
+  /* if   NK != 12  then you must return (12/NK)*sum - (NK/2) */
+}
+
+#undef NK
+     
+  
+/*********************************************************************/
+
+long nrand ( n )
+
+long n;
+
+{ return (long) ( rand01() * (double) n );
+}
+
+/*********************************************************************/
+
+#undef A
+#undef A1
+#undef A2
+#undef B
+#undef BF
+#undef T15
+#undef T16
diff --git a/isisd/topology/spacyc.c b/isisd/topology/spacyc.c
new file mode 100644
index 00000000..85314473
--- /dev/null
+++ b/isisd/topology/spacyc.c
@@ -0,0 +1,483 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <values.h>
+
+#include "random.c"
+
+#define DASH '-'
+#define VERY_FAR 100000000
+
+
+/* generator of acyclic random networks for the shortest paths problem;
+   extended DIMACS format for output */
+
+main ( argc, argv )
+
+int argc;
+char* argv[];
+
+{
+
+char   args[30];
+
+long   n,
+       n0,
+       source,
+       i,
+       i0,
+       j,
+       dij;
+
+long   m,
+       m0,
+       mc,
+       k;
+
+long   *p,
+       p_t,
+       l,
+       lx;
+
+long   seed,
+       seed1,
+       seed2;
+
+int    ext=0;
+
+FILE   *fout;
+
+/* variables for lengths generating */
+/* initialized by default values */
+int    l_f = 0, ll_f = 0, lm_f = 0, ln_f = 0, ls_f = 0;
+long   ll = 10000,    /* upper bound of the interval */
+       lm = 0;        /* lower bound of the interval */
+double ln = 0,        /* l += ln * |i-j| */ 
+       ls = 0;        /* l += ls * |i-j|^2 */
+
+/* variables for connecting path(s) */
+int    c_f = 0, cl_f = 0, ch_f = 0, c_rand = 1;
+long   cl = 1;        /* length of path arc */
+long   ch;            /* number of arcs in the path
+                         n - by default */
+
+/* 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,
+       pa_f = 0, pap_f = 0, pac_f = 0;
+long   pl,            /* upper bound of the interval */
+       pm;            /* lower bound of the interval */
+double pn = 0,        /* l += ln * |i-j| */ 
+       ps = 0,        /* l += ls * |i-j|^2 */
+       pap = 0,       /* part of nodes with alternative dustribution */
+       pac = -1;      /* multiplier for alternative distribution */
+
+int np;               /* number of parameter parsing now */
+
+#define PRINT_ARC( i, j, length )\
+{\
+l = length;\
+if ( p_f ) l += ( p[i] - p[j] );\
+printf ("a %8ld %8ld %12ld\n", i, j, l );\
+}
+
+  /* parsing  parameters */
+
+if ( argc < 2 ) goto usage;
+
+np = 0;
+
+strcpy ( args, argv[1] );
+
+  if ( ( args[0] == DASH ) && ( args[1] == 'h')
+     )
+      goto help;
+
+if ( argc < 4 ) goto usage;
+
+/* first parameter - number of nodes */
+np = 1;
+if ( ( n = atoi ( argv[1] ) )  <  2  )  goto usage;
+
+/* second parameter - number of arcs */
+np = 2;
+if ( ( m = atoi ( argv[2] ) )  <  n  )  goto usage;
+
+/* third parameter - seed */
+np=3;
+if ( ( seed = atoi ( argv[3] ) )  <=  0  )  goto usage;
+
+/* other parameters */
+
+for ( np = 4; np < argc; np ++ )
+  {
+    strcpy ( args, argv[np] );
+    if ( args[0] != DASH ) goto usage;
+
+    switch ( args[1] )
+      {
+
+      case 'l' : /* an interval for arc length */
+	l_f = 1;
+	switch ( args[2] )
+	  { 
+	  case 'l': /* length of the interval */
+	    ll_f = 1;
+	    ll  =  (long) atof ( &args[3] );
+	    break;
+	  case 'm': /* minimal bound */
+	    lm_f = 1;
+	    lm  = (long ) atof ( &args[3] );
+	    break;
+	  case 'n': /* additional length: l*|i-j| */
+	    ln_f = 1;
+	    ln  = atof ( &args[3] );
+	    break;
+	  case 's': /* additional length: l*|i-j|^2 */
+	    ls_f = 1;
+	    ls  = atof ( &args[3] );
+	    break;
+	  default:  /* unknown switch  value */
+	    goto usage;
+	  }
+	break;
+
+      case 'c' : /* connecting path(s) */
+        c_f = 1;
+	switch ( args[2] )
+	  { 
+	  case 'l': /* length of path arc */
+            c_rand = 0; /* fixed arc length */
+	    cl_f = 1;
+	    cl  =  (long) atof ( &args[3] );
+            break;
+	  case 'h': /* number of arcs in connecting path */
+	    ch_f = 1;
+	    ch  =  (long) atof ( &args[3] );
+            if ( ch < 1 || ch > n ) goto usage;
+	    break;
+	  default:  /* unknown switch  value */
+	    goto usage;
+          }
+	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  =  (long) atof ( &args[3] );
+            break;
+	  case 'm': /* lower bound of art. arc */
+	    sm_f = 1;
+	    sm  =  (long) atof ( &args[3] );
+            break;
+	  default:  /* unknown switch  value */
+	    goto usage;
+          }
+         }
+	break;
+
+      case 'p' : /* potentials */
+	p_f = 1;
+	if ( strlen ( args ) > 2 )
+	{  
+	switch ( args[2] )
+	  { 
+	  case 'l': /* length of the interval */
+	    pl_f = 1;
+	    pl  =  (long) atof ( &args[3] );
+	    break;
+	  case 'm': /* minimal bound */
+	    pm_f = 1;
+	    pm  = (long ) atof ( &args[3] );
+	    break;
+	  case 'n': /* additional length: l*|i-j| */
+	    pn_f = 1;
+	    pn  = atof ( &args[3] );
+	    break;
+	  case 's': /* additional length: l*|i-j|^2 */
+	    ps_f = 1;
+	    ps  = atof ( &args[3] );
+	    break;
+	  case 'a': /* bipolar distribution */
+	    pa_f = 1;
+	    switch ( args[3] )
+	      {
+	      case 'p': /* % of alternative potentials */
+                pap_f = 1;
+                pap  = atof ( &args[4] );
+		if ( pap < 0   ) pap = 0;
+		if ( pap > 100 ) pap = 100;
+                pap /= 100;
+		break;
+	      case 'c': /* multiplier */
+		pac_f = 1;
+		pac = atof ( &args[4] );
+		break;
+	      default: /* unknown switch value */
+		goto usage;
+	      }
+	    break;
+	  default:  /* unknown switch  value */
+	    goto usage;
+	  }
+      }
+	break;
+
+      default  : /* unknoun case */
+	goto usage;
+      }
+  }
+   
+/* ----- ajusting parameters ----- */
+
+n0 = n; m0 = m;
+
+/* length parameters */
+if ( ll < lm ) { lx = ll; ll = lm; lm = lx; }
+
+/* potential parameters */
+if ( p_f )
+  {
+   if ( ! pl_f ) pl = ll;
+   if ( ! pm_f ) pm = lm;
+   if ( pl < pm ) { lx = pl; pl = pm; pm = lx; }
+  }
+
+/* path(s) parameters */
+if ( ! ch_f ) ch = n - 1;
+mc = n - 1;
+
+ /* artifical source parameters */
+if ( s_f )          
+   { m0 += n; n0 ++ ; 
+     if ( ! sm_f ) sm = sl;
+     if ( sl < sm ) { lx = sl; sl = sm; sm = lx; }
+   }
+
+/*----- printing title -----*/
+
+printf ("c acyclic network for shortest paths problem\n");
+printf ("c extended DIMACS format\nc\n" );
+
+
+/* name of the problem */
+printf ("t ac_%ld_%ld_%ld_", n, m, seed );
+if ( l_f )
+  printf ("%c", 'l');
+if ( c_f )
+  printf ("%c", 'c');
+if ( s_f )
+  printf ("%c", 's');
+if ( p_f )
+  printf ("%c", 'p');
+printf ("\nc\n");
+
+/* printing additional information  */
+if ( l_f )
+  printf ("c length -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
+           lm, ll, ln, ls );
+if ( c_f )
+  printf ("c path(s) -> number of arcs: %ld arc length: %ld\n",
+           ch, cl );
+if ( s_f )
+  printf ("c length of arcs from artifical source -> min: %ld max: %ld\n",
+           sm, sl );
+if ( p_f )
+  {
+  printf ("c potentials -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
+	  pm, pl, pn, ps );
+  if ( pa_f )
+  printf ("c potentials -> part of alternative distribution: %.2f k: %.2f\n",
+          pap, pac );
+  }
+printf ("c\n" );
+
+printf ("p sp %8ld %8ld\nc\n", n0, m0 );
+
+source = ( s_f ) ? n0 : 1;
+printf ("n %8ld\nc\n", source );
+
+
+if ( p_f ) /* generating potentials */
+  {
+    seed1 = 2*seed + 1;
+    p = (long*) calloc ( n+2, sizeof (long) );
+    init_rand ( seed1);
+    pl = pl - pm + 1;
+
+    for ( i = 0; i <= n; i ++ )
+      {
+	p_t = pm + nrand ( pl );
+	if ( pn_f ) p_t += (long) ( i * pn );
+	if ( ps_f ) p_t += (long) ( i * ( i * ps ));
+	if ( pap_f )
+	    if ( rand01() < pap )
+		p_t = (long) ( p_t * pac );
+        p[i] = p_t;
+      }
+    p[n+1] = 0;
+  }
+
+
+if ( s_f ) /* additional arcs from artifical source */
+  {
+    seed2 = 3*seed + 1;
+    init_rand ( seed2 );
+    sl = sl - sm + 1;
+
+    for ( i = n; i > 1; i -- )
+      {
+	s = sm + nrand ( sl );
+	PRINT_ARC ( n0, i, s ) 
+      }
+
+    PRINT_ARC ( n0, 1, 0 )
+  }
+
+/* initialize random number generator */
+init_rand ( seed );
+ll = ll - lm + 1;
+
+/* generating connecting path(s) */
+for ( i = 1; i < n; i ++ )
+  {
+    if ( ( (i-1) % ch ) != 0 )
+      i0 = i;
+    else
+      i0 = 1;
+
+      if (c_rand)
+        cl = lm + nrand(ll);
+      PRINT_ARC ( i0, i+1, cl )
+  }
+
+/* generating random arcs */
+
+
+for ( k = 1; k <= m - mc; k ++ )
+  {
+    i = 1 + nrand ( n );
+
+    do
+    j = 1 + nrand ( n );
+    while ( j == i );
+
+    if ( i > j )
+      { i0 = i; i = j; j = i0; }
+
+    dij = j - i;
+    l = lm + nrand ( ll );
+    if ( ln_f ) l += (long) ( dij * ln );
+    if ( ls_f ) l += (long) ( dij * ( dij * ls ) );
+    PRINT_ARC ( i, j, l );
+  }
+
+/* all is done */
+exit (ext);
+
+/* ----- wrong usage ----- */
+
+ usage:
+fprintf ( stderr,
+"\nusage: %s  n  m  seed  [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
+help:  %s -h\n\n", argv[0], argv[0] );
+
+if ( np > 0 )
+  fprintf ( stderr, "error in parameter # %d\n\n", np );   
+exit (4);
+
+/* ---- help ---- */
+
+ help:
+
+if ( args[2] == 'h') goto hhelp;
+
+fprintf ( stderr, 
+"\n'%s' - acyclic network generator for shortest paths problem.\n\
+Generates problems in extended DIMACS format.\n\
+\n\
+   %s  n m seed [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
+   %s -hh\n\
+\n\
+                        #i - integer number   #f - real number\n\
+\n\
+-ll#i  - #i is the upper bound on arc lengths          (default 10000)\n\
+-lm#i  - #i is the lower bound on arc lengths          (default 0)\n\
+-cl#i  - #i is length of arcs in connecting path(s)    (default random)\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\
+\n\
+-hh    - extended help \n\n",
+argv[0], argv[0], argv[0] );
+
+exit (0);
+
+/* --------- sophisticated help ------------ */
+ hhelp:
+
+if ( argc < 3 )
+     fout = stderr;
+else
+     fout = fopen ( argv[2], "w" );
+
+if ( fout == NULL )
+{ fprintf ( stderr, "\nCan't open file  '%s' for writing help\n\n", argv[2] );
+  exit ( 2 );
+}
+
+fprintf (fout, 
+"\n'%s' - acyclic network generator for shortest paths problem.\n\
+Generates problems in extended DIMACS format.\n\
+\n\
+   %s  n m seed [ -ll#i -lm#i -ln#f -ls#f\n\
+                      -p  -pl#i -pm#i -pn#f -ps#f -pap#i -pac#f\n\
+                      -cl#i -ch#i\n\
+                      -s  -sl#i -sm#i\n\
+                    ]\n\
+   %s -hh file_name\n\
+\n\
+                        #i - integer number   #f - real number\n\
+\n\
+      Arc length parameters:\n\
+-ll#i  - #i is the upper bound on arc lengths          (default 10000)\n\
+-lm#i  - #i is the lower bound on arc lengths          (default 0)\n\
+-ln#f  - multipliy l(i, j) by #f * |i-j|               (default 0)\n\
+-ls#f  - multipliy l(i, j) by #f * |i-j|^2             (default 0)\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 * i                       (default 0)\n\
+-ps#f  - multiply p(i) by #f * i^2                     (default 0)\n\
+-pap#i - percentage of alternative potential nodes     (default 0)\n\
+-pac#f - if i is alternative, multiply  p(i) by #f     (default -1)\n\
+\n\
+      Connecting path(s) parameters:\n\
+-cl#i  - #i is length of arcs in connecting path(s)   (default random)\n\
+-ch#i  - #i is length of connecting path(s)           (default n-1)\n\
+\n\
+      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\
+\n\
+-hh file_name  - save this help in the file 'file_name'\n\n",
+argv[0], argv[0], argv[0] );
+
+exit (0);
+}
+
+
+
diff --git a/isisd/topology/spgrid.c b/isisd/topology/spgrid.c
new file mode 100644
index 00000000..22d3a804
--- /dev/null
+++ b/isisd/topology/spgrid.c
@@ -0,0 +1,729 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <values.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)
+
+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,
+       y1, y2, yp,
+       dl, dx, xn, yn, 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, 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  =  (long) atof ( &args[3] );
+            break;
+          case 'm': /* lower bound */
+            cm_f = 1;
+            cm  = (long ) atof ( &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  =  (long) atof ( &args[3] );
+            break;
+          case 'm': /* lower bound */
+            am_f = 1;
+            am  = (long ) atof ( &args[3] );
+            break;
+          case 'x': /* number of additional arcs */
+            ax_f = 1;
+            ax   = (long ) atof ( &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  =  (long) atof ( &args[3] );
+            break;
+          case 'm': /* lower bound */
+            im_f = 1;
+            im  = (long ) atof ( &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  =  (long) atof ( &args[3] );
+            break;
+          case 'm': /* lower bound of art. arc */
+            sm_f = 1;
+            sm  =  (long) atof ( &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  =  (long) atof ( &args[3] );
+            break;
+          case 'm': /* lower bound */
+            pm_f = 1;
+            pm  = (long ) atof ( &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)MAXLONG || m >= (double)MAXLONG )
+  {
+    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 -- )
+       {
+         y1 = nrand ( Y );
+         do
+            y2 = nrand ( Y );
+         while ( y2 == y1 );
+         i  = NODE ( x, y1 );
+         j  = NODE ( x, y2 );
+         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 )
+  	    {
+  	      yp = nrand(Y-y);
+  	      yn = mess[ yp ];
+                mess[ yp ] = mess[ Y - y - 1 ];
+  	    }
+  	  else
+               yn =  y;
+  	  j = NODE ( xn, yn );
+  	  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;
+}
+
+
+
diff --git a/isisd/topology/spgrid.h b/isisd/topology/spgrid.h
new file mode 100644
index 00000000..f96c00f3
--- /dev/null
+++ b/isisd/topology/spgrid.h
@@ -0,0 +1,45 @@
+/*
+ * IS-IS Rout(e)ing protocol - topology/spgrid.h
+                               Routines for manipulation of SSN and SRM flags
+ * Copyright (C) 2001 Sampo Saaristo, Ofer Wald
+ *
+ * This program is free software; you can redistribute it and/or modify it 
+ * under the terms of the GNU General Public Licenseas published by the Free 
+ * Software Foundation; either version 2 of the License, or (at your option) 
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful,but WITHOUT 
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for 
+ * more details.
+
+ * You should have received a copy of the GNU General Public License along 
+ * with this program; if not, write to the Free Software Foundation, Inc., 
+ * 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ */
+
+/*
+ * Based on:
+ * SPLIB Copyright C 1994 by Cherkassky, Goldberg, and Radzik
+ *
+ */
+#ifndef _ZEBRA_ISIS_TOPOLOGY_SPGRID_H
+#define _ZEBRA_ISIS_TOPOLOGY_SPGRID_H
+
+struct arc {
+  long from_node;
+  long to_node;
+  long distance;
+};
+
+int           gen_spgrid_topology (struct vty *vty, struct list *topology);
+int           spgrid_check_params (struct vty *vty, int argc, char **argv);
+
+
+#endif /* _ZEBRA_ISIS_TOPOLOGY_SPGRID_H */
+
+
+
+
+
+
diff --git a/isisd/topology/sprand.c b/isisd/topology/sprand.c
new file mode 100644
index 00000000..28b58b30
--- /dev/null
+++ b/isisd/topology/sprand.c
@@ -0,0 +1,499 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <values.h>
+
+#include "random.c"
+
+#define DASH '-'
+#define VERY_FAR 100000000
+
+/* generator of random networks for the shortest paths problem;
+   extended DIMACS format for output */
+
+main ( argc, argv )
+
+int argc;
+char* argv[];
+
+{
+
+char   args[30];
+
+long   n,
+       n0,
+       source,
+       i,
+       i0,
+       j,
+       dij;
+
+long   m,
+       m0,
+       mc,
+       k;
+
+long   *p,
+       p_t,
+       l,
+       lx;
+
+long   seed,
+       seed1,
+       seed2;
+
+int    ext=0;
+
+FILE   *fout;
+
+/* variables for lengths generating */
+/* initialized by default values */
+int    l_f = 0, ll_f = 0, lm_f = 0, ln_f = 0, ls_f = 0;
+long   ll = 10000,    /* length of the interval */
+       lm = 0;        /* minimal bound of the interval */
+double ln = 0,        /* l += ln * |i-j| */ 
+       ls = 0;        /* l += ls * |i-j|^2 */
+
+/* variables for connecting cycle(s) */
+int    c_f = 0, cl_f = 0, ch_f = 0, c_random = 1;
+long   cl = 1;        /* length of cycle arc */
+long   ch;            /* number of arcs in the cycle 
+                         n - by default */
+
+/* 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,
+       pa_f = 0, pap_f = 0, pac_f = 0;
+long   pl,            /* length of the interval */
+       pm;            /* minimal bound of the interval */
+double pn = 0,        /* l += ln * |i-j| */ 
+       ps = 0,        /* l += ls * |i-j|^2 */
+       pap = 0,       /* part of nodes with alternative dustribution */
+       pac = -1;      /* multiplier for alternative distribution */
+
+int np;               /* number of parameter parsing now */
+
+#define PRINT_ARC( i, j, length )\
+{\
+l = length;\
+if ( p_f ) l += ( p[i] - p[j] );\
+printf ("a %8ld %8ld %12ld\n", i, j, l );\
+}
+
+  /* parsing  parameters */
+
+if ( argc < 2 ) goto usage;
+
+np = 0;
+
+strcpy ( args, argv[1] );
+
+  if ( ( args[0] == DASH ) && ( args[1] == 'h')
+     )
+      goto help;
+
+if ( argc < 4 ) goto usage;
+
+/* first parameter - number of nodes */
+np = 1;
+if ( ( n = atoi ( argv[1] ) )  <  2  )  goto usage;
+
+/* second parameter - number of arcs */
+np = 2;
+if ( ( m = atoi ( argv[2] ) )  <  n  )  goto usage;
+
+/* third parameter - seed */
+np=3;
+if ( ( seed = atoi ( argv[3] ) )  <=  0  )  goto usage;
+
+/* other parameters */
+
+for ( np = 4; np < argc; np ++ )
+  {
+    strcpy ( args, argv[np] );
+    if ( args[0] != DASH ) goto usage;
+
+    switch ( args[1] )
+      {
+
+      case 'l' : /* an interval for arc length */
+	l_f = 1;
+	switch ( args[2] )
+	  { 
+	  case 'l': /* length of the interval */
+	    ll_f = 1;
+	    ll  =  (long) atof ( &args[3] );
+	    break;
+	  case 'm': /* minimal bound */
+	    lm_f = 1;
+	    lm  = (long ) atof ( &args[3] );
+	    break;
+	  case 'n': /* additional length: l*|i-j| */
+	    ln_f = 1;
+	    ln  = atof ( &args[3] );
+	    break;
+	  case 's': /* additional length: l*|i-j|^2 */
+	    ls_f = 1;
+	    ls  = atof ( &args[3] );
+	    break;
+	  default:  /* unknown switch  value */
+	    goto usage;
+	  }
+	break;
+
+      case 'c' : /* connecting cycle(s) */
+        c_f = 1;
+	switch ( args[2] )
+	  { 
+	  case 'l':
+            c_random = 0;
+	    cl_f = 1;
+	    cl  =  (long) atof ( &args[3] );
+            if ( cl < 0 ) goto usage;
+	    break;
+	  case 'h':
+	    ch_f = 1;
+	    ch  =  (long) atof ( &args[3] );
+            if ( ch < 2 || ch > n ) goto usage;
+	    break;
+	  default:  /* unknown switch  value */
+	    goto usage;
+          }
+	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  =  (long) atof ( &args[3] );
+            break;
+	  case 'm': /* lower bound of art. arc */
+	    sm_f = 1;
+	    sm  =  (long) atof ( &args[3] );
+            break;
+	  default:  /* unknown switch  value */
+	    goto usage;
+          }
+         }
+	break;
+
+      case 'p' : /* potentials */
+	p_f = 1;
+	if ( strlen ( args ) > 2 )
+	{  
+	switch ( args[2] )
+	  { 
+	  case 'l': /* length of the interval */
+	    pl_f = 1;
+	    pl  =  (long) atof ( &args[3] );
+	    break;
+	  case 'm': /* minimal bound */
+	    pm_f = 1;
+	    pm  = (long ) atof ( &args[3] );
+	    break;
+	  case 'n': /* additional length: l*|i-j| */
+	    pn_f = 1;
+	    pn  = atof ( &args[3] );
+	    break;
+	  case 's': /* additional length: l*|i-j|^2 */
+	    ps_f = 1;
+	    ps  = atof ( &args[3] );
+	    break;
+	  case 'a': /* bipolar distribution */
+	    pa_f = 1;
+	    switch ( args[3] )
+	      {
+	      case 'p': /* % of alternative potentials */
+                pap_f = 1;
+                pap  = atof ( &args[4] );
+		if ( pap < 0   ) pap = 0;
+		if ( pap > 100 ) pap = 100;
+                pap /= 100;
+		break;
+	      case 'c': /* multiplier */
+		pac_f = 1;
+		pac = atof ( &args[4] );
+		break;
+	      default: /* unknown switch value */
+		goto usage;
+	      }
+	    break;
+	  default:  /* unknown switch  value */
+	    goto usage;
+	  }
+      }
+	break;
+
+      default  : /* unknoun case */
+	goto usage;
+      }
+  }
+   
+
+/* ----- ajusting parameters ----- */
+
+n0 = n; m0 = m;
+
+/* length parameters */
+if ( ll < lm ) { lx = ll; ll = lm; lm = lx; }
+
+/* potential parameters */
+if ( p_f )
+  {
+   if ( ! pl_f ) pl = ll;
+   if ( ! pm_f ) pm = lm;
+   if ( pl < pm ) { lx = pl; pl = pm; pm = lx; }
+  }
+
+/* path(s) parameters */
+if ( ! ch_f ) ch = n;
+
+mc = n + (n-2) / (ch-1);
+if ( mc > m ) 
+  { fprintf ( stderr,
+              "Error: not enough arcs for generating connecting cycle(s)\n" );
+    exit (4);
+  }
+
+ /* artifical source parameters */
+if ( s_f )          
+   { m0 += n; n0 ++ ; 
+     if ( ! sm_f ) sm = sl;
+     if ( sl < sm ) { lx = sl; sl = sm; sm = lx; }
+   }
+
+/* printing title */
+printf ("c random network for shortest paths problem\n");
+printf ("c extended DIMACS format\nc\n" );
+
+/* name of the problem */
+printf ("t rd_%ld_%ld_%ld_", n, m, seed );
+if ( l_f )
+  printf ("%c", 'l');
+if ( c_f )
+  printf ("%c", 'c');
+if ( s_f )
+  printf ("%c", 's');
+if ( p_f )
+  printf ("%c", 'p');
+printf ("\nc\n");
+
+/* printing additional information  */
+if ( l_f )
+  printf ("c length -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
+           lm, ll, ln, ls );
+if ( c_f )
+  {
+    if ( c_random )
+      printf ("c cycle -> number of arcs: %ld  arc length: random\n", ch);
+    else
+      printf ("c cycle -> number of arcs: %ld  arc length: %ld\n",
+	       ch, cl );
+  }
+if ( s_f )
+  printf ("c length of arcs from artifical source -> min: %ld max: %ld\n",
+           sm, sl );
+if ( p_f )
+  {
+  printf ("c potentials -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
+	  pm, pl, pn, ps );
+  if ( pa_f )
+  printf ("c potentials -> part of alternative distribution: %.2f k: %.2f\n",
+          pap, pac );
+  }
+printf ("c\n" );
+
+
+printf ("p sp %8ld %8ld\nc\n", n0, m0 );
+
+source = ( s_f ) ? n0 : 1;
+printf ("n %8ld\nc\n", source );
+
+if ( p_f ) /* generating potentials */
+  {
+    p = (long*) calloc ( n+2, sizeof (long) );
+    seed1 = 2*seed + 1;
+    init_rand ( seed1);
+    pl = pl - pm + 1;
+
+    for ( i = 0; i <= n; i ++ )
+      {
+	p_t = pm + nrand ( pl );
+	if ( pn_f ) p_t += (long) ( i * pn );
+	if ( ps_f ) p_t += (long) ( i * ( i * ps ));
+	if ( pap_f )
+	    if ( rand01() < pap )
+		p_t = (long) ( p_t * pac );
+        p[i] = p_t;
+      }
+    p[n+1] = 0;
+  }
+
+
+if ( s_f ) /* additional arcs from artifical source */
+  {
+    seed2 = 3*seed + 1;
+    init_rand ( seed2 );
+    sl = sl - sm + 1;
+
+    for ( i = n; i > 1; i -- )
+      {
+	s = sm + nrand ( sl );
+	PRINT_ARC ( n0, i, s ) 
+      }
+
+    PRINT_ARC ( n0, 1, 0 )
+  }
+
+/* initialize random number generator */
+init_rand ( seed );
+ll = ll - lm + 1;
+
+/* generating connecting cycle(s) */
+if (c_random)
+  cl = lm + nrand ( ll );
+PRINT_ARC ( 1, 2, cl )
+if (c_random)
+  cl = lm + nrand ( ll );
+PRINT_ARC ( n, 1, cl )
+
+for ( i = 2; i < n; i ++ )
+  {
+    if (c_random)
+      cl = lm + nrand ( ll );
+
+    if ( ( (i-1) % (ch-1) ) != 0 )
+        PRINT_ARC ( i, i+1, cl )
+    else
+      { PRINT_ARC ( i,   1, cl )
+        if (c_random)
+          cl = lm + nrand ( ll );
+	PRINT_ARC ( 1, i+1, cl )
+      }
+  }
+
+/* generating random arcs */
+
+for ( k = 1; k <= m - mc; k ++ )
+  {
+    i = 1 + nrand ( n );
+
+    do
+    j = 1 + nrand ( n );
+    while ( j == i );
+
+    dij = ( i > j ) ? ( i - j ) : ( j - i );
+    l = lm + nrand ( ll );
+    if ( ln_f ) l += (long) ( dij * ln );
+    if ( ls_f ) l += (long) ( dij * ( dij * ls ) );
+    PRINT_ARC ( i, j, l );
+  }
+
+/* all is done */
+exit (ext);
+
+/* ----- wrong usage ----- */
+
+ usage:
+fprintf ( stderr,
+"\nusage: %s  n  m  seed  [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
+help:  %s -h\n\n", argv[0], argv[0] );
+
+if ( np > 0 )
+  fprintf ( stderr, "error in parameter # %d\n\n", np );   
+exit (4);
+
+/* ---- help ---- */
+
+ help:
+
+if ( args[2] == 'h') goto hhelp;
+
+fprintf ( stderr, 
+"\n'%s' - random network generator for shortest paths problem.\n\
+Generates problems in extended DIMACS format.\n\
+\n\
+   %s  n m seed [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
+   %s -hh\n\
+\n\
+                        #i - integer number   #f - real number\n\
+\n\
+-ll#i  - #i is the upper bound on arc lengths          (default 10000)\n\
+-lm#i  - #i is the lower bound on arc lengths          (default 0)\n\
+-cl#i  - #i is length of arcs in connecting cycle(s)   (default random)\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\
+\n\
+-hh    - extended help \n\n",
+argv[0], argv[0], argv[0] );
+
+exit (0);
+
+/* --------- sophisticated help ------------ */
+ hhelp:
+
+if ( argc < 3 )
+     fout = stderr;
+else
+     fout = fopen ( argv[2], "w" );
+
+if ( fout == NULL )
+{ fprintf ( stderr, "\nCan't open file  '%s' for writing help\n\n", argv[2] );
+  exit ( 2 );
+}
+
+fprintf (fout, 
+"\n'%s' - random network generator for shortest paths problem.\n\
+Generates problems in extended DIMACS format.\n\
+\n\
+   %s  n m seed [ -ll#i -lm#i -ln#f -ls#f\n\
+                      -p  -pl#i -pm#i -pn#f -ps#f -pap#i -pac#f\n\
+                      -cl#i -ch#i\n\
+                      -s -sl#i -sm#i\n\
+                    ]\n\
+   %s -hh file_name\n\
+\n\
+                        #i - integer number   #f - real number\n\
+\n\
+      Arc length parameters:\n\
+-ll#i  - #i is the upper bound on arc lengths          (default 10000)\n\
+-lm#i  - #i is the lower bound on arc lengths          (default 0)\n\
+-ln#f  - multipliy l(i, j) by #f * |i-j|               (default 0)\n\
+-ls#f  - multipliy l(i, j) by #f * |i-j|^2             (default 0)\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 * i                       (default 0)\n\
+-ps#f  - multiply p(i) by #f * i^2                     (default 0)\n\
+-pap#i - percentage of alternative potential nodes     (default 0)\n\
+-pac#f - if i is alternative, multiply  p(i) by #f     (default -1)\n\
+\n\
+      Connecting cycle(s) parameters:\n\
+-cl#i  - #i is length of arcs in connecting cycle(s)   (default random)\n\
+-ch#i  - #i is length of connecting cycles             (default n)\n\
+\n\
+      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\
+\n\
+-hh file_name  - save this help in the file 'file_name'\n\n",
+argv[0], argv[0], argv[0] );
+
+exit (0);
+}
+
+
+