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 /* BUILD SIMPLE CLIQUETREE FROM A COMB */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: July 3, 1997 */
25 /* */
26 /* */
27 /* EXPORTED FUNCTIONS: */
28 /* */
29 /* int CCtsp_test_pure_simple_cliquetree (int ncount, */
30 /* CCtsp_lpcut_in *c, int *yes_no) */
31 /* TEST if cut is a two handled cliquetree (assumes first two cliques */
32 /* cliques in the cut are the handles). */
33 /* -ncount is the number of nodes in the graph. */
34 /* -c points to the cut. */
35 /* -yes_no will be set to either 0 or 1, with 1 meaning yes. */
36 /* */
37 /* int CCtsp_comb_to_cliquetree (CCtsp_lpgraph *g, CC_GCgraph *h, */
38 /* double *x, CCtsp_lpcut_in *c, CCtsp_lpcut_in **d) */
39 /* ATTEMPTS to build a cliquetree from the comb by adding a bunny. */
40 /* -x is an lp vector (it should match the edge set of the graph g) */
41 /* -c is the comb (it will be tested) */
42 /* -d returns the double decker or NULL if none is found */
43 /* */
44 /****************************************************************************/
45
46 #include "machdefs.h"
47 #include "macrorus.h"
48 #include "util.h"
49 #include "tsp.h"
50 #include "combs.h"
51
52
53 static void
54 mark_GCgraph_clique (CC_GCgraph *g, CCtsp_lpclique *c, int marker);
55
56 static int
57 comb_to_cliquetree (CCtsp_lpgraph *g, CC_GCgraph *h, CCtsp_lpclique *handle,
58 int nteeth, CCtsp_lpclique **teeth, double *x, CCtsp_lpcut_in **cuts),
59 build_cliquetree (CCtsp_lpcut_in **cut, int nteeth, CCtsp_lpclique **teeth,
60 CCtsp_lpclique *hand1, CCtsp_lpclique *hand2, int ncount);
61
62
63
CCtsp_comb_to_cliquetree(CCtsp_lpgraph * g,CC_GCgraph * h,double * x,CCtsp_lpcut_in * c,CCtsp_lpcut_in ** d)64 int CCtsp_comb_to_cliquetree (CCtsp_lpgraph *g, CC_GCgraph *h, double *x,
65 CCtsp_lpcut_in *c, CCtsp_lpcut_in **d)
66 {
67 int rval = 0;
68 int i, test, ihandle;
69 int nteeth = 0;
70 CCtsp_lpclique **teeth = (CCtsp_lpclique **) NULL;
71 CCtsp_lpclique *handle;
72
73 rval = CCtsp_test_pure_comb (g->ncount, c, &test, &ihandle);
74 if (rval) {
75 fprintf (stderr, "CCtsp_test_pure_comb failed\n"); goto CLEANUP;
76 }
77 if (!test) goto CLEANUP;
78
79 handle = &c->cliques[ihandle];
80 teeth = CC_SAFE_MALLOC (c->cliquecount - 1, CCtsp_lpclique *);
81 if (teeth == (CCtsp_lpclique **) NULL) {
82 fprintf (stderr, "out of memory in CCtsp_comb_to_cliquetree\n");
83 rval = 1; goto CLEANUP;
84 }
85 for (i = 0; i < c->cliquecount; i++) {
86 if (i != ihandle) {
87 teeth[nteeth++] = &c->cliques[i];
88 }
89 }
90
91 rval = comb_to_cliquetree (g, h, handle, nteeth, teeth, x, d);
92 if (rval) {
93 fprintf (stderr, "comb_to_cliquetree failed\n");
94 goto CLEANUP;
95 }
96
97 CLEANUP:
98
99 CC_IFFREE (teeth, CCtsp_lpclique *);
100
101 return rval;
102 }
103
comb_to_cliquetree(CCtsp_lpgraph * g,CC_GCgraph * h,CCtsp_lpclique * handle,int nteeth,CCtsp_lpclique ** teeth,double * x,CCtsp_lpcut_in ** cuts)104 static int comb_to_cliquetree (CCtsp_lpgraph *g, CC_GCgraph *h,
105 CCtsp_lpclique *handle, int nteeth, CCtsp_lpclique **teeth, double *x,
106 CCtsp_lpcut_in **cuts)
107 {
108 int rval = 0;
109 int nbig = 0;
110 int t1[2];
111 int t2[2];
112 double t1val, t2val;
113 int i, j, k, e, n, test;
114 CCtsp_lpclique **ctlist = (CCtsp_lpclique **) NULL;
115 CCtsp_lpclique **bigteeth = (CCtsp_lpclique **) NULL;
116 CCtsp_lpclique bunny;
117 CCtsp_lpclique ear1;
118 CCtsp_lpclique ear2;
119 CCtsp_lpcut_in *dp;
120 int *gset = (int *) NULL;
121 int *marks = (int *) NULL;
122 int *ar = (int *) NULL;
123 int gcount = 0;
124 int acount = 0;
125 double gval, gbestval;
126 int gbest;
127
128 gset = CC_SAFE_MALLOC (g->ncount, int);
129 marks = CC_SAFE_MALLOC (g->ncount, int);
130 if (gset == (int *) NULL || marks == (int *) NULL) {
131 fprintf (stderr, "out of memory in comb_to_cliquetree\n");
132 rval = 1; goto CLEANUP;
133 }
134
135 CCtsp_mark_clique_and_neighbors (g, handle, marks, 0);
136 for (i = 0; i < nteeth; i++) {
137 CCtsp_mark_clique_and_neighbors (g, teeth[i], marks, 0);
138 }
139
140 bigteeth = CC_SAFE_MALLOC (nteeth, CCtsp_lpclique *);
141 if (!bigteeth) {
142 fprintf (stderr, "out of memory in comb_to_cliquetree\n");
143 rval = 1; goto CLEANUP;
144 }
145
146 CCtsp_mark_clique (handle, marks, 1);
147 for (i = 0; i < nteeth; i++) {
148 CCtsp_clique_marked_count (teeth[i], marks, 0, &test);
149 if (test > 1) {
150 bigteeth[nbig++] = teeth[i];
151 }
152 }
153
154 mark_GCgraph_clique (h, handle, 1);
155 for (i = 0; i < nteeth; i++) {
156 mark_GCgraph_clique (h, teeth[i], 1);
157 }
158
159 for (k = 0; k < nbig; k++) {
160 gbestval = 1000.0;
161 gbest = -1;
162
163 CCtsp_mark_clique_and_neighbors (g, handle, marks, 0);
164 for (i = 0; i < nteeth; i++) {
165 CCtsp_mark_clique_and_neighbors (g, teeth[i], marks, 0);
166 }
167 for (i = 0; i < nteeth; i++) {
168 CCtsp_mark_clique (teeth[i], marks, 1);
169 }
170 CCtsp_mark_clique (handle, marks, 2);
171
172 rval = CCtsp_clique_to_array (bigteeth[k], &ar, &acount);
173 if (rval) {
174 fprintf (stderr, "CCtsp_clique_to_array failed\n");
175 goto CLEANUP;
176 }
177
178 for (i = 0; i < acount; i++) {
179 n = ar[i];
180 if (marks[n] == 1) {
181 gcount = 1;
182 gset[0] = n;
183
184 rval = CCcombs_greedy_cut (h, &gcount, gset, 1, 2, 0, 2,
185 (int *) NULL, &gval);
186 if (rval) {
187 fprintf (stderr, "CCcombs_greedy_cut failed\n");
188 goto CLEANUP;
189 }
190 if (gcount >= 3) {
191 if (gval < gbestval) {
192 gbestval = gval;
193 gbest = n;
194 }
195 }
196 }
197 }
198 CC_IFFREE (ar, int);
199
200 if (gbest != -1 && gbestval < 2.5) {
201 gcount = 1;
202 gset[0] = gbest;
203
204 rval = CCcombs_greedy_cut (h, &gcount, gset, 1, 2, 0, 2,
205 (int *) NULL, &gval);
206 if (rval) {
207 fprintf (stderr, "CCcombs_greedy_cut failed\n");
208 goto CLEANUP;
209 }
210
211 rval = CCtsp_array_to_lpclique (gset, gcount, &bunny);
212 if (rval) {
213 fprintf (stderr, "CCtsp_array_to_lpclique failed\n");
214 goto CLEANUP;
215 }
216
217 t1[0] = t1[1] = -1;
218 t2[0] = t2[1] = -1;
219 t1val = t2val = -1.0;
220
221 CCtsp_mark_clique_and_neighbors (g, &bunny, marks, 0);
222 CCtsp_mark_clique (&bunny, marks, 1);
223 CCtsp_mark_clique (handle, marks, 2);
224 for (i = 0; i < nteeth; i++) {
225 CCtsp_mark_clique (teeth[i], marks, 2);
226 }
227
228 for (i = 0; i < gcount; i++) {
229 n = gset[i];
230 if (marks[n] == 1) {
231 for (j = 0; j < g->nodes[n].deg; j++) {
232 e = g->nodes[n].adj[j].edge;
233 if (marks[g->nodes[n].adj[j].to] == 0) {
234 if (x[e] > t1val) {
235 t1val = x[e];
236 t1[0] = n;
237 t1[1] = g->nodes[n].adj[j].to;
238 }
239 }
240 }
241 }
242 }
243 if (t1val >= 0.1) {
244 marks[t1[0]] = 2;
245 marks[t1[1]] = 2;
246 for (i = 0; i < gcount; i++) {
247 n = gset[i];
248 if (marks[n] == 1) {
249 for (j = 0; j < g->nodes[n].deg; j++) {
250 e = g->nodes[n].adj[j].edge;
251 if (marks[g->nodes[n].adj[j].to] == 0) {
252 if (x[e] > t2val) {
253 t2val = x[e];
254 t2[0] = n;
255 t2[1] = g->nodes[n].adj[j].to;
256 }
257 }
258 }
259 }
260 }
261 }
262
263 if (t1val >= 0.1 && t2val >= 0.1) {
264 rval = CCtsp_array_to_lpclique (t1, 2, &ear1);
265 if (rval) {
266 fprintf (stderr, "CCtsp_array_to_lpclique failed\n");
267 goto CLEANUP;
268 }
269 rval = CCtsp_array_to_lpclique (t2, 2, &ear2);
270 if (rval) {
271 fprintf (stderr, "CCtsp_array_to_lpclique failed\n");
272 goto CLEANUP;
273 }
274
275 ctlist = CC_SAFE_MALLOC (nteeth + 2, CCtsp_lpclique *);
276 if (!ctlist) {
277 fprintf (stderr, "out of memory in comb2ddecker\n");
278 CCtsp_free_lpclique (&ear1);
279 CCtsp_free_lpclique (&ear2);
280 CCtsp_free_lpclique (&bunny);
281 goto CLEANUP;
282 }
283 for (i = 0; i < nteeth; i++) {
284 ctlist[i] = teeth[i];
285 }
286 ctlist[i++] = &ear1;
287 ctlist[i] = &ear2;
288
289 rval = build_cliquetree (&dp, nteeth + 2, ctlist, handle,
290 &bunny, g->ncount);
291 if (rval) {
292 fprintf (stderr, "build_cliquegtee failed\n");
293 CCtsp_free_lpclique (&ear1);
294 CCtsp_free_lpclique (&ear2);
295 CCtsp_free_lpclique (&bunny);
296 goto CLEANUP;
297 }
298
299 rval = CCtsp_test_pure_simple_cliquetree (g->ncount, dp, &test);
300 if (rval) {
301 fprintf (stderr, "test_pure_simple_cliquetree failed\n");
302 CCtsp_free_lpclique (&ear1);
303 CCtsp_free_lpclique (&ear2);
304 CCtsp_free_lpclique (&bunny);
305 CCtsp_free_lpcut_in (dp);
306 goto CLEANUP;
307 }
308 if (test == 0) {
309 fprintf (stderr, "clique tree did not pass test\n");
310 CCtsp_free_lpclique (&ear1);
311 CCtsp_free_lpclique (&ear2);
312 CCtsp_free_lpclique (&bunny);
313 CCtsp_free_lpcut_in (dp);
314 rval = 1; goto CLEANUP;
315 }
316
317
318 CCtsp_free_lpclique (&ear1);
319 CCtsp_free_lpclique (&ear2);
320
321 dp->next = *cuts;
322 *cuts = dp;
323 CC_IFFREE (ctlist, CCtsp_lpclique *);
324 }
325 CCtsp_free_lpclique (&bunny);
326 }
327 }
328
329 CLEANUP:
330
331 mark_GCgraph_clique (h, handle, 0);
332 for (i = 0; i < nteeth; i++) {
333 mark_GCgraph_clique (h, teeth[i], 0);
334 }
335
336 CC_IFFREE (gset, int);
337 CC_IFFREE (marks, int);
338 CC_IFFREE (ar, int);
339 CC_IFFREE (bigteeth, CCtsp_lpclique *);
340 CC_IFFREE (ctlist, CCtsp_lpclique *);
341 return rval;
342 }
343
build_cliquetree(CCtsp_lpcut_in ** cut,int nteeth,CCtsp_lpclique ** teeth,CCtsp_lpclique * hand1,CCtsp_lpclique * hand2,int ncount)344 static int build_cliquetree (CCtsp_lpcut_in **cut, int nteeth,
345 CCtsp_lpclique **teeth, CCtsp_lpclique *hand1,
346 CCtsp_lpclique *hand2, int ncount)
347 {
348 int rval = 0;
349 CCtsp_lpcut_in *dp;
350 int i, j;
351
352 *cut = (CCtsp_lpcut_in *) NULL;
353
354 dp = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
355 CCcheck_NULL (dp, "out of memory in build_cliquetree");
356 CCtsp_init_lpcut_in (dp);
357
358
359 dp->cliques = CC_SAFE_MALLOC (nteeth + 2, CCtsp_lpclique);
360 if (!dp->cliques) {
361 fprintf (stderr, "out of memory in build_cliquetree\n");
362 CC_FREE (dp, CCtsp_lpcut_in);
363 rval = 1; goto CLEANUP;
364 }
365
366 rval = CCtsp_copy_lpclique (hand1, &dp->cliques[0]);
367 if (rval) {
368 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
369 CC_FREE (dp, CCtsp_lpcut_in);
370 goto CLEANUP;
371 }
372 rval = CCtsp_copy_lpclique (hand2, &dp->cliques[1]);
373 if (rval) {
374 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
375 CCtsp_free_lpclique (&dp->cliques[0]);
376 CC_FREE (dp, CCtsp_lpcut_in);
377 goto CLEANUP;
378 }
379
380 for (i = 0; i < nteeth; i++) {
381 rval = CCtsp_copy_lpclique (teeth[i], &dp->cliques[i+2]);
382 if (rval) {
383 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
384 for (j = 0; j < i+2; j++) {
385 CCtsp_free_lpclique (&dp->cliques[j]);
386 }
387 CC_FREE (dp->cliques, CCtsp_lpclique);
388 CC_FREE (dp, CCtsp_lpcut_in);
389 goto CLEANUP;
390 }
391 }
392
393
394 dp->cliquecount = nteeth + 2;
395 dp->rhs = (2 * (nteeth + 2)) + (nteeth - 1);
396 dp->sense = 'G';
397
398 rval = CCtsp_construct_skeleton (dp, ncount);
399 if (rval) {
400 fprintf (stderr, "CCtsp_construct_skeleton failed\n");
401 CCtsp_free_lpcut_in (dp);
402 goto CLEANUP;
403 }
404
405 *cut = dp;
406
407 CLEANUP:
408
409 return rval;
410 }
411
CCtsp_test_pure_simple_cliquetree(int ncount,CCtsp_lpcut_in * c,int * rtest)412 int CCtsp_test_pure_simple_cliquetree (int ncount, CCtsp_lpcut_in *c,
413 int *rtest)
414 {
415 int rval = 0;
416 int *marks = (int *) NULL;
417 int i, j, k, test, test2, rhs;
418
419 /* Assumes first two cliques are the handles */
420
421 *rtest = 1;
422
423 marks = CC_SAFE_MALLOC (ncount, int);
424 if (marks == (int *) NULL) {
425 fprintf (stderr, "out of memory in test_pure_simple_cliquetree\n");
426 rval = 1; goto CLEANUP;
427 }
428 for (i = 0; i < c->cliquecount; i++) {
429 CCtsp_mark_clique (&c->cliques[i], marks, 0);
430 }
431
432 /* Check that teeth are disjoint */
433
434 for (i = 2; i < c->cliquecount; i++) {
435 CCtsp_clique_marked_count (&c->cliques[i], marks, 1, &test);
436 if (test > 0) {
437 fprintf (stderr, "teeth are not disjoint\n");
438 *rtest = 0; goto CLEANUP;
439 }
440 CCtsp_mark_clique (&c->cliques[i], marks, 1);
441 }
442 for (i = 2; i < c->cliquecount; i++) {
443 CCtsp_mark_clique (&c->cliques[i], marks, 0);
444 }
445
446 /* Check that handles are disjoint */
447
448 CCtsp_mark_clique (&c->cliques[0], marks, 1);
449 CCtsp_clique_marked_count (&c->cliques[1], marks, 1, &test);
450 if (test > 0) {
451 fprintf (stderr, "handles are not disjoint\n");
452 *rtest = 0; goto CLEANUP;
453 }
454 CCtsp_mark_clique (&c->cliques[0], marks, 0);
455
456 /* Check that each tooth has a cavity */
457
458 CCtsp_mark_clique (&c->cliques[0], marks, 1);
459 CCtsp_mark_clique (&c->cliques[1], marks, 1);
460 for (i = 2; i < c->cliquecount; i++) {
461 CCtsp_clique_marked_count (&c->cliques[i], marks, 0, &test);
462 if (test == 0) {
463 fprintf (stderr, "tooth has no cavity\n");
464 *rtest = 0; goto CLEANUP;
465 }
466 }
467 CCtsp_mark_clique (&c->cliques[0], marks, 0);
468 CCtsp_mark_clique (&c->cliques[1], marks, 0);
469
470 /* Check that each handle intersects an odd number of teeth */
471
472 for (j = 0; j <= 1; j++) {
473 CCtsp_mark_clique (&c->cliques[j], marks, 1);
474 k = 0;
475 for (i = 2; i < c->cliquecount; i++) {
476 CCtsp_clique_marked_count (&c->cliques[i], marks, 0, &test);
477 if (test > 0) k++;
478 }
479 if (k % 2 == 0) {
480 fprintf (stderr, "handle meets even number of teeth\n");
481 *rtest = 0; goto CLEANUP;
482 }
483 if (k < 3) {
484 fprintf (stderr, "handle meets only %d teeth\n", k);
485 *rtest = 0; goto CLEANUP;
486 }
487 CCtsp_mark_clique (&c->cliques[j], marks, 0);
488 }
489
490 /* Check that structure is connected (i.e. there is a nonpendent tooth) */
491
492 CCtsp_mark_clique (&c->cliques[0], marks, 1);
493 CCtsp_mark_clique (&c->cliques[1], marks, 2);
494 k = 0;
495 for (i = 2; i < c->cliquecount; i++) {
496 CCtsp_clique_marked_count (&c->cliques[i], marks, 1, &test);
497 CCtsp_clique_marked_count (&c->cliques[i], marks, 2, &test2);
498 if (test > 0 && test2 > 0) k++;
499 }
500 if (k != 1) {
501 fprintf (stderr, "%d nonpendent teeth\n", k);
502 *rtest = 0; goto CLEANUP;
503 }
504
505 /* RHS should be 2*ncliques + (nteeth-1) */
506
507 rhs = (2 * c->cliquecount) + (c->cliquecount - 3);
508 if (rhs != c->rhs) {
509 fprintf (stderr, "rhs value is wrong\n");
510 *rtest = 0; goto CLEANUP;
511 }
512
513 CLEANUP:
514
515 if (rval) *rtest = 0;
516 CC_IFFREE (marks, int);
517 return rval;
518 }
519
mark_GCgraph_clique(CC_GCgraph * g,CCtsp_lpclique * c,int marker)520 static void mark_GCgraph_clique (CC_GCgraph *g, CCtsp_lpclique *c, int marker)
521 {
522 int j, tmp;
523
524 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
525 g->nodelist[j].mark = marker;
526 }
527 }
528