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