From eb5d44eb8dcf25a1b328e57d1eabb1f89e3bc59b Mon Sep 17 00:00:00 2001 From: jardin Date: Tue, 23 Dec 2003 08:09:43 +0000 Subject: Initial revision --- isisd/topology/Makefile.am | 23 ++ isisd/topology/random.c | 154 ++++++++++ isisd/topology/spacyc.c | 483 ++++++++++++++++++++++++++++++ isisd/topology/spgrid.c | 729 +++++++++++++++++++++++++++++++++++++++++++++ isisd/topology/spgrid.h | 45 +++ isisd/topology/sprand.c | 499 +++++++++++++++++++++++++++++++ 6 files changed, 1933 insertions(+) create mode 100644 isisd/topology/Makefile.am create mode 100644 isisd/topology/random.c create mode 100644 isisd/topology/spacyc.c create mode 100644 isisd/topology/spgrid.c create mode 100644 isisd/topology/spgrid.h create mode 100644 isisd/topology/sprand.c (limited to 'isisd/topology') 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: , */ +/* depends on compiler and OS */ +/* */ +/*********************************************************************/ + +#include +#include + +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 +#include +#include +#include + +#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 +#include +#include +#include + +#include "random.c" + +#include + +#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 +#include +#include +#include + +#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); +} + + + -- cgit v1.2.1