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 /* SOME ROUTINES FOR HANDLING CLIQUES AND CUTS */
19 /* */
20 /* TSP CODE */
21 /* */
22 /* */
23 /* Written by: Applegate, Bixby, Chvatal, and Cook */
24 /* Date: July 15, 1997 */
25 /* */
26 /* */
27 /* EXPORTED FUNCTIONS: */
28 /* */
29 /* void CCtsp_mark_clique (CCtsp_lpclique *c, int *marks, int marker) */
30 /* MARKS the nodes in clique c */
31 /* -marks an array of length at least ncount */
32 /* -marker an int that is used to mark the clique entries in marks */
33 /* */
34 /* void CCtsp_mark_domino (CCtsp_lpdomino *c, int *marks, int marker) */
35 /* MARKS the nodes in domino c */
36 /* */
37 /* void CCtsp_mark_clique_and_neighbors (CCtsp_lpgraph *g, */
38 /* CCtsp_lpclique *c, int *marks, int marker) */
39 /* MARKS the clique and the neighbors of the clique */
40 /* */
41 /* void CCtsp_mark_domino_and_neighbors (CCtsp_lpgraph *g, */
42 /* CCtsp_lpdomino *c, int *marks, int marker) */
43 /* MARKS the domino and the neighbors of the domino */
44 /* */
45 /* void CCtsp_mark_clique_and_neighbors_double (CCtsp_lpgraph *g, */
46 /* CCtsp_lpclique *c, double *marks, double marker) */
47 /* MARKS the clique and the neighbors of the clique in a double array. */
48 /* */
49 /* void CCtsp_mark_cut (CCtsp_lpcut_in *c, int *marks, int marker) */
50 /* MARKS the nodes in the cut. */
51 /* */
52 /* void CCtsp_mark_cut_and_neighbors (CCtsp_lpgraph *g, */
53 /* CCtsp_lpcut_in *c, int *marks, int marker) */
54 /* MARKS the nodes in the cut and their neighbors */
55 /* */
56 /* void CCtsp_is_clique_marked (CCtsp_lpclique *c, int *marks, */
57 /* int marker, int *yes_no) */
58 /* CHECKS if a node in the clique is marked with the value marker. */
59 /* -yesno returns the result (1 is yes and 0 is no) */
60 /* */
61 /* void CCtsp_clique_count (CCtsp_lpclique *c, int *count) */
62 /* COUNTS the nodes in the clique. */
63 /* */
64 /* void CCtsp_clique_marked_count (CCtsp_lpclique *c, int *marks, */
65 /* int marker, int *count) */
66 /* COUNTS the nodes in the clique have mark equal to marker. */
67 /* */
68 /* int CCtsp_clique_to_array (CCtsp_lpclique *c, int **ar, int *count) */
69 /* EXPANDS a clique into an array of integers. */
70 /* */
71 /* int CCtsp_clique_delta (CCtsp_lpgraph *g, double *x, */
72 /* CCtsp_lpclique *c, double *delta) */
73 /* COMPUTES the sum of the x-edges in the coboundary of the clique, */
74 /* that is, x(delta(c)). */
75 /* -delta returns the sum */
76 /* */
77 /* int CCtsp_segment_to_subtour (CCtsp_lpcut_in **cut, int a, int b, */
78 /* int ncount) */
79 /* BUILDS a subtour CCtsp_lpcut_in from an the segment. */
80 /* -cut will return the subtour (it will be allocated). */
81 /* */
82 /* int CCtsp_array_to_subtour (CCtsp_lpcut_in **cut, int *ar, */
83 /* int acount, int ncount) */
84 /* BUILDS a subtour CCtsp_lpcut_in from an array. */
85 /* -cut will return the subtour (it will be allocated). */
86 /* */
87 /* void CCtsp_init_lpcut_in (CCtsp_lpcut_in *c) */
88 /* INITIALIZE the fields of the CCtsp_lpcut_in structure */
89 /* */
90 /* void CCtsp_init_lpcut (CCtsp_lpcut *c) */
91 /* INITIALIZE the fields of the CCtsp_lpcut structure */
92 /* */
93 /* void CCtsp_init_lpclique (CCtsp_lpclique *c) */
94 /* INITIALIZE the fields of the CCtsp_lpclique structure */
95 /* */
96 /* void CCtsp_init_lpdomino (CCtsp_lpdomino *c) */
97 /* INITIALIZE the fields of the CCtsp_lpdomino structure */
98 /* */
99 /* int CCtsp_array_to_lpclique (int *ar, int acount, */
100 /* CCtsp_lpclique *cliq) */
101 /* BUILDS an CCtsp_lpclique represented the nodes in an array. */
102 /* -ar is an array of node numbers */
103 /* -acount is the length of ar */
104 /* -cliq's segcount and nodes will be filled with the compressed */
105 /* version of the nodes in ar */
106 /* */
107 /* int CCtsp_seglist_to_lpclique (int nseg, int *list, */
108 /* CCtsp_lpclique *cliq) */
109 /* BUILDS the CCtsp_lpclique represented by a list of segments (it */
110 /* will sort the segments before it puts them into the CCtsp_segment */
111 /* structures) */
112 /* -list is an array of segments in lo-hi-lo-hi format */
113 /* -clig's segcount and nodes will be filled in (nodes will be */
114 /* allocated) */
115 /* */
116 /* int CCtsp_shrunk_set_to_lpclique (int cnt, int *set, int *wset, */
117 /* CC_SRKexpinfo *expand, CCtsp_lpclique *cliq) */
118 /* BUILDS an lpclique by exanding a shrunk set of nodes. */
119 /* -cnt is the number of nodes in set */
120 /* -set is an array of the nodes */
121 /* -wset is a working array, it should be ncount long and the values */
122 /* may be changed by this function */
123 /* -expand contains the info to expand the nodes */
124 /* -cliq returns the clique */
125 /* */
126 /* int CCtsp_add_nodes_to_lpclique (CCtsp_lpclique *cin, */
127 /* CCtsp_lpclique *cout, int addcount, int *adda) */
128 /* ADDS nodes to clique cin, and returns the new clique in cout */
129 /* -addcount has number of nodes to be added. */
130 /* -adda has the indices of the addcount nodes to be added. */
131 /* */
132 /* int CCtsp_delete_nodes_from_lpclique (CCtsp_lpclique *cin, */
133 /* CCtsp_lpclique *cout, int delcount, int *del) */
134 /* DELETES nodes from clique cin, and returns the new clique in cout */
135 /* -delcount has number of nodes to be deleted. */
136 /* -del has the indices of the delcount nodes to be deleted. */
137 /* */
138 /* void CCtsp_print_lpcut_in (CCtsp_lpcut_in *c) */
139 /* PRINTS the CCtsp_lpcut_in */
140 /* */
141 /* void CCtsp_print_lpclique (CCtsp_lpclique *c) */
142 /* PRINTS the segments in the clique to stdout. */
143 /* */
144 /* void CCtsp_print_lpdomino (CCtsp_lpdomino *d) */
145 /* PRINTS the cliques of the domino. */
146 /* */
147 /* int CCtsp_copy_lpcut_in (CCtsp_lpcut_in *c, CCtsp_lpcut_in *new) */
148 /* COPIES an CCtsp_lpcut_in */
149 /* -c is a pointer to an CCtsp_lpcut_in */
150 /* -new returns the copied CCtsp_lpcut_in */
151 /* */
152 /* int CCtsp_lpcut_to_lpcut_in (CCtsp_lpcuts *cuts, CCtsp_lpcut *c, */
153 /* CCtsp_lpcut_in *new) */
154 /* COPIES an CCtsp_lpcut to an CCtsp_lpcut_in */
155 /* -cuts is a pointer to the structure holding the set of cuts */
156 /* -c is the cut to be copied */
157 /* -new returns the copied cut */
158 /* */
159 /* void CCtsp_lpclique_compare (CCtsp_lpclique *a, CCtsp_lpclique *b, */
160 /* int *diff) */
161 /* COMPARES two CCtsp_lpcliques. */
162 /* -diff is set to 1 if they differ and 0 if they are the same */
163 /* NOTES: Assumes segments are ordered. */
164 /* */
165 /* int CCtsp_copy_lpclique (CCtsp_lpclique *c, CCtsp_lpclique *new) */
166 /* COPIES an CCtsp_lpclique */
167 /* -c is a pointer to an CCtsp_lpclique */
168 /* -new returns the copied clique */
169 /* */
170 /* int CCtsp_copy_lpdomino (CCtsp_lpdomino *c, CCtsp_lpdomino *new) */
171 /* COPIES an CCtsp_lpdomino */
172 /* */
173 /* int CCtsp_create_lpcliques (CCtsp_lpcut_in *c, int cliquecount) */
174 /* ALLOCATES and INITIALIZES the cliques space for c. */
175 /* */
176 /* int CCtsp_max_node (CCtsp_lpcut_in *c) */
177 /* MISSING */
178 /* */
179 /* int CCtsp_build_dp_cut (CCtsp_lpcut_in **cut, int ndomino, int *Acount, */
180 /* int **A, int *Bcount, int **B, int handlecount, int *handle) */
181 /* BUILD the lpcut_in for a domino parity cut. */
182 /* -ndomino number of dominos */
183 /* -Acount[i] specifies the number of nodes in one side of ith domino */
184 /* -Bcount[i] specifies the number of nodes in other side of domino */
185 /* -A[i] is an array of the nodes in one side of ith domino */
186 /* -B[i] is an array of the nodes in other side of ith domino */
187 /* -handlecount is number of nodes in the handle */
188 /* -handle is an array of the nodes in the handle */
189 /* */
190 /****************************************************************************/
191
192 #include "machdefs.h"
193 #include "util.h"
194 #include "macrorus.h"
195 #include "tsp.h"
196 #include "cut.h"
197
198 static int build_dominos (CCtsp_lpcut_in *c, int ndomino, int *Acount,
199 int **A, int *Bcount, int **B);
200
CCtsp_mark_clique(CCtsp_lpclique * c,int * marks,int marker)201 void CCtsp_mark_clique (CCtsp_lpclique *c, int *marks, int marker)
202 {
203 int j, tmp;
204
205 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
206 marks[j] = marker;
207 }
208 }
209
CCtsp_mark_domino(CCtsp_lpdomino * c,int * marks,int marker)210 void CCtsp_mark_domino (CCtsp_lpdomino *c, int *marks, int marker)
211 {
212 CCtsp_mark_clique (&(c->sets[0]), marks, marker);
213 CCtsp_mark_clique (&(c->sets[1]), marks, marker);
214 }
215
CCtsp_mark_clique_and_neighbors(CCtsp_lpgraph * g,CCtsp_lpclique * c,int * marks,int marker)216 void CCtsp_mark_clique_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpclique *c,
217 int *marks, int marker)
218 {
219 int j, k, tmp;
220
221 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
222 marks[j] = marker;
223 for (k = 0; k < g->nodes[j].deg; k++) {
224 marks[g->nodes[j].adj[k].to] = marker;
225 }
226 }
227 }
228
CCtsp_mark_domino_and_neighbors(CCtsp_lpgraph * g,CCtsp_lpdomino * c,int * marks,int marker)229 void CCtsp_mark_domino_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpdomino *c,
230 int *marks, int marker)
231 {
232 CCtsp_mark_clique_and_neighbors (g, &(c->sets[0]), marks, marker);
233 CCtsp_mark_clique_and_neighbors (g, &(c->sets[1]), marks, marker);
234 }
235
CCtsp_mark_cut(CCtsp_lpcut_in * c,int * marks,int marker)236 void CCtsp_mark_cut (CCtsp_lpcut_in *c, int *marks, int marker)
237 {
238 int i;
239
240 for (i = 0; i < c->cliquecount; i++) {
241 CCtsp_mark_clique (&(c->cliques[i]), marks, marker);
242 }
243 for (i = 0; i < c->dominocount; i++) {
244 CCtsp_mark_domino (&(c->dominos[i]), marks, marker);
245 }
246 }
247
CCtsp_mark_cut_and_neighbors(CCtsp_lpgraph * g,CCtsp_lpcut_in * c,int * marks,int marker)248 void CCtsp_mark_cut_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpcut_in *c,
249 int *marks, int marker)
250 {
251 int i;
252
253 for (i = 0; i < c->cliquecount; i++) {
254 CCtsp_mark_clique_and_neighbors (g, &(c->cliques[i]), marks, marker);
255 }
256 for (i = 0; i < c->dominocount; i++) {
257 CCtsp_mark_domino_and_neighbors (g, &(c->dominos[i]), marks, marker);
258 }
259 }
260
CCtsp_mark_clique_and_neighbors_double(CCtsp_lpgraph * g,CCtsp_lpclique * c,double * marks,double marker)261 void CCtsp_mark_clique_and_neighbors_double (CCtsp_lpgraph *g,
262 CCtsp_lpclique *c, double *marks, double marker)
263 {
264 int j, k, tmp;
265
266 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
267 marks[j] = marker;
268 for (k = 0; k < g->nodes[j].deg; k++) {
269 marks[g->nodes[j].adj[k].to] = marker;
270 }
271 }
272 }
273
CCtsp_is_clique_marked(CCtsp_lpclique * c,int * marks,int marker,int * yes_no)274 void CCtsp_is_clique_marked (CCtsp_lpclique *c, int *marks, int marker,
275 int *yes_no)
276 {
277 int j, tmp;
278
279 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
280 if (marks[j] == marker) {
281 *yes_no = 1;
282 return;
283 }
284 }
285 *yes_no = 0;
286 }
287
CCtsp_clique_count(CCtsp_lpclique * c,int * count)288 void CCtsp_clique_count (CCtsp_lpclique *c, int *count)
289 {
290 int i;
291 CCtsp_segment *nodes = c->nodes;
292
293 *count = 0;
294 for (i = 0; i < c->segcount; i++) {
295 (*count) += (nodes[i].hi - nodes[i].lo + 1);
296 }
297 }
298
CCtsp_clique_marked_count(CCtsp_lpclique * c,int * marks,int marker,int * count)299 void CCtsp_clique_marked_count (CCtsp_lpclique *c, int *marks, int marker,
300 int *count)
301 {
302 int j, tmp;
303
304 *count = 0;
305 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
306 if (marks[j] == marker) {
307 (*count)++;
308 }
309 }
310 }
311
CCtsp_clique_to_array(CCtsp_lpclique * c,int ** ar,int * count)312 int CCtsp_clique_to_array (CCtsp_lpclique *c, int **ar, int *count)
313 {
314 int rval = 0;
315 int j, tmp;
316 int k = 0;
317
318 *ar = (int *) NULL;
319
320 CCtsp_clique_count (c, count);
321 if (count) {
322 *ar = CC_SAFE_MALLOC (*count, int);
323 if (!(*ar)) {
324 fprintf (stderr, "out of memory in CCtsp_clique_to_array\n");
325 rval = 1; goto CLEANUP;
326 }
327 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
328 (*ar)[k++] = j;
329 }
330 }
331
332 CLEANUP:
333
334 return rval;
335 }
336
CCtsp_clique_delta(CCtsp_lpgraph * g,double * x,CCtsp_lpclique * c,double * delta)337 int CCtsp_clique_delta (CCtsp_lpgraph *g, double *x, CCtsp_lpclique *c,
338 double *delta)
339 {
340 int rval = 0;
341 int j, k, tmp;
342 int *marks = (int *) NULL;
343 CCtsp_lpnode *n;
344
345 *delta = 0.0;
346
347 marks = CC_SAFE_MALLOC (g->ncount, int);
348 if (!marks) {
349 fprintf (stderr, "out of memory in CCtsp_clique_delta\n");
350 rval = 1; goto CLEANUP;
351 }
352
353 CCtsp_mark_clique_and_neighbors (g, c, marks, 0);
354 CCtsp_mark_clique (c, marks, 1);
355
356 CC_FOREACH_NODE_IN_CLIQUE (j, *c, tmp) {
357 n = &g->nodes[j];
358 for (k = 0; k < n->deg; k++) {
359 if (!marks[n->adj[k].to]) {
360 (*delta) += x[n->adj[k].edge];
361 }
362 }
363 }
364
365 CLEANUP:
366
367 CC_IFFREE (marks, int);
368 return rval;
369 }
370
CCtsp_init_lpcut_in(CCtsp_lpcut_in * c)371 void CCtsp_init_lpcut_in (CCtsp_lpcut_in *c)
372 {
373 if (c) {
374 c->cliquecount = 0;
375 c->dominocount = 0;
376 c->rhs = 0;
377 c->sense = 'X';
378 c->branch = 0;
379 c->cliques = (CCtsp_lpclique *) NULL;
380 c->dominos = (CCtsp_lpdomino *) NULL;
381 c->next = (CCtsp_lpcut_in *) NULL;
382 c->prev = (CCtsp_lpcut_in *) NULL;
383 CCtsp_init_skeleton (&c->skel);
384 }
385 }
386
CCtsp_init_lpcut(CCtsp_lpcut * c)387 void CCtsp_init_lpcut (CCtsp_lpcut *c)
388 {
389 if (c) {
390 c->cliquecount = 0;
391 c->dominocount = 0;
392 c->modcount = 0;
393 c->age = 0;
394 c->rhs = 0;
395 c->sense = 'X';
396 c->branch = 0;
397 c->cliques = (int *) NULL;
398 c->dominos = (int *) NULL;
399 c->mods = (CCtsp_sparser *) NULL;
400 CCtsp_init_skeleton (&c->skel);
401 }
402 }
403
CCtsp_copy_lpcut_in(CCtsp_lpcut_in * c,CCtsp_lpcut_in * new)404 int CCtsp_copy_lpcut_in (CCtsp_lpcut_in *c, CCtsp_lpcut_in *new)
405 {
406 int rval = 0;
407 int i;
408
409 CCtsp_init_lpcut_in (new);
410
411 new->cliquecount = c->cliquecount;
412 new->dominocount = c->dominocount;
413 new->rhs = c->rhs;
414 new->sense = c->sense;
415
416 if (c->cliquecount) {
417 new->cliques = CC_SAFE_MALLOC (c->cliquecount, CCtsp_lpclique);
418 CCcheck_NULL (new->cliques, "out of memory in CCtsp_lpcut_in");
419 for (i = 0; i < c->cliquecount; i++) {
420 rval = CCtsp_copy_lpclique (&c->cliques[i], &new->cliques[i]);
421 CCcheck_rval (rval, "CCtsp_copy_lpclique failed");
422 }
423 }
424
425 if (c->dominocount) {
426 new->dominos = CC_SAFE_MALLOC (c->dominocount, CCtsp_lpdomino);
427 CCcheck_NULL (new->dominos, "out of memory in CCtsp_lpcut_in");
428 for (i = 0; i < c->dominocount; i++) {
429 rval = CCtsp_copy_lpdomino (&c->dominos[i], &new->dominos[i]);
430 CCcheck_rval (rval, "CCtsp_copy_lpdomino failed");
431 }
432 }
433
434 rval = CCtsp_copy_skeleton (&c->skel, &new->skel);
435 CCcheck_rval (rval, "CCtsp_copy_skeleton failed");
436
437 CLEANUP:
438
439 if (rval) {
440 CCtsp_free_lpcut_in (new);
441 }
442 return rval;
443 }
444
CCtsp_segment_to_subtour(CCtsp_lpcut_in ** cut,int a,int b,int ncount)445 int CCtsp_segment_to_subtour (CCtsp_lpcut_in **cut, int a, int b, int ncount)
446 {
447 int rval = 0;
448 int list[2];
449 int t;
450 CCtsp_lpcut_in *c = (CCtsp_lpcut_in *) NULL;
451
452 *cut = (CCtsp_lpcut_in *) NULL;
453 if (a > b) CC_SWAP (a, b, t);
454
455 c = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
456 CCcheck_NULL (c, "out of memory in CCtsp_seqment_to_subtour");
457 CCtsp_init_lpcut_in (c);
458
459 c->cliquecount = 1;
460 c->cliques = CC_SAFE_MALLOC (1, CCtsp_lpclique);
461 if (!c->cliques) {
462 fprintf (stderr, "out of memory in CCtsp_segment_to_subtour\n");
463 rval = 1; goto CLEANUP;
464 }
465
466 list[0] = a;
467 list[1] = b;
468 rval = CCtsp_seglist_to_lpclique (1, list, &(c->cliques[0]));
469 if (rval) {
470 goto CLEANUP;
471 }
472 c->rhs = 2;
473 c->sense = 'G';
474 c->branch = 0;
475
476 rval = CCtsp_construct_skeleton (c, ncount);
477 if (rval) {
478 fprintf (stderr, "CCtsp_construct_skeleton failed\n");
479 goto CLEANUP;
480 }
481
482 *cut = c;
483 rval = 0;
484
485 CLEANUP:
486
487 if (rval) {
488 if (c) {
489 CCtsp_free_lpcut_in (c);
490 CC_FREE (c, CCtsp_lpcut_in);
491 }
492 }
493 return rval;
494 }
495
CCtsp_array_to_subtour(CCtsp_lpcut_in ** cut,int * ar,int acount,int ncount)496 int CCtsp_array_to_subtour (CCtsp_lpcut_in **cut, int *ar, int acount,
497 int ncount)
498 {
499 int rval = 0;
500 CCtsp_lpcut_in *c = (CCtsp_lpcut_in *) NULL;
501
502 *cut = (CCtsp_lpcut_in *) NULL;
503
504 c = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
505 CCcheck_NULL (c, "out of memory in CCtsp_array_to_subtour");
506 CCtsp_init_lpcut_in (c);
507
508 c->cliquecount = 1;
509 c->cliques = CC_SAFE_MALLOC (1, CCtsp_lpclique);
510 if (!c->cliques) {
511 fprintf (stderr, "out of memory in CCtsp_array_to_subtour\n");
512 rval = 1; goto CLEANUP;
513 }
514
515 rval = CCtsp_array_to_lpclique (ar, acount, &(c->cliques[0]));
516 if (rval) {
517 goto CLEANUP;
518 }
519 c->rhs = 2;
520 c->sense = 'G';
521 c->branch = 0;
522
523 rval = CCtsp_construct_skeleton (c, ncount);
524 if (rval) {
525 fprintf (stderr, "CCtsp_construct_skeleton failed\n");
526 goto CLEANUP;
527 }
528
529 *cut = c;
530 rval = 0;
531
532 CLEANUP:
533
534 if (rval) {
535 if (c) {
536 CCtsp_free_lpcut_in (c);
537 CC_FREE (c, CCtsp_lpcut_in);
538 }
539 }
540 return rval;
541 }
542
CCtsp_init_lpclique(CCtsp_lpclique * c)543 void CCtsp_init_lpclique (CCtsp_lpclique *c)
544 {
545 if (c) {
546 c->segcount = 0;
547 c->nodes = (CCtsp_segment *) NULL;
548 c->hashnext = 0;
549 c->refcount = 0;
550 }
551 }
552
CCtsp_init_lpdomino(CCtsp_lpdomino * c)553 void CCtsp_init_lpdomino (CCtsp_lpdomino *c)
554 {
555 if (c) {
556 CCtsp_init_lpclique (&(c->sets[0]));
557 CCtsp_init_lpclique (&(c->sets[1]));
558 c->hashnext = 0;
559 c->refcount = 0;
560 }
561 }
562
CCtsp_array_to_lpclique(int * ar,int acount,CCtsp_lpclique * cliq)563 int CCtsp_array_to_lpclique (int *ar, int acount, CCtsp_lpclique *cliq)
564 {
565 int i, nseg;
566
567 /* Function will alter the order on the array */
568
569 CCutil_int_array_quicksort (ar, acount);
570 nseg = 0;
571 i = 0;
572 while (i < acount) {
573 while (i < (acount - 1) && ar[i + 1] == (ar[i] + 1))
574 i++;
575 i++;
576 nseg++;
577 }
578
579 cliq->nodes = CC_SAFE_MALLOC (nseg, CCtsp_segment);
580 if (!cliq->nodes) {
581 fprintf (stderr, "out of memory in CCtsp_array_to_lpclique\n");
582 return 1;
583 }
584 cliq->segcount = nseg;
585
586 nseg = 0;
587 i = 0;
588 while (i < acount) {
589 cliq->nodes[nseg].lo = ar[i];
590 while (i < (acount - 1) && ar[i + 1] == (ar[i] + 1))
591 i++;
592 cliq->nodes[nseg].hi = ar[i++];
593 nseg++;
594 }
595 return 0;
596 }
597
CCtsp_seglist_to_lpclique(int nseg,int * list,CCtsp_lpclique * cliq)598 int CCtsp_seglist_to_lpclique (int nseg, int *list, CCtsp_lpclique *cliq)
599 {
600 int i;
601 int *perm = (int *) NULL;
602 int *len = (int *) NULL;
603 int rval = 0;
604
605 perm = CC_SAFE_MALLOC (nseg, int);
606 len = CC_SAFE_MALLOC (nseg, int);
607 if (!perm || !len) {
608 fprintf (stderr, "out of memory in CCtsp_seglist_to_lpclique\n");
609 rval = 1; goto CLEANUP;
610 }
611 for (i = 0; i < nseg; i++) {
612 perm[i] = i;
613 len[i] = list[2*i];
614 }
615 CCutil_int_perm_quicksort (perm, len, nseg);
616
617 cliq->nodes = CC_SAFE_MALLOC (nseg, CCtsp_segment);
618 if (!cliq->nodes) {
619 fprintf (stderr, "out of memory in CCtsp_seglist_to_lpclique\n");
620 rval = 1; goto CLEANUP;
621 }
622 cliq->segcount = nseg;
623
624 for (i = 0; i < nseg; i++) {
625 cliq->nodes[i].lo = list[2*perm[i]];
626 cliq->nodes[i].hi = list[2*perm[i]+1];
627 }
628
629 nseg = 0;
630
631 CLEANUP:
632
633 CC_IFFREE (perm, int);
634 CC_IFFREE (len, int);
635
636 return rval;
637 }
638
CCtsp_shrunk_set_to_lpclique(int cnt,int * set,int * wset,CC_SRKexpinfo * expand,CCtsp_lpclique * cliq)639 int CCtsp_shrunk_set_to_lpclique (int cnt, int *set, int *wset,
640 CC_SRKexpinfo *expand, CCtsp_lpclique *cliq)
641 {
642 int rval = 0;
643 int wcount = 0;
644 int i, j;
645
646 CCtsp_init_lpclique (cliq);
647
648 for (i = 0; i < cnt; i++) {
649 for (j = expand->memindex[set[i]];
650 j < expand->memindex[set[i]+1]; j++) {
651 wset[wcount++] = expand->members[j];
652 }
653 }
654 rval = CCtsp_array_to_lpclique (wset, wcount, cliq);
655 if (rval) {
656 fprintf (stderr, "CCtsp_array_to_lpclique failed\n"); goto CLEANUP;
657 }
658
659 CLEANUP:
660
661 return rval;
662 }
663
CCtsp_add_nodes_to_lpclique(CCtsp_lpclique * cin,CCtsp_lpclique * cout,int addcount,int * adda)664 int CCtsp_add_nodes_to_lpclique (CCtsp_lpclique *cin, CCtsp_lpclique *cout,
665 int addcount, int *adda)
666 {
667 int count = 0;
668 int rval = 0;
669 int *ar = (int *) NULL;
670 int i, tmp;
671 int maxn = 0;
672 char *marks = (char *) NULL;
673
674 if (addcount == 0) {
675 return CCtsp_copy_lpclique (cin, cout);
676 }
677
678 CCtsp_init_lpclique (cout);
679
680 for (i = 0; i < cin->segcount; i++) {
681 if (cin->nodes[i].hi > maxn) maxn = cin->nodes[i].hi;
682 }
683 for (i = 0; i < addcount; i++) {
684 if (adda[i] > maxn) maxn = adda[i];
685 }
686
687 marks = CC_SAFE_MALLOC (maxn + 1, char);
688 ar = CC_SAFE_MALLOC (maxn + 1, int);
689 if (!marks || !ar) {
690 fprintf (stderr, "out of memory in CCtsp_add_nodes_to_lpclique\n");
691 rval = 1; goto CLEANUP;
692 }
693 for (i = 0; i < addcount; i++) {
694 marks[adda[i]] = 0;
695 }
696
697 CC_FOREACH_NODE_IN_CLIQUE (i, *cin, tmp) {
698 ar[count++] = i;
699 marks[i] = 1;
700 }
701
702 for (i = 0; i < addcount; i++) {
703 if (marks[adda[i]] == 0) {
704 ar[count++] = adda[i];
705 marks[adda[i]] = 1;
706 }
707 }
708 rval = CCtsp_array_to_lpclique (ar, count, cout);
709 if (rval) {
710 fprintf (stderr, "CCtsp_array_to_lpclique failed\n"); goto CLEANUP;
711 }
712
713 CLEANUP:
714
715 CC_IFFREE (ar, int);
716 CC_IFFREE (marks, char);
717 return rval;
718 }
719
CCtsp_delete_nodes_from_lpclique(CCtsp_lpclique * cin,CCtsp_lpclique * cout,int delcount,int * del)720 int CCtsp_delete_nodes_from_lpclique (CCtsp_lpclique *cin,
721 CCtsp_lpclique *cout, int delcount, int *del)
722 {
723 int count = 0;
724 int rval = 0;
725 int *ar = (int *) NULL;
726 int i, tmp;
727 char *marks = (char *) NULL;
728 int maxn = 0;
729
730 CCtsp_init_lpclique (cout);
731
732 for (i = 0; i < cin->segcount; i++) {
733 if (cin->nodes[i].hi > maxn) maxn = cin->nodes[i].hi;
734 }
735 for (i = 0; i < delcount; i++) {
736 if (del[i] > maxn) maxn = del[i];
737 }
738 marks = CC_SAFE_MALLOC (maxn + 1, char);
739 ar = CC_SAFE_MALLOC (maxn + 1, int);
740 if (!marks || !ar) {
741 fprintf (stderr, "out of memory in CCtsp_delete_nodes_from_lpclique\n");
742 rval = 1; goto CLEANUP;
743 }
744 CC_FOREACH_NODE_IN_CLIQUE (i, *cin, tmp) {
745 marks[i] = 0;
746 }
747 for (i = 0; i < delcount; i++) {
748 marks[del[i]] = 1;
749 }
750
751 CC_FOREACH_NODE_IN_CLIQUE (i, *cin, tmp) {
752 if (!marks[i]) {
753 ar[count++] = i;
754 }
755 }
756 rval = CCtsp_array_to_lpclique (ar, count, cout);
757 if (rval) {
758 fprintf (stderr, "CCtsp_array_to_lpclique failed\n"); goto CLEANUP;
759 }
760
761 CLEANUP:
762
763 CC_IFFREE (ar, int);
764 CC_IFFREE (marks, char);
765 return rval;
766 }
767
CCtsp_print_lpcut_in(CCtsp_lpcut_in * c)768 void CCtsp_print_lpcut_in (CCtsp_lpcut_in *c)
769 {
770 int i;
771 /*
772 int j, k;
773
774
775 printf ("%d %d\n", c->cliquecount, c->rhs);
776 for (i = 0; i < c->cliquecount; i++) {
777 for (j = 0; j < c->cliques[i].segcount; j++) {
778 for (k = c->cliques[i].nodes[j].lo;
779 k <= c->cliques[i].nodes[j].hi; k++) {
780 printf ("%d ", k);
781 }
782 }
783 printf ("-1\n");
784 }
785 printf ("\n");
786 */
787
788 if (c->dominocount == 0) {
789 if (c->cliquecount == 1) {
790 printf ("Subtour\n");
791 printf (" ");
792 CCtsp_print_lpclique (&(c->cliques[0]));
793 } else {
794 printf ("Comb, Clique Tree or Wild Thing (rhs %d)\n", c->rhs);
795 for (i = 0; i < c->cliquecount; i++) {
796 printf (" ");
797 CCtsp_print_lpclique (&(c->cliques[i]));
798 }
799 }
800 } else {
801 if (c->cliquecount != 1) {
802 printf ("Bad Domino, more than one handle\n");
803 } else {
804 printf ("Domino Inequality\n");
805 printf (" ");
806 CCtsp_print_lpclique (&(c->cliques[0]));
807 for (i = 0; i < c->dominocount; i++) {
808 printf (" ");
809 CCtsp_print_lpdomino (&(c->dominos[i]));
810 }
811 }
812 }
813 printf ("\n"); fflush (stdout);
814 }
815
CCtsp_print_lpclique(CCtsp_lpclique * c)816 void CCtsp_print_lpclique (CCtsp_lpclique *c)
817 {
818 int i;
819
820 if (c->segcount == 0) {
821 printf ("Empty Clique\n"); fflush (stdout);
822 } else {
823 for (i = 0; i < c->segcount; i++) {
824 printf ("%d->%d ", c->nodes[i].lo, c->nodes[i].hi);
825 }
826 printf ("\n"); fflush (stdout);
827 }
828 }
829
CCtsp_print_lpdomino(CCtsp_lpdomino * d)830 void CCtsp_print_lpdomino (CCtsp_lpdomino *d)
831 {
832 int i, k;
833 CCtsp_lpclique *c;
834
835 for (k = 0; k < 2; k++) {
836 c = &(d->sets[k]);
837 if (c->segcount == 0) {
838 printf ("Empty Clique "); fflush (stdout);
839 } else {
840 for (i = 0; i < c->segcount; i++) {
841 printf ("%d->%d ", c->nodes[i].lo, c->nodes[i].hi);
842 }
843 }
844 if (k == 0) printf (" | ");
845 }
846 printf ("\n"); fflush (stdout);
847 }
848
CCtsp_lpcut_to_lpcut_in(CCtsp_lpcuts * cuts,CCtsp_lpcut * c,CCtsp_lpcut_in * new)849 int CCtsp_lpcut_to_lpcut_in (CCtsp_lpcuts *cuts, CCtsp_lpcut *c,
850 CCtsp_lpcut_in *new)
851 {
852 int i, k;
853 CCtsp_lpclique *cl;
854 CCtsp_lpdomino *dom;
855 int rval = 0;
856
857 /*
858 if (c->dominocount != 0) {
859 printf ("Yipes: %d\n", c->dominocount);
860 fflush (stdout);
861 exit (1);
862 }
863 */
864
865 CCtsp_init_lpcut_in (new);
866
867 new->cliquecount = c->cliquecount;
868 new->dominocount = c->dominocount;
869 new->rhs = c->rhs;
870 new->sense = c->sense;
871 new->branch = c->branch;
872 new->next = (CCtsp_lpcut_in *) NULL;
873 new->prev = (CCtsp_lpcut_in *) NULL;
874
875 new->cliques = CC_SAFE_MALLOC (c->cliquecount, CCtsp_lpclique);
876 CCcheck_NULL (new->cliques, "out of memory in CCtsp_lpcut_to_lpcut_in");
877
878 for (i = 0; i < c->cliquecount; i++) {
879 cl = &(cuts->cliques[c->cliques[i]]);
880 rval = CCtsp_copy_lpclique (cl, &new->cliques[i]);
881 if (rval) {
882 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
883 for (k = 0; k < i; k++) {
884 CC_FREE (new->cliques[k].nodes, CCtsp_segment);
885 }
886 CC_FREE (new->cliques, CCtsp_lpclique);
887 goto CLEANUP;
888 }
889 }
890
891 if (new->dominocount > 0) {
892 new->dominos = CC_SAFE_MALLOC (c->dominocount, CCtsp_lpdomino);
893 CCcheck_NULL (new->dominos,
894 "out of memory in CCtsp_lpcut_to_lpcut_in");
895
896 for (i = 0; i < c->dominocount; i++) {
897 dom = &(cuts->dominos[c->dominos[i]]);
898 rval = CCtsp_copy_lpdomino (dom, &new->dominos[i]);
899 if (rval) {
900 fprintf (stderr, "CCtsp_copy_lpdomino failed\n");
901 for (k = 0; k < i; k++) {
902 CCtsp_free_lpdomino (&new->dominos[k]);
903 }
904 CC_FREE (new->dominos, CCtsp_lpdomino);
905 goto CLEANUP;
906 }
907 }
908 }
909
910 rval = CCtsp_copy_skeleton (&c->skel, &new->skel);
911 if (rval) {
912 fprintf (stderr, "CCtsp_copy_skeleton failed\n");
913 CCtsp_free_lpcut_in (new);
914 goto CLEANUP;
915 }
916
917 CLEANUP:
918
919 return rval;
920 }
921
CCtsp_copy_lpclique(CCtsp_lpclique * c,CCtsp_lpclique * new)922 int CCtsp_copy_lpclique (CCtsp_lpclique *c, CCtsp_lpclique *new)
923 {
924 int k;
925 CCtsp_segment *s = (CCtsp_segment *) NULL;
926
927 CCtsp_init_lpclique (new);
928 if (c->segcount) {
929 s = CC_SAFE_MALLOC (c->segcount, CCtsp_segment);
930 if (!s) {
931 fprintf (stderr, "out of memory in copy_lpclique\n");
932 return 1;
933 }
934 for (k = 0; k < c->segcount; k++) {
935 s[k].lo = c->nodes[k].lo;
936 s[k].hi = c->nodes[k].hi;
937 }
938 }
939 new->segcount = c->segcount;
940 new->nodes = s;
941 return 0;
942 }
943
CCtsp_copy_lpdomino(CCtsp_lpdomino * c,CCtsp_lpdomino * new)944 int CCtsp_copy_lpdomino (CCtsp_lpdomino *c, CCtsp_lpdomino *new)
945 {
946 int k;
947 int rval = 0;
948
949 CCtsp_init_lpdomino (new);
950 for (k = 0; k < 2; k++) {
951 rval = CCtsp_copy_lpclique (&(c->sets[k]), &(new->sets[k]));
952 if (rval) {
953 fprintf (stderr, "CCtsp_copy_lpclique failed\n");
954 CCtsp_free_lpdomino (new);
955 goto CLEANUP;
956 }
957 }
958
959 CLEANUP:
960 return rval;
961 }
962
CCtsp_lpclique_compare(CCtsp_lpclique * a,CCtsp_lpclique * b,int * diff)963 void CCtsp_lpclique_compare (CCtsp_lpclique *a, CCtsp_lpclique *b, int *diff)
964 {
965 int i;
966
967 if (a->segcount != b->segcount) {
968 *diff = 1; return;
969 } else {
970 for (i = 0; i < a->segcount; i++) {
971 if (a->nodes[i].lo != b->nodes[i].lo) {
972 *diff = 1; return;
973 }
974 if (a->nodes[i].hi != b->nodes[i].hi) {
975 *diff = 1; return;
976 }
977 }
978 }
979 *diff = 0; return;
980 }
981
CCtsp_create_lpcliques(CCtsp_lpcut_in * c,int cliquecount)982 int CCtsp_create_lpcliques (CCtsp_lpcut_in *c, int cliquecount)
983 {
984 int i;
985
986 c->cliques = CC_SAFE_MALLOC (cliquecount, CCtsp_lpclique);
987 if (c->cliques == (CCtsp_lpclique *) NULL) {
988 fprintf (stderr, "Out of memory in CCtsp_create_lpcliques\n");
989 return 1;
990 }
991 for (i=0; i<cliquecount; i++) {
992 CCtsp_init_lpclique (&c->cliques[i]);
993 }
994 c->cliquecount = cliquecount;
995 return 0;
996 }
997
CCtsp_max_node(CCtsp_lpcut_in * c)998 int CCtsp_max_node (CCtsp_lpcut_in *c)
999 {
1000 int i, j, k;
1001 int maxn;
1002 int cliquecount = c->cliquecount;
1003 CCtsp_lpclique *cliques = c->cliques;
1004 int dominocount = c->dominocount;
1005 CCtsp_lpdomino *dominos = c->dominos;
1006
1007 maxn = 0;
1008
1009 for (i = 0; i < cliquecount; i++) {
1010 for (j = 0; j < cliques[i].segcount; j++) {
1011 if (cliques[i].nodes[j].hi > maxn) {
1012 maxn = cliques[i].nodes[j].hi;
1013 }
1014 }
1015 }
1016 for (i = 0; i < dominocount; i++) {
1017 for (k = 0; k < 2; k++) {
1018 for (j = 0; j < dominos[i].sets[k].segcount; j++) {
1019 if (dominos[i].sets[k].nodes[j].hi > maxn) {
1020 maxn = dominos[i].sets[k].nodes[j].hi;
1021 }
1022 }
1023 }
1024 }
1025 return maxn;
1026 }
1027
CCtsp_build_dp_cut(CCtsp_lpcut_in ** cut,int ndomino,int * Acount,int ** A,int * Bcount,int ** B,int handlecount,int * handle)1028 int CCtsp_build_dp_cut (CCtsp_lpcut_in **cut, int ndomino, int *Acount,
1029 int **A, int *Bcount, int **B, int handlecount, int *handle)
1030 {
1031 int rval = 0;
1032 CCtsp_lpcut_in *c = (CCtsp_lpcut_in *) NULL;
1033
1034 *cut = (CCtsp_lpcut_in *) NULL;
1035
1036 c = CC_SAFE_MALLOC (1, CCtsp_lpcut_in);
1037 CCcheck_NULL (c, "out of memory in CCtsp_build_dp_cut");
1038 CCtsp_init_lpcut_in (c);
1039
1040 c->cliquecount = 1;
1041 c->cliques = CC_SAFE_MALLOC (1, CCtsp_lpclique);
1042 CCcheck_NULL (c->cliques, "out of memory in CCtsp_build_dp_cut");
1043 CCtsp_init_lpclique (&(c->cliques[0]));
1044
1045 rval = CCtsp_array_to_lpclique (handle, handlecount, &(c->cliques[0]));
1046 CCcheck_rval (rval, "CCtsp_array_to_lpclique failed");
1047
1048 rval = build_dominos (c, ndomino, Acount, A, Bcount, B);
1049 CCcheck_rval (rval, "build_dominos failed");
1050
1051 c->rhs = CCtsp_DOMINORHS(c);
1052 c->sense = 'G';
1053 c->branch = 0;
1054
1055 *cut = c;
1056
1057 CLEANUP:
1058
1059 if (rval) {
1060 if (c) {
1061 CCtsp_free_lpcut_in (c);
1062 CC_FREE (c, CCtsp_lpcut_in);
1063 }
1064 }
1065 return rval;
1066 }
1067
build_dominos(CCtsp_lpcut_in * c,int ndomino,int * Acount,int ** A,int * Bcount,int ** B)1068 static int build_dominos (CCtsp_lpcut_in *c, int ndomino, int *Acount,
1069 int **A, int *Bcount, int **B)
1070 {
1071 int i, j, Amin, Bmin, tag, rval = 0;
1072
1073 if (ndomino == 0) {
1074 fprintf (stderr, "ndomino = 0 in build_dominos\n");
1075 rval = 1; goto CLEANUP;
1076 }
1077
1078 c->dominos = CC_SAFE_MALLOC (ndomino, CCtsp_lpdomino);
1079 CCcheck_NULL (c->dominos, "out of memory in build_dominos");
1080 for (i = 0; i < ndomino; i++) {
1081 CCtsp_init_lpdomino (&c->dominos[i]);
1082 }
1083
1084 for (i = 0; i < ndomino; i++) {
1085 Amin = Bmin = CCutil_MAXINT;
1086 for (j = 0; j < Acount[i]; j++) {
1087 if (A[i][j] < Amin) Amin = A[i][j];
1088 }
1089 for (j = 0; j < Bcount[i]; j++) {
1090 if (B[i][j] < Bmin) Bmin = B[i][j];
1091 }
1092 if (Amin < Bmin) tag = 0;
1093 else tag = 1;
1094
1095 rval = CCtsp_array_to_lpclique (A[i], Acount[i],
1096 &c->dominos[i].sets[tag]);
1097 CCcheck_rval (rval, "CCtsp_array_to_lpclique failed");
1098
1099 rval = CCtsp_array_to_lpclique (B[i], Bcount[i],
1100 &c->dominos[i].sets[1-tag]);
1101 CCcheck_rval (rval, "CCtsp_array_to_lpclique failed");
1102 }
1103
1104 c->dominocount = ndomino;
1105
1106 CLEANUP:
1107
1108 return rval;
1109 }
1110
1111