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 /* Teething Combs */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: March 13, 1997 */
25 /* July 15, 1997 */
26 /* */
27 /* */
28 /* EXPORTED FUNCTIONS: */
29 /* */
30 /* int CCtsp_teething (CCtsp_lpgraph *g, double *x, */
31 /* CCtsp_lpcut_in *cut, CCtsp_lpcut_in **newcut) */
32 /* CALLS teething with the handle and bigteeth of the comb given by */
33 /* cut (the code will test that it really is a comb or subtour). */
34 /* -g is the graph of the active edges in the LP */
35 /* -x is an LP solution */
36 /* -cut is the base comb */
37 /* -newcut returns the comb found after teething */
38 /* NOTES: */
39 /* The new cut may be just a subtour inequality. This code is based */
40 /* on the "Teething" section of the tsp notes. */
41 /* */
42 /* int CCtsp_teething_list (CCtsp_lpgraph *g, double *x, */
43 /* CCtsp_lpclique *handle, int nbig, CCtsp_lpclique **bigteeth, */
44 /* CCtsp_lpcut_in **newcut) */
45 /* CALLS teething with the given handle and bigteeth. */
46 /* NOTES: bigteeth should be filled in from 1 to nbig (not 0 to */
47 /* nbig-1). */
48 /* */
49 /****************************************************************************/
50
51 #include "machdefs.h"
52 #include "util.h"
53 #include "tsp.h"
54
55 typedef struct intptr {
56 int this;
57 struct intptr *next;
58 } intptr;
59
60 typedef struct Rrecord {
61 int add0;
62 int add1;
63 struct Rrecord *next;
64 } Rrecord;
65
66
67
68 static void
69 teething_free_world (CCptrworld *intptr_world, CCptrworld *Rrecord_world),
70 identify_big_teeth (CCtsp_lpcut_in *cut, int handle, int *nbig,
71 CCtsp_lpclique **bigteeth);
72
73 static int
74 optimal_pseudocomb (CCtsp_lpgraph *g, double *x, CCtsp_lpclique *handle,
75 int nbig, CCtsp_lpclique **bigteeth, CCtsp_lpcut_in *d,
76 CCptrworld *intptr_world, CCptrworld *Rrecord_world),
77 grab_record (Rrecord *r, int parity, intptr **list,
78 CCptrworld *intptr_world),
79 clean_pseudocomb (CCtsp_lpgraph *g, double *x, CCtsp_lpcut_in *c,
80 CCtsp_lpcut_in *d, CCptrworld *intptr_world),
81 add_to_record (CCptrworld *Rrecord_world, Rrecord **R, int add0, int add1);
82
83
CC_PTRWORLD_LIST_ROUTINES(intptr,int,intptralloc,intptr_bulkalloc,intptrfree,intptr_listadd,intptr_listfree)84 CC_PTRWORLD_LIST_ROUTINES (intptr, int, intptralloc, intptr_bulkalloc,
85 intptrfree, intptr_listadd, intptr_listfree)
86 CC_PTRWORLD_LEAKS_ROUTINE (intptr, intptr_check_leaks, this, int)
87
88 CC_PTRWORLD_ROUTINES (Rrecord, Rrecordalloc, Rrecord_bulkalloc, Rrecordfree)
89 CC_PTRWORLD_LISTFREE_ROUTINE (Rrecord, Rrecord_listfree, Rrecordfree)
90 CC_PTRWORLD_LEAKS_ROUTINE (Rrecord, Rrecord_check_leaks, add0, int)
91
92
93 int CCtsp_teething (CCtsp_lpgraph *g, double *x, CCtsp_lpcut_in *cut,
94 CCtsp_lpcut_in **newcut)
95 {
96 int rval = 0;
97 int test, ihandle, nbig;
98 CCtsp_lpclique **bigteeth = (CCtsp_lpclique **) NULL;
99 CCtsp_lpclique *handle = (CCtsp_lpclique *) NULL;
100
101 *newcut = (CCtsp_lpcut_in *) NULL;
102
103 if (cut->cliquecount > 1) {
104 rval = CCtsp_test_pure_comb (g->ncount, cut, &test, &ihandle);
105 if (rval) {
106 fprintf (stderr, "CCtsp_test_pure_comb failed\n"); goto CLEANUP;
107 }
108 if (test != 1) goto CLEANUP;
109 } else {
110 ihandle = 0;
111 }
112
113 handle = &(cut->cliques[ihandle]);
114 bigteeth = CC_SAFE_MALLOC (cut->cliquecount, CCtsp_lpclique *);
115 if (!bigteeth) {
116 fprintf (stderr, "out of memory in CCtsp_teething\n");
117 rval = 1; goto CLEANUP;
118 }
119 identify_big_teeth (cut, ihandle, &nbig, bigteeth);
120
121 rval = CCtsp_teething_list (g, x, handle, nbig, bigteeth, newcut);
122 if (rval) {
123 fprintf (stderr, "CCtsp_teething_list failed\n"); goto CLEANUP;
124 }
125
126 CLEANUP:
127
128 CC_IFFREE (bigteeth, CCtsp_lpclique *);
129 return rval;
130 }
131
CCtsp_teething_list(CCtsp_lpgraph * g,double * x,CCtsp_lpclique * handle,int nbig,CCtsp_lpclique ** bigteeth,CCtsp_lpcut_in ** newcut)132 int CCtsp_teething_list (CCtsp_lpgraph *g, double *x, CCtsp_lpclique *handle,
133 int nbig, CCtsp_lpclique **bigteeth, CCtsp_lpcut_in **newcut)
134 {
135 int rval = 0;
136 CCtsp_lpcut_in general;
137 CCtsp_lpcut_in pseudo;
138 CCptrworld intptr_world;
139 CCptrworld Rrecord_world;
140 int test;
141
142 CCptrworld_init (&intptr_world);
143 CCptrworld_init (&Rrecord_world);
144
145 *newcut = (CCtsp_lpcut_in *) NULL;
146
147 rval = optimal_pseudocomb (g, x, handle, nbig, bigteeth, &pseudo,
148 &intptr_world, &Rrecord_world);
149 if (rval) {
150 fprintf (stderr, "optimal_pseudocomb failed\n"); goto CLEANUP;
151 }
152
153 if (pseudo.cliquecount == 2 || pseudo.cliquecount == 1) {
154 CCtsp_free_lpcut_in (&pseudo);
155 goto CLEANUP;
156 }
157 rval = CCtsp_test_pseudocomb (g->ncount, &pseudo, 0, &test);
158 if (rval) {
159 fprintf (stderr, "CCtsp_test_pseudocomb failed\n"); goto CLEANUP;
160 }
161 if (test != 1) {
162 fprintf (stderr, "Not a pseudocomb\n");
163 CCtsp_print_lpcut_in (&pseudo);
164 rval = 1; goto CLEANUP;
165 }
166
167 rval = CCtsp_test_teeth_disjoint (g->ncount, &pseudo, 0, &test);
168 if (rval) {
169 fprintf (stderr, "CCtsp_test_teeth_disjoint failed\n"); goto CLEANUP;
170 }
171
172 if (!test) {
173 rval = clean_pseudocomb (g, x, &pseudo, &general, &intptr_world);
174 CCtsp_free_lpcut_in (&pseudo);
175 if (rval) {
176 fprintf (stderr, "clean_pseudocomb failed\n");
177 goto CLEANUP;
178 }
179 if (general.cliquecount <= 2) {
180 CCtsp_free_lpcut_in (&general);
181 goto CLEANUP;
182 }
183 }
184
185 *newcut = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
186 CCcheck_NULL (*newcut, "out of memory in CCtsp_teething");
187
188 if (test) {
189 **newcut = pseudo;
190 } else {
191 **newcut = general;
192 }
193
194 if ((*newcut)->dominocount != 0) {
195 printf ("TEETHING Yipes %d\n", (*newcut)->dominocount);
196 fflush (stdout);
197 exit (1);
198 }
199
200 rval = CCtsp_construct_skeleton (*newcut, g->ncount);
201 if (rval) {
202 fprintf (stderr, "CCtsp_construct_skeleton failed\n");
203 CCtsp_free_lpcut_in (*newcut);
204 CC_IFFREE (*newcut, CCtsp_lpcut_in);
205 goto CLEANUP;
206 }
207
208 rval = CCtsp_test_pure_comb (g->ncount, *newcut, &test, (int *) NULL);
209 if (rval) {
210 fprintf (stderr, "CCtsp_test_pure_comb failed\n");
211 CCtsp_print_lpcut_in (&general);
212 CC_FREE (*newcut, CCtsp_lpcut_in);
213 goto CLEANUP;
214 }
215
216 CLEANUP:
217
218 teething_free_world (&intptr_world, &Rrecord_world);
219 return rval;
220 }
221
optimal_pseudocomb(CCtsp_lpgraph * g,double * x,CCtsp_lpclique * handle,int nbig,CCtsp_lpclique ** bigteeth,CCtsp_lpcut_in * d,CCptrworld * intptr_world,CCptrworld * Rrecord_world)222 static int optimal_pseudocomb (CCtsp_lpgraph *g, double *x,
223 CCtsp_lpclique *handle, int nbig, CCtsp_lpclique **bigteeth,
224 CCtsp_lpcut_in *d, CCptrworld *intptr_world, CCptrworld *Rrecord_world)
225 {
226 int rval = 0;
227 int *hhit = (int *) NULL;
228 int *thit = (int *) NULL;
229 int *grab0 = (int *) NULL;
230 int *grab1 = (int *) NULL;
231 int *usebig = (int *) NULL;
232 double *ro0 = (double *) NULL;
233 double *ro1 = (double *) NULL;
234 intptr *newteeth = (intptr *) NULL;
235 Rrecord **R = (Rrecord **) NULL;
236 int i, j, tmp, sj, u, v, e;
237 int ncount = g->ncount;
238 int add0, add1, parity;
239 double nu0, nu1, delta;
240 intptr *ip;
241 int ends[2];
242
243 /* Note: bigteeth should be filled in from 1 up to nbig */
244
245 CCtsp_init_lpcut_in (d);
246
247 hhit = CC_SAFE_MALLOC (ncount, int);
248 thit = CC_SAFE_MALLOC (ncount, int);
249 if (!hhit || !thit) {
250 fprintf (stderr, "out of memory in optimal_pseudocombn");
251 rval = 1; goto CLEANUP;
252 }
253
254 ro0 = CC_SAFE_MALLOC (nbig + 1, double);
255 ro1 = CC_SAFE_MALLOC (nbig + 1, double);
256 grab0 = CC_SAFE_MALLOC (nbig + 1, int);
257 grab1 = CC_SAFE_MALLOC (nbig + 1, int);
258 usebig = CC_SAFE_MALLOC (nbig + 1, int);
259 if (!ro0 || !ro1 || !grab0 || !grab1 || !usebig) {
260 fprintf (stderr, "out of memory in optimal_pseudocomb\n");
261 rval = 1; goto CLEANUP;
262 }
263 R = CC_SAFE_MALLOC (nbig + 1, Rrecord *);
264 if (!R) {
265 fprintf (stderr, "out of memory in optimal_pseudocomb\n");
266 rval = 1; goto CLEANUP;
267 }
268 for (i = 0; i <= nbig; i++) {
269 R[i] = (Rrecord *) NULL;
270 ro0[i] = 0.0;
271 ro1[i] = CCtsp_LP_MAXDOUBLE;
272 }
273
274 CCtsp_mark_clique_and_neighbors (g, handle, hhit, 0);
275 CCtsp_mark_clique_and_neighbors (g, handle, thit, 0);
276 for (i = 1; i <= nbig; i++) {
277 CCtsp_mark_clique_and_neighbors (g, bigteeth[i], hhit, 0);
278 CCtsp_mark_clique_and_neighbors (g, bigteeth[i], thit, 0);
279 }
280
281 CCtsp_mark_clique (handle, hhit, 1);
282 for (i = 1; i <= nbig; i++) {
283 CCtsp_mark_clique (bigteeth[i], thit, i);
284 }
285
286 CC_FOREACH_NODE_IN_CLIQUE (u, *handle, tmp) {
287 for (sj = 0; sj < g->nodes[u].deg; sj++) {
288 v = g->nodes[u].adj[sj].to;
289 e = g->nodes[u].adj[sj].edge;
290 if (hhit[v] != 1 && x[e] > 0.0) {
291 if (thit[v] != 0 && thit[v] == thit[u]) {
292 i = thit[v];
293 } else {
294 i = 0;
295 }
296 nu0 = ro0[i];
297 nu1 = ro1[i];
298 if (nu1 + (1.0 - 2.0*x[e]) < nu0) {
299 ro0[i] = nu1 + (1.0 - 2.0*x[e]);
300 add0 = e;
301 } else {
302 add0 = -1;
303 }
304 if (nu0 + (1.0 - 2.0*x[e]) < nu1) {
305 ro1[i] = nu0 + (1.0 - 2.0*x[e]);
306 add1 = e;
307 } else {
308 add1 = -1;
309 }
310 if (add0 != -1 || add1 != -1) {
311 rval = add_to_record (Rrecord_world, &R[i], add0, add1);
312 if (rval) {
313 fprintf (stderr, "add_to_record failed\n");
314 goto CLEANUP;
315 }
316 }
317 }
318 }
319 }
320
321 for (i = 1; i <= nbig; i++) {
322 rval = CCtsp_clique_delta (g, x, bigteeth[i], &delta);
323 if (rval) {
324 fprintf (stderr, "CCtsp_clique_delta failed\n"); goto CLEANUP;
325 }
326 if (delta - 3.0 < ro1[i]) {
327 ro1[i] = delta - 3.0;
328 usebig[i] = 1;
329 } else {
330 usebig[i] = 0;
331 }
332 nu0 = ro0[0];
333 nu1 = ro1[0];
334 if (nu1 + ro1[i] < nu0 + ro0[i]) {
335 ro0[0] = nu1 + ro1[i];
336 grab0[i] = 1;
337 } else {
338 ro0[0] = nu0 + ro0[i];
339 grab0[i] = 0;
340 }
341 if (nu0 + ro1[i] < nu1 + ro0[i]) {
342 ro1[0] = nu0 + ro1[i];
343 grab1[i] = 1;
344 } else {
345 ro1[0] = nu1 + ro0[i];
346 grab1[i] = 0;
347 }
348 }
349
350 parity = 1;
351 for (i = nbig; i > 0; i--) {
352 if (parity) {
353 if (grab1[i]) {
354 if (usebig[i]) {
355 rval = intptr_listadd (&newteeth, -i, intptr_world);
356 if (rval) goto CLEANUP;
357 } else {
358 rval = grab_record (R[i], 1, &newteeth, intptr_world);
359 if (rval) goto CLEANUP;
360 }
361 parity = 0;
362 } else {
363 rval = grab_record (R[i], 0, &newteeth, intptr_world);
364 if (rval) goto CLEANUP;
365 parity = 1;
366 }
367 } else {
368 if (grab0[i]) {
369 if (usebig) {
370 rval = intptr_listadd (&newteeth, -i, intptr_world);
371 if (rval) goto CLEANUP;
372 } else {
373 rval = grab_record (R[i], 1, &newteeth, intptr_world);
374 if (rval) goto CLEANUP;
375 }
376 parity = 1;
377 } else {
378 rval = grab_record (R[i], 0, &newteeth, intptr_world);
379 if (rval) goto CLEANUP;
380 parity = 0;
381 }
382 }
383 }
384 rval = grab_record (R[0], parity, &newteeth, intptr_world);
385 if (rval) goto CLEANUP;
386
387 d->cliquecount = 1;
388 for (ip = newteeth; ip; ip = ip->next) {
389 d->cliquecount++;
390 }
391 d->cliques = CC_SAFE_MALLOC (d->cliquecount, CCtsp_lpclique);
392 if (!d->cliques) {
393 fprintf (stderr, "out of memory in optimal_pseudocombs\n");
394 rval = 1; goto CLEANUP;
395 }
396
397 rval = CCtsp_copy_lpclique (handle, &d->cliques[0]);
398 if (rval) {
399 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
400 CC_FREE (d->cliques, CCtsp_lpclique);
401 goto CLEANUP;
402 }
403 for (i = 1, ip = newteeth; ip; ip = ip->next, i++) {
404 if (ip->this < 0) {
405 rval = CCtsp_copy_lpclique (bigteeth[-ip->this], &d->cliques[i]);
406 if (rval) {
407 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
408 for (j = 0; j < i; j++) {
409 CCtsp_free_lpclique (&d->cliques[j]);
410 }
411 CC_FREE (d->cliques, CCtsp_lpclique);
412 goto CLEANUP;
413 }
414 } else {
415 ends[0] = g->edges[ip->this].ends[0];
416 ends[1] = g->edges[ip->this].ends[1];
417 rval = CCtsp_array_to_lpclique (ends, 2, &d->cliques[i]);
418 if (rval) {
419 fprintf (stderr, "CCtsp_array_to_lpclique failed\n");
420 for (j = 0; j < i; j++) {
421 CCtsp_free_lpclique (&d->cliques[j]);
422 }
423 CC_FREE (d->cliques, CCtsp_lpclique);
424 goto CLEANUP;
425 }
426 }
427 }
428
429 d->sense = 'G';
430 d->rhs = 3 * d->cliquecount - 2;
431
432 CLEANUP:
433
434 CC_IFFREE (hhit, int);
435 CC_IFFREE (thit, int);
436 if (R) {
437 for (i = 0; i <= nbig; i++) {
438 Rrecord_listfree (Rrecord_world, R[i]);
439 }
440 CC_FREE (R, Rrecord *);
441 }
442 intptr_listfree (intptr_world, newteeth);
443 CC_IFFREE (ro0, double);
444 CC_IFFREE (ro1, double);
445 CC_IFFREE (grab0, int);
446 CC_IFFREE (grab1, int);
447 CC_IFFREE (usebig, int);
448
449 return rval;
450 }
451
grab_record(Rrecord * r,int parity,intptr ** list,CCptrworld * intptr_world)452 static int grab_record (Rrecord *r, int parity, intptr **list,
453 CCptrworld *intptr_world)
454 {
455 int rval = 0;
456
457 while (r) {
458 if (parity) {
459 if (r->add1 != -1) {
460 rval = intptr_listadd (list, r->add1, intptr_world);
461 if (rval) goto CLEANUP;
462 parity = 0;
463 }
464 } else {
465 if (r->add0 != -1) {
466 rval = intptr_listadd (list, r->add0, intptr_world);
467 if (rval) goto CLEANUP;
468 parity = 1;
469 }
470 }
471 r = r->next;
472 }
473
474 CLEANUP:
475
476 return rval;
477 }
478
clean_pseudocomb(CCtsp_lpgraph * g,double * x,CCtsp_lpcut_in * c,CCtsp_lpcut_in * d,CCptrworld * intptr_world)479 static int clean_pseudocomb (CCtsp_lpgraph *g, double *x, CCtsp_lpcut_in *c,
480 CCtsp_lpcut_in *d, CCptrworld *intptr_world)
481 {
482 int rval = 0;
483 int *hmarks = (int *) NULL;
484 int *activeteeth = (int *) NULL;
485 int *cardteeth = (int *) NULL;
486 int *harray = (int *) NULL;
487 intptr **inteeth = (intptr **) NULL;
488 intptr *hlist = (intptr *) NULL;
489 int ccount = c->cliquecount;
490 CCtsp_lpclique *handle = &c->cliques[0];
491 CCtsp_lpclique *cl;
492 int i, tmp, k, si, ismarked, cnt, big, ibig, ismall, hcnt;
493 double delta, smalldelta;
494 intptr *ip;
495
496 CCtsp_init_lpcut_in (d);
497
498 hmarks = CC_SAFE_MALLOC (g->ncount, int);
499 activeteeth = CC_SAFE_MALLOC (ccount, int);
500 cardteeth = CC_SAFE_MALLOC (ccount, int);
501 if (!hmarks || !activeteeth || !cardteeth) {
502 fprintf (stderr, "out of memory in clean_pseudocomb\n");
503 rval = 1; goto CLEANUP;
504 }
505
506 CCtsp_mark_cut (c, hmarks, 0);
507 CCtsp_mark_clique (handle, hmarks, 1);
508 for (i = 1; i < ccount; i++) {
509 activeteeth[i] = 1;
510 CCtsp_clique_count (&c->cliques[i], &cardteeth[i]);
511 }
512
513 inteeth = CC_SAFE_MALLOC (g->ncount, intptr *);
514 if (!inteeth) {
515 fprintf (stderr, "out of memory in clean_pseudocomb\n");
516 rval = 1; goto CLEANUP;
517 }
518 for (i = 1; i < ccount; i++) {
519 cl = &c->cliques[i];
520 CC_FOREACH_NODE_IN_CLIQUE (k, *cl, tmp) {
521 inteeth[k] = (intptr *) NULL;
522 }
523 }
524 CC_FOREACH_NODE_IN_CLIQUE (k, *handle, tmp) {
525 inteeth[k] = (intptr *) NULL;
526 }
527
528 for (i = 1; i < ccount; i++) {
529 cl = &c->cliques[i];
530 CC_FOREACH_NODE_IN_CLIQUE (k, *cl, tmp) {
531 intptr_listadd (&inteeth[k], i, intptr_world);
532 }
533 }
534 for (i = 1; i < ccount; i++) {
535 if (!activeteeth[i]) continue;
536 cl = &c->cliques[i];
537 CC_FOREACH_NODE_IN_CLIQUE (k, *cl, tmp) {
538 if (!hmarks[k]) {
539 cnt = 0;
540 big = 0;
541 ibig = -1;
542 for (ip = inteeth[k]; ip; ip = ip->next) {
543 if (activeteeth[ip->this]) {
544 cnt++;
545 if (cardteeth[ip->this] > big) {
546 big = cardteeth[ip->this];
547 ibig = ip->this;
548 }
549 }
550 }
551 if (cnt > 1) {
552 CCtsp_mark_clique (&c->cliques[ibig], hmarks, 1);
553 for (si = 1; si < ccount; si++) {
554 if (activeteeth[si]) {
555 CCtsp_is_clique_marked (&c->cliques[si],
556 hmarks, 0, &ismarked);
557 activeteeth[si] = ismarked;
558 }
559 }
560 }
561 }
562 }
563 }
564 CC_FOREACH_NODE_IN_CLIQUE (k, *handle, tmp) {
565 if (hmarks[k]) {
566 cnt = 0;
567 big = 0;
568 ibig = -1;
569 for (ip = inteeth[k]; ip; ip = ip->next) {
570 if (activeteeth[ip->this]) {
571 cnt++;
572 if (cardteeth[ip->this] > big) {
573 big = cardteeth[ip->this];
574 ibig = ip->this;
575 }
576 }
577 }
578 if (cnt > 1) {
579 CCtsp_mark_clique (&c->cliques[ibig], hmarks, 0);
580 for (si = 1; si < ccount; si++) {
581 if (activeteeth[si]) {
582 CCtsp_is_clique_marked (&c->cliques[si],
583 hmarks, 1, &ismarked);
584 activeteeth[si] = ismarked;
585 }
586 }
587 }
588 }
589 }
590
591 for (i = 0, hcnt = 0; i < ccount; i++) {
592 cl = &c->cliques[i];
593 CC_FOREACH_NODE_IN_CLIQUE (k, *cl, tmp) {
594 if (hmarks[k] == 1) {
595 rval = intptr_listadd (&hlist, k, intptr_world);
596 if (rval) goto CLEANUP;
597 hmarks[k] = 2;
598 hcnt++;
599 }
600 }
601 }
602
603 if (!hcnt) {
604 /*
605 printf ("WARNING: generalized comb gets an empty handle\n");
606 fflush (stdout);
607 */
608 goto CLEANUP;
609 }
610 harray = CC_SAFE_MALLOC (hcnt, int);
611 if (!harray) {
612 fprintf (stderr, "out of memory in clean_pseudocomb\n");
613 rval = 1; goto CLEANUP;
614 }
615 for (ip = hlist, hcnt = 0; ip; ip = ip->next) {
616 harray[hcnt++] = ip->this;
617 }
618
619 cnt = 0;
620 for (i = 1; i < ccount; i++) {
621 if (activeteeth[i]) cnt++;
622 }
623 if (!cnt) {
624 /*
625 printf ("WARNING: generalized comb gets no teeth\n");
626 fflush (stdout);
627 */
628 goto CLEANUP;
629 }
630
631 if (cnt % 2 == 0) {
632 smalldelta = CCtsp_LP_MAXDOUBLE;
633 ismall = -1;
634 for (i = 1; i < ccount; i++) {
635 if (activeteeth[i]) {
636 rval = CCtsp_clique_delta (g, x, &c->cliques[i], &delta);
637 if (rval) {
638 fprintf (stderr, "CCtsp_clique_delta failed\n");
639 goto CLEANUP;
640 }
641 if (delta < smalldelta) {
642 smalldelta = delta;
643 ismall = i;
644 }
645 }
646 }
647 activeteeth[ismall] = 0;
648 cnt--;
649 }
650 cnt++;
651
652 d->cliques = CC_SAFE_MALLOC (cnt, CCtsp_lpclique);
653 if (!d->cliques) {
654 fprintf (stderr, "out of memory in clean_pseudocomb\n");
655 rval = 1; goto CLEANUP;
656 }
657 rval = CCtsp_array_to_lpclique (harray, hcnt, &d->cliques[0]);
658 if (rval) {
659 fprintf (stderr, "CCtsp_array_to_lpclique failed\n");
660 CC_FREE (d->cliques, CCtsp_lpclique);
661 goto CLEANUP;
662 }
663 for (i = 1, cnt = 1; i < ccount; i++) {
664 if (activeteeth[i]) {
665 rval = CCtsp_copy_lpclique (&c->cliques[i], &d->cliques[cnt++]);
666 if (rval) {
667 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
668 for (k = 0; k < cnt; k++) {
669 CCtsp_free_lpclique (&d->cliques[k]);
670 }
671 CC_FREE (d->cliques, CCtsp_lpclique);
672 goto CLEANUP;
673 }
674 }
675 }
676 d->cliquecount = cnt;
677 d->rhs = 3 * d->cliquecount - 2;
678 d->sense = 'G';
679
680 CLEANUP:
681
682 CC_IFFREE (hmarks, int);
683 CC_IFFREE (activeteeth, int);
684 CC_IFFREE (cardteeth, int);
685 CC_IFFREE (harray, int);
686 if (inteeth) {
687 for (i = 1; i < ccount; i++) {
688 cl = &c->cliques[i];
689 CC_FOREACH_NODE_IN_CLIQUE (k, *cl, tmp) {
690 if (inteeth[k]) {
691 intptr_listfree (intptr_world, inteeth[k]);
692 inteeth[k] = (intptr *) NULL;
693 }
694 }
695 }
696 CC_FREE (inteeth, intptr *);
697 }
698 intptr_listfree (intptr_world, hlist);
699
700 return rval;
701 }
702
teething_free_world(CCptrworld * intptr_world,CCptrworld * Rrecord_world)703 static void teething_free_world (CCptrworld *intptr_world,
704 CCptrworld *Rrecord_world)
705 {
706 /*
707 int total, onlist;
708
709 if (intptr_check_leaks (intptr_world, &total, &onlist)) {
710 fprintf (stderr, "WARNING: %d outstanding intptrs in teething\n",
711 total - onlist);
712 }
713 */
714 CCptrworld_delete (intptr_world);
715
716 /*
717 if (Rrecord_check_leaks (Rrecord_world, &total, &onlist)) {
718 fprintf (stderr, "WARNING: %d outstanding Rrecords in teething\n",
719 total - onlist);
720 }
721 */
722 CCptrworld_delete (Rrecord_world);
723 }
724
identify_big_teeth(CCtsp_lpcut_in * cut,int handle,int * nbig,CCtsp_lpclique ** bigteeth)725 static void identify_big_teeth (CCtsp_lpcut_in *cut, int handle, int *nbig,
726 CCtsp_lpclique **bigteeth)
727 {
728 int i, k;
729
730 /* teeth filled into positions 1 through nbig */
731
732 *nbig = 0;
733 for (i = 0; i < cut->cliquecount; i++) {
734 if (i != handle) {
735 CCtsp_clique_count (&(cut->cliques[i]), &k);
736 if (k >= 3) {
737 bigteeth[++(*nbig)] = &(cut->cliques[i]);
738 }
739 }
740 }
741 }
742
add_to_record(CCptrworld * Rrecord_world,Rrecord ** R,int add0,int add1)743 static int add_to_record (CCptrworld *Rrecord_world, Rrecord **R, int add0,
744 int add1)
745 {
746 Rrecord *p;
747
748 p = Rrecordalloc (Rrecord_world);
749 if (!p) { fprintf (stderr, "Rrecordalloc failed\n"); return 1; }
750 p->add0 = add0;
751 p->add1 = add1;
752 p->next = *R;
753 *R = p;
754 return 0;
755 }
756
757
758