1 /***************************************************************************/
2 /* */
3 /* MERGE CUTPOOLS */
4 /* */
5 /* TSP CODE */
6 /* */
7 /* */
8 /* Written by: Applegate, Bixby, Chvatal, and Cook */
9 /* Date: May 2, 1997 */
10 /* */
11 /* SEE short decsribtion in usage (). */
12 /* */
13 /* Link with: */
14 /* SEE Makefile */
15 /* */
16 /***************************************************************************/
17
18 #include "machdefs.h"
19 #include "util.h"
20 #include "tsp.h"
21
22 static int seed = 0;
23
24 #ifdef CC_PROTOTYPE_ANSI
25
26 int
27 main (int ac, char **av);
28
29 static void
30 usage (char *f);
31
32 #else
33
34 int
35 main ();
36
37 static void
38 usage ();
39
40 #endif
41
42
43 #ifdef CC_PROTOTYPE_ANSI
main(int ac,char ** av)44 int main (int ac, char **av)
45 #else
46 int main (ac, av)
47 int ac;
48 char **av;
49 #endif
50 {
51 double szeit;
52 int i, k, count;
53 CCtsp_lpcut_in *c, *cnext;
54 CCtsp_lpcut_in *cuts = (CCtsp_lpcut_in *) NULL;
55 CCtsp_lpcuts *pool = (CCtsp_lpcuts *) NULL;
56 CCtsp_lpcuts *nextpool = (CCtsp_lpcuts *) NULL;
57 CC_SFILE *in;
58 int ncount;
59 int textout, textin;
60 int *ptour = (int *) NULL;
61 int *qtour = (int *) NULL;
62 int *perm = (int *) NULL;
63 int rval = 0;
64
65 if (ac < 2) {
66 usage (*av);
67 return 0;
68 }
69
70 szeit = CCutil_zeit ();
71 seed = (int) CCutil_real_zeit ();
72 CCutil_sprand (seed);
73
74 k = 1;
75 if (av[k][0] == '-' && av[k][1] == 't') {
76 CCdatagroup dat;
77 printf ("Read master ...\n");
78 if (CCutil_getmaster (av[k+1], &ncount, &dat, &ptour)) {
79 fprintf (stderr, "CCutil_getmaster failed\n");
80 return 1;
81 }
82 CCutil_freedatagroup (ncount, &dat);
83 textout = 1;
84 k += 2;
85 } else {
86 textout = 0;
87 }
88
89 if (av[k][0] == '-' && av[k][1] == 's') {
90 CCdatagroup dat;
91 printf ("Read master ...\n");
92 if (CCutil_getmaster (av[k+1], &ncount, &dat, &qtour)) {
93 fprintf (stderr, "CCutil_getmaster failed\n");
94 return 1;
95 }
96 CCutil_freedatagroup (ncount, &dat);
97 textin = 1;
98 k += 2;
99 } else {
100 textin = 0;
101 }
102
103 if (av[k][0] == '-' && av[k][1] == 'p') {
104 FILE *tin = fopen (av[k+1], "r");
105
106 printf ("Read permutation tour ...\n");
107 if (!tin) {
108 fprintf (stderr, "could not open %s for reading\n", av[k+1]);
109 rval = 1; goto CLEANUP;
110 }
111
112 if (fscanf (tin, "%d", &ncount) != 1) {
113 fprintf (stderr, "perm file in wrong format\n");
114 rval = 1; fclose (tin); goto CLEANUP;
115 }
116 perm = CC_SAFE_MALLOC (ncount, int);
117 if (!perm) {
118 fprintf (stderr, "out of memory in main\n");
119 rval = 1; fclose (tin); goto CLEANUP;
120 }
121 for (i = 0; i < ncount; i++) {
122 if (fscanf (tin, "%d", &(perm[i])) != 1) {
123 fprintf (stderr, "perm file in wrong format\n");
124 rval = 1; fclose (tin); goto CLEANUP;
125 }
126 }
127 fclose (tin);
128 k += 2;
129 }
130
131 if (textin) {
132 printf ("Number of Nodes: %d\n", ncount); fflush (stdout);
133
134 rval = CCtsp_init_cutpool (ncount, (char *) NULL, &pool);
135 if (rval) {
136 fprintf (stderr, "CCtsp_init_cutpool failed\n"); goto CLEANUP;
137 }
138
139 cuts = (CCtsp_lpcut_in *) NULL;
140 rval = CCtsp_file_cuts (av[k], &cuts, &count, ncount, qtour);
141 if (rval) {
142 fprintf (stderr, "CCtsp_file_cuts failed\n"); goto CLEANUP;
143 }
144 printf ("File has %d cuts\n", count); fflush (stdout);
145 for (c = cuts; c; c = cnext) {
146 cnext = c->next;
147 rval = CCtsp_add_to_cutpool_lpcut_in (pool, c);
148 if (rval) {
149 fprintf (stderr, "CCtsp_add_to_cutpool_lpcut_in failed\n");
150 goto CLEANUP;
151 }
152 CCtsp_free_lpcut_in (c);
153 CC_FREE (c, CCtsp_lpcut_in);
154 }
155 k++;
156 } else {
157 in = CCutil_sopen (av[k], "r");
158 if (!in) {
159 fprintf (stderr, "sopen failed\n"); goto CLEANUP;
160 }
161 if (CCutil_sread_int (in, (unsigned int *) &ncount)) {
162 fprintf (stderr, "CCutil_sread_int failed\n");
163 CCutil_sclose (in);
164 return 1;
165 }
166 CCutil_sclose (in);
167 printf ("Number of Nodes: %d\n", ncount); fflush (stdout);
168
169 rval = CCtsp_init_cutpool (ncount, av[k], &pool);
170 if (rval) {
171 fprintf (stderr, "CCtsp_init_cutpool failed\n"); goto CLEANUP;
172 }
173 printf ("Initial Pool: %d cuts\n", pool->cutcount);
174 fflush (stdout);
175 k++;
176 }
177
178 for (; k < ac; k++) {
179 printf ("Adding Pool %s ... ", av[k]);
180 fflush (stdout);
181
182 if (textin) {
183 cuts = (CCtsp_lpcut_in *) NULL;
184 rval = CCtsp_file_cuts (av[k], &cuts, &count, ncount, qtour);
185 if (rval) {
186 fprintf (stderr, "CCtsp_file_cuts failed\n"); goto CLEANUP;
187 }
188 for (c = cuts; c; c = cnext) {
189 cnext = c->next;
190 rval = CCtsp_add_to_cutpool_lpcut_in (pool, c);
191 if (rval) {
192 fprintf (stderr, "CCtsp_add_to_cutpool_lpcut_in failed\n");
193 goto CLEANUP;
194 }
195 CCtsp_free_lpcut_in (c);
196 CC_FREE (c, CCtsp_lpcut_in);
197 }
198 } else {
199 rval = CCtsp_init_cutpool (ncount, av[k], &nextpool);
200 if (rval) {
201 fprintf (stderr, "CCtsp_init_cutpool failed\n"); goto CLEANUP;
202 }
203
204 for (i = 0; i < nextpool->cutcount; i++) {
205 rval = CCtsp_add_to_cutpool (pool, nextpool,
206 &(nextpool->cuts[i]));
207 if (rval) {
208 fprintf (stderr, "CCtsp_add_to_cutpool failed\n");
209 goto CLEANUP;
210 }
211 }
212 CCtsp_free_cutpool (&nextpool);
213 }
214 printf ("%d\n", pool->cutcount); fflush (stdout);
215 }
216
217
218 printf ("Final Pool: %d cuts\n", pool->cutcount);
219 fflush (stdout);
220
221 if (textout) {
222 printf ("Write text file ...\n"); fflush (stdout);
223 if (perm) {
224 int *pperm = (int *) NULL;
225
226 pperm = CC_SAFE_MALLOC (ncount, int);
227 if (!pperm) {
228 fprintf (stderr, "out of memory in main\n");
229 rval = 1; goto CLEANUP;
230 }
231 for (i = 0; i < ncount; i++) {
232 pperm[i] = perm[ptour[i]];
233 }
234 for (i = 0; i < ncount; i++) {
235 ptour[i] = pperm[i];
236 }
237 CC_FREE (pperm, int);
238 }
239 rval = CCtsp_file_cuts_write ("merge.txt", pool, ptour);
240 if (rval) {
241 fprintf (stderr, "CCtsp_file_cuts_write failed\n");
242 goto CLEANUP;
243 }
244 } else {
245 rval = CCtsp_write_cutpool (ncount, "merge.pul", pool);
246 if (rval) {
247 fprintf (stderr, "CCtsp_write_cutpool failed\n");
248 goto CLEANUP;
249 }
250 }
251
252 printf ("Running Time: %.2f seconds\n", CCutil_zeit () - szeit);
253 fflush (stdout);
254
255 CLEANUP:
256
257 if (pool) {
258 CCtsp_free_cutpool (&pool);
259 }
260 if (nextpool) {
261 CCtsp_free_cutpool (&nextpool);
262 }
263 if (CCutil_bigchunk_free_world ()) {
264 fprintf (stderr, "ERROR: CCutil_bigchunk_free_world failed\n");
265 return 1;
266 }
267 CC_IFFREE (ptour, int);
268 CC_IFFREE (qtour, int);
269
270 return rval;
271 }
272
273 #ifdef CC_PROTOTYPE_ANSI
usage(char * f)274 static void usage (char *f)
275 #else
276 static void usage (f)
277 char *f;
278 #endif
279 {
280 fprintf (stderr, "Usage: %s [-t] pool1 pool2 ... \n", f);
281 fprintf (stderr, " -t f: to write a text file specify a master\n");
282 fprintf (stderr, " -p f: to permute nodes when writing text\n");
283 fprintf (stderr, " -s f: to read text files specify a master\n");
284 fprintf (stderr, "Note: merged pool will be written merge.pul (.txt)\n");
285 fprintf (stderr, " the master files are used to map the nodes\n");
286 fprintf (stderr, " the permuation given by p can be used to\n");
287 fprintf (stderr, " handle the different node orders in dat and tsp\n");
288 }
289