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