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 linkern_path */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Cook */
24 /* Date: May 6, 2003 */
25 /* */
26 /* For a short describtion see usage () */
27 /* */
28 /****************************************************************************/
29
30 #include "machdefs.h"
31 #include "linkern.h"
32 #include "util.h"
33 #include "kdtree.h"
34 #include "edgegen.h"
35 #include "macrorus.h"
36
37 static int norm = CC_EUCLIDEAN;
38 static int seed = 0;
39 static int binary_in = 0;
40 static int tsplib_in = 1;
41 static int nnodes_want = 0;
42 static int gridsize = 0;
43 static int quadtry = 2;
44 static int run_silently = 0;
45
46 static int in_repeater = -1;
47
48 static char *nodefile = (char *) NULL;
49 static char *goodfname = (char *) NULL;
50 static char *cycfname = (char *) NULL;
51 static char *outfname = (char *) NULL;
52
53
54 int
55 main (int, char **);
56
57 static int
58 print_command (int ac, char **av),
59 parseargs (int, char **);
60
61 static void
62 usage (char *f);
63
64
main(int ac,char ** av)65 int main (int ac, char **av)
66 {
67 int k, ncount;
68 double val, best;
69 double startzeit;
70 int tempcount, *templist;
71 int *incycle = (int *) NULL, *outcycle = (int *) NULL;
72 CCdatagroup dat;
73 int rval = 0;
74 CCrandstate rstate;
75 int allow_dups;
76 int use_gridsize;
77
78 CCutil_printlabel ();
79 CCutil_init_datagroup (&dat);
80
81 rval = print_command (ac, av);
82 CCcheck_rval (rval, "print_command failed");
83
84 seed = (int) CCutil_real_zeit ();
85 rval = parseargs (ac, av);
86 if (rval) goto CLEANUP;
87
88 CCutil_sprand (seed, &rstate);
89
90 printf ("Chained Lin-Kernighan with seed %d\n", seed);
91 fflush (stdout);
92
93 if ((!nnodes_want && !nodefile) || (tsplib_in && !nodefile)) {
94 usage (av[0]);
95 goto CLEANUP;
96 }
97
98 startzeit = CCutil_zeit ();
99
100 if (tsplib_in) {
101 if (CCutil_gettsplib (nodefile, &ncount, &dat)) {
102 fprintf (stderr, "could not read the TSPLIB file\n");
103 rval = 1;
104 goto CLEANUP;
105 }
106 CCutil_dat_getnorm (&dat, &norm);
107 } else {
108 ncount = nnodes_want;
109 if (gridsize < 0) {
110 use_gridsize = -gridsize;
111 allow_dups = 0;
112 } else if (gridsize > 0) {
113 use_gridsize = gridsize;
114 allow_dups = 1;
115 } else {
116 use_gridsize = nnodes_want;
117 allow_dups = 0;
118 }
119 if (CCutil_getdata (nodefile, binary_in, norm, &ncount, &dat,
120 use_gridsize, allow_dups, &rstate)) {
121 rval = 1;
122 goto CLEANUP;
123 }
124 }
125
126 if (in_repeater == -1) in_repeater = ncount / 10;
127
128
129 if (cycfname) {
130 incycle = CC_SAFE_MALLOC (ncount, int);
131 CCcheck_NULL (incycle, "out of memory in main");
132
133 rval = CCutil_getcycle (ncount, cycfname, incycle, 0);
134 CCcheck_rval (rval, "CCutil_getcycle failed");
135 }
136
137 if (goodfname) {
138 int *templen = (int *) NULL;
139 rval = CCutil_getedgelist (ncount, goodfname, &tempcount, &templist,
140 &templen, 0);
141 CCcheck_rval (rval, "CCutil_getedgelist failed");
142
143 CC_IFFREE (templen, int);
144 printf ("Read good-edge file: %d edges\n", tempcount);
145 fflush (stdout);
146 } else {
147 CCedgegengroup plan;
148
149 CCedgegen_init_edgegengroup (&plan);
150 plan.quadnearest = quadtry;
151
152 rval = CCedgegen_edges (&plan, ncount, &dat, (double *) NULL,
153 &tempcount, &templist, 0, &rstate);
154 CCcheck_rval (rval, "CCedgegen_edges failed");
155 }
156
157
158 outcycle = CC_SAFE_MALLOC (ncount, int);
159 CCcheck_NULL (outcycle, "out of memory in main");
160
161 rval = CClinkern_path (ncount, &dat, tempcount, templist,
162 in_repeater, incycle, outcycle, &val, run_silently, &rstate);
163 CCcheck_rval (rval, "CClinkern_path failed");
164
165 printf ("First: %d Last: %d\n", outcycle[0], outcycle[ncount-1]);
166 printf ("Total Running Time: %.2f\n", CCutil_zeit () - startzeit);
167 fflush (stdout);
168
169 if (outfname) {
170 rval = CCutil_writecycle (ncount, outfname, outcycle, 0);
171 CCcheck_rval (rval, "CCutil_writecycle failed");
172 }
173
174 CLEANUP:
175
176 CC_IFFREE (templist, int);
177 CC_IFFREE (incycle, int);
178 CC_IFFREE (outcycle, int);
179 CCutil_freedatagroup (&dat);
180
181 return rval;
182 }
183
parseargs(int ac,char ** av)184 static int parseargs (int ac, char **av)
185 {
186 int c, k;
187 int inorm;
188 int boptind = 1;
189 char *boptarg = (char *) NULL;
190
191 while ((c = CCutil_bix_getopt (ac, av, "bBg:G:k:lN:o:q:QR:s:y:", &boptind, &boptarg)) != EOF)
192 switch (c) {
193 case 'B':
194 binary_in = 1;
195 break;
196 case 'b':
197 binary_in = 2;
198 break;
199 case 'g':
200 goodfname = boptarg;
201 break;
202 case 'G':
203 gridsize = atoi(boptarg);
204 break;
205 case 'k':
206 nnodes_want = atoi (boptarg);
207 tsplib_in = 0;
208 break;
209 case 'N':
210 inorm = atoi(boptarg);
211 switch (inorm) {
212 case 0: norm = CC_MAXNORM; break;
213 case 1: norm = CC_EUCLIDEAN_CEIL; break;
214 case 2: norm = CC_EUCLIDEAN; break;
215 case 3: norm = CC_EUCLIDEAN_3D; break;
216 case 4: norm = CC_USER; break;
217 case 5: norm = CC_ATT; break;
218 case 6: norm = CC_GEOGRAPHIC; break;
219 case 7: norm = CC_MATRIXNORM; break;
220 case 8: norm = CC_DSJRANDNORM; break;
221 case 9: norm = CC_CRYSTAL; break;
222 case 10: norm = CC_SPARSE; break;
223 case 11: norm = CC_RHMAP1; break;
224 case 12: norm = CC_RHMAP2; break;
225 case 13: norm = CC_RHMAP3; break;
226 case 14: norm = CC_RHMAP4; break;
227 case 15: norm = CC_RHMAP5; break;
228 case 16: norm = CC_EUCTOROIDAL; break;
229 case 17: norm = CC_GEOM; break;
230 case 18: norm = CC_MANNORM; break;
231 default:
232 usage (av[0]);
233 return 1;
234 }
235 tsplib_in = 0;
236 break;
237 case 'o':
238 outfname = boptarg;
239 break;
240 case 'q':
241 quadtry = atoi (boptarg);
242 break;
243 case 'Q':
244 run_silently++;
245 break;
246 case 'R':
247 in_repeater = atoi (boptarg);
248 break;
249 case 's':
250 seed = atoi (boptarg);
251 break;
252 case 'y':
253 cycfname = boptarg;
254 break;
255 case CC_BIX_GETOPT_UNKNOWN:
256 case '?':
257 default:
258 usage (av[0]);
259 return 1;
260 }
261 if (boptind < ac)
262 nodefile = av[boptind++];
263
264 if (boptind > ac) {
265 usage (av[0]);
266 return 1;
267 }
268 return 0;
269 }
270
usage(char * f)271 static void usage (char *f)
272 {
273 fprintf (stderr, "usage: %s [- see below -] [tsplib_file or dat_file]\n", f);
274 fprintf (stderr, " -s # random number seed\n");
275 fprintf (stderr, " -k # number of nodes for random problem\n");
276 fprintf (stderr, " -G # use #x# grid for random points, no dups if #<0\n");
277 fprintf (stderr, " -o f save final tour\n");
278 fprintf (stderr, " -q # use quad #-nearest as the sparse set (default is 2)\n");
279 fprintf (stderr, " -g f use the edges in file f as the sparse edge set\n");
280 fprintf (stderr, " -R # number of kicks in iterated Lin-Kernighan (default is #nodes)\n");
281 fprintf (stderr, " -y f starting cycle\n");
282 fprintf (stderr, " -Q run silently\n");
283 fprintf (stderr, " -b dat file in binary doubles\n");
284 fprintf (stderr, " -B dat file in binary ints\n");
285 fprintf (stderr, " -N # norm (must specify if dat file is not a TSPLIB file)\n");
286 fprintf (stderr, " 0=MAX, 1=JOHNSON, 2=L2, 3=3D, 4=USER, 5=ATT, 6=GEO, 7=MATRIX,\n");
287 fprintf (stderr, " 8=DSJRAND, 9=CRYSTAL, 10=SPARSE, 11-15=RH-norm 1-5, 16=TOROIDAL\n");
288 fprintf (stderr, " 17=GEOM, 18=L1\n");
289 }
290
print_command(int ac,char ** av)291 static int print_command (int ac, char **av)
292 {
293 int rval = 0;
294 int i, cmdlen = 0;
295 char *cmdout = (char *) NULL;
296
297 for (i=0; i<ac; i++) {
298 cmdlen += strlen(av[i]) + 1;
299 }
300 cmdout = CC_SAFE_MALLOC (cmdlen, char);
301 CCcheck_NULL (cmdout, "out of memory in print_command");
302
303 cmdlen = 0;
304 for (i=0; i<ac; i++) {
305 strcpy (cmdout + cmdlen, av[i]);
306 cmdlen += strlen(av[i]);
307 cmdout[cmdlen] = ' ';
308 cmdlen++;
309 }
310 cmdout[cmdlen-1] = '\0';
311 printf ("%s\n", cmdout); fflush (stdout);
312
313 CLEANUP:
314
315 CC_IFFREE (cmdout, char);
316 return rval;
317 }
318