Initial revision
diff --git a/isisd/topology/Makefile.am b/isisd/topology/Makefile.am
new file mode 100644
index 0000000..045c15c
--- /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 0000000..d4ef995
--- /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 0000000..8531447
--- /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 0000000..22d3a80
--- /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 0000000..f96c00f
--- /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 0000000..28b58b3
--- /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);
+}
+
+
+