1 /***************************************************************************/
2 /* */
3 /* Interface to the Cutters */
4 /* */
5 /* TSP CODE */
6 /* */
7 /* */
8 /* Written by: Applegate, Bixby, Chvatal, and Cook */
9 /* Date: February 17, 1997 */
10 /* */
11 /* */
12 /* EXPORTED FUNCTIONS: */
13 /* int CCtsp_connect_cuts (CCtsp_lpcut_in **cuts, int *cutcount, */
14 /* int ncount, int ecount, int *elist, double *x) */
15 /* FINDS violated subtour inequalities via connectivity. */
16 /* -cuts will return any new cuts found (they will be added to the */
17 /* head of the linked list) */
18 /* -cutcount will return the number of new cuts added */
19 /* -ncount is the number of nodes */
20 /* -ecount is the number of edges */
21 /* -elist contains the LP edges in node node format */
22 /* -x is an LP solution */
23 /* */
24 /* int CCtsp_segment_cuts (CCtsp_lpcut_in **cuts, int *cutcount, */
25 /* int ncount, int ecount, int *elist, double *x) */
26 /* FINDS violated subtour inequalities via linsub. */
27 /* */
28 /* int CCtsp_exact_subtours (CCtsp_lpcut_in **cuts, int *cutcount, */
29 /* int ncount, int ecount, int *elist, double *x) */
30 /* FINDS violated subtour inequalities via a mincut algorithm. */
31 /* */
32 /* int CCtsp_tighten_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, */
33 /* CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, */
34 /* int ecount, int *elist, double *x, double testtol, */
35 /* int maxcuts) */
36 /* CALLS tighten for each cut in the cuts. */
37 /* -stats contains some running statistics of tighten */
38 /* -cutsout returns the tightened cuts that are violated (they are */
39 /* added to the head of the linked list) */
40 /* -cutcount is the number of cuts in cutsout */
41 /* -testtol is a tolerance for calling tighten (call only when the */
42 /* cut has slack value within testtol) */
43 /* -maxcuts is a bound on the number of cuts to be returned */
44 /* */
45 /* void CCtsp_init_lpcut_in (CCtsp_lpcut_in *c) */
46 /* INITIALIZE the fields of the CCtsp_lpcut_in structure */
47 /* */
48 /* int CCtsp_segment_to_subtour (CCtsp_lpcut_in **cut, int a, int b) */
49 /* BUILDS a subtour CCtsp_lpcut_in from an the segment. */
50 /* -cut will return the subtour (it will be allocated). */
51 /* */
52 /* int CCtsp_array_to_subtour (CCtsp_lpcut_in **cut, int *ar, */
53 /* int acount) */
54 /* BUILDS a subtour CCtsp_lpcut_in from an array. */
55 /* -cut will return the subtour (it will be allocated). */
56 /* */
57 /* void CCtsp_init_lpclique (CCtsp_lpclique *c) */
58 /* INITIALIZE the fields of the CCtsp_lpclique structure */
59 /* */
60 /* int CCtsp_array_to_lpclique (int *ar, int acount, */
61 /* CCtsp_lpclique *cliq) */
62 /* BUILDS an CCtsp_lpclique represented the nodes in an array. */
63 /* -ar is an array of node numbers */
64 /* -acount is the length of ar */
65 /* -cliq's segcount and nodes will be filled with the compressed */
66 /* version of the nodes in ar */
67 /* */
68 /* int CCtsp_seglist_to_lpclique (int nseg, int *list, */
69 /* CCtsp_lpclique *cliq) */
70 /* BUILDS the CCtsp_lpclique represented by a list of CCtsp_segments */
71 /* (it will sort the CCtsp_segments before it puts them into the */
72 /* CCtsp_segment structures) */
73 /* -list is an array of CCtsp_segments in lo-hi-lo-hi format */
74 /* -clig's segcount and nodes will be filled in (nodes will be */
75 /* allocated) */
76 /* */
77 /* int CCtsp_add_node_to_lpclique (CCtsp_lpclique *cin, */
78 /* CCtsp_lpclique *cout, int n) */
79 /* ADDS node n to clique cin, and returns the new clique in cout */
80 /* */
81 /* int CCtsp_delete_node_from_lpclique (CCtsp_lpclique *cin, */
82 /* CCtsp_lpclique *cout, int n) */
83 /* DELETES node n from clique cin, and returns the new clique in cout */
84 /* */
85 /* void CCtsp_print_lpcut_in (CCtsp_lpcut_in *c) */
86 /* PRINTS the CCtsp_lpcut_in */
87 /* */
88 /* void CCtsp_print_lpclique (CCtsp_lpclique *c) */
89 /* PRINTS the CCtsp_segments in the clique to stdout. */
90 /* */
91 /* int CCtsp_copy_lpcut_in (CCtsp_lpcut_in *c, */
92 /* CCtsp_lpcut_in *new) */
93 /* COPIES an CCtsp_lpcut_in */
94 /* -c is a pointer to an CCtsp_lpcut_in */
95 /* -new returns the copied CCtsp_lpcut */
96 /* */
97 /* int CCtsp_lpcut_to_lpcut_in (CCtsp_lpcuts *cuts, */
98 /* CCtsp_lpcut *c, CCtsp_lpcut_in *new) */
99 /* COPIES an CCtsp_lpcut to an CCtsp_lpcut_in */
100 /* -cuts is a pointer to the structure holding the set of cuts */
101 /* -c is the cut to be copied */
102 /* -new returns the copied cut */
103 /* */
104 /* void CCtsp_lpclique_compare (CCtsp_lpclique *a, */
105 /* CCtsp_lpclique *b, int *diff) */
106 /* COMPARES two CCtsp_lpcliques. */
107 /* -diff is set to 1 if they differ and 0 if they are the same */
108 /* Note: Assumes CCtsp_segments are ordered. */
109 /* */
110 /* int CCtsp_copy_lpclique (CCtsp_lpclique *c, */
111 /* CCtsp_lpclique *new) */
112 /* COPIES an CCtsp_lpclique */
113 /* -c is a pointer to an CCtsp_lpclique */
114 /* -new returns the copied clique */
115 /* */
116 /* int CCtsp_file_cuts (char *cutfile, CCtsp_lpcut_in **cuts, */
117 /* int *cutcount, int ncount, int *tour) */
118 /* READS a set of cuts from a file; the format of the cuts can be */
119 /* found by examining the code */
120 /* -cutfile is an asci file with a list of cuts */
121 /* -cuts will return any new cuts found (they will be added to the */
122 /* head of the linked list) */
123 /* -cutcount with return the number of new cuts added */
124 /* -ncount is the number of nodes */
125 /* -tour the permutation tour (used to map the incoming nodes) */
126 /* */
127 /* int CCtsp_file_cuts_write (char *cutfile, CCtsp_lpcuts *cuts, */
128 /* int *tour) */
129 /* WRITES a set of cuts in a text file that can be read by */
130 /* tsp_file_cuts */
131 /* -cutfile is the name of the file to be written */
132 /* -cuts is the set of cuts to be written */
133 /* -tour is a permutation tour (used to map the outgoing nodes) */
134 /* */
135 /* int CCtsp_test_pure_comb (int ncount, CCtsp_lpcut_in *c, int *yes_no,*/
136 /* int *handle) */
137 /* TEST if the cut is a comb (without flipped teeth or intersections) */
138 /* -ncount is the number of nodes in the TSP */
139 /* -yes_no will be set to either 0 or 1, with 1 meaning yes */
140 /* -handle with return the index of the handle if the cut is a comb */
141 /* (handle can be NULL) */
142 /* */
143 /* int CCtsp_test_pseudocomb (int ncount, CCtsp_lpcut_in *c, int handle,*/
144 /* int *yes_no) */
145 /* TEST if the cut is a pseudocomb. */
146 /* -handle gives the index of the handle of the pseudocomb */
147 /* */
148 /* int CCtsp_test_teeth_disjoint (int ncount, CCtsp_lpcut_in *c, */
149 /* int handle, int *yes_no) */
150 /* TEST if the cliques other than handle are pairwise disjoint. */
151 /* -yes_no is 1 if disjoint and 0 otherwise. */
152 /* */
153 /* int CCtsp_find_pure_handle (int ncount, CCtsp_lpcut_in *c, */
154 /* int *handle) */
155 /* FINDS a clique that is c's handle if c is a comb; the search */
156 /* assumes that the teeth are disjoint, so if the comb has */
157 /* extra intersections then a tooth may be returned. */
158 /* -handle returns the potential handle (it will return -1 if no */
159 /* clique is a potential handle) */
160 /* */
161 /* NOTES: */
162 /* */
163 /***************************************************************************/
164
165 #include "machdefs.h"
166 #include "macrorus.h"
167 #include "util.h"
168 #include "tsp.h"
169 #include "cut.h"
170
171 #define X_FLUFF (1e-10)
172 #undef DUMP_BUILDCUT
173
174 typedef struct exactsub_param {
175 int cutcount;
176 CCtsp_lpcut_in *cuts;
177 } exactsub_param;
178
179 #ifdef CC_PROTOTYPE_ANSI
180
181 static int
182 add_segment (double val, int a, int b, void *pass_param),
183 add_exact (double val, int count, int *cutarray, void *pass_param),
184 work_on_combs_in_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats,
185 CCtsp_lpcut_in **cutsout,
186 int *cutcount, int ncount, int ecount, int *elist, double *x,
187 double testtol, int maxcuts,
188 int (*doit_fn) (CCtsp_lpgraph *, double *, CCtsp_lpcut_in *,
189 CCtsp_lpcut_in **)),
190 grab_nonzero_x (int ecount, int *elist, double *x, int *new_ecount,
191 int **new_elist, double **new_x, double tol);
192
193 #else
194
195 static int
196 add_segment (),
197 add_exact (),
198 work_on_combs_in_lp (),
199 grab_nonzero_x ();
200
201 #endif
202
203
204 #ifdef CC_PROTOTYPE_ANSI
CCtsp_connect_cuts(CCtsp_lpcut_in ** cuts,int * cutcount,int ncount,int ecount,int * elist,double * x)205 int CCtsp_connect_cuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount,
206 int ecount, int *elist, double *x)
207 #else
208 int CCtsp_connect_cuts (cuts, cutcount, ncount, ecount, elist, x)
209 CCtsp_lpcut_in **cuts;
210 int *cutcount;
211 int ncount, ecount;
212 int *elist;
213 double *x;
214 #endif
215 {
216 int rval;
217 int i, k, ncomp;
218 CCtsp_lpcut_in *c = (CCtsp_lpcut_in *) NULL;
219 int *comps = (int *) NULL;
220 int *compscount = (int *) NULL;
221
222 *cutcount = 0;
223 rval = CCcut_connect_components (ncount, ecount, elist, x, &ncomp,
224 &compscount, &comps);
225 if (rval) {
226 fprintf (stderr, "CCcut_connect_components failed\n"); goto CLEANUP;
227 }
228
229 for (i = 0, k = 0; i < ncomp - 1; k += compscount[i], i++) {
230 rval = CCtsp_array_to_subtour (&c, comps + k, compscount[i]);
231 if (rval) {
232 fprintf (stderr, "CCtsp_array_to_subtour failed\n");
233 rval = 1; goto CLEANUP;
234 }
235 c->next = *cuts;
236 *cuts = c;
237 (*cutcount)++;
238 }
239
240 CLEANUP:
241
242 CC_IFFREE (comps, int);
243 CC_IFFREE (compscount, int);
244
245 return rval;
246 }
247
248 #ifdef CC_PROTOTYPE_ANSI
CCtsp_segment_cuts(CCtsp_lpcut_in ** cuts,int * cutcount,int ncount,int ecount,int * elist,double * x)249 int CCtsp_segment_cuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount,
250 int ecount, int *elist, double *x)
251 #else
252 int CCtsp_segment_cuts (cuts, cutcount, ncount, ecount, elist, x)
253 CCtsp_lpcut_in **cuts;
254 int *cutcount;
255 int ncount, ecount;
256 int *elist;
257 double *x;
258 #endif
259 {
260 int rval = 0;
261 exactsub_param p;
262 double szeit = CCutil_zeit ();
263
264 *cutcount = 0;
265
266 p.cutcount = 0;
267 p.cuts = *cuts;
268
269 rval = CCcut_linsub (ncount, ecount, elist, x, 2.0 - 0.0001,
270 add_segment, (void *) &p);
271 if (rval) {
272 fprintf (stderr, "CCcut_linsub failed\n"); goto CLEANUP;
273 }
274
275 *cutcount = p.cutcount;
276 *cuts = p.cuts;
277
278 printf ("DONE (found %d segment cuts in %.2f seconds)\n", *cutcount,
279 CCutil_zeit () - szeit);
280 fflush (stdout);
281
282 CLEANUP:
283
284 return rval;
285 }
286
287
288 #ifdef CC_PROTOTYPE_ANSI
CCtsp_exact_subtours(CCtsp_lpcut_in ** cuts,int * cutcount,int ncount,int ecount,int * elist,double * x)289 int CCtsp_exact_subtours (CCtsp_lpcut_in **cuts, int *cutcount, int ncount,
290 int ecount, int *elist, double *x)
291 #else
292 int CCtsp_exact_subtours (cuts, cutcount, ncount, ecount, elist, x)
293 CCtsp_lpcut_in **cuts;
294 int *cutcount;
295 int ncount, ecount;
296 int *elist;
297 double *x;
298 #endif
299 {
300 int rval = 0;
301 exactsub_param p;
302 double szeit = CCutil_zeit ();
303
304
305 printf ("exact_subtours ... \n"); fflush (stdout);
306 *cutcount = 0;
307 rval = CCtsp_connect_cuts (cuts, cutcount, ncount, ecount, elist, x);
308 if (rval) {
309 fprintf (stderr, "CCtsp_connect_cuts failed\n"); goto CLEANUP;
310 }
311
312 if (*cutcount > 0) {
313 fprintf (stderr, "found connect cuts, do not call exact cut routine\n");
314 rval = 0; goto CLEANUP;
315 }
316
317 p.cutcount = 0;
318 p.cuts = *cuts;
319
320 rval = CCcut_violated_cuts (ncount, ecount, elist, x, 2.0 - 0.0001,
321 add_exact, (void *) &p);
322 if (rval) {
323 fprintf (stderr, "CCcut_violated_cuts failed\n"); goto CLEANUP;
324 }
325
326 *cutcount = p.cutcount;
327 *cuts = p.cuts;
328
329 printf ("DONE (found %d cuts in %.2f seconds)\n", *cutcount,
330 CCutil_zeit () - szeit);
331 fflush (stdout);
332
333 #if 0
334 - this is just to check the values of the exact cuts
335 if (*cutcount) {
336 CCtsp_lpgraph lg;
337 CCtsp_lpcut_in *c;
338 double t;
339
340 CCtsp_init_lpgraph_struct (&lg);
341
342 rval = CCtsp_build_lpgraph (&lg, ncount, ecount, elist, (int *) NULL);
343 if (rval) {
344 fprintf (stderr, "CCtsp_build_lpgraph failed\n"); goto CLEANUP;
345 }
346 rval = CCtsp_build_lpadj (&lg, 0, ecount);
347 if (rval) {
348 CCtsp_free_lpgraph (&lg);
349 fprintf (stderr, "CCtsp_build_lpadj failed\n"); goto CLEANUP;
350 }
351 for (c = p.cuts; c; c = c->next) {
352 t = CCtsp_cutprice (&lg, c, x);
353 printf ("[%f] ", 2.0 + t); fflush (stdout);
354 }
355 printf ("\n"); fflush (stdout);
356 CCtsp_free_lpgraph (&lg);
357 }
358 #endif
359
360 CLEANUP:
361
362 return rval;
363 }
364
365 #ifdef CC_PROTOTYPE_ANSI
add_segment(double val,int a,int b,void * pass_param)366 static int add_segment (double val, int a, int b, void *pass_param)
367 #else
368 static int add_segment (val, a, b, pass_param)
369 double val;
370 int a, b;
371 void *pass_param;
372 #endif
373 {
374 int rval = 0;
375 exactsub_param *p = (exactsub_param *) pass_param;
376 CCtsp_lpcut_in *c = (CCtsp_lpcut_in *) NULL;
377
378 if (val > 2.0) {
379 printf ("Warning: Cut of value %f in add_segment\n", val);
380 fflush (stdout);
381 goto CLEANUP;
382 }
383
384 rval = CCtsp_segment_to_subtour (&c, a, b);
385 if (rval) {
386 fprintf (stderr, "CCtsp_array_to_subtour failed\n");
387 rval = 1; goto CLEANUP;
388 }
389 c->next = p->cuts;
390 p->cuts = c;
391 p->cutcount++;
392
393 CLEANUP:
394
395 return rval;
396 }
397 #ifdef CC_PROTOTYPE_ANSI
add_exact(double val,int count,int * cutarray,void * pass_param)398 static int add_exact (double val, int count, int *cutarray, void *pass_param)
399 #else
400 static int add_exact (val, count, cutarray, pass_param)
401 double val;
402 int count;
403 int *cutarray;
404 void *pass_param;
405 #endif
406 {
407 int rval = 0;
408 exactsub_param *p = (exactsub_param *) pass_param;
409 CCtsp_lpcut_in *c = (CCtsp_lpcut_in *) NULL;
410
411 if (val > 2.0) {
412 printf ("Warning: Cut of value %f in add_exact\n", val);
413 fflush (stdout);
414 goto CLEANUP;
415 }
416
417 rval = CCtsp_array_to_subtour (&c, cutarray, count);
418 if (rval) {
419 fprintf (stderr, "CCtsp_array_to_subtour failed\n");
420 rval = 1; goto CLEANUP;
421 }
422 c->next = p->cuts;
423 p->cuts = c;
424 p->cutcount++;
425
426 CLEANUP:
427
428 return rval;
429 }
430
431 #ifdef CC_PROTOTYPE_ANSI
CCtsp_tighten_lp(CCtsp_lpcuts * cuts,CCtsp_tighten_info * stats,CCtsp_lpcut_in ** cutsout,int * cutcount,int ncount,int ecount,int * elist,double * x,double testtol,int maxcuts)432 int CCtsp_tighten_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats,
433 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount,
434 int *elist, double *x, double testtol, int maxcuts)
435 #else
436 int CCtsp_tighten_lp (cuts, stats, cutsout, cutcount, ncount, ecount, elist, x,
437 testtol, maxcuts)
438 CCtsp_lpcuts *cuts;
439 CCtsp_tighten_info *stats;
440 CCtsp_lpcut_in **cutsout;
441 int *cutcount;
442 int ncount, ecount;
443 int *elist;
444 double *x;
445 double testtol;
446 int maxcuts;
447 #endif
448 {
449 CCtsp_lpcut_in new, old;
450 CCtsp_lpcut_in *c;
451 int i;
452 int rval = 0;
453 double improve;
454 CCtsp_lpgraph lg;
455 double *newx = (double *) NULL;
456 int *newelist = (int *) NULL;
457 int newecount;
458 CCtsp_lpcut_in **clist = (CCtsp_lpcut_in **) NULL;
459 double *vlist = (double *) NULL;
460 double maxviol = 0.0;
461 int clistsize = 0, vlistsize = 0;
462 int count = 0;
463 int *perm = (int *) NULL;
464 double szeit = CCutil_zeit ();
465 double *cutval = (double *) NULL;
466
467 *cutcount = 0;
468 if (!cuts || !cuts->cutcount) return 0;
469
470
471 rval = grab_nonzero_x (ecount, elist, x, &newecount, &newelist, &newx,
472 X_FLUFF);
473 if (rval) {
474 fprintf (stderr, "grab_nonzero_x failed\n"); goto CLEANUP;
475 }
476
477 cutval = CC_SAFE_MALLOC (cuts->cutcount, double);
478 if (!cutval) {
479 fprintf (stderr, "out of memory in CCtsp_tighten_lp\n");
480 rval = 1; goto CLEANUP;
481 }
482 rval = CCtsp_price_cuts (cuts, ncount, newecount, newelist, newx, cutval);
483 if (rval) {
484 fprintf (stderr, "CCtsp_price_cuts failed\n"); goto CLEANUP;
485 }
486
487 CCtsp_init_lpgraph_struct (&lg);
488
489 rval = CCtsp_build_lpgraph (&lg, ncount, newecount, newelist, (int *) NULL);
490 if (rval) {
491 fprintf (stderr, "CCtsp_build_lpgraph failed\n"); goto CLEANUP;
492 }
493 CC_FREE (newelist, int);
494 rval = CCtsp_build_lpadj (&lg, 0, newecount);
495 if (rval) {
496 fprintf (stderr, "CCtsp_build_lpadj failed\n"); goto CLEANUP;
497 }
498
499 for (i = 0; i < cuts->cutcount; i++) {
500 if (cutval[i] < testtol && !cuts->cuts[i].branch) {
501 rval = CCtsp_lpcut_to_lpcut_in (cuts, &(cuts->cuts[i]), &old);
502 if (rval) {
503 fprintf (stderr, "CCtsp_lpcut_to_lpcut_in failed\n");
504 goto CLEANUP;
505 }
506 rval = CCtsp_tighten_lpcut_in (&lg, &old, newx, &new, stats,
507 &improve);
508 if (rval) {
509 fprintf (stderr, "CCtsp_tighten_lpcut failed\n");
510 goto CLEANUP;
511 }
512 CCtsp_free_lpcut_in (&old);
513
514 if (improve - cutval[i] > CCtsp_MIN_VIOL) {
515 c = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
516 if (!c) {
517 fprintf (stderr, "out of memory in CCtsp_tighten_lp\n");
518 rval = 1; goto CLEANUP;
519 }
520 *c = new;
521 if (count >= clistsize) {
522 rval = CCutil_reallocrus_scale ((void **) &clist,
523 &clistsize,
524 count + 1, 1.3, sizeof (CCtsp_lpcut_in *));
525 if (rval) {
526 fprintf (stderr, "CCutil_reallocrus_scale failed\n");
527 rval = 1; goto CLEANUP;
528 }
529 }
530 if (count >= vlistsize) {
531 rval = CCutil_reallocrus_scale ((void **) &vlist,
532 &vlistsize,
533 count + 1, 1.3, sizeof (double));
534 if (rval) {
535 fprintf (stderr, "CCutil_reallocrus_scale failed\n");
536 rval = 1; goto CLEANUP;
537 }
538 }
539 clist[count] = c;
540 vlist[count] = cutval[i] - improve;
541 count++;
542 } else {
543 CCtsp_free_lpcut_in (&new);
544 }
545 }
546 }
547
548 if (count) {
549 perm = CC_SAFE_MALLOC (count, int);
550 if (!perm) {
551 fprintf (stderr, "out of memory in CCtsp_tighten_lp\n");
552 rval = 1; goto CLEANUP;
553 }
554 for (i = 0; i < count; i++) {
555 perm[i] = i;
556 }
557 if (count > maxcuts) {
558 CCutil_rselect (perm, 0, count - 1, maxcuts, vlist);
559 for (i = maxcuts; i < count; i++) {
560 CCtsp_free_lpcut_in (clist[perm[i]]);
561 }
562 count = maxcuts;
563 }
564 for (i = 0; i < count; i++) {
565 if (vlist[perm[i]] < maxviol)
566 maxviol = vlist[perm[i]];
567 clist[perm[i]]->next = *cutsout;
568 *cutsout = clist[perm[i]];
569 }
570 }
571
572 *cutcount = count;
573 printf ("%d tighten cuts, %.5f max violation (%.2f seconds)\n",
574 count, -maxviol, CCutil_zeit () - szeit);
575 fflush (stdout);
576
577 CLEANUP:
578
579 CC_IFFREE (newelist, int);
580 CC_IFFREE (newx, double);
581 CC_IFFREE (clist, CCtsp_lpcut_in *);
582 CC_IFFREE (vlist, double);
583 CC_IFFREE (perm, int);
584 CC_IFFREE (cutval, double);
585 CCtsp_free_lpgraph (&lg);
586 return rval;
587 }
588
589 #ifdef CC_PROTOTYPE_ANSI
CCtsp_teething_lp(CCtsp_lpcuts * cuts,CCtsp_tighten_info * stats,CCtsp_lpcut_in ** cutsout,int * cutcount,int ncount,int ecount,int * elist,double * x,double testtol,int maxcuts)590 int CCtsp_teething_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats,
591 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount,
592 int *elist, double *x, double testtol, int maxcuts)
593 #else
594 int CCtsp_teething_lp (cuts, stats, cutsout, cutcount, ncount, ecount,
595 elist, x, testtol, maxcuts)
596 CCtsp_lpcuts *cuts;
597 CCtsp_tighten_info *stats;
598 CCtsp_lpcut_in **cutsout;
599 int *cutcount;
600 int ncount, ecount;
601 int *elist;
602 double *x;
603 double testtol;
604 int maxcuts;
605 #endif
606 {
607 int rval = 0;
608
609 rval = work_on_combs_in_lp (cuts, stats, cutsout, cutcount, ncount, ecount,
610 elist, x, testtol, maxcuts,
611 CCtsp_teething);
612 if (rval) {
613 fprintf (stderr, "work_on_combs_in_lp failed\n");
614 goto CLEANUP;
615 }
616
617 CLEANUP:
618
619 return rval;
620 }
621
622 #ifdef CC_PROTOTYPE_ANSI
work_on_combs_in_lp(CCtsp_lpcuts * cuts,CCtsp_tighten_info * stats,CCtsp_lpcut_in ** cutsout,int * cutcount,int ncount,int ecount,int * elist,double * x,double testtol,int maxcuts,int (* doit_fn)(CCtsp_lpgraph *,double *,CCtsp_lpcut_in *,CCtsp_lpcut_in **))623 static int work_on_combs_in_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats,
624 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount,
625 int *elist, double *x, double testtol, int maxcuts,
626 int (*doit_fn) (CCtsp_lpgraph *, double *, CCtsp_lpcut_in *,
627 CCtsp_lpcut_in **))
628 #else
629 static int work_on_combs_in_lp (cuts, stats, cutsout, cutcount, ncount, ecount,
630 elist, x, testtol, maxcuts, doit_fn)
631 CCtsp_lpcuts *cuts;
632 CCtsp_tighten_info *stats;
633 CCtsp_lpcut_in **cutsout;
634 int *cutcount;
635 int ncount, ecount;
636 int *elist;
637 double *x;
638 double testtol;
639 int maxcuts;
640 int (*doit_fn) ();
641 #endif
642 {
643 CCtsp_lpcut_in new, old;
644 CCtsp_lpcut_in *c = (CCtsp_lpcut_in *) NULL;
645 CCtsp_lpcut_in *dd = (CCtsp_lpcut_in *) NULL;
646 int i, test;
647 int rval = 0;
648 double improve, newslack;
649 CCtsp_lpgraph lg;
650 double *newx = (double *) NULL;
651 int *newelist = (int *) NULL;
652 int newecount;
653 CCtsp_lpcut_in **clist = (CCtsp_lpcut_in **) NULL;
654 double *vlist = (double *) NULL;
655 double maxviol = 0.0;
656 int clistsize = 0, vlistsize = 0;
657 int count = 0;
658 int *perm = (int *) NULL;
659 double *cutval = (double *) NULL;
660 double szeit = CCutil_zeit ();
661
662 *cutcount = 0;
663 if (!cuts || !cuts->cutcount) return 0;
664
665 rval = grab_nonzero_x (ecount, elist, x, &newecount, &newelist, &newx,
666 X_FLUFF);
667 if (rval) {
668 fprintf (stderr, "grab_nonzero_x failed\n"); goto CLEANUP;
669 }
670
671 cutval = CC_SAFE_MALLOC (cuts->cutcount, double);
672 if (!cutval) {
673 fprintf (stderr, "out of memory in CCtsp_tighten_lp\n");
674 rval = 1; goto CLEANUP;
675 }
676 rval = CCtsp_price_cuts (cuts, ncount, newecount, newelist, newx, cutval);
677 if (rval) {
678 fprintf (stderr, "CCtsp_price_cuts failed\n"); goto CLEANUP;
679 }
680
681 CCtsp_init_lpgraph_struct (&lg);
682 rval = CCtsp_build_lpgraph (&lg, ncount, newecount, newelist, (int *) NULL);
683 if (rval) {
684 fprintf (stderr, "CCtsp_build_lpgraph failed\n"); goto CLEANUP;
685 }
686 CC_FREE (newelist, int);
687 rval = CCtsp_build_lpadj (&lg, 0, newecount);
688 if (rval) {
689 fprintf (stderr, "CCtsp_build_lpadj failed\n"); goto CLEANUP;
690 }
691
692 for (i = 0; i < cuts->cutcount; i++) {
693 if (cuts->cuts[i].branch || cuts->cuts[i].cliquecount % 2 ||
694 cuts->cuts[i].cliquecount < 4 || cutval[i] >= testtol) {
695 continue;
696 }
697 rval = CCtsp_lpcut_to_lpcut_in (cuts, &(cuts->cuts[i]), &old);
698 if (rval) {
699 fprintf (stderr, "CCtsp_lpcut_to_lpcut_in failed\n"); goto CLEANUP;
700 }
701 rval = CCtsp_test_pure_comb (ncount, &old, &test, (int *) NULL);
702 if (rval) {
703 fprintf (stderr, "CCtsp_test_pure_comb failed\n");
704 CCtsp_free_lpcut_in (&old);
705 goto CLEANUP;
706 }
707 if (test == 1) {
708 rval = doit_fn (&lg, newx, &old, &dd);
709 if (rval) {
710 fprintf (stderr, "doit_fn failed\n"); goto CLEANUP;
711 }
712 CCtsp_free_lpcut_in (&old);
713 if (dd) {
714 rval = CCtsp_tighten_lpcut_in (&lg, dd, newx, &new,
715 stats, &improve);
716 if (rval) {
717 fprintf (stderr, "CCtsp_tighten_lpcut failed\n");
718 goto CLEANUP;
719 }
720 CCtsp_free_lpcut_in (dd);
721 CC_FREE (dd, CCtsp_lpcut_in);
722
723 newslack = CCtsp_cutprice (&lg, &new, newx);
724 if (-newslack > CCtsp_MIN_VIOL) {
725 c = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
726 if (!c) {
727 fprintf (stderr,
728 "out of memory in work_on_combs_in_lp\n");
729 CCtsp_free_lpcut_in (&new);
730 rval = 1; goto CLEANUP;
731 }
732 *c = new;
733 if (count >= clistsize) {
734 rval = CCutil_reallocrus_scale ((void **) &clist,
735 &clistsize, count + 1, 1.3,
736 sizeof (CCtsp_lpcut_in *));
737 if (rval) {
738 fprintf (stderr,
739 "CCutil_reallocrus_scale failed\n");
740 rval = 1; goto CLEANUP;
741 }
742 }
743 if (count >= vlistsize) {
744 rval = CCutil_reallocrus_scale ((void **) &vlist,
745 &vlistsize, count + 1, 1.3,
746 sizeof (double));
747 if (rval) {
748 fprintf (stderr,
749 "CCutil_reallocrus_scale failed\n");
750 rval = 1; goto CLEANUP;
751 }
752 }
753 clist[count] = c;
754 vlist[count] = newslack;
755 count++;
756 } else {
757 CCtsp_free_lpcut_in (&new);
758 }
759 }
760 } else {
761 CCtsp_free_lpcut_in (&old);
762 }
763 }
764
765 if (count) {
766 perm = CC_SAFE_MALLOC (count, int);
767 if (!perm) {
768 fprintf (stderr, "out of memory in work_on_combs_in_lp\n");
769 rval = 1; goto CLEANUP;
770 }
771 for (i = 0; i < count; i++) {
772 perm[i] = i;
773 }
774 if (count > maxcuts) {
775 CCutil_rselect (perm, 0, count - 1, maxcuts, vlist);
776 for (i = maxcuts; i < count; i++) {
777 CCtsp_free_lpcut_in (clist[perm[i]]);
778 }
779 count = maxcuts;
780 }
781 for (i = 0; i < count; i++) {
782 if (vlist[perm[i]] < maxviol)
783 maxviol = vlist[perm[i]];
784 clist[perm[i]]->next = *cutsout;
785 *cutsout = clist[perm[i]];
786 }
787 }
788
789 *cutcount = count;
790 printf ("%d cuts, %.5f max violation (%.2f seconds)\n", count, -maxviol,
791 CCutil_zeit () - szeit);
792 fflush (stdout);
793
794 CLEANUP:
795
796 CC_IFFREE (newelist, int);
797 CC_IFFREE (newx, double);
798 CC_IFFREE (clist, CCtsp_lpcut_in *);
799 CC_IFFREE (vlist, double);
800 CC_IFFREE (perm, int);
801 CC_IFFREE (cutval, double);
802 CCtsp_free_lpgraph (&lg);
803 if (dd) {
804 CCtsp_free_lpcut_in (dd);
805 }
806 return rval;
807 }
808
809 #ifdef CC_PROTOTYPE_ANSI
CCtsp_init_lpcut_in(CCtsp_lpcut_in * c)810 void CCtsp_init_lpcut_in (CCtsp_lpcut_in *c)
811 #else
812 void CCtsp_init_lpcut_in (c)
813 CCtsp_lpcut_in *c;
814 #endif
815 {
816 if (c) {
817 c->handlecount = 0;
818 c->cliquecount = 0;
819 c->rhs = 0;
820 c->sense = 'X';
821 c->branch = 0;
822 c->cliques = (CCtsp_lpclique *) NULL;
823 c->next = (CCtsp_lpcut_in *) NULL;
824 c->prev = (CCtsp_lpcut_in *) NULL;
825 }
826 }
827
828 #ifdef CC_PROTOTYPE_ANSI
CCtsp_copy_lpcut_in(CCtsp_lpcut_in * c,CCtsp_lpcut_in * new)829 int CCtsp_copy_lpcut_in (CCtsp_lpcut_in *c, CCtsp_lpcut_in *new)
830 #else
831 int CCtsp_copy_lpcut_in (c, new)
832 CCtsp_lpcut_in *c;
833 CCtsp_lpcut_in *new;
834 #endif
835 {
836 int rval = 0;
837 int i;
838
839 CCtsp_init_lpcut_in (new);
840
841 new->handlecount = c->handlecount;
842 new->cliquecount = c->cliquecount;
843 new->rhs = c->rhs;
844 new->sense = c->sense;
845
846 if (c->cliquecount) {
847 new->cliques = CC_SAFE_MALLOC (c->cliquecount, CCtsp_lpclique);
848 if (!new->cliques) {
849 fprintf (stderr, "out of memory in CCtsp_copy_lpcut_in\n");
850 rval = 1; goto CLEANUP;
851 }
852 for (i = 0; i < c->cliquecount; i++) {
853 rval = CCtsp_copy_lpclique (&c->cliques[i], &new->cliques[i]);
854 if (rval) {
855 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
856 goto CLEANUP;
857 }
858 }
859 }
860
861 CLEANUP:
862
863 return rval;
864 }
865
866 #ifdef CC_PROTOTYPE_ANSI
CCtsp_segment_to_subtour(CCtsp_lpcut_in ** cut,int a,int b)867 int CCtsp_segment_to_subtour (CCtsp_lpcut_in **cut, int a, int b)
868 #else
869 int CCtsp_segment_to_subtour (cut, a, b)
870 CCtsp_lpcut_in **cut;
871 int a, b;
872 #endif
873 {
874 int rval = 0;
875 int list[2];
876 int t;
877 CCtsp_lpcut_in *c = (CCtsp_lpcut_in *) NULL;
878
879 *cut = (CCtsp_lpcut_in *) NULL;
880 if (a > b) CC_SWAP (a, b, t);
881
882 c = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
883 if (!c) {
884 fprintf (stderr, "out of memory in CCtsp_segment_to_subtour\n");
885 rval = 1; goto CLEANUP;
886 }
887 CCtsp_init_lpcut_in (c);
888
889 c->cliquecount = 1;
890 c->handlecount = 0;
891 c->cliques = CC_SAFE_MALLOC (1, CCtsp_lpclique);
892 if (!c->cliques) {
893 fprintf (stderr, "out of memory in CCtsp_segment_to_subtour\n");
894 rval = 1; goto CLEANUP;
895 }
896
897 list[0] = a;
898 list[1] = b;
899 rval = CCtsp_seglist_to_lpclique (1, list, &(c->cliques[0]));
900 if (rval) {
901 goto CLEANUP;
902 }
903 c->rhs = CCtsp_CUTRHS(c);
904 c->sense = 'G';
905 c->branch = 0;
906
907 *cut = c;
908
909 CLEANUP:
910
911 if (rval) {
912 if (c) {
913 CCtsp_free_lpcut_in (c);
914 CC_FREE (c, CCtsp_lpcut_in);
915 }
916 }
917 return rval;
918 }
919
920 #ifdef CC_PROTOTYPE_ANSI
CCtsp_array_to_subtour(CCtsp_lpcut_in ** cut,int * ar,int acount)921 int CCtsp_array_to_subtour (CCtsp_lpcut_in **cut, int *ar, int acount)
922 #else
923 int CCtsp_array_to_subtour (cut, ar, acount)
924 CCtsp_lpcut_in **cut;
925 int *ar;
926 int acount;
927 #endif
928 {
929 int rval = 0;
930 CCtsp_lpcut_in *c = (CCtsp_lpcut_in *) NULL;
931
932 *cut = (CCtsp_lpcut_in *) NULL;
933
934 c = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
935 if (!c) {
936 fprintf (stderr, "out of memory in CCtsp_array_to_subtour\n");
937 rval = 1; goto CLEANUP;
938 }
939 CCtsp_init_lpcut_in (c);
940
941 c->cliquecount = 1;
942 c->handlecount = 0;
943 c->cliques = CC_SAFE_MALLOC (1, CCtsp_lpclique);
944 if (!c->cliques) {
945 fprintf (stderr, "out of memory in CCtsp_array_to_subtour\n");
946 rval = 1; goto CLEANUP;
947 }
948
949 rval = CCtsp_array_to_lpclique (ar, acount, &(c->cliques[0]));
950 if (rval) {
951 goto CLEANUP;
952 }
953 c->rhs = CCtsp_CUTRHS(c);
954 c->sense = 'G';
955 c->branch = 0;
956
957 *cut = c;
958
959 CLEANUP:
960
961 if (rval) {
962 if (c) {
963 CCtsp_free_lpcut_in (c);
964 CC_FREE (c, CCtsp_lpcut_in);
965 }
966 }
967 return rval;
968 }
969
970 #ifdef CC_PROTOTYPE_ANSI
CCtsp_init_lpclique(CCtsp_lpclique * c)971 void CCtsp_init_lpclique (CCtsp_lpclique *c)
972 #else
973 void CCtsp_init_lpclique (c)
974 CCtsp_lpclique *c;
975 #endif
976 {
977 if (c) {
978 c->segcount = 0;
979 c->nodes = (CCtsp_segment *) NULL;
980 c->hashnext = 0;
981 c->refcount = 0;
982 }
983 }
984
985 #ifdef CC_PROTOTYPE_ANSI
CCtsp_array_to_lpclique(int * ar,int acount,CCtsp_lpclique * cliq)986 int CCtsp_array_to_lpclique (int *ar, int acount, CCtsp_lpclique *cliq)
987 #else
988 int CCtsp_array_to_lpclique (ar, acount, cliq)
989 int *ar;
990 int acount;
991 CCtsp_lpclique *cliq;
992 #endif
993 {
994 int i, nseg;
995
996 /* Function will alter the order on the array */
997
998 CCutil_int_array_quicksort (ar, acount);
999 nseg = 0;
1000 i = 0;
1001 while (i < acount) {
1002 while (i < (acount - 1) && ar[i + 1] == (ar[i] + 1))
1003 i++;
1004 i++;
1005 nseg++;
1006 }
1007
1008 cliq->nodes = CC_SAFE_MALLOC (nseg, CCtsp_segment);
1009 if (!cliq->nodes) {
1010 fprintf (stderr, "out of memory in CCtsp_array_to_lpclique\n");
1011 return 1;
1012 }
1013 cliq->segcount = nseg;
1014
1015 nseg = 0;
1016 i = 0;
1017 while (i < acount) {
1018 cliq->nodes[nseg].lo = ar[i];
1019 while (i < (acount - 1) && ar[i + 1] == (ar[i] + 1))
1020 i++;
1021 cliq->nodes[nseg].hi = ar[i++];
1022 nseg++;
1023 }
1024 return 0;
1025 }
1026
1027 #ifdef CC_PROTOTYPE_ANSI
CCtsp_seglist_to_lpclique(int nseg,int * list,CCtsp_lpclique * cliq)1028 int CCtsp_seglist_to_lpclique (int nseg, int *list, CCtsp_lpclique *cliq)
1029 #else
1030 int CCtsp_seglist_to_lpclique (nseg, list, cliq)
1031 int nseg;
1032 int *list;
1033 CCtsp_lpclique *cliq;
1034 #endif
1035 {
1036 int i;
1037 int *perm = (int *) NULL;
1038 int *len = (int *) NULL;
1039 int rval = 0;
1040
1041 perm = CC_SAFE_MALLOC (nseg, int);
1042 len = CC_SAFE_MALLOC (nseg, int);
1043 if (!perm || !len) {
1044 fprintf (stderr, "out of memory in CCtsp_seglist_to_lpclique\n");
1045 rval = 1; goto CLEANUP;
1046 }
1047 for (i = 0; i < nseg; i++) {
1048 perm[i] = i;
1049 len[i] = list[2*i];
1050 }
1051 CCutil_int_perm_quicksort (perm, len, nseg);
1052
1053 cliq->nodes = CC_SAFE_MALLOC (nseg, CCtsp_segment);
1054 if (!cliq->nodes) {
1055 fprintf (stderr, "out of memory in CCtsp_seglist_to_lpclique\n");
1056 rval = 1; goto CLEANUP;
1057 }
1058 cliq->segcount = nseg;
1059
1060 for (i = 0; i < nseg; i++) {
1061 cliq->nodes[i].lo = list[2*perm[i]];
1062 cliq->nodes[i].hi = list[2*perm[i]+1];
1063 }
1064
1065 nseg = 0;
1066
1067 CLEANUP:
1068
1069 CC_IFFREE (perm, int);
1070 CC_IFFREE (len, int);
1071
1072 return rval;
1073 }
1074
1075 #ifdef CC_PROTOTYPE_ANSI
CCtsp_add_node_to_lpclique(CCtsp_lpclique * cin,CCtsp_lpclique * cout,int n)1076 int CCtsp_add_node_to_lpclique (CCtsp_lpclique *cin, CCtsp_lpclique *cout,
1077 int n)
1078 #else
1079 int CCtsp_add_node_to_lpclique (cin, cout, n)
1080 CCtsp_lpclique *cin;
1081 CCtsp_lpclique *cout;
1082 int n;
1083 #endif
1084 {
1085 int count = 0;
1086 int rval = 0;
1087 int *ar = (int *) NULL;
1088 int i, j;
1089
1090 CCtsp_init_lpclique (cout);
1091
1092 for (i = 0; i < cin->segcount; i++) {
1093 count += (cin->nodes[i].hi - cin->nodes[i].lo + 1);
1094 if (cin->nodes[i].lo <= n && n <= cin->nodes[i].hi) {
1095 fprintf (stderr, "node already in clique\n");
1096 rval = 1; goto CLEANUP;
1097 }
1098 }
1099
1100 ar = CC_SAFE_MALLOC (count + 1, int);
1101 if (!ar) {
1102 fprintf (stderr, "out of memory in CCtsp_add_node_to_lpclique\n");
1103 rval = 1; goto CLEANUP;
1104 }
1105
1106 count = 0;
1107 for (i = 0; i < cin->segcount; i++) {
1108 for (j = cin->nodes[i].lo; j <= cin->nodes[i].hi; j++) {
1109 ar[count++] = j;
1110 }
1111 }
1112 ar[count++] = n;
1113 rval = CCtsp_array_to_lpclique (ar, count, cout);
1114 if (rval) {
1115 fprintf (stderr, "CCtsp_array_to_lpclique failed\n"); goto CLEANUP;
1116 }
1117
1118 CLEANUP:
1119
1120 CC_IFFREE (ar, int);
1121 return rval;
1122 }
1123
1124 #ifdef CC_PROTOTYPE_ANSI
CCtsp_delete_node_from_lpclique(CCtsp_lpclique * cin,CCtsp_lpclique * cout,int n)1125 int CCtsp_delete_node_from_lpclique (CCtsp_lpclique *cin,
1126 CCtsp_lpclique *cout, int n)
1127 #else
1128 int CCtsp_delete_node_from_lpclique (cin, cout, n)
1129 CCtsp_lpclique *cin;
1130 CCtsp_lpclique *cout;
1131 int n;
1132 #endif
1133 {
1134 int count = 0;
1135 int rval = 0;
1136 int *ar = (int *) NULL;
1137 int i, j, hit = 0;
1138
1139 CCtsp_init_lpclique (cout);
1140
1141 for (i = 0; i < cin->segcount; i++) {
1142 count += (cin->nodes[i].hi - cin->nodes[i].lo + 1);
1143 if (cin->nodes[i].lo <= n && n <= cin->nodes[i].hi) {
1144 hit++;
1145 }
1146 }
1147 if (!hit) {
1148 fprintf (stderr, "node is not in clique\n");
1149 rval = 1; goto CLEANUP;
1150 }
1151
1152 ar = CC_SAFE_MALLOC (count, int);
1153 if (!ar) {
1154 fprintf (stderr, "out of memory in CCtsp_delete_node_from_lpclique\n");
1155 rval = 1; goto CLEANUP;
1156 }
1157
1158 count = 0;
1159 for (i = 0; i < cin->segcount; i++) {
1160 for (j = cin->nodes[i].lo; j <= cin->nodes[i].hi; j++) {
1161 if (j != n) {
1162 ar[count++] = j;
1163 }
1164 }
1165 }
1166 rval = CCtsp_array_to_lpclique (ar, count, cout);
1167 if (rval) {
1168 fprintf (stderr, "CCtsp_array_to_lpclique failed\n"); goto CLEANUP;
1169 }
1170
1171 CLEANUP:
1172
1173 CC_IFFREE (ar, int);
1174 return rval;
1175 }
1176
1177 #ifdef CC_PROTOTYPE_ANSI
CCtsp_print_lpcut_in(CCtsp_lpcut_in * c)1178 void CCtsp_print_lpcut_in (CCtsp_lpcut_in *c)
1179 #else
1180 void CCtsp_print_lpcut_in (c)
1181 CCtsp_lpcut_in *c;
1182 #endif
1183 {
1184 int i;
1185
1186 if (c->cliquecount == 1) {
1187 printf ("Subtour\n");
1188 printf (" ");
1189 CCtsp_print_lpclique (&(c->cliques[0]));
1190 } else {
1191 if (c->handlecount == 1) {
1192 printf ("Comb\n");
1193 printf (" Handle\n");
1194 } else {
1195 printf ("Clique Tree or Wild Thing\n");
1196 printf (" Handles:\n");
1197 }
1198 for (i = 0; i < c->handlecount; i++) {
1199 printf (" ");
1200 CCtsp_print_lpclique (&(c->cliques[i]));
1201 }
1202 if (c->cliquecount > c->handlecount) {
1203 printf (" Teeth\n");
1204 for (; i < c->cliquecount; i++) {
1205 printf (" ");
1206 CCtsp_print_lpclique (&(c->cliques[i]));
1207 }
1208 }
1209 }
1210 printf ("\n"); fflush (stdout);
1211 }
1212
1213 #ifdef CC_PROTOTYPE_ANSI
CCtsp_print_lpclique(CCtsp_lpclique * c)1214 void CCtsp_print_lpclique (CCtsp_lpclique *c)
1215 #else
1216 void CCtsp_print_lpclique (c)
1217 CCtsp_lpclique *c;
1218 #endif
1219 {
1220 int i;
1221
1222 if (c->segcount == 0) {
1223 printf ("Empty Clique\n"); fflush (stdout);
1224 } else {
1225 for (i = 0; i < c->segcount; i++) {
1226 printf ("%d->%d ", c->nodes[i].lo, c->nodes[i].hi);
1227 }
1228 printf ("\n"); fflush (stdout);
1229 }
1230 }
1231
1232 #ifdef CC_PROTOTYPE_ANSI
CCtsp_lpcut_to_lpcut_in(CCtsp_lpcuts * cuts,CCtsp_lpcut * c,CCtsp_lpcut_in * new)1233 int CCtsp_lpcut_to_lpcut_in (CCtsp_lpcuts *cuts, CCtsp_lpcut *c,
1234 CCtsp_lpcut_in *new)
1235 #else
1236 int CCtsp_lpcut_to_lpcut_in (cuts, c, new)
1237 CCtsp_lpcuts *cuts;
1238 CCtsp_lpcut *c;
1239 CCtsp_lpcut_in *new;
1240 #endif
1241 {
1242 int i, k;
1243 CCtsp_lpclique *cl;
1244 int rval = 0;
1245
1246 new->handlecount = c->handlecount;
1247 new->cliquecount = c->cliquecount;
1248 new->rhs = c->rhs;
1249 new->sense = c->sense;
1250 new->branch = c->branch;
1251 new->next = (CCtsp_lpcut_in *) NULL;
1252 new->prev = (CCtsp_lpcut_in *) NULL;
1253
1254 new->cliques = CC_SAFE_MALLOC (c->cliquecount, CCtsp_lpclique);
1255 if (!new->cliques) {
1256 fprintf (stderr, "out of memory in CCtsp_lpcut_to_lpcut_in\n");
1257 return 1;
1258 }
1259
1260 for (i = 0; i < c->cliquecount; i++) {
1261 cl = &(cuts->cliques[c->cliques[i]]);
1262 rval = CCtsp_copy_lpclique (cl, &new->cliques[i]);
1263 if (rval) {
1264 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
1265 for (k = 0; k < i; k++) {
1266 CC_FREE (new->cliques[k].nodes, CCtsp_segment);
1267 }
1268 CC_FREE (new->cliques, CCtsp_lpclique);
1269 return 1;
1270 }
1271 }
1272
1273 return 0;
1274 }
1275
1276 #ifdef CC_PROTOTYPE_ANSI
CCtsp_copy_lpclique(CCtsp_lpclique * c,CCtsp_lpclique * new)1277 int CCtsp_copy_lpclique (CCtsp_lpclique *c, CCtsp_lpclique *new)
1278 #else
1279 int CCtsp_copy_lpclique (c, new)
1280 CCtsp_lpclique *c;
1281 CCtsp_lpclique *new;
1282 #endif
1283 {
1284 int k;
1285 CCtsp_segment *s = (CCtsp_segment *) NULL;
1286
1287 CCtsp_init_lpclique (new);
1288 if (c->segcount) {
1289 s = CC_SAFE_MALLOC (c->segcount, CCtsp_segment);
1290 if (!s) {
1291 fprintf (stderr, "out of memory in copy_lpclique\n");
1292 return 1;
1293 }
1294 for (k = 0; k < c->segcount; k++) {
1295 s[k].lo = c->nodes[k].lo;
1296 s[k].hi = c->nodes[k].hi;
1297 }
1298 }
1299 new->segcount = c->segcount;
1300 new->nodes = s;
1301 return 0;
1302 }
1303
1304 #ifdef CC_PROTOTYPE_ANSI
CCtsp_lpclique_compare(CCtsp_lpclique * a,CCtsp_lpclique * b,int * diff)1305 void CCtsp_lpclique_compare (CCtsp_lpclique *a, CCtsp_lpclique *b, int *diff)
1306 #else
1307 void CCtsp_lpclique_compare (a, b, diff)
1308 CCtsp_lpclique *a, *b;
1309 int *diff;
1310 #endif
1311 {
1312 int i;
1313
1314 if (a->segcount != b->segcount) {
1315 *diff = 1; return;
1316 } else {
1317 for (i = 0; i < a->segcount; i++) {
1318 if (a->nodes[i].lo != b->nodes[i].lo) {
1319 *diff = 1; return;
1320 }
1321 if (a->nodes[i].hi != b->nodes[i].hi) {
1322 *diff = 1; return;
1323 }
1324 }
1325 }
1326 *diff = 0; return;
1327 }
1328
1329 #ifdef CC_PROTOTYPE_ANSI
CCtsp_file_cuts(char * cutfile,CCtsp_lpcut_in ** cuts,int * cutcount,int ncount,int * tour)1330 int CCtsp_file_cuts (char *cutfile, CCtsp_lpcut_in **cuts, int *cutcount,
1331 int ncount, int *tour)
1332 #else
1333 int CCtsp_file_cuts (cutfile, cuts, cutcount, ncount, tour)
1334 char *cutfile;
1335 CCtsp_lpcut_in **cuts;
1336 int *cutcount;
1337 int ncount;
1338 int *tour;
1339 #endif
1340 {
1341 FILE *in = (FILE *) NULL;
1342 int *inv = (int *) NULL;
1343 CCtsp_lpcut_in *c;
1344 int i, j, k;
1345 int ncliques, nhandles, size;
1346 int *icliq = (int *) NULL;
1347 int rval = 0;
1348
1349 *cutcount = 0;
1350
1351 in = fopen (cutfile, "r");
1352 if (in == (FILE *) NULL) {
1353 fprintf (stderr, "unable to open %s for reading\n", cutfile);
1354 return 0;
1355 }
1356
1357 inv = CC_SAFE_MALLOC (ncount, int);
1358 if (!inv) {
1359 fprintf (stderr, "out of memory in CCtsp_file_cuts\n");
1360 rval = 1; goto CLEANUP;
1361 }
1362 for (i = 0; i < ncount; i++) {
1363 inv[tour[i]] = i;
1364 }
1365
1366 while (fscanf (in, "%d", &ncliques) != EOF) {
1367 c = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
1368 if (!c) {
1369 fprintf (stderr, "out of memory in CCtsp_file_cuts\n");
1370 rval = 1; goto CLEANUP;
1371 }
1372 c->cliquecount = ncliques;
1373 c->cliques = CC_SAFE_MALLOC (ncliques, CCtsp_lpclique);
1374 if (!c->cliques) {
1375 fprintf (stderr, "out of memory in CCtsp_file_cuts\n");
1376 rval = 1; goto CLEANUP;
1377 }
1378 if (fscanf (in, "%d", &nhandles) != 1) {
1379 rval = 1; goto CLEANUP;
1380 }
1381 c->handlecount = nhandles;
1382 for (i = 0; i < ncliques; i++) {
1383 if (fscanf (in, "%d", &size) != 1) {
1384 rval = 1; goto CLEANUP;
1385 }
1386 icliq = CC_SAFE_MALLOC (size, int);
1387 if (!icliq) {
1388 fprintf (stderr, "out of memory in CCtsp_file_cuts\n");
1389 rval = 1; goto CLEANUP;
1390 }
1391 for (j = 0; j < size; j++) {
1392 if (fscanf (in, "%d", &k) != 1) {
1393 rval = 1; goto CLEANUP;
1394 }
1395 icliq[j] = inv[k];
1396 }
1397 rval = CCtsp_array_to_lpclique (icliq, size, &(c->cliques[i]));
1398 if (rval) {
1399 fprintf (stderr, "CCtsp_array_to_lpclique failed\n");
1400 goto CLEANUP;
1401 }
1402 CC_FREE (icliq, int);
1403 }
1404 if (fscanf (in, "%d", &(c->rhs)) != 1) {
1405 rval = 1; goto CLEANUP;
1406 }
1407 c->sense = 'G';
1408 c->branch = 0;
1409 c->next = *cuts;
1410 *cuts = c;
1411 (*cutcount)++;
1412 }
1413
1414 CLEANUP:
1415
1416 CC_IFFREE (inv, int);
1417 fclose (in);
1418 return rval;
1419 }
1420
1421 #ifdef CC_PROTOTYPE_ANSI
CCtsp_file_cuts_write(char * cutfile,CCtsp_lpcuts * cuts,int * tour)1422 int CCtsp_file_cuts_write (char *cutfile, CCtsp_lpcuts *cuts, int *tour)
1423 #else
1424 int CCtsp_file_cuts_write (cutfile, cuts, tour)
1425 char *cutfile;
1426 CCtsp_lpcuts *cuts;
1427 int *tour;
1428 #endif
1429 {
1430 FILE *out = (FILE *) NULL;
1431 int i, j, k, p;
1432 int cutcount = cuts->cutcount;
1433 CCtsp_lpcut *c;
1434 CCtsp_lpclique *cl;
1435 int isize;
1436
1437 out = fopen (cutfile, "w");
1438 if (out == (FILE *) NULL) {
1439 fprintf (stderr, "unable to open %s for writing\n", cutfile);
1440 return 1;
1441 }
1442
1443 for (i = 0; i < cutcount; i++) {
1444 c = &cuts->cuts[i];
1445 if (!c->branch) {
1446 fprintf (out, "%d %d\n", c->cliquecount, c->handlecount);
1447 for (j = 0; j < c->cliquecount; j++) {
1448 cl = &cuts->cliques[c->cliques[j]];
1449 for (k = 0, isize = 0; k < cl->segcount; k++) {
1450 isize += (cl->nodes[k].hi - cl->nodes[k].lo + 1);
1451 }
1452 fprintf (out, "%d ", isize);
1453 for (k = 0; k < cl->segcount; k++) {
1454 for (p = cl->nodes[k].lo; p <= cl->nodes[k].hi; p++) {
1455 fprintf (out, "%d ", tour[p]);
1456 }
1457 }
1458 fprintf (out, "\n");
1459 }
1460 fprintf (out, "%d\n", c->rhs);
1461 }
1462 }
1463
1464 fclose (out);
1465 return 0;
1466 }
1467
1468 #ifdef CC_PROTOTYPE_ANSI
CCtsp_buildcut_begin(cutinfo * cuts,int init_cliquecount)1469 int CCtsp_buildcut_begin (cutinfo *cuts, int init_cliquecount)
1470 #else
1471 int CCtsp_buildcut_begin (cuts, init_cliquecount)
1472 cutinfo *cuts;
1473 int init_cliquecount;
1474 #endif
1475 {
1476 cuts->current = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
1477 if (!cuts->current) return -1;
1478 cuts->current->cliquecount = 0;
1479 cuts->current->handlecount = 0;
1480 cuts->current->rhs = 0;
1481 cuts->current->sense = 'G';
1482 cuts->current->branch = 0;
1483 cuts->current->cliques = CC_SAFE_MALLOC (init_cliquecount, CCtsp_lpclique);
1484 if (!cuts->current->cliques) {
1485 CC_FREE (cuts->current, CCtsp_lpcut_in);
1486 return -1;
1487 }
1488 return 0;
1489 }
1490
1491 #ifdef CC_PROTOTYPE_ANSI
CCtsp_buildcut_addclique(cutinfo * cuts,int * arr,int size,int handle)1492 int CCtsp_buildcut_addclique (cutinfo *cuts, int *arr, int size, int handle)
1493 #else
1494 int CCtsp_buildcut_addclique (cuts, arr, size, handle)
1495 cutinfo *cuts;
1496 int *arr;
1497 int size;
1498 int handle;
1499 #endif
1500 {
1501 int i;
1502 int *newarr = (int *) NULL;
1503 int newsize;
1504 int rval;
1505 CCtsp_lpcut_in *c = cuts->current;
1506
1507 if (!c) {
1508 fprintf (stderr, "Trying to add to nonexistent clique\n");
1509 return -1;
1510 }
1511
1512 rval = CCcut_SRK_expand (&cuts->expand, arr, size, &newarr, &newsize);
1513 if (rval) {
1514 fprintf (stderr, "CCcut_SRK_expand failed\n");
1515 CCtsp_buildcut_abort (cuts);
1516 return rval;
1517 }
1518
1519 rval = CCutil_reallocrus_count ((void **) &(c->cliques), c->cliquecount+1,
1520 sizeof (c->cliques[0]));
1521 if (rval) {
1522 fprintf (stderr, "couldn't realloc cliques\n");
1523 CC_IFFREE (newarr, int);
1524 CCtsp_buildcut_abort (cuts);
1525 return rval;
1526 }
1527
1528 if (handle) {
1529 for (i=c->cliquecount; i>c->handlecount; i--) {
1530 c->cliques[i] = c->cliques[i-1];
1531 }
1532 i = c->handlecount;
1533 c->handlecount++;
1534 } else {
1535 i = c->cliquecount;
1536 }
1537
1538 rval = CCtsp_array_to_lpclique (newarr, newsize, &(c->cliques[i]));
1539 if (rval) {
1540 fprintf (stderr, "CCtsp_array_to_lpclique failed\n");
1541 CC_IFFREE (newarr, int);
1542 CCtsp_buildcut_abort (cuts);
1543 return rval;
1544 }
1545 c->cliquecount++;
1546 CC_IFFREE (newarr, int);
1547 return 0;
1548 }
1549
1550 #ifdef CC_PROTOTYPE_ANSI
CCtsp_buildcut_abort(cutinfo * cuts)1551 void CCtsp_buildcut_abort (cutinfo *cuts)
1552 #else
1553 void CCtsp_buildcut_abort (cuts)
1554 cutinfo *cuts;
1555 #endif
1556 {
1557 int i;
1558 CCtsp_lpcut_in *c = cuts->current;
1559
1560 if (c) {
1561 for (i=0; i<c->cliquecount; i++) {
1562 CC_FREE (c->cliques[i].nodes, CCtsp_segment);
1563 }
1564 CC_FREE (c->cliques, CCtsp_lpclique);
1565 CC_FREE (cuts->current, CCtsp_lpcut_in);
1566 }
1567 }
1568
1569 #ifdef CC_PROTOTYPE_ANSI
CCtsp_buildcut_finish(cutinfo * cuts,int rhs)1570 void CCtsp_buildcut_finish (cutinfo *cuts, int rhs)
1571 #else
1572 void CCtsp_buildcut_finish (cuts, rhs)
1573 cutinfo *cuts;
1574 int rhs;
1575 #endif
1576 {
1577 CCtsp_lpcut_in *c = cuts->current;
1578
1579 #ifdef DUMP_BUILDCUT
1580 {
1581 int i, j, k;
1582 printf ("new buildcut (%d %d):", c->cliquecount, c->handlecount);
1583 for (i=0; i<c->cliquecount; i++) {
1584 printf (" (");
1585 for (j=0; j<c->cliques[i].segcount; j++) {
1586 for (k=c->cliques[i].nodes[j].lo; k<=c->cliques[i].nodes[j].hi;
1587 k++) {
1588 printf ("%d ",k);
1589 }
1590 }
1591 printf (")");
1592 }
1593 printf (" >= %d\n", rhs);
1594 fflush (stdout);
1595 }
1596 #endif
1597
1598 c->rhs = rhs;
1599 c->next = *cuts->clist;
1600 (*cuts->clist) = c;
1601 cuts->current = (CCtsp_lpcut_in *) NULL;
1602 (*cuts->cutcount)++;
1603 }
1604
1605 #ifdef CC_PROTOTYPE_ANSI
grab_nonzero_x(int ecount,int * elist,double * x,int * new_ecount,int ** new_elist,double ** new_x,double tol)1606 static int grab_nonzero_x (int ecount, int *elist, double *x,
1607 int *new_ecount, int **new_elist, double **new_x, double tol)
1608 #else
1609 static int grab_nonzero_x (ecount, elist, x, new_ecount, new_elist, new_x, tol)
1610 int ecount;
1611 int *elist;
1612 double *x;
1613 int *new_ecount;
1614 int **new_elist;
1615 double **new_x;
1616 double tol;
1617 #endif
1618 {
1619 int i;
1620 int count;
1621
1622 *new_ecount = 0;
1623 *new_elist = (int *) NULL;
1624 *new_x = (double *) NULL;
1625
1626 for (i = 0, count = 0; i < ecount; i++) {
1627 if (x[i] > tol) {
1628 count++;
1629 }
1630 }
1631
1632 *new_elist = CC_SAFE_MALLOC (2*count, int);
1633 *new_x = CC_SAFE_MALLOC (count, double);
1634 if (!(*new_elist) || !(*new_x)) {
1635 fprintf (stderr, "out of memory in grab_nonzero_x\n");
1636 CC_IFFREE (*new_elist, int);
1637 CC_IFFREE (*new_x, double);
1638 return 1;
1639 }
1640
1641 for (i = 0, count = 0; i < ecount; i++) {
1642 if (x[i] > tol) {
1643 (*new_elist)[2*count] = elist[2*i];
1644 (*new_elist)[2*count+1] = elist[2*i+1];
1645 (*new_x)[count] = x[i];
1646 count++;
1647 }
1648 }
1649 *new_ecount = count;
1650 return 0;
1651 }
1652
1653 #ifdef CC_PROTOTYPE_ANSI
CCtsp_test_pure_comb(int ncount,CCtsp_lpcut_in * c,int * yes_no,int * handle)1654 int CCtsp_test_pure_comb (int ncount, CCtsp_lpcut_in *c, int *yes_no,
1655 int *handle)
1656 #else
1657 int CCtsp_test_pure_comb (ncount, c, yes_no, handle)
1658 int ncount;
1659 CCtsp_lpcut_in *c;
1660 int *yes_no;
1661 int *handle;
1662 #endif
1663 {
1664 int rval = 0;
1665 int i, marked, ihandle;
1666 int *marks = (int *) NULL;
1667
1668 *yes_no = 0;
1669 if (handle) *handle = -1;
1670
1671 if (c->cliquecount < 4 || c->cliquecount % 2 ||
1672 c->sense != 'G') {
1673 goto CLEANUP;
1674 }
1675
1676 rval = CCtsp_find_pure_handle (ncount, c, &ihandle);
1677 if (rval) {
1678 fprintf (stderr, "CCtsp_find_pure_handle failed\n");
1679 goto CLEANUP;
1680 }
1681 if (ihandle == -1) goto CLEANUP;
1682
1683 marks = CC_SAFE_MALLOC (ncount, int);
1684 if (!marks) {
1685 fprintf (stderr, "out of memory in CCtsp_test_pure_comb\n");
1686 rval = 1; goto CLEANUP;
1687 }
1688 CCtsp_mark_cut (c, marks, 0);
1689
1690 CCtsp_mark_clique (&c->cliques[ihandle], marks, 1);
1691 for (i = 0; i < c->cliquecount; i++) {
1692 if (i != ihandle) {
1693 CCtsp_is_clique_marked (&c->cliques[i], marks, 1, &marked);
1694 if (!marked) goto CLEANUP;
1695 CCtsp_is_clique_marked (&c->cliques[i], marks, 0, &marked);
1696 if (!marked) goto CLEANUP;
1697 }
1698 }
1699 CCtsp_mark_clique (&c->cliques[ihandle], marks, 0);
1700
1701 for (i = 0; i < c->cliquecount; i++) {
1702 if (i != ihandle) {
1703 CCtsp_is_clique_marked (&c->cliques[i], marks, 1, &marked);
1704 if (marked) goto CLEANUP;
1705 CCtsp_mark_clique (&c->cliques[i], marks, 1);
1706 }
1707 }
1708
1709 *yes_no = 1;
1710 if (handle) *handle = ihandle;
1711
1712 CLEANUP:
1713
1714 CC_IFFREE (marks, int);
1715 return rval;
1716 }
1717
1718 #ifdef CC_PROTOTYPE_ANSI
CCtsp_test_pseudocomb(int ncount,CCtsp_lpcut_in * c,int handle,int * yes_no)1719 int CCtsp_test_pseudocomb (int ncount, CCtsp_lpcut_in *c, int handle,
1720 int *yes_no)
1721 #else
1722 int CCtsp_test_pseudocomb (ncount, c, handle, yes_no)
1723 int ncount;
1724 CCtsp_lpcut_in *c;
1725 int handle;
1726 int *yes_no;
1727 #endif
1728 {
1729 int rval = 0;
1730 int i, k, marked;
1731 int *ends = (int *) NULL;
1732 int *marks = (int *) NULL;
1733
1734 *yes_no = 0;
1735 if (c->cliquecount <= 1 || c->cliquecount % 2 || c->sense != 'G') {
1736 printf ("bad cliquecount or sense in pseudocomb\n"); fflush (stdout);
1737 goto CLEANUP;
1738 }
1739
1740 marks = CC_SAFE_MALLOC (ncount, int);
1741 if (!marks) {
1742 fprintf (stderr, "out of memory in CCtsp_test_pseudocomb\n");
1743 rval = 1; goto CLEANUP;
1744 }
1745 CCtsp_mark_cut (c, marks, 0);
1746
1747 /* Teeth intersect H and are not contained in H */
1748
1749 CCtsp_mark_clique (&c->cliques[handle], marks, 1);
1750 for (i = 0; i < c->cliquecount; i++) {
1751 if (i != handle) {
1752 CCtsp_is_clique_marked (&c->cliques[i], marks, 1, &marked);
1753 if (!marked) goto CLEANUP;
1754 CCtsp_is_clique_marked (&c->cliques[i], marks, 0, &marked);
1755 if (!marked) goto CLEANUP;
1756 }
1757 }
1758 CCtsp_mark_clique (&c->cliques[0], marks, 0);
1759
1760 /* Big teeth are pairwise disjoint */
1761
1762 for (i = 0; i < c->cliquecount; i++) {
1763 if (i != handle) {
1764 CCtsp_clique_count (&c->cliques[i], &k);
1765 if (k >= 3) {
1766 CCtsp_is_clique_marked (&c->cliques[i], marks, 1, &marked);
1767 if (marked) goto CLEANUP;
1768 CCtsp_mark_clique (&c->cliques[i], marks, 1);
1769 }
1770 }
1771 }
1772 for (i = 1; i < c->cliquecount; i++) {
1773 CCtsp_mark_clique (&c->cliques[i], marks, 0);
1774 }
1775
1776 /* No small tooth is contained in a big tooth */
1777
1778 for (i = 0; i < c->cliquecount; i++) {
1779 if (i != handle) {
1780 CCtsp_clique_count (&c->cliques[i], &k);
1781 if (k >= 3) {
1782 CCtsp_mark_clique (&c->cliques[i], marks, i + 1);
1783 }
1784 }
1785 }
1786 for (i = 0; i < c->cliquecount; i++) {
1787 if (i != handle) {
1788 CCtsp_clique_count (&c->cliques[i], &k);
1789 if (k < 3) {
1790 rval = CCtsp_clique_to_array (&c->cliques[i], &ends, &k);
1791 if (rval) {
1792 fprintf (stderr, "CCtsp_clique_to_array failed\n");
1793 goto CLEANUP;
1794 }
1795 if (ends[0] != 0 && ends[0] == ends[1]) goto CLEANUP;
1796 CC_IFFREE (ends, int);
1797 }
1798 }
1799 }
1800
1801
1802 *yes_no = 1;
1803
1804
1805 CLEANUP:
1806
1807 CC_IFFREE (marks, int);
1808 CC_IFFREE (ends, int);
1809 return rval;
1810 }
1811
1812 #ifdef CC_PROTOTYPE_ANSI
CCtsp_test_teeth_disjoint(int ncount,CCtsp_lpcut_in * c,int handle,int * yes_no)1813 int CCtsp_test_teeth_disjoint (int ncount, CCtsp_lpcut_in *c, int handle,
1814 int *yes_no)
1815 #else
1816 int CCtsp_test_teeth_disjoint (ncount, c, handle, yes_no)
1817 int ncount;
1818 CCtsp_lpcut_in *c;
1819 int handle;
1820 int *yes_no;
1821 #endif
1822 {
1823 int rval = 0;
1824 int i, marked;
1825 int *marks = (int *) NULL;
1826
1827 *yes_no = 0;
1828
1829 marks = CC_SAFE_MALLOC (ncount, int);
1830 if (!marks) {
1831 fprintf (stderr, "out of memory in CCtsp_teeth_disjoint\n");
1832 rval = 1; goto CLEANUP;
1833 }
1834 CCtsp_mark_cut (c, marks, 0);
1835
1836 for (i = 0; i < c->cliquecount; i++) {
1837 if (i != handle) {
1838 CCtsp_is_clique_marked (&c->cliques[i], marks, 1, &marked);
1839 if (marked) goto CLEANUP;
1840 CCtsp_mark_clique (&c->cliques[i], marks, 1);
1841 }
1842 }
1843
1844 *yes_no = 1;
1845
1846 CLEANUP:
1847
1848 CC_IFFREE (marks, int);
1849 return rval;
1850 }
1851
1852 #ifdef CC_PROTOTYPE_ANSI
CCtsp_find_pure_handle(int ncount,CCtsp_lpcut_in * c,int * handle)1853 int CCtsp_find_pure_handle (int ncount, CCtsp_lpcut_in *c, int *handle)
1854 #else
1855 int CCtsp_find_pure_handle (ncount, c, handle)
1856 int ncount;
1857 CCtsp_lpcut_in *c;
1858 int *handle;
1859 #endif
1860 {
1861 int rval = 0;
1862 int *marks = (int *) NULL;
1863 int i, test;
1864
1865 *handle = -1;
1866 if (c->cliquecount % 2 || c->cliquecount < 4) goto CLEANUP;
1867
1868 marks = CC_SAFE_MALLOC (ncount, int);
1869 if (!marks) {
1870 fprintf (stderr, "out of memory in CCtsp_pure_find_handle\n");
1871 rval = 1; goto CLEANUP;
1872 }
1873 CCtsp_mark_cut (c, marks, 0);
1874
1875 CCtsp_mark_clique (&c->cliques[0], marks, 1);
1876 CCtsp_is_clique_marked (&c->cliques[1], marks, 1, &test);
1877 if (test) {
1878 CCtsp_is_clique_marked (&c->cliques[2], marks, 1, &test);
1879 if (test) {
1880 *handle = 0; goto CLEANUP;
1881 } else {
1882 *handle = 1; goto CLEANUP;
1883 }
1884 } else {
1885 for (i = 2; i < c->cliquecount; i++) {
1886 CCtsp_is_clique_marked (&c->cliques[i], marks, 1, &test);
1887 if (test) {
1888 *handle = i;
1889 goto CLEANUP;
1890 }
1891 }
1892 }
1893
1894 CLEANUP:
1895
1896 CC_IFFREE (marks, int);
1897 return rval;
1898 }
1899