diff options
author | jardin <jardin> | 2003-12-23 08:09:43 +0000 |
---|---|---|
committer | jardin <jardin> | 2003-12-23 08:09:43 +0000 |
commit | eb5d44eb8dcf25a1b328e57d1eabb1f89e3bc59b (patch) | |
tree | 2973e8563fcbd4a8cf901d211ff4f8de00c36381 /isisd/topology/spgrid.c | |
parent | 3dbf99698a3be2e920871c3127ea089e061a127c (diff) |
Initial revision
Diffstat (limited to 'isisd/topology/spgrid.c')
-rw-r--r-- | isisd/topology/spgrid.c | 729 |
1 files changed, 729 insertions, 0 deletions
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; +} + + + |