![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to spgrid.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / isisd / topology|
Return to spgrid.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / isisd / topology |
1.1 misho 1: #include <stdio.h>
2: #include <stdlib.h>
3: #include <string.h>
4:
5: #include "random.c"
6:
7: #include <zebra.h>
8:
9: #include "thread.h"
10: #include "vty.h"
11: #include "log.h"
12: #include "linklist.h"
13:
14: #include "spgrid.h"
15:
16:
17: #define DASH '-'
18: #define VERY_FAR 100000000
19:
20: #define DOUBLE_CYCLE 0
21: #define CYCLE 1
22: #define PATH 2
23:
24: #define NO 0
25: #define YES 1
26:
27: #define NODE( x, y ) (x*Y + y + 1)
28:
29: /*
30: * Prototypes.
31: */
32: void free_arc(void *);
33: void help(struct vty *);
34: void print_arc(struct vty *, struct list *, long, long, long);
35: void hhelp(struct vty *);
36: void usage(struct vty *);
37:
38: const char *graph_type[] = {
39: "double cycle",
40: "cycle",
41: "path"
42: };
43:
44: struct arc *arc;
45:
46: char args[30];
47:
48: long X, /* horizontal size of grid */
49: Y; /* vertical size of grid */
50:
51: long x,
52: y,
53: y1, y2, yp,
54: dl, dx, xn, yn, count,
55: *mess;
56:
57: double n;
58: long n0,
59: source,
60: i,
61: i0,
62: j,
63: dij;
64:
65: double m;
66: long m0,
67: mc,
68: k;
69:
70: long *p,
71: p_t,
72: l,
73: lx;
74:
75: long seed,
76: seed1,
77: seed2;
78:
79: int ext=0;
80:
81: /* initialized by default values */
82:
83: /* variables for generating one layer */
84:
85: /* variables for generating spanning graph */
86: int c_f = 0, cw_f = 0, cm_f = 0, cl_f = 0;
87:
88: int cw = DOUBLE_CYCLE; /* type of spanning graph */
89: long cm = 0, /* lower bound of the interval */
90: cl = 100; /* upper bound of the interval */
91:
92: /* variables for generating additional arcs */
93: int a_f = 0, ax_f = 0, am_f = 0, al_f = 0;
94:
95: long ax = 0, /* number of additional arcs */
96: am = 0, /* lower bound of the interval */
97: al = 100; /* upper bound of the interval */
98:
99: /* variables for inter-layer arcs */
100: int i_f = 0, ip_f = 0, ix_f = 0, ih_f = 0,
101: im_f = 0, il_f = 0, in_f = 0, is_f = 0;
102:
103: int ip = NO; /* to mess or not to mess */
104: long ix = 1, /* number of interlayered arcs in a NODE */
105: ih = 1, /* step between two layeres */
106: il = 10000, /* upper bound of the interval */
107: im = 1000; /* lower bound of the interval */
108: double in = 1, /* l *= in * |x1-x2| */
109: is = 0; /* l *= is * |x1-x2|^2 */
110:
111: /* variables for artifical source */
112: int s_f = 0, sl_f = 0, sm_f = 0;
113: long sl = VERY_FAR, /* upper bound of artifical arc */
114: sm, /* lower bound of artifical arc */
115: s;
116:
117: /* variables for potentials */
118: int p_f = 0, pl_f = 0, pm_f = 0, pn_f = 0, ps_f = 0;
119:
120: long pl, /* upper bound of the interval */
121: pm; /* lower bound of the interval */
122: double pn = 0, /* p += ln * (x+1) */
123: ps = 0; /* p += ls * (x+1)^2 */
124:
125: int np; /* number of parameter parsing now */
126:
127:
128: void
129: free_arc (void *val) {
130: free(val);
131: }
132:
133: void
134: print_arc (struct vty *vty, struct list *topology, long i, long j, long length)
135: {
136: struct arc *myarc;
137:
138: l = length;
139: if ( p_f ) l += ( p[i] - p[j] );
140: // vty_out (vty,"a %8ld %8ld %12ld%s", i, j, l ,VTY_NEWLINE);
141: myarc = malloc (sizeof(struct arc));
142: myarc->from_node = i;
143: myarc->to_node = j;
144: myarc->distance = l;
145: topology->del = free_arc;
146: listnode_add (topology, myarc);
147: }
148:
149: /* ---- help ---- */
150: void
151: help (struct vty *vty) {
152: // if ( args[2] == 'h') hhelp (vty);
153: vty_out (vty,"grid network generator for shortest paths problem.%s",VTY_NEWLINE);
154: vty_out (vty,"Generates problems in extended DIMACS format.%s",VTY_NEWLINE);
155: 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);
156: vty_out (vty,"#i - integer number%s",VTY_NEWLINE);
157: vty_out (vty,"-cl#i - #i is the upper bound on layer arc lengths (default 100)%s",VTY_NEWLINE);
158: vty_out (vty,"-cm#i - #i is the lower bound on layer arc lengths (default 0)%s",VTY_NEWLINE);
159: vty_out (vty,"-c#t - #t is the type of connecting graph: { c | d | p }%s",VTY_NEWLINE);
160: vty_out (vty," c - cycle, d - double cycle, p - path (default d)%s",VTY_NEWLINE);
161: vty_out (vty,"-ip - shuffle inter-layer arcs (default NO)%s",VTY_NEWLINE);
162: vty_out (vty,"-il#i - #i is the upper bound on inter-layer arc lengths (default 10000)%s",VTY_NEWLINE);
163: vty_out (vty,"-im#i - #i is the lower bound on inter-layer arc lengths (default 1000)%s",VTY_NEWLINE);
164: vty_out (vty,"-p - generate potentials%s",VTY_NEWLINE);
165: vty_out (vty,"-pl#i - #i is the upper bound on potentials (default il)%s",VTY_NEWLINE);
166: vty_out (vty,"-pm#i - #i is the lower bound on potentials (default im)%s",VTY_NEWLINE);
167: vty_out (vty,"%s",VTY_NEWLINE);
168: vty_out (vty,"-hh - extended help%s",VTY_NEWLINE);
169: }
170:
171: /* --------- sophisticated help ------------ */
172: void
173: hhelp (struct vty *vty) {
174: /*
175: zlog_info (
176: "\n'%s' - grid network generator for shortest paths problem.\n\
177: Generates problems in extended DIMACS format.\n\
178: \n\
179: %s X Y seed [ -cl#i -cm#i -c{c|d|p}\n\
180: -ax#i -al#i -am#i\n\
181: -ip -il#i -im#i -in#i -is#i -ix#i -ih#i\n\
182: -p -pl#i -pm#i -pn#f -ps#f\n\
183: -s -sl#i -sm#i\n\
184: ]\n\
185: %s -hh file_name\n\
186: \n\
187: #i - integer number #f - real number\n\
188: \n\
189: Parameters of connecting arcs within one layer:\n\
190: -cl#i - #i is the upper bound on arc lengths (default 100)\n\
191: -cm#i - #i is the lower bound on arc lengths (default 0)\n\
192: -c#t - #t is the type of connecting graph: { c | d | p }\n\
193: c - cycle, d - double cycle, p - path (default d)\n\
194: \n\
195: Parameters of additional arcs within one layer:\n\
196: -ax#i - #i is the number of additional arcs (default 0)\n\
197: -al#i - #i is the upper bound on arc lengths (default 100)\n\
198: -am#i - #i is the lower bound on arc lengths (default 0)\n\
199: \n\
200: Interlayerd arc parameters:\n\
201: -ip - shuffle inter-layer arcs (default NO)\n\
202: -il#i - #i is the upper bound on arc lengths (default 10000)\n\
203: -im#i - #i is the lower bound on arc lengths (default 1000)\n\
204: -in#f - multiply l(i, j) by #f * x(j)-x(i) (default 1)\n\
205: if #f=0 - don't multiply\n\
206: -is#f - multiply l(i, j) by #f * (x(j)-x(i))^2 (default NO)\n\
207: -ix#i - #i - is the number of arcs from a node (default 1)\n\
208: -ih#i - #i - is the step between connected layers (default 1)\n\
209: \n\
210: Potential parameters:\n\
211: -p - generate potentials \n\
212: -pl#i - #i is the upper bound on potentials (default ll)\n\
213: -pm#i - #i is the lower bound on potentials (default lm)\n\
214: -pn#f - multiply p(i) by #f * x(i) (default NO)\n\
215: -ps#f - multiply p(i) by #f * x(i)^2 (default NO)\n\
216: \n");
217: zlog_info (
218: " Artificial source parameters:\n\
219: -s - generate artificial source with default connecting arc lengths\n\
220: -sl#i - #i is the upper bound on art. arc lengths (default 100000000)\n\
221: -sm#i - #i is the lower bound on art. arc lengths (default sl)\n\"
222: );*/
223: }
224:
225: /* ----- wrong usage ----- */
226: void
227: usage (struct vty *vty) {
228: vty_out (vty,"usage: X Y seed [-ll#i -lm#i -cl#i -p -pl#i -pm#i ...]%s",VTY_NEWLINE);
229: vty_out (vty,"help: -h or -hh%s",VTY_NEWLINE);
230:
231: if ( np > 0 )
232: zlog_err ("error in parameter # %d\n\n", np );
233: }
234:
235:
236: /* parsing parameters */
237: /* checks the validity of incoming parameters */
238: int
239: spgrid_check_params ( struct vty *vty, int argc, const char **argv)
240: {
241: /* initialized by default values */
242: ext=0;
243:
244: /* variables for generating one layer */
245:
246: /* variables for generating spanning graph */
247: c_f = 0;
248: cw_f = 0;
249: cm_f = 0;
250: cl_f = 0;
251:
252: cw = PATH; /* type of spanning graph */
253: cm = 0; /* lower bound of the interval */
254: cl = 63; /* upper bound of the interval */
255:
256: /* variables for generating additional arcs */
257: a_f = 0;
258: ax_f = 0;
259: am_f = 0;
260: al_f = 0;
261:
262: ax = 0; /* number of additional arcs */
263: am = 0; /* lower bound of the interval */
264: al = 63; /* upper bound of the interval */
265:
266: /* variables for inter-layer arcs */
267: i_f = 0;
268: ip_f = 0;
269: ix_f = 0;
270: ih_f = 0;
271: im_f = 0;
272: il_f = 0;
273: in_f = 0;
274: is_f = 0;
275:
276: ip = NO; /* to mess or not to mess */
277: ix = 1; /* number of interlayered arcs in a NODE */
278: ih = 1; /* step between two layeres */
279: il = 63; //was 10000; /* upper bound of the interval */
280: im = 0; //was 1000; /* lower bound of the interval */
281: in = 1; /* l *= in * |x1-x2| */
282: is = 0; /* l *= is * |x1-x2|^2 */
283:
284: /* variables for artifical source */
285: s_f = 0;
286: sl_f = 0;
287: sm_f = 0;
288: sl = VERY_FAR; /* upper bound of artifical arc */
289:
290: /* variables for potentials */
291: p_f = 0;
292: pl_f = 0;
293: pm_f = 0;
294: pn_f = 0;
295: ps_f = 0;
296:
297: pn = 0; /* p += ln * (x+1) */
298: ps = 0; /* p += ls * (x+1)^2 */
299:
300:
301: if ( argc < 1 ) {
302: usage (vty);
303: return 1;
304: }
305:
306: np = 0;
307:
308: strcpy ( args, argv[0] );
309:
310: if ((args[0] == DASH) && (args[1] == 'h'))
311: help (vty);
312:
313: if ( argc < 3 ) {
314: usage (vty);
315: return 1;
316: }
317:
318: /* first parameter - horizontal size */
319: np = 1;
320: if ( ( X = atoi ( argv[0] ) ) < 1 ) {
321: usage (vty);
322: return 1;
323: }
324:
325: /* second parameter - vertical size */
326: np = 2;
327: if ( ( Y = atoi ( argv[1] ) ) < 1 ) {
328: usage (vty);
329: return 1;
330: }
331:
332: /* third parameter - seed */
333: np=3;
334: if ( ( seed = atoi ( argv[2] ) ) <= 0 ) {
335: usage (vty);
336: return 1;
337: }
338:
339: /* other parameters */
340: for ( np = 3; np < argc; np ++ ) {
341: strcpy ( args, argv[np] );
342: if ( args[0] != DASH ) {
343: usage (vty);
344: return 1;
345: }
346:
347: switch ( args[1] ) {
348: case 'c' : /* spanning graph in one layer */
349: c_f = 1;
350: switch ( args[2] ) {
351: case 'l': /* upper bound of the interval */
352: cl_f = 1;
353: cl = atol ( &args[3] );
354: break;
355: case 'm': /* lower bound */
356: cm_f = 1;
357: cm = atol ( &args[3] );
358: break;
359: case 'c': /* type - cycle */
360: cw_f = 1;
361: cw = CYCLE;
362: break;
363: case 'd': /* type - double cycle */
364: cw_f = 1;
365: cw = DOUBLE_CYCLE;
366: break;
367: case 'p': /* type - path */
368: cw_f = 1;
369: cw = PATH;
370: break;
371:
372: default: /* unknown switch value */
373: usage (vty);
374: return 1;
375: }
376: break;
377:
378: case 'a' : /* additional arcs in one layer */
379: a_f = 1;
380: switch ( args[2] )
381: {
382: case 'l': /* upper bound of the interval */
383: al_f = 1;
384: al = atol ( &args[3] );
385: break;
386: case 'm': /* lower bound */
387: am_f = 1;
388: am = atol ( &args[3] );
389: break;
390: case 'x': /* number of additional arcs */
391: ax_f = 1;
392: ax = atol ( &args[3] );
393: if ( ax < 0 )
394: {
395: usage (vty);
396: return 1;
397: }
398: break;
399:
400: default: /* unknown switch value */
401: {
402: usage (vty);
403: return 1;
404: }
405: }
406: break;
407:
408:
409: case 'i' : /* interlayered arcs */
410: i_f = 1;
411:
412: switch ( args[2] )
413: {
414: case 'l': /* upper bound */
415: il_f = 1;
416: il = atol ( &args[3] );
417: break;
418: case 'm': /* lower bound */
419: im_f = 1;
420: im = atol ( &args[3] );
421: break;
422: case 'n': /* additional length: l *= in*|i1-i2| */
423: in_f = 1;
424: in = atof ( &args[3] );
425: break;
426: case 's': /* additional length: l *= is*|i1-i2|^2 */
427: is_f = 1;
428: is = atof ( &args[3] );
429: break;
430: case 'p': /* mess interlayered arcs */
431: ip_f = 1;
432: ip = YES;
433: break;
434: case 'x': /* number of interlayered arcs */
435: ix_f = 1;
436: ix = atof ( &args[3] );
437: if ( ix < 1 ) {
438: usage (vty);
439: return 1;
440: }
441: break;
442: case 'h': /* step between two layeres */
443: ih_f = 1;
444: ih = atof ( &args[3] );
445: if ( ih < 1 ) {
446: usage (vty);
447: return 1;
448: }
449: break;
450: default: /* unknown switch value */
451: usage (vty);
452: return 1;
453: }
454: break;
455:
456: case 's' : /* additional source */
457: s_f = 1;
458: if ( strlen ( args ) > 2 )
459: {
460: switch ( args[2] )
461: {
462: case 'l': /* upper bound of art. arc */
463: sl_f = 1;
464: sl = atol ( &args[3] );
465: break;
466: case 'm': /* lower bound of art. arc */
467: sm_f = 1;
468: sm = atol ( &args[3] );
469: break;
470: default: /* unknown switch value */
471: usage (vty);
472: return 1;
473: }
474: }
475: break;
476:
477: case 'p' : /* potentials */
478: p_f = 1;
479: if ( strlen ( args ) > 2 )
480: {
481: switch ( args[2] )
482: {
483: case 'l': /* upper bound */
484: pl_f = 1;
485: pl = atol ( &args[3] );
486: break;
487: case 'm': /* lower bound */
488: pm_f = 1;
489: pm = atol ( &args[3] );
490: break;
491: case 'n': /* additional: p *= pn*(x+1) */
492: pn_f = 1;
493: pn = atof ( &args[3] );
494: break;
495: case 's': /* additional: p = ps* (x+1)^2 */
496: ps_f = 1;
497: ps = atof ( &args[3] );
498: break;
499: default: /* unknown switch value */
500: usage (vty);
501: return 1;
502: }
503: }
504: break;
505:
506: default: /* unknoun case */
507: usage (vty);
508: return 1;
509: }
510: }
511:
512:
513: return 0;
514: }
515:
516:
517: /* generator of layered networks for the shortest paths problem;
518: extended DIMACS format for output */
519: int
520: gen_spgrid_topology (struct vty *vty, struct list *topology)
521: {
522: /* ----- ajusting parameters ----- */
523:
524: /* spanning */
525: if ( cl < cm ) { lx = cl; cl = cm; cm = lx; }
526:
527: /* additional arcs */
528: if ( al < am ) { lx = al; al = am; am = lx; }
529:
530: /* interlayered arcs */
531: if ( il < im ) { lx = il; il = im; im = lx; }
532:
533: /* potential parameters */
534: if ( p_f )
535: {
536: if ( ! pl_f ) pl = il;
537: if ( ! pm_f ) pm = im;
538: if ( pl < pm ) { lx = pl; pl = pm; pm = lx; }
539: }
540:
541: /* number of nodes and arcs */
542:
543: n = (double)X *(double)Y + 1;
544:
545: m = (double)Y; /* arcs from source */
546:
547: switch ( cw )
548: {
549: case PATH:
550: mc = (double)Y - 1;
551: break;
552: case CYCLE:
553: mc = (double)Y;
554: break;
555: case DOUBLE_CYCLE:
556: mc = 2*(double)Y;
557: }
558:
559: m += (double)X * (double)mc; /* spanning arcs */
560: m += (double)X * (double)ax; /* additional arcs */
561:
562: /* interlayered arcs */
563: for ( x = 0; x < X; x ++ )
564: {
565: dl = ( ( X - x - 1 ) + ( ih - 1 ) ) / ih;
566: if ( dl > ix ) dl = ix;
567: m += (double)Y * (double)dl;
568: }
569:
570: /* artifical source parameters */
571: if ( s_f ) {
572: m += n; n ++ ;
573: if ( ! sm_f ) sm = sl;
574: if ( sl < sm ) { lx = sl; sl = sm; sm = lx; }
575: }
576:
577: if ( n >= (double)LONG_MAX || m >= (double)LONG_MAX )
578: {
579: zlog_err ("Too large problem. It can't be generated\n");
580: exit (4);
581: }
582: else
583: {
584: n0 = (long)n; m0 = (long)m;
585: }
586:
587: if ( ip_f )
588: mess = (long*) calloc ( Y, sizeof ( long ) );
589:
590: /* printing title */
591: zlog_info ("Generating topology for ISIS");
592:
593: source = ( s_f ) ? n0-1 : n0;
594:
595: if ( p_f ) /* generating potentials */ {
596: p = (long*) calloc ( n0+1, sizeof (long) );
597: seed1 = 2*seed + 1;
598: init_rand ( seed1);
599: pl = pl - pm + 1;
600:
601: for ( x = 0; x < X; x ++ )
602: for ( y = 0; y < Y; y ++ ) {
603: p_t = pm + nrand ( pl );
604: if ( pn_f ) p_t *= (long) ( (1 + x) * pn );
605: if ( ps_f ) p_t *= (long) ( (1 + x) * ( (1 + x) * ps ));
606:
607: p[ NODE ( x, y ) ] = p_t;
608: }
609: p[n0] = 0;
610: if ( s_f ) p[n0-1] = 0;
611: }
612:
613: if ( s_f ) /* additional arcs from artifical source */
614: {
615: seed2 = 3*seed + 1;
616: init_rand ( seed2 );
617: sl = sl - sm + 1;
618:
619: for ( x = X - 1; x >= 0; x -- )
620: for ( y = Y - 1; y >= 0; y -- )
621: {
622: i = NODE ( x, y );
623: s = sm + nrand ( sl );
624: print_arc (vty, topology, n0, i, s );
625: }
626:
627: print_arc (vty, topology, n0, n0-1, 0 );
628: }
629:
630:
631: /* ----- generating arcs within layers ----- */
632:
633: init_rand ( seed );
634: cl = cl - cm + 1;
635: al = al - am + 1;
636:
637: for ( x = 0; x < X; x ++ )
638: {
639: /* generating arcs within one layer */
640: for ( y = 0; y < Y-1; y ++ )
641: {
642: /* generating spanning graph */
643: i = NODE ( x, y );
644: j = NODE ( x, y+1 );
645: l = cm + nrand ( cl );
646: print_arc (vty, topology, i, j, l );
647:
648: if ( cw == DOUBLE_CYCLE )
649: {
650: l = cm + nrand ( cl );
651: print_arc (vty, topology, j, i, l );
652: }
653: }
654:
655: if ( cw <= CYCLE )
656: {
657: i = NODE ( x, Y-1 );
658: j = NODE ( x, 0 );
659: l = cm + nrand ( cl );
660: print_arc (vty, topology, i, j, l );
661:
662: if ( cw == DOUBLE_CYCLE )
663: {
664: l = cm + nrand ( cl );
665: print_arc (vty, topology, j, i, l );
666: }
667: }
668:
669: /* generating additional arcs */
670:
671: for ( k = ax; k > 0; k -- )
672: {
673: y1 = nrand ( Y );
674: do
675: y2 = nrand ( Y );
676: while ( y2 == y1 );
677: i = NODE ( x, y1 );
678: j = NODE ( x, y2 );
679: l = am + nrand ( al );
680: print_arc (vty, topology, i, j, l );
681: }
682: }
683:
684: /* ----- generating interlayered arcs ------ */
685:
686: il = il - im + 1;
687:
688: /* arcs from the source */
689:
690: for ( y = 0; y < Y; y ++ )
691: {
692: l = im + nrand ( il );
693: i = NODE ( 0, y );
694: print_arc (vty, topology, source, i, l );
695: }
696:
697: for ( x = 0; x < X-1; x ++ )
698: {
699: /* generating arcs from one layer */
700: for ( count = 0, xn = x + 1;
701: count < ix && xn < X;
702: count ++, xn += ih )
703: {
704: if ( ip_f )
705: for ( y = 0; y < Y; y ++ )
706: mess[y] = y;
707:
708: for ( y = 0; y < Y; y ++ )
709: {
710: i = NODE ( x, y );
711: dx = xn - x;
712: if ( ip_f )
713: {
714: yp = nrand(Y-y);
715: yn = mess[ yp ];
716: mess[ yp ] = mess[ Y - y - 1 ];
717: }
718: else
719: yn = y;
720: j = NODE ( xn, yn );
721: l = im + nrand ( il );
722: if ( in != 0 )
723: l *= (long) ( in * dx );
724: if ( is_f )
725: l *= (long) ( ( is * dx ) * dx );
726: print_arc (vty, topology, i, j, l );
727: }
728: }
729: }
730: /* all is done */
731: return ext;
732:
733: return 0;
734: }
735:
736:
737: