1 /************************************************************************/
2 /* */
3 /* ROUTINE FOR WEIGHTED PERFECT MATCHING PROBLEMS */
4 /* */
5 /* Written by: A. Rohe */
6 /* Date: November 7, 1995 (rohe) */
7 /* November 12, 1995 (rohe) */
8 /* February 7, 1996 (rohe - short look at program) */
9 /* July, 1996 (rohe - change from tree to forest) */
10 /* October, 1996 (bico - change to concorde format) */
11 /* */
12 /************************************************************************/
13
14 #include "concorde.h"
15 #include "match.h"
16
17 #ifdef CC_PROTOTYPE_ANSI
18
19 static void
20 usage (char *name);
21 static int
22 parseargs (int ac, char **av);
23
24 #else
25
26 static void
27 usage ();
28 static int
29 parseargs ();
30
31 #endif
32
33 static int seed = 0;
34 static char *blossom_file = (char *) NULL;
35 static char *match_file = (char *) NULL;
36 static char *datfilename = (char *) NULL;
37 static char *edgefilename = (char *) NULL;
38 static char *edgegenfname = (char *) NULL;
39 static int no_frac = 0;
40 static int just_frac = 0;
41 static int use_all_trees = 0;
42 static int binary_in = 0;
43 static int tsplib_in = 0;
44 static int nnodes_want = 0;
45 static int partialprice = 0;
46 static int norm = CC_EUCLIDEAN;
47 static int no_price = 0;
48
49 #ifdef CC_PROTOTYPE_ANSI
main(int ac,char ** av)50 int main (int ac, char **av)
51 #else
52 int main (ac, av)
53 int ac;
54 char **av;
55 #endif
56 {
57 double zero_zeit = CCutil_zeit ();
58 double matzeit = 0.0;
59 double genzeit = 0.0;
60 int ncount, ecount;
61 int *elist = (int *) NULL;
62 int *elen = (int *) NULL;
63 long l;
64 CCdatagroup dat, *mydat = (CCdatagroup *) NULL;
65
66 seed = time (&l);
67 if (parseargs (ac, av))
68 return 0;
69 CCutil_sprand (seed);
70
71 if (edgefilename == (char *) NULL && datfilename == (char *) NULL &&
72 nnodes_want == 0) {
73 usage (av[0]);
74 return 0;
75 }
76 ncount = nnodes_want;
77
78 if (tsplib_in && datfilename != (char *) NULL) {
79 if (CCutil_gettsplib (datfilename, &ncount, &dat)) {
80 fprintf (stderr, "could not read the TSPLIB file\n");
81 goto CLEANUP;
82 }
83 mydat = &dat;
84 norm = dat.norm;
85 } else if (datfilename != (char *) NULL || nnodes_want != 0) {
86 if (CCutil_getdata (datfilename, binary_in, norm, &ncount, &dat)) {
87 fprintf (stderr, "Could not create data set\n");
88 goto CLEANUP;
89 }
90 mydat = &dat;
91 } else {
92 mydat = (CCdatagroup *) NULL;
93 }
94
95 if (mydat) {
96 if (CCutil_init_dat_edgelen (mydat)) {
97 fprintf (stderr, "init_dat_edgelen failed\n");
98 goto CLEANUP;
99 }
100 }
101
102 if (edgefilename) {
103 if (CCutil_getedgelist_n (&ncount, edgefilename, &ecount, &elist, &elen)) {
104 fprintf (stderr, "getedgelist_n failed\n");
105 goto CLEANUP;
106 }
107 } else {
108 CCedgegengroup plan;
109 int i;
110
111 if (edgegenfname) {
112 if (CCedgegen_read (edgegenfname, &plan)) {
113 fprintf (stderr, "CCedgegen_read failed\n");
114 goto CLEANUP;
115 }
116 } else {
117 CCedgegen_init_edgegengroup (&plan);
118 if ((norm & CC_NORM_BITS) != CC_KD_NORM_TYPE) {
119 plan.nearest = 5;
120 } else {
121 plan.quadnearest = 2;
122 plan.tour.nearest_count = 1;
123 }
124 }
125 genzeit = CCutil_zeit ();
126 if (CCedgegen_edges (&plan, ncount, mydat, (double *) NULL, &ecount,
127 &elist)) {
128 fprintf (stderr, "CCedgegen_edges failed\n");
129 goto CLEANUP;
130 }
131 elen = CC_SAFE_MALLOC (ecount, int);
132 if (!elen) {
133 fprintf (stderr, "out of memory in main\n");
134 CC_FREE (elist, int);
135 goto CLEANUP;
136 }
137 for (i = 0; i < ecount; i++) {
138 elen[i] = CCutil_dat_edgelen (elist[2*i], elist[2*i+1], mydat);
139 }
140 genzeit = CCutil_zeit () - genzeit;
141 }
142
143 if (mydat != (CCdatagroup *) NULL && no_price) {
144 CCutil_freedatagroup (ncount, mydat);
145 mydat = (CCdatagroup *) NULL;
146 }
147
148 printf ("ZZ nnodes: %d seed: %d\n", ncount, seed); fflush (stdout);
149
150 if (perfect_match (ncount, mydat, ecount, &elist, &elen,
151 blossom_file, match_file, just_frac, no_frac,
152 use_all_trees, partialprice, &matzeit)) {
153 fprintf (stderr, "perfect_match failed\n");
154 goto CLEANUP;
155 }
156
157 CLEANUP:
158
159 if (mydat != (CCdatagroup *) NULL) {
160 CCutil_freedatagroup (ncount, mydat);
161 }
162
163 printf ("\nZZ Running Time: %.2f seconds (Edgegen %.2f, Matching %.2f)\n",
164 genzeit + matzeit, genzeit, matzeit);
165 printf ("ZZ Total Time: %.2f Seconds (includes IO and checking)\n",
166 CCutil_zeit () - zero_zeit);
167 fflush (stdout);
168
169 return 0;
170 }
171
172 #ifdef CC_PROTOTYPE_ANSI
parseargs(int ac,char ** av)173 static int parseargs (int ac, char **av)
174 #else
175 static int parseargs (ac, av)
176 int ac;
177 char **av;
178 #endif
179 {
180 int c;
181
182 while ((c = CCutil_bix_getopt (ac, av, "bB:dD:e:fjk:lp:Ps:tTx:w:0123456789")) != EOF)
183 switch (c) {
184 case 'b':
185 binary_in = 1;
186 break;
187 case 'B':
188 blossom_file = CCutil_bix_optarg;
189 break;
190 case 'd':
191 use_all_trees = 2;
192 break;
193 case 'D':
194 edgegenfname = CCutil_bix_optarg;
195 break;
196 case 'e':
197 edgefilename = CCutil_bix_optarg;
198 break;
199 case 'f':
200 just_frac = 1;
201 break;
202 case 'j':
203 no_frac = 1;
204 break;
205 case 'k':
206 nnodes_want = atoi (CCutil_bix_optarg);
207 break;
208 case 'p':
209 partialprice = atoi (CCutil_bix_optarg);
210 break;
211 case 'P':
212 no_price = 1;
213 break;
214 case 's':
215 seed = atoi (CCutil_bix_optarg);
216 break;
217 case 't':
218 use_all_trees = 1;
219 break;
220 case 'T':
221 tsplib_in = 1;
222 break;
223 case 'w':
224 match_file = CCutil_bix_optarg;
225 break;
226 case 'x':
227 datfilename = CCutil_bix_optarg;
228 break;
229 case '0':
230 norm = CC_MAXNORM;
231 break;
232 case '1':
233 norm = CC_EUCLIDEAN_CEIL;
234 break;
235 case '2':
236 norm = CC_EUCLIDEAN;
237 break;
238 case '3':
239 norm = CC_EUCLIDEAN_3D;
240 break;
241 case '4':
242 norm = CC_IBM;
243 break;
244 case '5':
245 norm = CC_ATT;
246 break;
247 case '6':
248 norm = CC_GEOGRAPHIC;
249 break;
250 case '7':
251 norm = CC_MATRIXNORM;
252 break;
253 case '8':
254 norm = CC_DSJRANDNORM;
255 break;
256 case '9':
257 norm = CC_CRYSTAL;
258 break;
259 case CC_BIX_GETOPT_UNKNOWN:
260 case '?':
261 default:
262 usage (av[0]);
263 return 1;
264 }
265
266 if (CCutil_bix_optind != ac) {
267 usage (av[0]);
268 return 1;
269 }
270 return 0;
271 }
272
273 #ifdef CC_PROTOTYPE_ANSI
usage(char * name)274 static void usage (char *name)
275 #else
276 static void usage (name)
277 char *name;
278 #endif
279 {
280 fprintf (stderr, "Usage: %s [-see below-]\n", name);
281 fprintf (stderr, " -b datfile in integer binary format\n");
282 fprintf (stderr, " -B f blossom-tree-file (for writing)\n");
283 fprintf (stderr, " -d grow a single tree\n");
284 fprintf (stderr, " -D f edgegen description file (initial edges)\n");
285 fprintf (stderr, " -e f edge_file\n");
286 fprintf (stderr, " -f just fractional\n");
287 fprintf (stderr, " -j no fractional jumpstart\n");
288 fprintf (stderr, " -k # number of nodes for random problem\n");
289 fprintf (stderr, " -p # number of neighbors in partial pricing\n");
290 fprintf (stderr, " -P do not do pricing (just solve initial set)\n");
291 fprintf (stderr, " -s # random seed\n");
292 fprintf (stderr, " -t make same dual change to all trees\n");
293 fprintf (stderr, " -T the dat file is a TSPLIB file\n");
294 fprintf (stderr, " -w f match_file (for writing)\n");
295 fprintf (stderr, " -x f datfile for pricing\n");
296 fprintf (stderr, " -0 Max norm for edge lengths\n");
297 fprintf (stderr, " -1 Ceiling Euclidean norm - from DSJ\n");
298 fprintf (stderr, " -2 Rounded Euclidean norm (default)\n");
299 fprintf (stderr, " -3 Rounded Euclidean 3D norm\n");
300 fprintf (stderr, " -(4 5 6 7 8 9) IBM ATT GEO MATRIX DSJRAND CRYSTAL norm\n");
301 }
302