sprand.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502
  1. #include <zebra.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <values.h>
  6. #include "random.c"
  7. #define DASH '-'
  8. #define VERY_FAR 100000000
  9. /* generator of random networks for the shortest paths problem;
  10. extended DIMACS format for output */
  11. main ( argc, argv )
  12. int argc;
  13. char* argv[];
  14. {
  15. char args[30];
  16. long n,
  17. n0,
  18. source,
  19. i,
  20. i0,
  21. j,
  22. dij;
  23. long m,
  24. m0,
  25. mc,
  26. k;
  27. long *p,
  28. p_t,
  29. l,
  30. lx;
  31. long seed,
  32. seed1,
  33. seed2;
  34. int ext=0;
  35. FILE *fout;
  36. /* variables for lengths generating */
  37. /* initialized by default values */
  38. int l_f = 0, ll_f = 0, lm_f = 0, ln_f = 0, ls_f = 0;
  39. long ll = 10000, /* length of the interval */
  40. lm = 0; /* minimal bound of the interval */
  41. double ln = 0, /* l += ln * |i-j| */
  42. ls = 0; /* l += ls * |i-j|^2 */
  43. /* variables for connecting cycle(s) */
  44. int c_f = 0, cl_f = 0, ch_f = 0, c_random = 1;
  45. long cl = 1; /* length of cycle arc */
  46. long ch; /* number of arcs in the cycle
  47. n - by default */
  48. /* variables for artifical source */
  49. int s_f = 0, sl_f = 0, sm_f = 0;
  50. long sl = VERY_FAR, /* upper bound of artifical arc */
  51. sm, /* lower bound of artifical arc */
  52. s;
  53. /* variables for potentials */
  54. int p_f = 0, pl_f = 0, pm_f = 0, pn_f = 0, ps_f = 0,
  55. pa_f = 0, pap_f = 0, pac_f = 0;
  56. long pl, /* length of the interval */
  57. pm; /* minimal bound of the interval */
  58. double pn = 0, /* l += ln * |i-j| */
  59. ps = 0, /* l += ls * |i-j|^2 */
  60. pap = 0, /* part of nodes with alternative dustribution */
  61. pac = -1; /* multiplier for alternative distribution */
  62. int np; /* number of parameter parsing now */
  63. #define PRINT_ARC( i, j, length )\
  64. {\
  65. l = length;\
  66. if ( p_f ) l += ( p[i] - p[j] );\
  67. printf ("a %8ld %8ld %12ld\n", i, j, l );\
  68. }
  69. /* parsing parameters */
  70. if ( argc < 2 ) goto usage;
  71. np = 0;
  72. strcpy ( args, argv[1] );
  73. if ( ( args[0] == DASH ) && ( args[1] == 'h')
  74. )
  75. goto help;
  76. if ( argc < 4 ) goto usage;
  77. /* first parameter - number of nodes */
  78. np = 1;
  79. if ( ( n = atoi ( argv[1] ) ) < 2 ) goto usage;
  80. /* second parameter - number of arcs */
  81. np = 2;
  82. if ( ( m = atoi ( argv[2] ) ) < n ) goto usage;
  83. /* third parameter - seed */
  84. np=3;
  85. if ( ( seed = atoi ( argv[3] ) ) <= 0 ) goto usage;
  86. /* other parameters */
  87. for ( np = 4; np < argc; np ++ )
  88. {
  89. strcpy ( args, argv[np] );
  90. if ( args[0] != DASH ) goto usage;
  91. switch ( args[1] )
  92. {
  93. case 'l' : /* an interval for arc length */
  94. l_f = 1;
  95. switch ( args[2] )
  96. {
  97. case 'l': /* length of the interval */
  98. ll_f = 1;
  99. ll = (long) atof ( &args[3] );
  100. break;
  101. case 'm': /* minimal bound */
  102. lm_f = 1;
  103. lm = (long ) atof ( &args[3] );
  104. break;
  105. case 'n': /* additional length: l*|i-j| */
  106. ln_f = 1;
  107. ln = atof ( &args[3] );
  108. break;
  109. case 's': /* additional length: l*|i-j|^2 */
  110. ls_f = 1;
  111. ls = atof ( &args[3] );
  112. break;
  113. default: /* unknown switch value */
  114. goto usage;
  115. }
  116. break;
  117. case 'c' : /* connecting cycle(s) */
  118. c_f = 1;
  119. switch ( args[2] )
  120. {
  121. case 'l':
  122. c_random = 0;
  123. cl_f = 1;
  124. cl = (long) atof ( &args[3] );
  125. if ( cl < 0 ) goto usage;
  126. break;
  127. case 'h':
  128. ch_f = 1;
  129. ch = (long) atof ( &args[3] );
  130. if ( ch < 2 || ch > n ) goto usage;
  131. break;
  132. default: /* unknown switch value */
  133. goto usage;
  134. }
  135. break;
  136. case 's' : /* additional source */
  137. s_f = 1;
  138. if ( strlen ( args ) > 2 )
  139. {
  140. switch ( args[2] )
  141. {
  142. case 'l': /* upper bound of art. arc */
  143. sl_f = 1;
  144. sl = (long) atof ( &args[3] );
  145. break;
  146. case 'm': /* lower bound of art. arc */
  147. sm_f = 1;
  148. sm = (long) atof ( &args[3] );
  149. break;
  150. default: /* unknown switch value */
  151. goto usage;
  152. }
  153. }
  154. break;
  155. case 'p' : /* potentials */
  156. p_f = 1;
  157. if ( strlen ( args ) > 2 )
  158. {
  159. switch ( args[2] )
  160. {
  161. case 'l': /* length of the interval */
  162. pl_f = 1;
  163. pl = (long) atof ( &args[3] );
  164. break;
  165. case 'm': /* minimal bound */
  166. pm_f = 1;
  167. pm = (long ) atof ( &args[3] );
  168. break;
  169. case 'n': /* additional length: l*|i-j| */
  170. pn_f = 1;
  171. pn = atof ( &args[3] );
  172. break;
  173. case 's': /* additional length: l*|i-j|^2 */
  174. ps_f = 1;
  175. ps = atof ( &args[3] );
  176. break;
  177. case 'a': /* bipolar distribution */
  178. pa_f = 1;
  179. switch ( args[3] )
  180. {
  181. case 'p': /* % of alternative potentials */
  182. pap_f = 1;
  183. pap = atof ( &args[4] );
  184. if ( pap < 0 ) pap = 0;
  185. if ( pap > 100 ) pap = 100;
  186. pap /= 100;
  187. break;
  188. case 'c': /* multiplier */
  189. pac_f = 1;
  190. pac = atof ( &args[4] );
  191. break;
  192. default: /* unknown switch value */
  193. goto usage;
  194. }
  195. break;
  196. default: /* unknown switch value */
  197. goto usage;
  198. }
  199. }
  200. break;
  201. default : /* unknoun case */
  202. goto usage;
  203. }
  204. }
  205. /* ----- ajusting parameters ----- */
  206. n0 = n; m0 = m;
  207. /* length parameters */
  208. if ( ll < lm ) { lx = ll; ll = lm; lm = lx; }
  209. /* potential parameters */
  210. if ( p_f )
  211. {
  212. if ( ! pl_f ) pl = ll;
  213. if ( ! pm_f ) pm = lm;
  214. if ( pl < pm ) { lx = pl; pl = pm; pm = lx; }
  215. }
  216. /* path(s) parameters */
  217. if ( ! ch_f ) ch = n;
  218. mc = n + (n-2) / (ch-1);
  219. if ( mc > m )
  220. { fprintf ( stderr,
  221. "Error: not enough arcs for generating connecting cycle(s)\n" );
  222. exit (4);
  223. }
  224. /* artifical source parameters */
  225. if ( s_f )
  226. { m0 += n; n0 ++ ;
  227. if ( ! sm_f ) sm = sl;
  228. if ( sl < sm ) { lx = sl; sl = sm; sm = lx; }
  229. }
  230. /* printing title */
  231. printf ("c random network for shortest paths problem\n");
  232. printf ("c extended DIMACS format\nc\n" );
  233. /* name of the problem */
  234. printf ("t rd_%ld_%ld_%ld_", n, m, seed );
  235. if ( l_f )
  236. printf ("%c", 'l');
  237. if ( c_f )
  238. printf ("%c", 'c');
  239. if ( s_f )
  240. printf ("%c", 's');
  241. if ( p_f )
  242. printf ("%c", 'p');
  243. printf ("\nc\n");
  244. /* printing additional information */
  245. if ( l_f )
  246. printf ("c length -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
  247. lm, ll, ln, ls );
  248. if ( c_f )
  249. {
  250. if ( c_random )
  251. printf ("c cycle -> number of arcs: %ld arc length: random\n", ch);
  252. else
  253. printf ("c cycle -> number of arcs: %ld arc length: %ld\n",
  254. ch, cl );
  255. }
  256. if ( s_f )
  257. printf ("c length of arcs from artifical source -> min: %ld max: %ld\n",
  258. sm, sl );
  259. if ( p_f )
  260. {
  261. printf ("c potentials -> min: %ld max: %ld k1: %.2f k2: %.2f\n",
  262. pm, pl, pn, ps );
  263. if ( pa_f )
  264. printf ("c potentials -> part of alternative distribution: %.2f k: %.2f\n",
  265. pap, pac );
  266. }
  267. printf ("c\n" );
  268. printf ("p sp %8ld %8ld\nc\n", n0, m0 );
  269. source = ( s_f ) ? n0 : 1;
  270. printf ("n %8ld\nc\n", source );
  271. if ( p_f ) /* generating potentials */
  272. {
  273. p = (long*) calloc ( n+2, sizeof (long) );
  274. seed1 = 2*seed + 1;
  275. init_rand ( seed1);
  276. pl = pl - pm + 1;
  277. for ( i = 0; i <= n; i ++ )
  278. {
  279. p_t = pm + nrand ( pl );
  280. if ( pn_f ) p_t += (long) ( i * pn );
  281. if ( ps_f ) p_t += (long) ( i * ( i * ps ));
  282. if ( pap_f )
  283. if ( rand01() < pap )
  284. p_t = (long) ( p_t * pac );
  285. p[i] = p_t;
  286. }
  287. p[n+1] = 0;
  288. }
  289. if ( s_f ) /* additional arcs from artifical source */
  290. {
  291. seed2 = 3*seed + 1;
  292. init_rand ( seed2 );
  293. sl = sl - sm + 1;
  294. for ( i = n; i > 1; i -- )
  295. {
  296. s = sm + nrand ( sl );
  297. PRINT_ARC ( n0, i, s )
  298. }
  299. PRINT_ARC ( n0, 1, 0 )
  300. }
  301. /* initialize random number generator */
  302. init_rand ( seed );
  303. ll = ll - lm + 1;
  304. /* generating connecting cycle(s) */
  305. if (c_random)
  306. cl = lm + nrand ( ll );
  307. PRINT_ARC ( 1, 2, cl )
  308. if (c_random)
  309. cl = lm + nrand ( ll );
  310. PRINT_ARC ( n, 1, cl )
  311. for ( i = 2; i < n; i ++ )
  312. {
  313. if (c_random)
  314. cl = lm + nrand ( ll );
  315. if ( ( (i-1) % (ch-1) ) != 0 )
  316. PRINT_ARC ( i, i+1, cl )
  317. else
  318. { PRINT_ARC ( i, 1, cl )
  319. if (c_random)
  320. cl = lm + nrand ( ll );
  321. PRINT_ARC ( 1, i+1, cl )
  322. }
  323. }
  324. /* generating random arcs */
  325. for ( k = 1; k <= m - mc; k ++ )
  326. {
  327. i = 1 + nrand ( n );
  328. do
  329. j = 1 + nrand ( n );
  330. while ( j == i );
  331. dij = ( i > j ) ? ( i - j ) : ( j - i );
  332. l = lm + nrand ( ll );
  333. if ( ln_f ) l += (long) ( dij * ln );
  334. if ( ls_f ) l += (long) ( dij * ( dij * ls ) );
  335. PRINT_ARC ( i, j, l );
  336. }
  337. /* all is done */
  338. exit (ext);
  339. /* ----- wrong usage ----- */
  340. usage:
  341. fprintf ( stderr,
  342. "\nusage: %s n m seed [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
  343. help: %s -h\n\n", argv[0], argv[0] );
  344. if ( np > 0 )
  345. fprintf ( stderr, "error in parameter # %d\n\n", np );
  346. exit (4);
  347. /* ---- help ---- */
  348. help:
  349. if ( args[2] == 'h') goto hhelp;
  350. fprintf ( stderr,
  351. "\n'%s' - random network generator for shortest paths problem.\n\
  352. Generates problems in extended DIMACS format.\n\
  353. \n\
  354. %s n m seed [ -ll#i -lm#i -cl#i -p -pl#i -pm#i ... ]\n\
  355. %s -hh\n\
  356. \n\
  357. #i - integer number #f - real number\n\
  358. \n\
  359. -ll#i - #i is the upper bound on arc lengths (default 10000)\n\
  360. -lm#i - #i is the lower bound on arc lengths (default 0)\n\
  361. -cl#i - #i is length of arcs in connecting cycle(s) (default random)\n\
  362. -p - generate potentials \n\
  363. -pl#i - #i is the upper bound on potentials (default ll)\n\
  364. -pm#i - #i is the lower bound on potentials (default lm)\n\
  365. \n\
  366. -hh - extended help \n\n",
  367. argv[0], argv[0], argv[0] );
  368. exit (0);
  369. /* --------- sophisticated help ------------ */
  370. hhelp:
  371. if ( argc < 3 )
  372. fout = stderr;
  373. else
  374. fout = fopen ( argv[2], "w" );
  375. if ( fout == NULL )
  376. { fprintf ( stderr, "\nCan't open file '%s' for writing help\n\n", argv[2] );
  377. exit ( 2 );
  378. }
  379. fprintf (fout,
  380. "\n'%s' - random network generator for shortest paths problem.\n\
  381. Generates problems in extended DIMACS format.\n\
  382. \n\
  383. %s n m seed [ -ll#i -lm#i -ln#f -ls#f\n\
  384. -p -pl#i -pm#i -pn#f -ps#f -pap#i -pac#f\n\
  385. -cl#i -ch#i\n\
  386. -s -sl#i -sm#i\n\
  387. ]\n\
  388. %s -hh file_name\n\
  389. \n\
  390. #i - integer number #f - real number\n\
  391. \n\
  392. Arc length parameters:\n\
  393. -ll#i - #i is the upper bound on arc lengths (default 10000)\n\
  394. -lm#i - #i is the lower bound on arc lengths (default 0)\n\
  395. -ln#f - multipliy l(i, j) by #f * |i-j| (default 0)\n\
  396. -ls#f - multipliy l(i, j) by #f * |i-j|^2 (default 0)\n\
  397. \n\
  398. Potential parameters:\n\
  399. -p - generate potentials \n\
  400. -pl#i - #i is the upper bound on potentials (default ll)\n\
  401. -pm#i - #i is the lower bound on potentials (default lm)\n\
  402. -pn#f - multiply p(i) by #f * i (default 0)\n\
  403. -ps#f - multiply p(i) by #f * i^2 (default 0)\n\
  404. -pap#i - percentage of alternative potential nodes (default 0)\n\
  405. -pac#f - if i is alternative, multiply p(i) by #f (default -1)\n\
  406. \n\
  407. Connecting cycle(s) parameters:\n\
  408. -cl#i - #i is length of arcs in connecting cycle(s) (default random)\n\
  409. -ch#i - #i is length of connecting cycles (default n)\n\
  410. \n\
  411. Artificial source parameters:\n\
  412. -s - generate artificial source with default connecting arc lengths\n\
  413. -sl#i - #i is the upper bound on art. arc lengths (default 100000000)\n\
  414. -sm#i - #i is the lower bound on art. arc lengths (default sl)\n\
  415. \n\
  416. -hh file_name - save this help in the file 'file_name'\n\n",
  417. argv[0], argv[0], argv[0] );
  418. exit (0);
  419. }