1 #include <zebra.h>
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
6
7 #include "random.c"
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 yy1, yy2, yyp,
54 dl, dx, xn, yyn, 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
free_arc(void * val)129 free_arc (void *val) {
130 free(val);
131 }
132
133 void
print_arc(struct vty * vty,struct list * topology,long i,long j,long length)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
help(struct vty * vty)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
hhelp(struct vty * vty)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
usage(struct vty * vty)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
spgrid_check_params(struct vty * vty,int argc,const char ** argv)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
gen_spgrid_topology(struct vty * vty,struct list * topology)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 }
610 p[n0] = 0;
611 if ( s_f ) p[n0-1] = 0;
612 }
613
614 if ( s_f ) /* additional arcs from artifical source */
615 {
616 seed2 = 3*seed + 1;
617 init_rand ( seed2 );
618 sl = sl - sm + 1;
619
620 for ( x = X - 1; x >= 0; x -- )
621 for ( y = Y - 1; y >= 0; y -- )
622 {
623 i = NODE ( x, y );
624 s = sm + nrand ( sl );
625 print_arc (vty, topology, n0, i, s );
626 }
627
628 print_arc (vty, topology, n0, n0-1, 0 );
629 }
630
631
632 /* ----- generating arcs within layers ----- */
633
634 init_rand ( seed );
635 cl = cl - cm + 1;
636 al = al - am + 1;
637
638 for ( x = 0; x < X; x ++ )
639 {
640 /* generating arcs within one layer */
641 for ( y = 0; y < Y-1; y ++ )
642 {
643 /* generating spanning graph */
644 i = NODE ( x, y );
645 j = NODE ( x, y+1 );
646 l = cm + nrand ( cl );
647 print_arc (vty, topology, i, j, l );
648
649 if ( cw == DOUBLE_CYCLE )
650 {
651 l = cm + nrand ( cl );
652 print_arc (vty, topology, j, i, l );
653 }
654 }
655
656 if ( cw <= CYCLE )
657 {
658 i = NODE ( x, Y-1 );
659 j = NODE ( x, 0 );
660 l = cm + nrand ( cl );
661 print_arc (vty, topology, i, j, l );
662
663 if ( cw == DOUBLE_CYCLE )
664 {
665 l = cm + nrand ( cl );
666 print_arc (vty, topology, j, i, l );
667 }
668 }
669
670 /* generating additional arcs */
671
672 for ( k = ax; k > 0; k -- )
673 {
674 yy1 = nrand ( Y );
675 do
676 yy2 = nrand ( Y );
677 while ( yy2 == yy1 );
678 i = NODE ( x, yy1 );
679 j = NODE ( x, yy2 );
680 l = am + nrand ( al );
681 print_arc (vty, topology, i, j, l );
682 }
683 }
684
685 /* ----- generating interlayered arcs ------ */
686
687 il = il - im + 1;
688
689 /* arcs from the source */
690
691 for ( y = 0; y < Y; y ++ )
692 {
693 l = im + nrand ( il );
694 i = NODE ( 0, y );
695 print_arc (vty, topology, source, i, l );
696 }
697
698 for ( x = 0; x < X-1; x ++ )
699 {
700 /* generating arcs from one layer */
701 for ( count = 0, xn = x + 1;
702 count < ix && xn < X;
703 count ++, xn += ih )
704 {
705 if ( ip_f )
706 for ( y = 0; y < Y; y ++ )
707 mess[y] = y;
708
709 for ( y = 0; y < Y; y ++ )
710 {
711 i = NODE ( x, y );
712 dx = xn - x;
713 if ( ip_f )
714 {
715 yyp = nrand(Y-y);
716 yyn = mess[ yyp ];
717 mess[ yyp ] = mess[ Y - y - 1 ];
718 }
719 else
720 yyn = y;
721 j = NODE ( xn, yyn );
722 l = im + nrand ( il );
723 if ( in != 0 )
724 l *= (long) ( in * dx );
725 if ( is_f )
726 l *= (long) ( ( is * dx ) * dx );
727 print_arc (vty, topology, i, j, l );
728 }
729 }
730 }
731 /* all is done */
732 return ext;
733
734 return 0;
735 }
736
737
738
739