spgrid.c 18 KB

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