1 /****************************************************************************/
2 /* */
3 /* This file is part of CONCORDE */
4 /* */
5 /* (c) Copyright 1995--1999 by David Applegate, Robert Bixby, */
6 /* Vasek Chvatal, and William Cook */
7 /* */
8 /* Permission is granted for academic research use. For other uses, */
9 /* contact the authors for licensing options. */
10 /* */
11 /* Use at your own risk. We make no guarantees about the */
12 /* correctness or usefulness of this code. */
13 /* */
14 /****************************************************************************/
15
16 /****************************************************************************/
17 /* */
18 /* CODE FOR TESTING EDGE GENERATION ROUTINES */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: February 25, 1995 */
25 /* */
26 /* For a short describtion see usage () */
27 /* */
28 /****************************************************************************/
29
30
31 #include "machdefs.h"
32 #include "util.h"
33 #include "edgegen.h"
34
35 #define DEFAULT_EDGE_RANGE (5) /* for random edge sets */
36
37 static int norm = CC_EUCLIDEAN;
38 static int seed = 0;
39 static int nnodes_want = 0;
40 static int gridsize = 0;
41 static int nearnum = 0;
42 static int quadnearnum = 0;
43 static int f2match_nearnum = 0;
44 static int usenodeweights = 0;
45 static int random_weight_limit = 0;
46 static int random_edge_count = 0;
47 static int random_edge_range = -1;
48 static int random_tour_count = 0;
49 static int nearest_tour_count = 0;
50 static int linkern_tour_count = 0;
51 static int linkern_kicks = 100;
52 static int use_greedy_in_linkern = 0;
53 static int use_boruvka_in_linkern = 0;
54 static int use_qboruvka_in_linkern = 0;
55 static int use_random_in_linkern = 0;
56 static int linkern_nearnum = 0;
57 static int linkern_quadnum = 0;
58 static int twoopt_tour_count = 0;
59 static int twoopt5_tour_count = 0;
60 static int threeopt_tour_count = 0;
61 static int nearest_twomatch_count = 0;
62 static int find_greedy_tour = 0;
63 static int find_boruvka_tour = 0;
64 static int find_qboruvka_tour = 0;
65 static int find_fractional_2match = 0;
66 static int find_spanning_tree = 0;
67 static int find_delaunay_edges = 0;
68 static int find_mlinkern_edges = 0;
69 static int binary_in = 0;
70 static int tsplib_in = 1;
71 static int binary_out = 0;
72
73 static char *nodefile = (char *) NULL;
74 static char *weightfile = (char *) NULL;
75 static char *outfile = (char *) NULL;
76 static char *pointfile = (char *) NULL;
77 static char *describefile = (char *) NULL;
78
79
80
81 int
82 main (int ac, char **av);
83 static void
84 usage (char *f);
85 static int
86 parseargs (int ac, char **av);
87
88
main(int ac,char ** av)89 int main (int ac, char **av)
90 {
91 double szeit;
92 double *wcoord = (double *) NULL;
93 int ncount, maxlen;
94 int rval = 0;
95 int ecount = 0;
96 int *elist = (int *) NULL;
97 int *elen = (int *) NULL;
98 CCdatagroup dat;
99 CCedgegengroup plan;
100 CCrandstate rstate;
101
102 CCutil_init_datagroup (&dat);
103
104 seed = (int) CCutil_real_zeit ();
105 rval = parseargs (ac, av);
106 if (rval) goto CLEANUP;
107
108 CCutil_sprand (seed, &rstate);
109
110 if ((!nnodes_want && !nodefile)) {
111 usage (av[0]);
112 rval = 1; goto CLEANUP;
113 }
114 if (nnodes_want) tsplib_in = 0;
115
116 if (!nodefile && norm == CC_SPARSE) {
117 if (random_edge_count == 0) {
118 fprintf (stderr, "Must specify the number of edges\n");
119 rval = 1; goto CLEANUP;
120 }
121 if (nearnum != 0 || quadnearnum != 0 || random_tour_count != 0 ||
122 nearest_tour_count != 0 || linkern_tour_count != 0 ||
123 twoopt_tour_count != 0 || twoopt5_tour_count != 0 ||
124 threeopt_tour_count != 0 || nearest_twomatch_count != 0 ||
125 find_greedy_tour != 0 || find_boruvka_tour != 0 ||
126 find_qboruvka_tour != 0 || find_fractional_2match != 0 ||
127 find_spanning_tree != 0 || find_delaunay_edges != 0 ||
128 find_mlinkern_edges != 0) {
129 fprintf (stderr, "Only permitted operation with SPARSE norm is a random edge set\n");
130 rval = 1; goto CLEANUP;
131 }
132 ncount = nnodes_want;
133 ecount = random_edge_count;
134 if (random_edge_range == -1) {
135 maxlen = DEFAULT_EDGE_RANGE * ncount;
136 } else {
137 maxlen = random_edge_range;
138 }
139 rval = CCutil_genedgelist (ncount, ecount, &elist, &elen,
140 (CCdatagroup *) NULL, maxlen, &rstate);
141 if (rval) {
142 fprintf (stderr, "CCutil_genedgelist failed\n"); goto CLEANUP;
143 }
144 if (outfile) {
145 rval = CCutil_writeedges_int (ncount, outfile, ecount, elist,
146 elen, binary_out);
147 if (rval) {
148 fprintf (stderr, "CCutil_writeedges_int failed\n");
149 goto CLEANUP;
150 }
151 }
152 goto CLEANUP;
153 }
154
155 if (tsplib_in) {
156 if (CCutil_gettsplib (nodefile, &ncount, &dat)) {
157 fprintf (stderr, "could not read the TSPLIB file\n");
158 rval = 1;
159 goto CLEANUP;
160 }
161 CCutil_dat_getnorm (&dat, &norm);
162 } else {
163 int allow_dups;
164 int use_gridsize;
165
166 ncount = nnodes_want;
167 if (gridsize < 0) {
168 use_gridsize = -gridsize;
169 allow_dups = 0;
170 } else if (gridsize > 0) {
171 use_gridsize = gridsize;
172 allow_dups = 1;
173 } else {
174 use_gridsize = ncount;
175 allow_dups = 0;
176 }
177 if (CCutil_getdata (nodefile, binary_in, norm, &ncount, &dat,
178 use_gridsize, allow_dups, &rstate)) {
179 rval = 1;
180 goto CLEANUP;
181 }
182 }
183
184 if (usenodeweights) {
185 if (CCutil_getnodeweights (weightfile, ncount, random_weight_limit,
186 &wcoord, &rstate)) {
187 fprintf (stderr, "could not read the nodeweight file\n");
188 rval = 1;
189 goto CLEANUP;
190 }
191 }
192
193 if (describefile) {
194 if (CCedgegen_read (describefile, &plan)) {
195 fprintf (stderr, "CCedgegen_read failed\n");
196 rval = 1;
197 goto CLEANUP;
198 }
199 } else {
200 CCedgegen_init_edgegengroup (&plan);
201
202 plan.random = random_edge_count;
203 plan.nearest = nearnum;
204 plan.quadnearest = quadnearnum;
205 plan.delaunay = find_delaunay_edges;
206 plan.mlinkern = find_mlinkern_edges;
207 plan.tour.random_count = random_tour_count;
208 plan.tour.nearest_count = nearest_tour_count;
209 plan.tour.greedy = find_greedy_tour;
210 plan.tour.boruvka = find_boruvka_tour;
211 plan.tour.qboruvka = find_qboruvka_tour;
212 plan.want_tree = find_spanning_tree;
213 plan.tour.twoopt_count = twoopt_tour_count;
214 plan.tour.twoopt5_count = twoopt5_tour_count;
215 plan.tour.threeopt_count = threeopt_tour_count;
216 if (linkern_tour_count) {
217 plan.linkern.count = linkern_tour_count;
218 if (!linkern_quadnum && !linkern_nearnum) {
219 linkern_quadnum = 3;
220 } else {
221 plan.linkern.quadnearest = linkern_quadnum;
222 plan.linkern.nearest = linkern_nearnum;
223 }
224 if (!use_greedy_in_linkern && !use_random_in_linkern &&
225 !use_boruvka_in_linkern && !use_qboruvka_in_linkern) {
226 plan.linkern.nearest_start = 1;
227 } else {
228 plan.linkern.greedy_start = use_greedy_in_linkern;
229 plan.linkern.random_start = use_random_in_linkern;
230 plan.linkern.boruvka_start = use_boruvka_in_linkern;
231 plan.linkern.qboruvka_start = use_qboruvka_in_linkern;
232 }
233 plan.linkern.nkicks = linkern_kicks;
234 }
235 plan.nearest_twomatch_count = nearest_twomatch_count;
236 plan.f2match.wantit = find_fractional_2match;
237 if (f2match_nearnum) {
238 plan.f2match_nearest.number = f2match_nearnum;
239 plan.f2match_nearest.basic = 0;
240 plan.f2match_nearest.priced = 1;
241 }
242 }
243
244 szeit = CCutil_zeit ();
245
246 if (CCedgegen_edges (&plan, ncount, &dat, wcoord, &ecount, &elist,
247 0, &rstate)) {
248 fprintf (stderr, "CCedgegen_edges failed\n");
249 rval = 1;
250 goto CLEANUP;
251 }
252
253 printf ("Edgegen running time: %.2f (seconds)\n", CCutil_zeit () - szeit);
254 fflush (stdout);
255
256 if (outfile && ecount) {
257 if (CCutil_writeedges (ncount, outfile, ecount, elist, &dat,
258 binary_out)) {
259 fprintf (stderr, "Could not write the edge set\n");
260 rval = 1;
261 goto CLEANUP;
262 }
263 }
264
265 if (pointfile && ncount) {
266 if (CCutil_writedata (pointfile, binary_out, ncount, &dat)) {
267 fprintf (stderr, "Could not write the point set\n");
268 rval = 1;
269 goto CLEANUP;
270 }
271 }
272
273 CLEANUP:
274
275 CCutil_freedatagroup (&dat);
276 CC_IFFREE (wcoord, double);
277 CC_IFFREE (elist, int);
278 CC_IFFREE (elist, int);
279
280 return rval;
281 }
282
parseargs(int ac,char ** av)283 static int parseargs (int ac, char **av)
284 {
285 int c, inorm;
286 int boptind = 1;
287 char *boptarg = (char *) NULL;
288
289 while ((c = CCutil_bix_getopt (ac, av, "A:bB:C:de:D:f:FGhHiIk:K:L:s:m:M:n:N:o:Op:q:r:R:ST:uU:vw:W:x:y:?", &boptind, &boptarg))
290 != EOF)
291 switch (c) {
292 case 'A':
293 twoopt_tour_count = atoi (boptarg);
294 break;
295 case 'b':
296 binary_in = 1;
297 break;
298 case 'B':
299 twoopt5_tour_count = atoi (boptarg);
300 break;
301 case 'C':
302 threeopt_tour_count = atoi (boptarg);
303 break;
304 case 'd':
305 find_delaunay_edges = 1;
306 break;
307 case 'e':
308 random_edge_count = atoi (boptarg);
309 break;
310 case 'D':
311 describefile = boptarg;
312 break;
313 case 'f':
314 f2match_nearnum = atoi (boptarg);
315 break;
316 case 'F':
317 find_fractional_2match = 1;
318 break;
319 case 'G':
320 find_greedy_tour = 1;
321 break;
322 case 'h':
323 find_boruvka_tour = 1;
324 break;
325 case 'H':
326 use_boruvka_in_linkern = 1;
327 break;
328 case 'i':
329 find_qboruvka_tour = 1;
330 break;
331 case 'I':
332 use_qboruvka_in_linkern = 1;
333 break;
334 case 'k':
335 nnodes_want = atoi (boptarg);
336 break;
337 case 'K':
338 random_edge_range = atoi (boptarg);
339 break;
340 case 'L':
341 linkern_tour_count = atoi (boptarg);
342 break;
343 case 'm':
344 find_mlinkern_edges = atoi (boptarg);
345 break;
346 case 'M':
347 nearest_twomatch_count = atoi (boptarg);
348 break;
349 case 'n':
350 nearnum = atoi (boptarg);
351 break;
352 case 'p':
353 pointfile = boptarg;
354 break;
355 case 'T':
356 nearest_tour_count = atoi (boptarg);
357 break;
358 case 'o':
359 outfile = boptarg;
360 break;
361 case 'O':
362 binary_out = 1;
363 break;
364 case 'q':
365 quadnearnum = atoi (boptarg);
366 break;
367 case 'r':
368 gridsize = atoi(boptarg);
369 break;
370 case 'R':
371 linkern_kicks = atoi (boptarg);
372 break;
373 case 's':
374 seed = atoi (boptarg);
375 break;
376 case 'S':
377 find_spanning_tree = 1;
378 break;
379 case 'u':
380 use_greedy_in_linkern = 1;
381 use_random_in_linkern = 0;
382 break;
383 case 'U':
384 random_tour_count = atoi (boptarg);
385 break;
386 case 'v':
387 use_random_in_linkern = 1;
388 use_greedy_in_linkern = 0;
389 break;
390 case 'w':
391 usenodeweights = 1;
392 weightfile = boptarg;
393 break;
394 case 'W':
395 usenodeweights = 1;
396 random_weight_limit = atoi (boptarg);
397 break;
398 case 'x':
399 linkern_quadnum = atoi (boptarg);
400 break;
401 case 'y':
402 linkern_nearnum = atoi (boptarg);
403 break;
404 case 'N':
405 inorm = atoi (boptarg);
406 switch (inorm) {
407 case 0: norm = CC_MAXNORM; break;
408 case 1: norm = CC_MANNORM; break;
409 case 2: norm = CC_EUCLIDEAN; break;
410 case 3: norm = CC_EUCLIDEAN_3D; break;
411 case 4: norm = CC_USER; break;
412 case 5: norm = CC_ATT; break;
413 case 6: norm = CC_GEOGRAPHIC; break;
414 case 7: norm = CC_MATRIXNORM; break;
415 case 8: norm = CC_DSJRANDNORM; break;
416 case 9: norm = CC_CRYSTAL; break;
417 case 10: norm = CC_SPARSE; break;
418 case 11: norm = CC_RHMAP1; break;
419 case 12: norm = CC_RHMAP2; break;
420 case 13: norm = CC_RHMAP3; break;
421 case 14: norm = CC_RHMAP4; break;
422 case 15: norm = CC_RHMAP5; break;
423 case 16: norm = CC_EUCTOROIDAL; break;
424 case 17: norm = CC_GEOM; break;
425 case 18: norm = CC_EUCLIDEAN_CEIL; break;
426 default:
427 usage (av[0]);
428 return 1;
429 }
430 tsplib_in = 0;
431 break;
432 case CC_BIX_GETOPT_UNKNOWN:
433 case '?':
434 default:
435 usage (av[0]);
436 return 1;
437 }
438 if (boptind < ac)
439 nodefile = av[boptind++];
440
441 if (boptind > ac) {
442 usage (av[0]);
443 return 1;
444 }
445 return 0;
446 }
447
usage(char * f)448 static void usage (char *f)
449 {
450 fprintf (stderr, "Usage: %s [- see below -] [dat file]\n", f);
451 fprintf (stderr, " -b dat file in binary-ints\n");
452 fprintf (stderr, " -w f node weight file\n");
453 fprintf (stderr, " -W # use random node weights, from 0 to # - 1\n");
454 fprintf (stderr, " -k # number of nodes for random problem\n");
455 fprintf (stderr, " -K # in a SPARSE-norm problem, use edge weights from 0 to # - 1\n");
456 fprintf (stderr, " -s # random seed\n");
457 fprintf (stderr, " -D f description file\n");
458 fprintf (stderr, " -e # find # random edges\n");
459 fprintf (stderr, " -n # find # nearest graph\n");
460 fprintf (stderr, " -q # find quadrant # nearest graph\n");
461 fprintf (stderr, " -d find Delaunay triangulation\n");
462 fprintf (stderr, " -f # find # nearest using f2match reduced costs\n");
463 fprintf (stderr, " -U # find # random tours\n");
464 fprintf (stderr, " -T # find # nearest neighbor tours\n");
465 fprintf (stderr, " -G find greedy tour\n");
466 fprintf (stderr, " -h find boruvka tour\n");
467 fprintf (stderr, " -i find quick boruvka tour\n");
468 fprintf (stderr, " -(A B C) # find # (2opt, 2.5opt, 3opt) tours\n");
469 fprintf (stderr, " -L # find # linkern tours\n");
470 fprintf (stderr, " -m # find # linkern matchings\n");
471 fprintf (stderr, " -r n use nXn grid for random points, no dups if n<0\n");
472 fprintf (stderr, " -R # use # kicks in linkern (default: 100)\n");
473 fprintf (stderr, " -u use greedy starting tour for linkern\n");
474 fprintf (stderr, " -H use boruvka starting tour for linkern\n");
475 fprintf (stderr, " -I use quick boruvka starting tour for linkern\n");
476 fprintf (stderr, " -v use random starting tours for linkern\n");
477 fprintf (stderr, " -x # use # quadnearest in linkern\n");
478 fprintf (stderr, " -y # use # nearest in linkern (can use x & y)\n");
479 fprintf (stderr, " -M # find # nearest neighbor 2-matchings\n");
480 fprintf (stderr, " -S find min spanning tree\n");
481 fprintf (stderr, " -F find fractional twomatch (not priced)\n");
482 fprintf (stderr, " -o f write the cycle or edge set to f\n");
483 fprintf (stderr, " -p f write the point set to f\n");
484 fprintf (stderr, " -O use binary output\n");
485 fprintf (stderr, " -N # norm (must specify if dat file is not a TSPLIB file)\n");
486 fprintf (stderr, " 0=MAX, 1=L1, 2=L2, 3=3D, 4=USER, 5=ATT, 6=GEO, 7=MATRIX,\n");
487 fprintf (stderr, " 8=DSJRAND, 9=CRYSTAL, 10=SPARSE, 11-15=RH-norm 1-5, 16=TOROIDAL\n");
488 fprintf (stderr, " 17=GEOM, 18=JOHNSON\n");
489 }
490