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 /* ROUTINES TO MAINTAIN SKELETONS */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: October 19, 1997 */
25 /* January 28, 2003 (bico) */
26 /* */
27 /* These routines maintain skeletons for CCtsp_lpcut and CCtsp_lpcut_in. */
28 /* A skeleton is a set of atoms of the cut, and is represented by a */
29 /* sorted array of the lowest numbered node in each atom. The only */
30 /* function that cares about which representative is chosen for each */
31 /* atom, or the order of the atoms is CCtsp_compare_skeleton. */
32 /* */
33 /* EXPORTED FUNCTIONS: */
34 /* */
35 /* void CCtsp_init_skeleton (CCtsp_skeleton *skel) */
36 /* INITIALIZES a skeleton (to the NULL skeleton) */
37 /* */
38 /* void CCtsp_free_skeleton (CCtsp_skeleton *skel) */
39 /* FREES the memory used by skel */
40 /* */
41 /* int CCtsp_copy_skeleton (CCtsp_skeleton *old, CCtsp_skeleton *new) */
42 /* COPIES a skeleton */
43 /* */
44 /* int CCtsp_read_skeleton (CC_SFILE *f, CCtsp_skeleton *skel, */
45 /* int ncount) */
46 /* READS a skeleton from f */
47 /* */
48 /* int CCtsp_write_skeleton (CC_SFILE *f, CCtsp_skeleton *skel, */
49 /* int ncount) */
50 /* WRITES a skeleton to f */
51 /* */
52 /* int CCtsp_construct_skeleton (CCtsp_lpcut_in *c, int nodecount) */
53 /* CONSTRUCTS a skeleton for c, representing all atoms in c */
54 /* */
55 /* void CCtsp_compare_skeletons (CCtsp_skeleton *a, CCtsp_skeleton *b, */
56 /* int *diff) */
57 /* COMPARES two skeletons, setting *diff=0 if they are the same, and */
58 /* *diff=1 if they are not. */
59 /* */
60 /****************************************************************************/
61
62 #include "machdefs.h"
63 #include "util.h"
64 #include "tsp.h"
65
66 #define SKELETON_WILD 0
67
68 #undef DEBUG_CONSTRUCT
69
CCtsp_init_skeleton(CCtsp_skeleton * skel)70 void CCtsp_init_skeleton (CCtsp_skeleton *skel)
71 {
72 skel->atomcount = 0;
73 skel->atoms = (int *) NULL;
74 }
75
CCtsp_free_skeleton(CCtsp_skeleton * skel)76 void CCtsp_free_skeleton (CCtsp_skeleton *skel)
77 {
78 if (skel != (CCtsp_skeleton *) NULL) {
79 skel->atomcount = 0;
80 CC_IFFREE (skel->atoms, int);
81 }
82 }
83
CCtsp_copy_skeleton(CCtsp_skeleton * old,CCtsp_skeleton * new)84 int CCtsp_copy_skeleton (CCtsp_skeleton *old, CCtsp_skeleton *new)
85 {
86 int i;
87
88 CCtsp_init_skeleton (new);
89
90 if (old->atomcount == 0) return 0;
91 new->atoms = CC_SAFE_MALLOC (old->atomcount, int);
92 if (new->atoms == (int *) NULL) {
93 fprintf (stderr, "Out of memory in CCtsp_copy_skeleton\n");
94 return 1;
95 }
96 for (i=0; i<old->atomcount; i++) {
97 new->atoms[i] = old->atoms[i];
98 }
99 new->atomcount = old->atomcount;
100
101 return 0;
102 }
103
CCtsp_read_skeleton(CC_SFILE * f,CCtsp_skeleton * skel,int ncount)104 int CCtsp_read_skeleton (CC_SFILE *f, CCtsp_skeleton *skel, int ncount)
105 {
106 int rval;
107 int atomcount;
108 int i;
109 int nbits = CCutil_sbits (ncount);
110 char type;
111
112 CCtsp_init_skeleton (skel);
113
114 rval = CCutil_sread_char (f, &type);
115 if (rval) {
116 fprintf (stderr, "CCutil_sread_char failed\n");
117 goto CLEANUP;
118 }
119
120 switch (type) {
121 case SKELETON_WILD:
122 rval = CCutil_sread_bits (f, &atomcount, nbits);
123 if (rval) {
124 fprintf (stderr, "CCutil_sread_bits failed\n");
125 goto CLEANUP;
126 }
127 skel->atomcount = atomcount;
128
129 if (atomcount == 0) {
130 skel->atoms = (int *) NULL;
131 rval = 0;
132 goto CLEANUP;
133 }
134
135 skel->atoms = CC_SAFE_MALLOC (atomcount, int);
136 if (skel->atoms == (int *) NULL) {
137 fprintf (stderr, "Out of memory in CCtsp_read_skeleton\n");
138 rval = 1; goto CLEANUP;
139 }
140
141 for (i=0; i<atomcount; i++) {
142 rval = CCutil_sread_bits (f, &skel->atoms[i], nbits);
143 if (rval) {
144 fprintf (stderr, "CCutil_sread_bits failed\n");
145 goto CLEANUP;
146 }
147 }
148 break;
149 default:
150 fprintf (stderr, "Unknown skeleton type %ud\n", (unsigned) type);
151 rval = 1; goto CLEANUP;
152 }
153 rval = 0;
154
155 CLEANUP:
156 if (rval) {
157 CCtsp_free_skeleton (skel);
158 }
159 return rval;
160 }
161
CCtsp_write_skeleton(CC_SFILE * f,CCtsp_skeleton * skel,int ncount)162 int CCtsp_write_skeleton (CC_SFILE *f, CCtsp_skeleton *skel, int ncount)
163 {
164 int rval;
165 int atomcount = skel->atomcount;
166 int i;
167 int nbits = CCutil_sbits (ncount);
168
169 rval = CCutil_swrite_char (f, SKELETON_WILD);
170 if (rval) {
171 fprintf (stderr, "CCutil_swrite_char failed\n");
172 goto CLEANUP;
173 }
174
175 rval = CCutil_swrite_bits (f, atomcount, nbits);
176 if (rval) {
177 fprintf (stderr, "CCutil_swrite_bits failed\n");
178 goto CLEANUP;
179 }
180
181 for (i=0; i<atomcount; i++) {
182 rval = CCutil_swrite_bits (f, skel->atoms[i], nbits);
183 if (rval) {
184 fprintf (stderr, "CCutil_swrite_bits failed\n");
185 goto CLEANUP;
186 }
187 }
188
189 rval = 0;
190
191 CLEANUP:
192 return rval;
193 }
194
CCtsp_construct_skeleton(CCtsp_lpcut_in * c,int nodecount)195 int CCtsp_construct_skeleton (CCtsp_lpcut_in *c, int nodecount)
196 {
197 int cliquecount = c->cliquecount;
198 CCtsp_lpclique *cliques = c->cliques;
199 int *label = (int *) NULL;
200 int ccount;
201 int *cnodes = (int *) NULL;
202 int atomcount;
203 int atomcount_save;
204 int *atomsize = (int *) NULL;
205 int *atomnew = (int *) NULL;
206 int *atomwork = (int *) NULL;
207 int *atoms = (int *) NULL;
208 int i;
209 int j;
210 int tmp;
211 int rval = 0;
212
213 if (c->dominocount != 0) {
214 printf ("Skeleton Yipes %d\n", c->dominocount);
215 fflush (stdout);
216 exit (1);
217 }
218
219 CCtsp_init_skeleton (&c->skel);
220 if (c->dominocount > 0) goto CLEANUP; /* don't build for dominos */
221
222 label = CC_SAFE_MALLOC (nodecount, int);
223 if (label == (int *) NULL) {
224 fprintf (stderr, "Out of memory in CCtsp_construct_skeleton\n");
225 rval = 1; goto CLEANUP;
226 }
227
228 /* initialize labels */
229 for (i=0; i<cliquecount; i++) {
230 CC_FOREACH_NODE_IN_CLIQUE (j, cliques[i], tmp) {
231 label[j] = 0;
232 }
233 }
234
235 /* count nodes */
236 ccount = 0;
237 for (i=0; i<cliquecount; i++) {
238 CC_FOREACH_NODE_IN_CLIQUE (j, cliques[i], tmp) {
239 if (label[j] == 0) {
240 label[j] = 1;
241 ccount++;
242 }
243 }
244 }
245
246 cnodes = CC_SAFE_MALLOC (ccount, int);
247 atomsize = CC_SAFE_MALLOC (ccount+1, int);
248 atomnew = CC_SAFE_MALLOC (ccount+1, int);
249 atomwork = CC_SAFE_MALLOC (ccount+1, int);
250 if (cnodes == (int *) NULL ||
251 atomsize == (int *) NULL ||
252 atomnew == (int *) NULL ||
253 atomwork == (int *) NULL) {
254 fprintf (stderr, "Out of memory in CCtsp_construct_skeleton\n");
255 rval = 1; goto CLEANUP;
256 }
257
258 /* collect nodes */
259 ccount = 0;
260 for (i=0; i<cliquecount; i++) {
261 CC_FOREACH_NODE_IN_CLIQUE (j, cliques[i], tmp) {
262 if (label[j] == 1) {
263 label[j] = 0;
264 cnodes[ccount++] = j;
265 }
266 }
267 }
268
269 CCutil_int_array_quicksort (cnodes, ccount);
270
271 /* refine atoms */
272 atomsize[0] = ccount;
273 atomcount = 1;
274 for (i=0; i<cliquecount; i++) {
275 for (j=0; j<atomcount; j++) {
276 atomwork[j] = 0;
277 }
278 CC_FOREACH_NODE_IN_CLIQUE (j, cliques[i], tmp) {
279 atomwork[label[j]]++;
280 }
281 atomcount_save = atomcount;
282 for (j=0; j<atomcount_save; j++) {
283 if (atomwork[j] == 0) {
284 atomnew[j] = -1;
285 } else if (atomwork[j] == atomsize[j]) {
286 atomnew[j] = j;
287 } else {
288 atomsize[atomcount] = atomwork[j];
289 atomsize[j] -= atomwork[j];
290 atomnew[j] = atomcount;
291 atomcount++;
292 }
293 }
294 CC_FOREACH_NODE_IN_CLIQUE (j, cliques[i], tmp) {
295 label[j] = atomnew[label[j]];
296 }
297 }
298
299 atomcount_save = atomcount;
300 if (ccount < nodecount) {
301 atomcount += 1;
302 }
303 atoms = CC_SAFE_MALLOC (atomcount, int);
304 if (atoms == (int *) NULL) {
305 fprintf (stderr, "Out of memory in CCtsp_construct_skeleton\n");
306 rval = 1; goto CLEANUP;
307 }
308
309 for (i=0; i<atomcount; i++) {
310 atoms[i] = -1;
311 }
312
313 /* find representatives */
314 for (i=0; i<ccount; i++) {
315 if (atoms[label[cnodes[i]]] == -1) {
316 atoms[label[cnodes[i]]] = cnodes[i];
317 }
318 }
319
320 if (ccount < nodecount) {
321 if (cnodes[ccount-1] == ccount-1) {
322 atoms[atomcount_save] = ccount;
323 } else {
324 for (i=0; i<ccount; i++) {
325 if (cnodes[i] != i) {
326 atoms[atomcount_save] = i;
327 break;
328 }
329 }
330 }
331 }
332
333 CCutil_int_array_quicksort (atoms, atomcount);
334
335 c->skel.atoms = atoms;
336 c->skel.atomcount = atomcount;
337 atoms = (int *) NULL;
338
339 #ifdef DEBUG_CONSTRUCT
340 printf ("skeleton:");
341 for (i=0; i<c->skel.atomcount; i++) {
342 printf (" %d", c->skel.atoms[i]);
343 }
344 printf ("\n");
345 fflush (stdout);
346 #endif
347
348 rval = 0;
349
350 CLEANUP:
351 CC_IFFREE (atoms, int);
352 CC_IFFREE (atomwork, int);
353 CC_IFFREE (atomnew, int);
354 CC_IFFREE (atomsize, int);
355 CC_IFFREE (cnodes, int);
356 CC_IFFREE (label, int);
357 if (rval) {
358 CCtsp_free_skeleton (&c->skel);
359 }
360 return rval;
361 }
362
CCtsp_compare_skeletons(CCtsp_skeleton * a,CCtsp_skeleton * b,int * diff)363 void CCtsp_compare_skeletons (CCtsp_skeleton *a, CCtsp_skeleton *b, int *diff)
364 {
365 int i;
366
367 *diff = 1;
368 if (a->atomcount != b->atomcount) {
369 return;
370 }
371 for (i=0; i<a->atomcount; i++) {
372 if (a->atoms[i] != b->atoms[i]) {
373 return;
374 }
375 }
376 *diff = 0;
377 }
378