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 /* A PROGRAM TO COMPUTE THE LENGTH OF A TOUR IN A FILE */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: May 3, 1999 */
25 /* */
26 /* SEE short decsribtion in usage (). */
27 /* */
28 /****************************************************************************/
29
30 #include "machdefs.h"
31 #include "util.h"
32
33 static char *cycfname = (char *) NULL;
34 static char *tspfname = (char *) NULL;
35 static char *edgefname = (char *) NULL;
36 static int eformat = 0;
37 static int simpletour = 0;
38 static int seed = 0;
39
40
41 int
42 main (int ac, char **av);
43
44 static int
45 parseargs (int ac, char **av);
46
47 static void
48 usage (char *fname);
49
50
main(int ac,char ** av)51 int main (int ac, char **av)
52 {
53 int ncount, rval = 0;
54 int *tour = (int *) NULL;
55 double val;
56 CCdatagroup dat;
57 CCrandstate rstate;
58
59 CCutil_init_datagroup (&dat);
60
61 seed = (int) CCutil_real_zeit ();
62
63 rval = parseargs (ac, av);
64 if (rval) return 1;
65
66 if ((!edgefname && !tspfname) || (edgefname && tspfname)) {
67 usage (av[0]);
68 return 1;
69 }
70
71 CCutil_sprand (seed, &rstate);
72
73 if (tspfname) {
74 rval = CCutil_gettsplib (tspfname, &ncount, &dat);
75 if (rval) {
76 fprintf (stderr, "CCutil_gettsplib failed\n"); goto CLEANUP;
77 }
78 } else {
79 rval = CCutil_getdata (edgefname, 0, CC_SPARSE, &ncount, &dat,
80 0, 0, &rstate);
81 if (rval) {
82 fprintf (stderr, "CCutil_getdata failed\n"); goto CLEANUP;
83 }
84 }
85
86 tour = CC_SAFE_MALLOC (ncount, int);
87 if (!tour) {
88 fprintf (stderr, "out of memory in main\n");
89 rval = 1; goto CLEANUP;
90 }
91
92 if (eformat == 0) {
93 if (simpletour) {
94 rval = CCutil_getcycle (ncount, cycfname, tour, 0);
95 if (rval) {
96 fprintf (stderr, "CCutil_getcycle failed\n"); goto CLEANUP;
97 }
98 } else {
99 rval = CCutil_getcycle_tsplib (ncount, cycfname, tour);
100 CCcheck_rval (rval, "CCutil_getcycle_tsplib failed");
101 }
102 } else {
103 rval = CCutil_getcycle_edgelist (ncount, cycfname, tour, 0);
104 if (rval) {
105 fprintf (stderr, "CCutil_getcycle_edgelist failed\n");
106 goto CLEANUP;
107 }
108 }
109
110 {
111 int *chk = (int *) NULL;
112 int i;
113
114 chk = CC_SAFE_MALLOC (ncount, int);
115 CCcheck_NULL (chk, "out of memory in main");
116
117 for (i = 0; i < ncount; i++) chk[i] = 0;
118 for (i = 0; i < ncount; i++) {
119 if (chk[tour[i]] == 1) {
120 fprintf (stderr, "duplicate node in tour: %d, position %d\n",
121 tour[i], i);
122 rval = 1; goto CLEANUP;
123 }
124 chk[tour[i]] = 1;
125 }
126 CC_IFFREE (chk, int);
127 }
128
129 if (edgefname) {
130 int istour;
131 rval = CCutil_sparse_real_tour (ncount, &dat, tour, &istour);
132 if (rval) {
133 fprintf (stderr, "CCutil_sparse_real_tour failed\n");
134 goto CLEANUP;
135 }
136 if (istour == 0) {
137 printf ("Tour is not contained in the sparse edge set\n");
138 fflush (stdout);
139 goto CLEANUP;
140 }
141 }
142
143 CCutil_cycle_len (ncount, &dat, tour, &val);
144 printf ("Tour Length: %.0f\n", val); fflush (stdout);
145
146
147 CLEANUP:
148
149 CC_IFFREE (tour, int);
150 CCutil_freedatagroup (&dat);
151
152 return rval;
153 }
154
parseargs(int ac,char ** av)155 static int parseargs (int ac, char **av)
156 {
157 int c;
158 int boptind = 1;
159 char *boptarg = (char *) NULL;
160
161 while ((c = CCutil_bix_getopt (ac, av, "eE:tT:", &boptind, &boptarg)) != EOF) {
162 switch (c) {
163 case 'e':
164 eformat = 1;
165 break;
166 case 'E':
167 edgefname = boptarg;
168 break;
169 case 't':
170 simpletour = 1;
171 break;
172 case 'T':
173 tspfname = boptarg;
174 break;
175 case CC_BIX_GETOPT_UNKNOWN:
176 case '?':
177 default:
178 usage (av[0]);
179 return 1;
180 }
181 }
182
183 if (boptind < ac) {
184 cycfname = av[boptind++];
185 } else {
186 usage (av[0]);
187 return 1;
188 }
189
190 return 0;
191 }
192
usage(char * fname)193 static void usage (char *fname)
194 {
195 fprintf (stderr, "Usage: %s [-flags below] tour_file\n", fname);
196 fprintf (stderr, " -e tour file is an edge list (default is TSPLIB)\n");
197 fprintf (stderr, " -t tour file in concorde permutation format (default TSPLIB)\n");
198 fprintf (stderr, " -E f edge file to specify lengths\n");
199 fprintf (stderr, " -T f TSPLIB file to specify lengths\n");
200 }
201