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