1 #ifndef __PREFIX_H 2 #define __PREFIX_H 3 4 #define CC_PROTOTYPE_ANSI 5 6 #include <stdio.h> 7 #include <stdlib.h> 8 9 #endif /* __PREFIX_H */ 10 /***************************************************************************/ 11 /***************************************************************************/ 12 /* */ 13 /* PROTOTYPES FOR FILES IN UTIL */ 14 /* */ 15 /***************************************************************************/ 16 /***************************************************************************/ 17 18 19 #ifndef __UTIL_H 20 #define __UTIL_H 21 22 23 24 /***************************************************************************/ 25 /* */ 26 /* allocrus.c */ 27 /* */ 28 /***************************************************************************/ 29 30 /***************************************************************************/ 31 /* */ 32 /* MEMORY ALLOCATION MACROS */ 33 /* */ 34 /* TSP CODE */ 35 /* */ 36 /* */ 37 /* Written by: Applegate, Bixby, Chvatal, and Cook */ 38 /* Date: February 24, 1995 (cofeb24) */ 39 /* */ 40 /* */ 41 /* EXPORTED MACROS: */ 42 /* CC_SAFE_MALLOC (nnum,type) */ 43 /* int nnum (the number of objects to be malloced) */ 44 /* data type (the sort of objects to be malloced) */ 45 /* RETURNS a pointer to the allocated space. If out of memory, */ 46 /* it prints an error message and returns NULL. */ 47 /* */ 48 /* CC_FREE (object,type) */ 49 /* type *object (pointer to previously allocated space) */ 50 /* data type (the sort of object) */ 51 /* ACTION: frees the memory and sets the object to NULL. */ 52 /* */ 53 /* CC_IFFREE (object,type) */ 54 /* type *object (pointer to previously allocated space) */ 55 /* data type (the sort of object) */ 56 /* ACTION: if *object is not NULL, frees the memory and sets */ 57 /* the object to NULL. */ 58 /* */ 59 /* CC_PTR_ALLOC_ROUTINE (type, functionname, chunklist, freelist) */ 60 /* data type (the sort of objects) */ 61 /* string functionname (the generated function) */ 62 /* CCbigchunkptr *chunklist (used to accumulate bigchunks) */ 63 /* type *freelist (used for the linked list of objects) */ 64 /* ACTION: Generates a function ("functionname") that returns */ 65 /* (type *) objects, keeping the free ones on freelist */ 66 /* and getting its space from calls to bigchunkalloc. */ 67 /* */ 68 /* CC_PTR_FREE_ROUTINE (type, functionname, freelist) */ 69 /* Parameters as above. */ 70 /* ACTION: Generates a function that adds an object to the */ 71 /* freelist. */ 72 /* */ 73 /* CC_PTR_FREE_LIST_ROUTINE (type, functionname, freefunction) */ 74 /* Parameters defined as above, with freefunction the function */ 75 /* generated by PTR_FREE_ROUTINE. */ 76 /* ACTION: Generates a function to free a linked list of */ 77 /* objects using calls to freefunction. */ 78 /* */ 79 /* CC_PTR_FREE_WORLD_ROUTINE( type, functionname, chunklist, freelist) */ 80 /* Parameters defined as above. */ 81 /* ACTION: Generates a function that returns all of the */ 82 /* memory used in the PTR_ALLOC_ROUTINE allocations */ 83 /* back to the global supply of CCbigchunkptrs. */ 84 /* */ 85 /* CC_PTR_LEAKS_ROUTINE (type, name, chunklist, freelist, field, */ 86 /* fieldtype) */ 87 /* As above, with "field" the name of a "fieldtype" field in the */ 88 /* object type that can be set to 0 or to 1. */ 89 /* ACTION: Generates a function that checks to see that we have */ 90 /* not leaked any of the objects. */ 91 /* */ 92 /* CC_PTR_STATUS_ROUTINE (type, name, chunklist, freelist) */ 93 /* ACTION: Like LEAKS, but does not check for duplicates (and so */ 94 /* does not corrupt the objects). */ 95 /* */ 96 /* NOTES: */ 97 /* These routines use the functions in allocrus.c. The PTR macros */ 98 /* The PTR macros generate the functions for allocating objects for */ 99 /* linked lists. They get their raw memory from the bigchunk supply, so */ 100 /* so foo_free_world (geneated by PTR_FREE_WORLD_ROUTINE) should be */ 101 /* called for each type of linked object "foo" when closing down the */ 102 /* local memory. */ 103 /* To use these functions, put the macros near the top of the file */ 104 /* before any calls to the functions (since the macros also write the */ 105 /* function prototypes). If you use PTR_FREE_LIST_ROUTINE for foo, you */ 106 /* must also use PTR_FREE_ROUTINE, and PTR_FREE_LIST_ROUTINE must be */ 107 /* listed after CC_PTR_FREE_ROUTINE (to get the prototype). */ 108 /* */ 109 /***************************************************************************/ 110 111 112 #define CC_SAFE_MALLOC(nnum,type) \ 113 (type *) CCutil_allocrus (((unsigned int) (nnum)) * sizeof (type)) 114 115 #define CC_FREE(object,type) { \ 116 CCutil_freerus ((void *) (object)); \ 117 object = (type *) NULL; \ 118 } 119 120 #define CC_IFFREE(object,type) { \ 121 if ((object)) CC_FREE ((object),type); \ 122 } 123 124 #ifdef CC_PROTOTYPE_ANSI 125 #define CC_HEADER_PTR_ALLOC_ROUTINE(type, functionname) \ 126 static type * functionname (void); \ 127 static type * functionname (void) 128 #else 129 #define CC_HEADER_PTR_ALLOC_ROUTINE(type, functionname) \ 130 static type * functionname (); \ 131 static type * functionname () 132 #endif 133 134 #define CC_PTR_ALLOC_ROUTINE(type, functionname, chunklist, freelist) \ 135 static type * freelist = ( type * ) NULL; \ 136 static CCbigchunkptr * chunklist = ( CCbigchunkptr * ) NULL; \ 137 CC_HEADER_PTR_ALLOC_ROUTINE (type, functionname) \ 138 { \ 139 type *p; \ 140 \ 141 if (! freelist ) { \ 142 int count = CC_BIGCHUNK / sizeof ( type ); \ 143 CCbigchunkptr *bp; \ 144 \ 145 bp = CCutil_bigchunkalloc (); \ 146 if (!bp) { \ 147 fprintf (stderr, "ptr alloc failed\n"); \ 148 return ( type * ) NULL; \ 149 } \ 150 freelist = ( type * ) bp->this; \ 151 bp->next = chunklist ; \ 152 chunklist = bp; \ 153 \ 154 for (p = freelist + count - 2; p >= freelist ; p--) \ 155 p->next = p + 1; \ 156 freelist [count - 1].next = ( type * ) NULL; \ 157 } \ 158 p = freelist ; \ 159 freelist = p->next; \ 160 \ 161 return p; \ 162 } 163 164 165 #ifdef CC_PROTOTYPE_ANSI 166 #define CC_HEADER_PTR_FREE_ROUTINE(type, functionname) \ 167 static void functionname ( type *p ); \ 168 static void functionname ( type *p ) 169 #else 170 #define CC_HEADER_PTR_FREE_ROUTINE(type, functionname) \ 171 static void functionname (); \ 172 static void functionname ( p ) \ 173 type *p; 174 #endif 175 176 #define CC_PTR_FREE_ROUTINE(type, functionname, freelist) \ 177 CC_HEADER_PTR_FREE_ROUTINE(type, functionname) \ 178 { \ 179 p->next = freelist ; \ 180 freelist = p; \ 181 } 182 183 184 #ifdef CC_PROTOTYPE_ANSI 185 #define CC_HEADER_PTR_FREE_LIST_ROUTINE(type, functionname) \ 186 static void functionname ( type *p ); \ 187 static void functionname ( type *p ) 188 #else 189 #define CC_HEADER_PTR_FREE_LIST_ROUTINE(type, functionname) \ 190 static void functionname (); \ 191 static void functionname ( p ) \ 192 type *p; 193 #endif 194 195 #define CC_PTR_FREE_LIST_ROUTINE(type, functionname, freefunction) \ 196 CC_HEADER_PTR_FREE_LIST_ROUTINE (type, functionname) \ 197 { \ 198 type *next; \ 199 \ 200 while (p) { \ 201 next = p->next; \ 202 freefunction (p); \ 203 p = next; \ 204 } \ 205 } 206 207 #ifdef CC_PROTOTYPE_ANSI 208 #define CC_HEADER_PTR_FREE_WORLD_ROUTINE(functionname) \ 209 static void functionname (void); \ 210 static void functionname (void) 211 #else 212 #define CC_HEADER_PTR_FREE_WORLD_ROUTINE(functionname) \ 213 static void functionname (); \ 214 static void functionname () 215 #endif 216 217 #define CC_PTR_FREE_WORLD_ROUTINE(type, functionname, chunklist, freelist) \ 218 CC_HEADER_PTR_FREE_WORLD_ROUTINE(functionname) \ 219 { \ 220 CCbigchunkptr *bp, *bpnext; \ 221 \ 222 for (bp = chunklist ; bp; bp = bpnext) { \ 223 bpnext = bp->next; \ 224 CCutil_bigchunkfree (bp); \ 225 } \ 226 chunklist = (CCbigchunkptr *) NULL; \ 227 freelist = (type *) NULL; \ 228 } 229 230 231 #ifdef CC_PROTOTYPE_ANSI 232 #define CC_HEADER_PTR_LEAKS_ROUTINE(functionname) \ 233 static int functionname (int *total, int *onlist); \ 234 static int functionname (int *total, int *onlist) 235 #else 236 #define CC_HEADER_PTR_LEAKS_ROUTINE(functionname) \ 237 static int functionname (); \ 238 static int functionname (total, onlist) \ 239 int *total, *onlist; 240 #endif 241 242 #define CC_PTR_LEAKS_ROUTINE(type,name,chunklist,freelist,field,fieldtype) \ 243 CC_HEADER_PTR_LEAKS_ROUTINE(name) \ 244 { \ 245 int count = CC_BIGCHUNK / sizeof ( type ); \ 246 int duplicates = 0; \ 247 type * p; \ 248 CCbigchunkptr *bp; \ 249 \ 250 *total = 0; \ 251 *onlist = 0; \ 252 \ 253 for (bp = chunklist ; bp; bp = bp->next) \ 254 (*total) += count; \ 255 \ 256 for (p = freelist ; p; p = p->next) { \ 257 (*onlist)++; \ 258 p-> field = ( fieldtype ) 0; \ 259 } \ 260 for (p = freelist ; p; p = p->next) { \ 261 if (p-> field == ( fieldtype ) 1) \ 262 duplicates++; \ 263 else \ 264 p-> field = ( fieldtype ) 1; \ 265 } \ 266 if (duplicates) { \ 267 fprintf (stderr, "WARNING: %d duplicates on ptr free list \n", \ 268 duplicates); \ 269 } \ 270 return *total - *onlist; \ 271 } 272 273 #ifdef CC_PROTOTYPE_ANSI 274 #define CC_HEADER_PTR_STATUS_ROUTINE(functionname) \ 275 static int functionname (int *total, int *onlist); \ 276 static int functionname (int *total, int *onlist) 277 #else 278 #define CC_HEADER_PTR_STATUS_ROUTINE(functionname) \ 279 static int functionname (); \ 280 static int functionname (total, onlist) \ 281 int *total, *onlist; 282 #endif 283 284 #define CC_PTR_STATUS_ROUTINE(type, name, chunklist, freelist) \ 285 CC_HEADER_PTR_STATUS_ROUTINE(name) \ 286 { \ 287 int count = CC_BIGCHUNK / sizeof ( type ); \ 288 type * p; \ 289 CCbigchunkptr *bp; \ 290 \ 291 *total = 0; \ 292 *onlist = 0; \ 293 \ 294 for (bp = chunklist ; bp; bp = bp->next) \ 295 (*total) += count; \ 296 \ 297 for (p = freelist ; p; p = p->next) \ 298 (*onlist)++; \ 299 return *total - *onlist; \ 300 } 301 302 303 #define CC_BIGCHUNK ((int) ((1<<16)-16)) 304 305 typedef struct CCbigchunkptr { 306 void *this; 307 struct CCbigchunkptr *next; 308 } CCbigchunkptr; 309 310 311 #ifdef CC_PROTOTYPE_ANSI 312 313 void 314 *CCutil_allocrus (unsigned int size), 315 *CCutil_reallocrus (void *ptr, unsigned int size), 316 CCutil_freerus (void *p), 317 CCutil_bigchunkquery (int *total, int *reserve), 318 CCutil_bigchunkfree (CCbigchunkptr *bp); 319 320 int 321 CCutil_reallocrus_scale (void **pptr, int *pnnum, int count, double scale, 322 unsigned int size), 323 CCutil_reallocrus_count (void **pptr, int count, unsigned int size), 324 CCutil_bigchunk_free_world (void); 325 326 CCbigchunkptr 327 *CCutil_bigchunkalloc (void); 328 329 #else 330 331 void 332 *CCutil_allocrus (), 333 *CCutil_reallocrus (), 334 CCutil_freerus (), 335 CCutil_bigchunkquery (), 336 CCutil_bigchunkfree (); 337 338 int 339 CCutil_reallocrus_scale (), 340 CCutil_reallocrus_count (), 341 CCutil_bigchunk_free_world (); 342 343 CCbigchunkptr 344 *CCutil_bigchunkalloc (); 345 346 #endif 347 348 349 /***************************************************************************/ 350 /* */ 351 /* bgetopt.c */ 352 /* */ 353 /***************************************************************************/ 354 355 #ifdef CC_PROTOTYPE_ANSI 356 357 int 358 CCutil_bix_getopt (int, char **, char *); 359 360 #else 361 362 int 363 CCutil_bix_getopt (); 364 365 #endif 366 367 #define CC_BIX_GETOPT_UNKNOWN -3038 368 369 extern int CCutil_bix_optind; 370 extern char *CCutil_bix_optarg; 371 372 373 374 /***************************************************************************/ 375 /* */ 376 /* dheaps_i.c */ 377 /* */ 378 /***************************************************************************/ 379 380 typedef struct CCdheap { 381 double *key; 382 int *entry; 383 int *loc; 384 int total_space; 385 int size; 386 } CCdheap; 387 388 #ifdef CC_PROTOTYPE_ANSI 389 390 void 391 CCutil_dheap_free (CCdheap *h), 392 CCutil_dheap_insert (CCdheap *h, int i), 393 CCutil_dheap_delete (CCdheap *h, int i), 394 CCutil_dheap_changekey (CCdheap *h, int i, double newkey); 395 int 396 CCutil_dheap_init (CCdheap *h, int k), 397 CCutil_dheap_resize (CCdheap *h, int newsize), 398 CCutil_dheap_findmin (CCdheap *h), 399 CCutil_dheap_deletemin (CCdheap *h); 400 401 #else 402 403 void 404 CCutil_dheap_free (), 405 CCutil_dheap_insert (), 406 CCutil_dheap_delete (), 407 CCutil_dheap_changekey (); 408 int 409 CCutil_dheap_init (), 410 CCutil_dheap_resize (), 411 CCutil_dheap_findmin (), 412 CCutil_dheap_deletemin (); 413 414 #endif 415 416 417 /***************************************************************************/ 418 /* */ 419 /* edg2cyc.c */ 420 /* */ 421 /***************************************************************************/ 422 423 #ifdef CC_PROTOTYPE_ANSI 424 425 int 426 CCutil_edge_to_cycle (int ncount, int *elist, int *cyc); 427 428 #else 429 430 int 431 CCutil_edge_to_cycle (); 432 433 #endif 434 435 436 437 /***************************************************************************/ 438 /* */ 439 /* edgelen.c */ 440 /* */ 441 /***************************************************************************/ 442 443 typedef struct CCdatagroup { 444 double *x; 445 double *y; 446 double *z; 447 int **adj; 448 int norm; 449 } CCdatagroup; 450 451 452 #ifdef CC_PROTOTYPE_ANSI 453 454 extern int 455 (*CCutil_dat_edgelen) (int i, int j, CCdatagroup *dat); 456 int 457 CCutil_init_dat_edgelen (CCdatagroup *dat), 458 CCutil_max_edgelen (int i, int j, CCdatagroup *dat), 459 CCutil_euclid_edgelen (int i, int j, CCdatagroup *dat), 460 CCutil_ibm_edgelen (int i, int j, CCdatagroup *dat), 461 CCutil_euclid_ceiling_edgelen (int i, int j, CCdatagroup *dat), 462 CCutil_euclid3d_edgelen (int i, int j, CCdatagroup *dat), 463 CCutil_geographic_edgelen (int i, int j, CCdatagroup *dat), 464 CCutil_att_edgelen (int i, int j, CCdatagroup *dat), 465 CCutil_dsjrand_edgelen (int i, int j, CCdatagroup *dat), 466 CCutil_crystal_edgelen (int i, int j, CCdatagroup *dat), 467 CCutil_matrix_edgelen (int i, int j, CCdatagroup *dat); 468 void 469 CCutil_dsjrand_init (int maxdist, int seed), 470 CCutil_freedatagroup (int ncount, CCdatagroup *dat); 471 472 #else 473 474 extern int 475 (*CCutil_dat_edgelen) (); 476 int 477 CCutil_init_dat_edgelen (), 478 CCutil_max_edgelen (), 479 CCutil_euclid_edgelen (), 480 CCutil_ibm_edgelen (), 481 CCutil_euclid_ceiling_edgelen (), 482 CCutil_euclid3d_edgelen (), 483 CCutil_geographic_edgelen (), 484 CCutil_att_edgelen (), 485 CCutil_dsjrand_edgelen (), 486 CCutil_crystal_edgelen (), 487 CCutil_matrix_edgelen (); 488 void 489 CCutil_dsjrand_init (), 490 CCutil_freedatagroup (); 491 492 #endif 493 494 495 #define CC_KD_NORM_TYPE 128 /* Kdtrees work */ 496 #define CC_X_NORM_TYPE 256 /* Old nearest works */ 497 #define CC_JUNK_NORM_TYPE 512 /* Nothing works */ 498 499 #define CC_D2_NORM_SIZE 1024 /* x,y coordinates */ 500 #define CC_D3_NORM_SIZE 2048 /* x,y,z coordinates */ 501 #define CC_MATRIX_NORM_SIZE 4096 /* adj matrix */ 502 503 #define CC_NORM_BITS (CC_KD_NORM_TYPE | CC_X_NORM_TYPE | CC_JUNK_NORM_TYPE) 504 #define CC_NORM_SIZE_BITS (CC_D2_NORM_SIZE | CC_D3_NORM_SIZE | CC_MATRIX_NORM_SIZE) 505 506 #define CC_MAXNORM (0 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE) 507 #define CC_EUCLIDEAN_CEIL (1 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE) 508 #define CC_EUCLIDEAN (2 | CC_KD_NORM_TYPE | CC_D2_NORM_SIZE) 509 #define CC_EUCLIDEAN_3D (3 | CC_X_NORM_TYPE | CC_D3_NORM_SIZE) 510 #define CC_IBM (4 | CC_JUNK_NORM_TYPE | CC_D2_NORM_SIZE) 511 #define CC_ATT (5 | CC_X_NORM_TYPE | CC_D2_NORM_SIZE) 512 #define CC_GEOGRAPHIC (6 | CC_X_NORM_TYPE | CC_D2_NORM_SIZE) 513 #define CC_MATRIXNORM (7 | CC_JUNK_NORM_TYPE | CC_MATRIX_NORM_SIZE) 514 #define CC_DSJRANDNORM (8 | CC_JUNK_NORM_TYPE) 515 #define CC_CRYSTAL (9 | CC_X_NORM_TYPE | CC_D3_NORM_SIZE) 516 517 #define CC_GEOGRAPHIC_SCALE (6378.388 * 3.14 / 180.0) /* see edgelen.c */ 518 #define CC_ATT_SCALE (.31622) /* sqrt(1/10) */ 519 520 /* For X-NORMS, scales are such that |x[i] - x[j]| * scale <= edgelen(i,j). */ 521 /* Ggeographic is slightly off, since the fractional part of x[i] is really */ 522 /* really minutes, not fractional degrees. */ 523 524 525 526 /***************************************************************************/ 527 /* */ 528 /* fastread.c */ 529 /* */ 530 /***************************************************************************/ 531 532 #ifdef CC_PROTOTYPE_ANSI 533 534 int 535 CCutil_readint (FILE *); 536 537 #else 538 539 int 540 CCutil_readint (); 541 542 #endif 543 544 545 546 /***************************************************************************/ 547 /* */ 548 /* genhash.c */ 549 /* */ 550 /***************************************************************************/ 551 552 typedef struct CCgenhash { 553 int nelem; 554 int maxelem; 555 int size; 556 #ifdef CC_PROTOTYPE_ANSI 557 int (*hcmp) (void *key1, void *key2, void *u_data); 558 unsigned int (*hfunc) (void *key, void *u_data); 559 #else 560 int (*hcmp) (); 561 unsigned int (*hfunc) (); 562 #endif 563 void *u_data; 564 double maxdensity; 565 double lowdensity; 566 struct CCgenhash_elem **table; 567 } CCgenhash; 568 569 typedef struct CCgenhash_iter { 570 int i; 571 struct CCgenhash_elem *next; 572 } CCgenhash_iter; 573 574 #ifdef CC_PROTOTYPE_ANSI 575 576 int 577 CCutil_genhash_init (CCgenhash *h, int size, 578 int (*hcmp) (void *key1, void *key2, void *u_data), 579 unsigned int (*hfunc) (void *key, void *u_data), 580 void *u_data, double maxdensity, double lowdensity), 581 CCutil_genhash_insert (CCgenhash *h, void *key, void *data), 582 CCutil_genhash_insert_h (CCgenhash *h, unsigned int hashval, void *key, 583 void *data), 584 CCutil_genhash_replace (CCgenhash *h, void *key, void *data), 585 CCutil_genhash_replace_h (CCgenhash *h, unsigned int hashval, void *key, 586 void *data), 587 CCutil_genhash_delete (CCgenhash *h, void *key), 588 CCutil_genhash_delete_h (CCgenhash *h, unsigned int hashval, void *key); 589 590 unsigned int 591 CCutil_genhash_hash (CCgenhash *h, void *key); 592 593 void 594 *CCutil_genhash_lookup (CCgenhash *h, void *key), 595 *CCutil_genhash_lookup_h (CCgenhash *h, unsigned int hashval, void *key), 596 *CCutil_genhash_next (CCgenhash *h, CCgenhash_iter *iter, void **key, 597 int *keysize); 598 599 void 600 CCutil_genhash_u_data (CCgenhash *h, void *u_data), 601 CCutil_genhash_free (CCgenhash *h, void (*freefunc)(void *key, void *data, 602 void *u_data)), 603 CCutil_genhash_start (CCgenhash *h, CCgenhash_iter *iter); 604 605 #else 606 607 int 608 CCutil_genhash_init (), 609 CCutil_genhash_insert (), 610 CCutil_genhash_insert_h (), 611 CCutil_genhash_replace (), 612 CCutil_genhash_replace_h (), 613 CCutil_genhash_delete (), 614 CCutil_genhash_delete_h (); 615 616 unsigned int 617 CCutil_genhash_hash (); 618 619 void 620 *CCutil_genhash_lookup (), 621 *CCutil_genhash_lookup_h (), 622 *CCutil_genhash_next (); 623 624 void 625 CCutil_genhash_u_data (), 626 CCutil_genhash_free (), 627 CCutil_genhash_start (); 628 629 #endif 630 631 632 633 /***************************************************************************/ 634 /* */ 635 /* getdata.c */ 636 /* */ 637 /***************************************************************************/ 638 639 #define CC_MASTER_NO_DAT 100 640 #define CC_MASTER_DAT 101 641 642 #ifdef CC_PROTOTYPE_ANSI 643 644 int 645 CCutil_getdata (char *datname, int binary_in, int innorm, int *ncount, 646 CCdatagroup *dat), 647 CCutil_writemaster (char *mastername, int ncount, CCdatagroup *dat, 648 int *perm), 649 CCutil_getmaster (char *mastername, int *ncount, CCdatagroup *dat, 650 int **perm), 651 CCutil_getnodeweights (char *weightname, int ncount, int weight_limit, 652 double **wcoord), 653 CCutil_gettsplib (char *datname, int *ncount, CCdatagroup *dat), 654 CCutil_datagroup_perm (int ncount, CCdatagroup *dat, int *perm), 655 CCutil_getedgelist (int ncount, char *fname, int *ecount, int **elist, 656 int **elen), 657 CCutil_getedgelist_n (int *ncount, char *fname, int *ecount, int **elist, 658 int **elen), 659 CCutil_getcycle_edgelist (int ncount, char *cyclename, int *outcycle), 660 CCutil_getcycle (int ncount, char *cyclename, int *outcycle), 661 CCutil_getedges_double (int *ncount, char *fname, int *ecount, int **elist, 662 double **elen, int binary_in), 663 CCutil_writeedges (int ncount, char *outedgename, int ecount, int *elist, 664 CCdatagroup *dat), 665 CCutil_writecycle_edgelist (int ncount, char *outedgename, int *cycle, 666 CCdatagroup *dat), 667 CCutil_writecycle (int ncount, char *outcyclename, int *cycle), 668 CCutil_writeedges_double (int ncount, char *outedgename, int ecount, 669 int *elist, double *elen, int binary_out); 670 671 #else 672 673 int 674 CCutil_getdata (), 675 CCutil_writemaster (), 676 CCutil_getmaster (), 677 CCutil_getnodeweights (), 678 CCutil_gettsplib (), 679 CCutil_datagroup_perm (), 680 CCutil_getedgelist (), 681 CCutil_getedgelist_n (), 682 CCutil_getcycle_edgelist (), 683 CCutil_getcycle (), 684 CCutil_getedges_double (), 685 CCutil_writeedges (), 686 CCutil_writecycle_edgelist (), 687 CCutil_writecycle (), 688 CCutil_writeedges_double (); 689 690 #endif 691 692 693 694 /***************************************************************************/ 695 /* */ 696 /* priority.c */ 697 /* */ 698 /***************************************************************************/ 699 700 typedef struct CCpriority { 701 CCdheap heap; 702 union pri_data { 703 void *data; 704 int next; 705 } *pri_info; 706 int space; 707 int freelist; 708 } CCpriority; 709 710 #ifdef CC_PROTOTYPE_ANSI 711 712 void 713 CCutil_priority_free (CCpriority *pri), 714 CCutil_priority_delete (CCpriority *pri, int handle), 715 CCutil_priority_changekey (CCpriority *pri, int handle, double newkey), 716 *CCutil_priority_findmin (CCpriority *pri, double *keyval), 717 *CCutil_priority_deletemin (CCpriority *pri, double *keyval); 718 719 int 720 CCutil_priority_init (CCpriority *pri, int k), 721 CCutil_priority_insert (CCpriority *pri, void *data, double keyval); 722 723 #else 724 725 void 726 CCutil_priority_free (), 727 CCutil_priority_delete (), 728 CCutil_priority_changekey (), 729 *CCutil_priority_findmin (), 730 *CCutil_priority_deletemin (); 731 732 int 733 CCutil_priority_init (), 734 CCutil_priority_insert (); 735 736 #endif 737 738 739 /***************************************************************************/ 740 /* */ 741 /* safe_io.c */ 742 /* */ 743 /***************************************************************************/ 744 745 #define CC_SBUFFER_SIZE (4000) 746 #define CC_SFNAME_SIZE (32) 747 748 typedef struct CC_SFILE { 749 int status; 750 int desc; 751 int chars_in_buffer; 752 int current_buffer_char; /* only used for reading */ 753 int bits_in_last_char; /* writing: number of empty bits in 754 * buffer[chars_in_buffer]; 755 * reading: number of full bits in 756 * buffer[?] */ 757 int pos; 758 char fname[CC_SFNAME_SIZE]; 759 unsigned char buffer[CC_SBUFFER_SIZE]; 760 } CC_SFILE; 761 762 #ifdef CC_PROTOTYPE_ANSI 763 764 CC_SFILE 765 *CCutil_sopen (char *f, char *s), 766 *CCutil_sdopen (int d, char *s); 767 768 int 769 CCutil_swrite (CC_SFILE *f, unsigned char *buf, int size), 770 CCutil_swrite_bits (CC_SFILE *f, unsigned int x, int xbits), 771 CCutil_swrite_char (CC_SFILE *f, unsigned char x), 772 CCutil_swrite_string (CC_SFILE *f, unsigned char *x), 773 CCutil_swrite_short (CC_SFILE *f, unsigned short x), 774 CCutil_swrite_int (CC_SFILE *f, unsigned int x), 775 CCutil_swrite_double (CC_SFILE *f, double x), 776 CCutil_sread (CC_SFILE *f, unsigned char *buf, int size), 777 CCutil_sread_bits (CC_SFILE *f, unsigned int *x, int xbits), 778 CCutil_sread_char (CC_SFILE *f, unsigned char *x), 779 CCutil_sread_string (CC_SFILE *f, unsigned char *x, int maxlen), 780 CCutil_sread_short (CC_SFILE *f, unsigned short *x), 781 CCutil_sread_short_r (CC_SFILE *f, unsigned short *x), 782 CCutil_sread_int (CC_SFILE *f, unsigned int *x), 783 CCutil_sread_int_r (CC_SFILE *f, unsigned int *x), 784 CCutil_sread_double (CC_SFILE *f, double *x), 785 CCutil_sread_double_r (CC_SFILE *f, double *x), 786 CCutil_sflush (CC_SFILE *f), 787 CCutil_stell (CC_SFILE *f), 788 CCutil_sseek (CC_SFILE *f, int offset), 789 CCutil_srewind (CC_SFILE *f), 790 CCutil_sclose (CC_SFILE *f), 791 CCutil_sbits (unsigned int x), 792 CCutil_sdelete_file (char *fname), 793 CCutil_sdelete_file_backup (char *fname); 794 795 #else 796 797 CC_SFILE 798 *CCutil_sopen (), 799 *CCutil_sdopen (); 800 801 int 802 CCutil_swrite (), 803 CCutil_swrite_bits (), 804 CCutil_swrite_char (), 805 CCutil_swrite_string (), 806 CCutil_swrite_short (), 807 CCutil_swrite_int (), 808 CCutil_swrite_double (), 809 CCutil_sread (), 810 CCutil_sread_bits (), 811 CCutil_sread_char (), 812 CCutil_sread_string (), 813 CCutil_sread_short (), 814 CCutil_sread_short_r (), 815 CCutil_sread_int (), 816 CCutil_sread_int_r (), 817 CCutil_sread_double (), 818 CCutil_sread_double_r (), 819 CCutil_sflush (), 820 CCutil_stell (), 821 CCutil_sseek (), 822 CCutil_srewind (), 823 CCutil_sclose (), 824 CCutil_sbits (), 825 CCutil_sdelete_file (), 826 CCutil_sdelete_file_backup (); 827 828 #endif 829 830 831 832 /***************************************************************************/ 833 /* */ 834 /* sortrus.c */ 835 /* */ 836 /***************************************************************************/ 837 838 #ifdef CC_PROTOTYPE_ANSI 839 840 void 841 CCutil_int_array_quicksort (int *len, int n), 842 CCutil_int_perm_quicksort (int *perm, int *len, int n), 843 CCutil_double_perm_quicksort (int *perm, double *len, int n), 844 CCutil_rselect (int *arr, int l, int r, int m, double *coord); 845 846 char 847 *CCutil_linked_radixsort (char *data, char *datanext, char *dataval, 848 int valsize); 849 850 #else 851 852 void 853 CCutil_int_array_quicksort (), 854 CCutil_int_perm_quicksort (), 855 CCutil_double_perm_quicksort (), 856 CCutil_rselect (); 857 858 char 859 *CCutil_linked_radixsort (); 860 861 #endif 862 863 864 865 /***************************************************************************/ 866 /* */ 867 /* urandom.c */ 868 /* */ 869 /***************************************************************************/ 870 871 #ifdef CC_PROTOTYPE_ANSI 872 873 void 874 CCutil_sprand (int); 875 int 876 CCutil_lprand (void); 877 878 #else 879 880 void 881 CCutil_sprand (); 882 int 883 CCutil_lprand (); 884 885 #endif 886 887 888 889 /***************************************************************************/ 890 /* */ 891 /* util.c */ 892 /* */ 893 /***************************************************************************/ 894 895 896 #ifdef CC_PROTOTYPE_ANSI 897 898 char 899 *CCutil_strrchr (char *s, int c); 900 901 unsigned int 902 CCutil_nextprime (unsigned int x); 903 904 int 905 CCutil_our_gcd (int a, int b); 906 907 #else 908 909 char 910 *CCutil_strrchr (); 911 912 unsigned int 913 CCutil_nextprime (); 914 915 int 916 CCutil_our_gcd (); 917 918 #endif 919 920 921 922 /***************************************************************************/ 923 /* */ 924 /* zeit.c */ 925 /* */ 926 /***************************************************************************/ 927 928 929 #ifdef CC_PROTOTYPE_ANSI 930 931 double 932 CCutil_zeit (void), 933 CCutil_real_zeit (void); 934 935 #else 936 937 double 938 CCutil_zeit (), 939 CCutil_real_zeit (); 940 941 #endif 942 943 944 #endif /* __UTIL_H */ 945 #ifndef __BIGGUY_H 946 #define __BIGGUY_H 947 948 949 #ifdef CC_BIGGUY_LONGLONG 950 951 typedef long long CCbigguy; 952 953 #define CCbigguy_FRACBITS 32 954 #define CCbigguy_DUALSCALE (((CCbigguy) 1) << CCbigguy_FRACBITS) 955 #define CCbigguy_FRACPART(x) ((x) & (CCbigguy_DUALSCALE-1)) 956 #define CCbigguy_MAXBIGGUY (((((CCbigguy) 1) << 62) - 1) + \ 957 (((CCbigguy) 1) << 62)) 958 #define CCbigguy_MINBIGGUY (-CCbigguy_MAXBIGGUY) 959 #define CCbigguy_bigguytod(x) (((double) (x)) / ((double) CCbigguy_DUALSCALE)) 960 #define CCbigguy_itobigguy(d) ((CCbigguy) ((d) * (double) CCbigguy_DUALSCALE)) 961 #define CCbigguy_ceil(x) (CCbigguy_FRACPART(x) ? \ 962 ((x) + (CCbigguy_DUALSCALE - CCbigguy_FRACPART(x))) : (x)) 963 #define CCbigguy_cmp(x,y) (((x) < (y)) ? -1 : ((x) > (y)) ? 1 : 0) 964 #define CCbigguy_ZERO ((CCbigguy) 0) 965 #define CCbigguy_ONE ((CCbigguy) CCbigguy_DUALSCALE) 966 #define CCbigguy_addmult(x,y,m) ((*x) += (y)*(m)) 967 #define CCbigguy_dtobigguy(d) ((CCbigguy) ((d) * (double) CCbigguy_DUALSCALE)) 968 969 #else /* CC_BIGGUY_LONGLONG */ 970 971 typedef struct CCbigguy { 972 unsigned short ihi; 973 unsigned short ilo; 974 unsigned short fhi; 975 unsigned short flo; 976 } CCbigguy; 977 978 extern const CCbigguy CCbigguy_MINBIGGUY; 979 extern const CCbigguy CCbigguy_MAXBIGGUY; 980 extern const CCbigguy CCbigguy_ZERO; 981 extern const CCbigguy CCbigguy_ONE; 982 983 #ifdef CC_PROTOTYPE_ANSI 984 985 void 986 CCbigguy_addmult (CCbigguy *x, CCbigguy y, short m); 987 988 int 989 CCbigguy_cmp (CCbigguy x, CCbigguy y); 990 991 double 992 CCbigguy_bigguytod (CCbigguy x); 993 994 CCbigguy 995 CCbigguy_itobigguy (int d), 996 CCbigguy_dtobigguy (double d), 997 CCbigguy_ceil (CCbigguy x); 998 999 #else 1000 1001 void 1002 CCbigguy_addmult (); 1003 1004 int 1005 CCbigguy_cmp (); 1006 1007 double 1008 CCbigguy_bigguytod (); 1009 1010 CCbigguy 1011 CCbigguy_itobigguy (), 1012 CCbigguy_dtobigguy (), 1013 CCbigguy_ceil (); 1014 1015 #endif 1016 1017 #endif /* CC_BIGGUY_LONGLONG */ 1018 1019 #define CCbigguy_add(x,y) (CCbigguy_addmult(x,y,1)) 1020 #define CCbigguy_sub(x,y) (CCbigguy_addmult(x,y,-1)) 1021 1022 #ifdef CC_PROTOTYPE_ANSI 1023 1024 int 1025 CCbigguy_swrite (CC_SFILE *f, CCbigguy x), 1026 CCbigguy_sread (CC_SFILE *f, CCbigguy *x); 1027 1028 #else 1029 1030 int 1031 CCbigguy_swrite (), 1032 CCbigguy_sread (); 1033 1034 #endif 1035 1036 #endif /* __BIGGUY_H */ 1037 #ifndef __LP_H 1038 #define __LP_H 1039 1040 #define CClp_METHOD_DUAL 1 1041 #define CClp_METHOD_BARRIER 2 1042 1043 #define CClp_SUCCESS 0 1044 #define CClp_FAILURE 1 1045 #define CClp_UNBOUNDED 2 1046 #define CClp_INFEASIBLE 3 1047 #define CClp_UNKNOWN 4 1048 1049 typedef struct CClp { 1050 struct cpxenv *cplex_env; 1051 struct cpxlp *cplex_lp; 1052 int lp_allocated; 1053 } CClp; 1054 1055 typedef struct CClpbasis { 1056 int *rstat; 1057 int *cstat; 1058 double *dnorm; 1059 } CClpbasis; 1060 1061 #ifdef CC_PROTOTYPE_ANSI 1062 1063 int 1064 CClp_init (CClp *lp), 1065 CClp_loadlp (CClp *lp, char *name, int ncols, int nrows, int objsense, 1066 double *obj, double *rhs, char *sense, int *matbeg, int *matcnt, 1067 int *matind, double *matval, double *lb, double *ub), 1068 CClp_opt (CClp *lp, int method), 1069 CClp_dualopt (CClp *lp), 1070 CClp_limited_dualopt (CClp *lp, int lim, int *status, double *upperbound), 1071 CClp_primalopt (CClp *lp), 1072 CClp_addrows (CClp *lp, int newrows, int newnz, double *rhs, char *sense, 1073 int *rmatbeg, int *rmatind, double *rmatval), 1074 CClp_addcols (CClp *lp, int newcols, int newnz, double *obj, 1075 int *cmatbeg, int *cmatind, double *cmatval, double *lb, 1076 double *ub), 1077 CClp_delete_row (CClp *lp, int i), 1078 CClp_delete_set_of_rows (CClp *lp, int *delstat), 1079 CClp_delete_column (CClp *lp, int i), 1080 CClp_delete_set_of_columns (CClp *lp, int *delstat), 1081 CClp_setbnd (CClp *lp, int col, char lower_or_upper, double bnd), 1082 CClp_get_basis_and_norms (CClp *lp, CClpbasis *b), 1083 CClp_load_basis_and_norms (CClp *lp, CClpbasis *b), 1084 CClp_basis (CClp *lp, int *cstat, int *rstat), 1085 CClp_loadbasis (CClp *lp, int *cstat, int *rstat), 1086 CClp_getbasis_and_norms (CClp *lp, int *cstat, int *rstat, 1087 double *dnorm), 1088 CClp_loadbasis_and_norms (CClp *lp, int *cstat, int *rstat, 1089 double *dnorm), 1090 CClp_x (CClp *lp, double *x), 1091 CClp_rc (CClp *lp, double *rc), 1092 CClp_pi_range (CClp *lp, double *pi, int from, int to), 1093 CClp_objval (CClp *lp, double *obj), 1094 CClp_nonzeros (CClp *lp), 1095 CClp_status (CClp *lp, int *status), 1096 CClp_getweight (CClp *lp, int nrows, int *rmatbeg, int *rmatind, 1097 double *rmatval, double *weight), 1098 CClp_dump_lp (CClp *lp, char *fname), 1099 CClp_getgoodlist (CClp *lp, int *goodlist, int *goodlen_p, 1100 double *downpen, double *uppen), 1101 CClp_strongbranch (CClp *lp, int *candidatelist, int ncand, 1102 double *downpen, double *uppen, int iterations, 1103 double *upperbound), 1104 CClp_getfarkasmultipliers (CClp *lp, double *y); 1105 1106 void 1107 CClp_init_struct (CClp *lp), 1108 CClp_free (CClp *lp), 1109 CClp_init_basis (CClpbasis *b), 1110 CClp_free_basis (CClpbasis *b), 1111 CClp_pivotin (CClp *lp, int i); 1112 1113 #else 1114 1115 int 1116 CClp_init (), 1117 CClp_loadlp (), 1118 CClp_opt (), 1119 CClp_dualopt (), 1120 CClp_limited_dualopt (), 1121 CClp_primalopt (), 1122 CClp_addrows (), 1123 CClp_addcols (), 1124 CClp_delete_row (), 1125 CClp_delete_set_of_rows (), 1126 CClp_delete_column (), 1127 CClp_delete_set_of_columns (), 1128 CClp_setbnd (), 1129 CClp_get_basis_and_norms (), 1130 CClp_load_basis_and_norms (), 1131 CClp_basis (), 1132 CClp_loadbasis (), 1133 CClp_getbasis_and_norms (), 1134 CClp_loadbasis_and_norms (), 1135 CClp_x (), 1136 CClp_rc (), 1137 CClp_pi_range (), 1138 CClp_objval (), 1139 CClp_nonzeros (), 1140 CClp_status (), 1141 CClp_getweight (), 1142 CClp_dump_lp (), 1143 CClp_getgoodlist (), 1144 CClp_strongbranch (), 1145 CClp_getfarkasmultipliers (); 1146 1147 void 1148 CClp_init_struct (), 1149 CClp_free (), 1150 CClp_init_basis (), 1151 CClp_free_basis (), 1152 CClp_pivotin (); 1153 1154 #endif 1155 1156 1157 #endif /* __LP_H */ 1158 #ifndef __KDTREE_H 1159 #define __KDTREE_H 1160 1161 1162 typedef struct CCkdnode { 1163 double cutval; 1164 struct CCkdnode *loson; 1165 struct CCkdnode *hison; 1166 struct CCkdnode *father; 1167 struct CCkdnode *next; 1168 struct CCkdbnds *bnds; 1169 int lopt; 1170 int hipt; 1171 char bucket; 1172 char empty; 1173 char cutdim; 1174 } CCkdnode; 1175 1176 typedef struct CCkdtree { 1177 CCkdnode *root; 1178 CCkdnode **bucketptr; 1179 int *perm; 1180 } CCkdtree; 1181 1182 typedef struct CCkdbnds { 1183 double x[2]; 1184 double y[2]; 1185 struct CCkdbnds *next; 1186 } CCkdbnds; 1187 1188 #ifdef CC_PROTOTYPE_ANSI 1189 1190 void 1191 CCkdtree_free (CCkdtree *kt), 1192 CCkdtree_delete (CCkdtree *kt, int k), 1193 CCkdtree_delete_all (CCkdtree *kt, int ncount), 1194 CCkdtree_undelete (CCkdtree *kt, int k), 1195 CCkdtree_undelete_all (CCkdtree *kt, int ncount); 1196 int 1197 CCkdtree_build (CCkdtree *kt, int ncount, CCdatagroup *dat, double *wcoord), 1198 CCkdtree_k_nearest (CCkdtree *kt, int ncount, int k, CCdatagroup *dat, 1199 double *wcoord, int wantlist, int *ocount, int **olist), 1200 CCkdtree_quadrant_k_nearest (CCkdtree *kt, int ncount, int k, 1201 CCdatagroup *dat, double *wcoord, int wantlist, int *ocount, 1202 int **olist), 1203 CCkdtree_node_k_nearest (CCkdtree *kt, int ncount, int n, int k, 1204 CCdatagroup *dat, double *wcoord, int *list), 1205 CCkdtree_node_quadrant_k_nearest (CCkdtree *kt, int ncount, int n, int k, 1206 CCdatagroup *dat, double *wcoord, int *list), 1207 CCkdtree_node_nearest (CCkdtree *kt, int n, CCdatagroup *dat, 1208 double *wcoord), 1209 CCkdtree_fixed_radius_nearest (CCkdtree *kt, CCdatagroup *dat, 1210 double *wcoord, int n, double rad, 1211 int (*doit_fn) (int, int, void *), void *pass_param), 1212 CCkdtree_nearest_neighbor_tour (CCkdtree *kt, int ncount, int start, 1213 CCdatagroup *dat, int *outcycle, double *val), 1214 CCkdtree_nearest_neighbor_2match (CCkdtree *kt, int ncount, int start, 1215 CCdatagroup *dat, int *outmatch, double *val), 1216 CCkdtree_prim_spanningtree (CCkdtree *kt, int ncount, CCdatagroup *dat, 1217 double *wcoord, int *outtree, double *val), 1218 CCkdtree_greedy_tour (CCkdtree *kt, int ncount, CCdatagroup *dat, 1219 int *outcycle, double *val), 1220 CCkdtree_far_add_tour (CCkdtree *kt, int ncount, int start, 1221 CCdatagroup *dat, int *outcycle, double *val), 1222 CCkdtree_qboruvka_tour (CCkdtree *kt, int ncount, CCdatagroup *dat, 1223 int *outcycle, double *val), 1224 CCkdtree_boruvka_tour (CCkdtree *kt, int ncount, CCdatagroup *dat, 1225 int *outcycle, double *val), 1226 CCkdtree_twoopt_tour (CCkdtree *kt, int ncount, CCdatagroup *dat, 1227 int *incycle, int *outcycle, double *val, 1228 int in_run_two_and_a_half_opt, int run_silently), 1229 CCkdtree_3opt_tour (CCkdtree *kt, int ncount, CCdatagroup *dat, 1230 int *incycle, int *outcycle, double *val, int run_silently); 1231 1232 #else 1233 1234 void 1235 CCkdtree_free (), 1236 CCkdtree_delete (), 1237 CCkdtree_delete_all (), 1238 CCkdtree_undelete (), 1239 CCkdtree_undelete_all (); 1240 int 1241 CCkdtree_build (), 1242 CCkdtree_k_nearest (), 1243 CCkdtree_quadrant_k_nearest (), 1244 CCkdtree_node_k_nearest (), 1245 CCkdtree_node_quadrant_k_nearest (), 1246 CCkdtree_node_nearest (), 1247 CCkdtree_fixed_radius_nearest (), 1248 CCkdtree_nearest_neighbor_tour (), 1249 CCkdtree_nearest_neighbor_2match (), 1250 CCkdtree_prim_spanningtree (), 1251 CCkdtree_greedy_tour (), 1252 CCkdtree_far_add_tour (), 1253 CCkdtree_qboruvka_tour (), 1254 CCkdtree_boruvka_tour (), 1255 CCkdtree_twoopt_tour (), 1256 CCkdtree_3opt_tour (); 1257 #endif 1258 1259 #endif /* __KDTREE_H */ 1260 1261 /***************************************************************************/ 1262 /***************************************************************************/ 1263 /* */ 1264 /* PROTOTYPES FOR FILES IN CUT */ 1265 /* */ 1266 /***************************************************************************/ 1267 /***************************************************************************/ 1268 1269 1270 #ifndef __CUT_H 1271 #define __CUT_H 1272 1273 1274 #define CC_MINCUT_BIGDOUBLE (100000000000.0) 1275 #define CC_MINCUT_ONE_EPSILON (0.000001) 1276 1277 1278 #ifdef CC_PROTOTYPE_ANSI 1279 1280 int 1281 CCcut_mincut (int ncount, int ecount, int *elist, double *dlen, 1282 double *valval, int **cut, int *cutcount), 1283 CCcut_violated_cuts (int ncount, int ecount, int *elist, double *dlen, 1284 double cutoff, int (*doit_fn) (double, int, int *, void *), 1285 void *pass_param), 1286 CCcut_mincut_st (int ncount, int ecount, int *elist, double *ecap, 1287 int s, int t, double *value, int **cut, int *cutcount), 1288 CCcut_linsub (int ncount, int ecount, int *elist, double *x, double cutoff, 1289 int (*doit_fn) (double, int, int, void *), void *pass_param), 1290 CCcut_connect_components (int ncount, int ecount, int *elist, double *x, 1291 int *ncomp, int **compscount, int **comps); 1292 1293 #else 1294 1295 int 1296 CCcut_mincut (), 1297 CCcut_violated_cuts (), 1298 CCcut_mincut_st (), 1299 CCcut_linsub (), 1300 CCcut_connect_components (); 1301 1302 #endif 1303 1304 1305 1306 /***************************************************************************/ 1307 /* */ 1308 /* shrink.c */ 1309 /* */ 1310 /***************************************************************************/ 1311 1312 typedef struct CC_SRKnode { 1313 struct CC_SRKedge *adj; 1314 struct CC_SRKnode *next; 1315 struct CC_SRKnode *prev; 1316 struct CC_SRKnode *members; 1317 struct CC_SRKnode *parent; 1318 struct CC_SRKnode *qnext; 1319 double prweight; 1320 double weight; 1321 int num; 1322 int newnum; 1323 int onecnt; 1324 int onqueue; 1325 } CC_SRKnode; 1326 1327 typedef struct CC_SRKedge { 1328 struct CC_SRKnode *end; 1329 struct CC_SRKedge *other; 1330 struct CC_SRKedge *next; 1331 struct CC_SRKedge *prev; 1332 double weight; 1333 } CC_SRKedge; 1334 1335 typedef struct CC_SRKgraph { 1336 struct CC_SRKnode *nodespace; 1337 struct CC_SRKedge *edgespace; 1338 struct CC_SRKnode *head; 1339 struct CC_SRKedge **hit; 1340 int original_ncount; 1341 int original_ecount; 1342 } CC_SRKgraph; 1343 1344 typedef struct CC_SRKexpinfo { 1345 int *members; 1346 int *memindex; 1347 } CC_SRKexpinfo; 1348 1349 typedef struct CC_SRKcallback { 1350 double cutoff; 1351 void *pass_param; 1352 #ifdef CC_PROTOTYPE_ANSI 1353 int (*doit_fn) (double, int, int *, void *); 1354 #else 1355 int (*doit_fn) (); 1356 #endif 1357 } CC_SRKcallback; 1358 1359 #ifdef CC_PROTOTYPE_ANSI 1360 1361 void 1362 CCcut_SRK_identify_paths (CC_SRKgraph *G, int *newcount, int onecnt_okay), 1363 CCcut_SRK_identify_paths_to_edges (CC_SRKgraph *G, int *newcount, 1364 int onecnt_okay), 1365 CCcut_SRK_identify_ones (CC_SRKgraph *G, int *count, double epsilon), 1366 CCcut_SRK_identify_one_triangles (CC_SRKgraph *G, int *count, 1367 CC_SRKnode *qstart, double epsilon), 1368 CCcut_SRK_identify_nodes (CC_SRKgraph *G, CC_SRKnode *n, CC_SRKnode *m), 1369 CCcut_SRK_init_graph (CC_SRKgraph *G), 1370 CCcut_SRK_free_graph (CC_SRKgraph *G), 1371 CCcut_SRK_init_expinfo (CC_SRKexpinfo *expand), 1372 CCcut_SRK_free_expinfo (CC_SRKexpinfo *expand), 1373 CCcut_SRK_init_callback (CC_SRKcallback *cb); 1374 1375 int 1376 CCcut_SRK_buildgraph (CC_SRKgraph *G, int ncount, int ecount, int *elist, 1377 double *dlen), 1378 CCcut_SRK_subtour_shrink (CC_SRKgraph *G, double *minval, double epsilon, 1379 CC_SRKcallback *cb, int **cut, int *cutcount), 1380 CCcut_SRK_identify_pr_edges (CC_SRKgraph *G, double *minval, int *count, 1381 CC_SRKnode *qstart, double epsilon, CC_SRKcallback *cb, int **cut, 1382 int *cutcount), 1383 CCcut_SRK_defluff (CC_SRKgraph *G), 1384 CCcut_SRK_grab_edges (CC_SRKgraph *G, int *oncount, int *oecount, 1385 int **olist, double **olen, CC_SRKexpinfo *expand), 1386 CCcut_SRK_grab_nodes (CC_SRKgraph *G, CC_SRKexpinfo *expand), 1387 CCcut_SRK_trivial (int ncount, CC_SRKexpinfo *expand), 1388 CCcut_SRK_expand (CC_SRKexpinfo *expand, int *arr, int size, int **pnewarr, 1389 int *pnewsize); 1390 1391 #else 1392 1393 void 1394 CCcut_SRK_identify_paths (), 1395 CCcut_SRK_identify_paths_to_edges (), 1396 CCcut_SRK_identify_ones (), 1397 CCcut_SRK_identify_one_triangles (), 1398 CCcut_SRK_identify_nodes (), 1399 CCcut_SRK_init_graph (), 1400 CCcut_SRK_free_graph (), 1401 CCcut_SRK_init_expinfo (), 1402 CCcut_SRK_free_expinfo (), 1403 CCcut_SRK_init_callback (); 1404 1405 int 1406 CCcut_SRK_buildgraph (), 1407 CCcut_SRK_subtour_shrink (), 1408 CCcut_SRK_identify_pr_edges (), 1409 CCcut_SRK_defluff (), 1410 CCcut_SRK_grab_edges (), 1411 CCcut_SRK_grab_nodes (), 1412 CCcut_SRK_trivial (), 1413 CCcut_SRK_expand (); 1414 1415 #endif 1416 1417 #endif /* __CUT_H */ 1418 /***************************************************************************/ 1419 /***************************************************************************/ 1420 /* */ 1421 /* PROTOTYPES FOR FILES IN EDGEGEN */ 1422 /* */ 1423 /***************************************************************************/ 1424 /***************************************************************************/ 1425 1426 #ifndef __EDGEGEN_H 1427 #define __EDGEGEN_H 1428 1429 1430 1431 /***************************************************************************/ 1432 /* */ 1433 /* edgegen.c */ 1434 /* */ 1435 /***************************************************************************/ 1436 1437 typedef struct CCedgegengroup { 1438 struct { 1439 int count; 1440 int quadnearest; 1441 int nearest; 1442 int nearest_start; 1443 int greedy_start; 1444 int random_start; 1445 int nkicks; 1446 } linkern; 1447 1448 struct { 1449 int twoopt_count; 1450 int twoopt5_count; 1451 int threeopt_count; 1452 int greedy; 1453 int nearest_count; 1454 int random_count; 1455 } tour; 1456 1457 struct { 1458 int wantit; 1459 int basic; 1460 int priced; 1461 } f2match; 1462 1463 struct { 1464 int number; 1465 int basic; 1466 int priced; 1467 } f2match_nearest; 1468 1469 int nearest; 1470 int quadnearest; 1471 int want_tree; 1472 int nearest_twomatch_count; 1473 int delaunay; 1474 int mlinkern; 1475 } CCedgegengroup; 1476 1477 1478 #ifdef CC_PROTOTYPE_ANSI 1479 1480 int 1481 CCedgegen_read (char *egname, CCedgegengroup *plan), 1482 CCedgegen_edges (CCedgegengroup *plan, int ncount, CCdatagroup *dat, 1483 double *wcoord, int *ecount, int **elist); 1484 void 1485 CCedgegen_init_edgegengroup (CCedgegengroup *plan); 1486 1487 #else 1488 1489 int 1490 CCedgegen_read (), 1491 CCedgegen_edges (); 1492 void 1493 CCedgegen_init_edgegengroup (); 1494 1495 #endif 1496 1497 1498 1499 /***************************************************************************/ 1500 /* */ 1501 /* xnear.c */ 1502 /* */ 1503 /***************************************************************************/ 1504 1505 typedef struct CCxnear { 1506 struct CCdatagroup dat; 1507 double *w; 1508 int *nodenames; 1509 int *invnames; 1510 } CCxnear; 1511 1512 1513 #ifdef CC_PROTOTYPE_ANSI 1514 1515 int 1516 CCedgegen_x_k_nearest (int ncount, int num, CCdatagroup *dat, 1517 double *wcoord, int wantlist, int *ecount, int **elist), 1518 CCedgegen_x_quadrant_k_nearest (int ncount, int num, CCdatagroup *dat, 1519 double *wcoord, int wantlist, int *ecount, int **elist), 1520 CCedgegen_x_node_k_nearest (CCxnear *xn, int n, int nearnum, int ncount, 1521 int *list), 1522 CCedgegen_x_node_quadrant_k_nearest (CCxnear *xn, int n, int nearnum, 1523 int ncount, int *list), 1524 CCedgegen_x_node_nearest (CCxnear *xn, int ncount, int ni, char *marks), 1525 CCedgegen_x_nearest_neighbor_tour (int ncount, int start, CCdatagroup *dat, 1526 int *outcycle, double *val), 1527 CCedgegen_junk_k_nearest (int ncount, int num, CCdatagroup *dat, 1528 double *wcoord, int wantlist, int *ecount, int **elist), 1529 CCedgegen_junk_node_k_nearest (CCdatagroup *dat, double *wcoord, int n, 1530 int nearnum, int ncount, int *list), 1531 CCedgegen_junk_node_nearest (CCdatagroup *dat, double *wcoord, int ncount, 1532 int n, char *marks), 1533 CCedgegen_junk_nearest_neighbor_tour (int ncount, int start, 1534 CCdatagroup *dat, int *outcycle, double *val), 1535 CCedgegen_xnear_build (int ncount, CCdatagroup *dat, double *wcoord, 1536 CCxnear *xn); 1537 1538 void 1539 CCedgegen_xnear_free (int ncount, CCxnear *xn); 1540 1541 #else 1542 1543 int 1544 CCedgegen_x_k_nearest (), 1545 CCedgegen_x_quadrant_k_nearest (), 1546 CCedgegen_x_node_k_nearest (), 1547 CCedgegen_x_node_quadrant_k_nearest (), 1548 CCedgegen_x_node_nearest (), 1549 CCedgegen_x_nearest_neighbor_tour (), 1550 CCedgegen_junk_k_nearest (), 1551 CCedgegen_junk_node_k_nearest (), 1552 CCedgegen_junk_node_nearest (), 1553 CCedgegen_junk_nearest_neighbor_tour (), 1554 CCedgegen_xnear_build (); 1555 void 1556 CCedgegen_xnear_free (); 1557 1558 #endif 1559 1560 #endif /* __EDGEGEN_H */ 1561 /***************************************************************************/ 1562 /***************************************************************************/ 1563 /* */ 1564 /* PROTOTYPES FOR FILES IN CUT */ 1565 /* */ 1566 /***************************************************************************/ 1567 /***************************************************************************/ 1568 1569 1570 #ifndef __TSP_H 1571 #define __TSP_H 1572 1573 1574 /*************** Tolerances for the LP and Cutting routines ***************/ 1575 1576 #define CCtsp_MIN_VIOL (0.00001) /* min violation for cut to be added to lp */ 1577 #define CCtsp_CUTS_NEXT_TOL (0.0001) /* to try next level */ 1578 #define CCtsp_CUTS_NEXT_ROUND (0.00000001) /* if improve is less, stop round */ 1579 #define CCtsp_PRICE_RCTHRESH (-0.00001) /* to add a bad edge */ 1580 #define CCtsp_PRICE_MAXPENALTY (0.49) /* penalty permitted in addbad */ 1581 #define CCtsp_PHASE1_RCTHRESH (-0.000000001) 1582 #define CCtsp_PHASE1_MAXPENALTY (0.00000001) 1583 #define CCtsp_EDGE_LIFE (1000000) /* 200 */ /* Large for subtour runs */ 1584 #define CCtsp_CUT_LIFE (50) 1585 #define CCtsp_CUT_BATCH (250) /* number of new cuts before lp optimize */ 1586 #define CCtsp_STORE_BATCH (50) /* number of new cuts before lp addrows */ 1587 #define CCtsp_INTTOL (0.0001) /* used to check if lp soln is integral */ 1588 1589 /************************** Branching Strategies ************************/ 1590 1591 #define CCtsp_BRANCH_MIDDLE 1 1592 #define CCtsp_BRANCH_STRONG 2 1593 1594 /*************************************************************************/ 1595 1596 #define CCtsp_LP_MAXDOUBLE 1e30 1597 1598 #define CCtsp_CUTRHS(c) (3*(c)->cliquecount - (c)->handlecount - 1) 1599 1600 typedef struct CCtsp_lpnode { 1601 int deg; 1602 int mark; 1603 struct CCtsp_lpadj *adj; 1604 } CCtsp_lpnode; 1605 1606 typedef struct CCtsp_lpedge { 1607 int ends[2]; /* ends[0] should always be < ends[1] */ 1608 int fixed; 1609 int branch; /* < 0 means set to 0 and > 0 means set to 1 */ 1610 int len; 1611 int age; 1612 int coef; /* should be maintained at zero */ 1613 int coefnext; /* should be maintained at -2 */ 1614 } CCtsp_lpedge; 1615 1616 typedef struct CCtsp_lpadj { 1617 int to; 1618 int edge; 1619 } CCtsp_lpadj; 1620 1621 typedef struct CCtsp_lpgraph { 1622 int ncount; 1623 int espace; 1624 int ecount; 1625 int nodemarker; 1626 CCtsp_lpnode *nodes; 1627 CCtsp_lpedge *edges; 1628 CCtsp_lpadj *adjspace; 1629 int adjstart; 1630 int adjend; 1631 } CCtsp_lpgraph; 1632 1633 typedef struct CCtsp_predge { 1634 int ends[2]; 1635 int len; 1636 double rc; 1637 } CCtsp_predge; 1638 1639 typedef struct CCtsp_pricegroup { 1640 int ncount; 1641 int espace; 1642 int ecount; 1643 CCtsp_lpnode *nodes; 1644 CCtsp_predge *edges; 1645 int cliquecount; 1646 struct CCtsp_lpclique *cliques; /* just a copy of the pointer */ 1647 CCtsp_lpgraph *graph; /* pointer to the copy in a CCtsp_lp */ 1648 CCtsp_lpadj *adjspace; 1649 double *node_pi; 1650 double *clique_pi; 1651 double penalty; 1652 } CCtsp_pricegroup; 1653 1654 typedef struct CCtsp_extraedge { 1655 int ends[2]; 1656 } CCtsp_extraedge; 1657 1658 typedef struct CCtsp_sparser { 1659 unsigned int node : 24; 1660 unsigned int mult : 8; 1661 } CCtsp_sparser; 1662 1663 typedef struct CCtsp_segment { 1664 int lo; 1665 int hi; 1666 } CCtsp_segment; 1667 1668 typedef struct CCtsp_lpclique { 1669 int segcount; 1670 struct CCtsp_segment *nodes; 1671 int hashnext; 1672 int refcount; 1673 } CCtsp_lpclique; 1674 1675 #define CC_FOREACH_NODE_IN_CLIQUE(i,c,tmp) \ 1676 for(tmp=0;tmp<(c).segcount;tmp++) \ 1677 for(i=(c).nodes[tmp].lo;i<=(c).nodes[tmp].hi;i++) 1678 1679 #define CCtsp_NEWCUT_AGE (-1) 1680 1681 typedef struct CCtsp_lpcut { 1682 int handlecount; 1683 int cliquecount; 1684 int modcount; 1685 int age; 1686 int rhs; 1687 char sense; 1688 char branch; 1689 int *cliques; 1690 struct CCtsp_sparser *mods; 1691 } CCtsp_lpcut; 1692 1693 typedef struct CCtsp_lpcut_in { 1694 int handlecount; 1695 int cliquecount; 1696 int rhs; 1697 char sense; 1698 char branch; 1699 CCtsp_lpclique *cliques; 1700 struct CCtsp_lpcut_in *next; 1701 struct CCtsp_lpcut_in *prev; 1702 } CCtsp_lpcut_in; 1703 1704 typedef struct CCtsp_lp_result { 1705 double ub; 1706 double lb; 1707 int ecount; 1708 int *elist; 1709 double *x; 1710 double *rc; 1711 } CCtsp_lp_result; 1712 1713 typedef struct CCtsp_lpcuts { 1714 int cutcount; 1715 int cliqueend; 1716 int cutspace; 1717 int cliquespace; 1718 int cliquehashsize; 1719 int cliquefree; 1720 int *cliquehash; 1721 CCtsp_lpcut *cuts; 1722 CCtsp_lpclique *cliques; 1723 CCgenhash *cuthash; 1724 char *tempcuthash; 1725 int tempcuthashsize; 1726 } CCtsp_lpcuts; 1727 1728 typedef struct CCtsp_bigdual { 1729 int cutcount; 1730 CCbigguy *node_pi; 1731 CCbigguy *cut_pi; 1732 } CCtsp_bigdual; 1733 1734 typedef struct CCtsp_tighten_info { 1735 int ncall; 1736 int nfail; 1737 int nadd; 1738 int nadd_tied; 1739 int ndel; 1740 int ndel_tied; 1741 double add_delta; 1742 double del_delta; 1743 double time; 1744 } CCtsp_tighten_info; 1745 1746 typedef struct CCtsp_branchobj { 1747 int depth; 1748 int rhs; 1749 int ends[2]; 1750 char sense; 1751 CCtsp_lpclique *clique; 1752 } CCtsp_branchobj; 1753 1754 typedef struct CCtsp_cutselect { 1755 int cutpool; 1756 int connect; 1757 int segments; 1758 int exactsubtour; 1759 int tighten_lp; 1760 int decker_lp; 1761 int teething_lp; 1762 int tighten_pool; 1763 int decker_pool; 1764 int teething_pool; 1765 int maxchunksize; 1766 int Xfastcuts; 1767 int Xexactsubtours; 1768 int Xslowcuts; 1769 int consecutiveones; 1770 int necklace; 1771 int usetighten; /* set to 1 to tighten before cuts are added */ 1772 int extra_connect; /* set to 1 to force a connected solution */ 1773 double nexttol; 1774 double roundtol; 1775 } CCtsp_cutselect; 1776 1777 /* nodes are reordered to match compression tour */ 1778 1779 typedef struct CCtsp_genadj { 1780 int deg; 1781 struct CCtsp_genadjobj *list; 1782 } CCtsp_genadj; 1783 1784 typedef struct CCtsp_genadjobj { 1785 int end; 1786 int len; 1787 } CCtsp_genadjobj; 1788 1789 typedef struct CCtsp_edgegenerator { 1790 double *node_piest; 1791 struct CCdatagroup *dg; 1792 int *supply; 1793 CCkdtree *kdtree; 1794 CCxnear *xnear; 1795 struct CCtsp_xnorm_pricer *xprice; 1796 CCtsp_genadjobj *adjobjspace; 1797 CCtsp_genadj *adj; 1798 int ncount; 1799 int nneighbors; 1800 int start; 1801 int current; 1802 int supplyhead; 1803 int supplycount; 1804 } CCtsp_edgegenerator; 1805 1806 typedef struct CCtsp_xnorm_pricer_val { 1807 double val; 1808 struct CCtsp_xnorm_pricer_val *next; 1809 struct CCtsp_xnorm_pricer_val *prev; 1810 int index; 1811 } CCtsp_xnorm_pricer_val; 1812 1813 typedef struct CCtsp_xnorm_pricer { 1814 CCdatagroup *dat; 1815 double *pi; 1816 int *order; 1817 CCtsp_xnorm_pricer_val *xminuspi_space; 1818 CCtsp_xnorm_pricer_val *xminuspi; 1819 int *invxminuspi; 1820 int ncount; 1821 } CCtsp_xnorm_pricer; 1822 1823 typedef struct CCtsp_lp { 1824 CCtsp_lpgraph graph; 1825 CCtsp_lpcuts cuts; 1826 CCtsp_lpcuts *pool; 1827 CClp lp; 1828 int *perm; 1829 CCdatagroup *dat; 1830 int fullcount; 1831 struct CCtsp_genadj *fulladj; 1832 struct CCtsp_genadjobj *fulladjspace; 1833 int nfixededges; 1834 int *fixededges; 1835 struct CCtsp_qsparsegroup *sparsifier; 1836 int edge_life; 1837 int cut_life; 1838 char *name; 1839 int id; 1840 int parent_id; 1841 int root; 1842 double upperbound; 1843 double lowerbound; 1844 CCbigguy exact_lowerbound; 1845 CCtsp_bigdual *exact_dual; 1846 int infeasible; 1847 int full_edges_valid; 1848 CClpbasis *basis; 1849 CCtsp_lpcut_in cutqueue; /* dummy entry for doubly-linked 1850 list */ 1851 CCtsp_lp_result result; 1852 CCtsp_tighten_info tighten_stats; 1853 int branchdepth; 1854 CCtsp_branchobj *branchhistory; 1855 } CCtsp_lp; 1856 1857 typedef struct CCtsp_lprow { 1858 int rowcnt; 1859 int nzcnt; 1860 char *sense; 1861 double *rhs; 1862 int *begin; /* offset into the array for start of row */ 1863 int indexspace; 1864 int *indices; /* the column indices of the row entries */ 1865 int entryspace; 1866 double *entries; /* the matrix entries */ 1867 } CCtsp_lprow; 1868 1869 1870 1871 /***************************************************************************/ 1872 /* */ 1873 /* tsp_lp.c */ 1874 /* */ 1875 /***************************************************************************/ 1876 1877 #ifdef CC_PROTOTYPE_ANSI 1878 1879 int 1880 CCtsp_cutting_loop (CCtsp_lp *lp, CCtsp_cutselect *sel, int savelp), 1881 CCtsp_subtour_loop (CCtsp_lp *lp), 1882 CCtsp_pricing_loop (CCtsp_lp *lp, double *bnd), 1883 CCtsp_init_cutselect (CCtsp_lp *lp, CCtsp_cutselect *s), 1884 CCtsp_call_x_heuristic (CCtsp_lp *lp, double *val, int *outcyc), 1885 CCtsp_bb_cutting (char *probname, int probnum, int ncount, 1886 CCdatagroup *dat, int *ptour, double *upbound, CCtsp_lpcuts *pool, 1887 CCtsp_cutselect *sel, double *val, int *prune, int *foundtour, 1888 int *besttour), 1889 CCtsp_init_lp (CCtsp_lp **lp, char *probname, int probnum, 1890 char *probfilename, int ncount, CCdatagroup *dat, int ecount, 1891 int *elist, int *elen, int excount, int *exlist, int *exlen, 1892 int exvalid, int *ptour, double initial_ub, CCtsp_lpcuts *pool), 1893 CCtsp_bb_init_lp (CCtsp_lp **lp, char *probname, int probnum, 1894 int ncount, CCdatagroup *dat, int *ptour, double initial_ub, 1895 CCtsp_lpcuts *pool), 1896 CCtsp_get_lp_result (CCtsp_lp *lp, double *lb, double *ub, int *ecount, 1897 int **elist, double **x, double **rc, double **node_pi, 1898 double **cut_pi), 1899 CCtsp_process_cuts (CCtsp_lp *lp, int *pnadded, int tighten), 1900 CCtsp_add_cut_to_cutlist (CCtsp_lpcuts *cuts, CCtsp_lpcut *c), 1901 CCtsp_add_cut (CCtsp_lp *lp, CCtsp_lpcut_in *d, CCtsp_lprow *cr), 1902 CCtsp_lpcut_in_nzlist (CCtsp_lpgraph *g, CCtsp_lpcut_in *c), 1903 CCtsp_add_nzlist_to_lp (CCtsp_lp *lp, int nzlist, int rhs, char sense, 1904 CCtsp_lprow *cr), 1905 CCtsp_add_vars_to_lp (CCtsp_lp *lp, CCtsp_predge *prlist, int n), 1906 CCtsp_update_result (CCtsp_lp *lp), 1907 CCtsp_infeas_recover (CCtsp_lp *lp), 1908 CCtsp_test_cut_branch (CCtsp_lp *lp, CCtsp_lpclique *c, double *down, 1909 double *up), 1910 CCtsp_register_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut_in *c, 1911 CCtsp_lpcut *new), 1912 CCtsp_addbad_variables (CCtsp_lp *lp, struct CCtsp_edgegenerator *eg, 1913 double *ppenalty, int *pnadded, double rcthresh, 1914 double maxpenalty, int phase1, int *feasible), 1915 CCtsp_eliminate_variables (CCtsp_lp *lp), 1916 CCtsp_build_lpgraph (CCtsp_lpgraph *g, int ncount, int ecount, 1917 int *elist, int *elen), 1918 CCtsp_build_lpadj (CCtsp_lpgraph *g, int estart, int eend), 1919 CCtsp_add_multiple_rows (CCtsp_lp *lp, CCtsp_lprow *cr), 1920 CCtsp_delete_cut (CCtsp_lp *lp, int i), 1921 CCtsp_find_edge (CCtsp_lpgraph *g, int from, int to), 1922 CCtsp_find_branch (CCtsp_lp *lp, int nwant, int *ngot, 1923 CCtsp_branchobj **bobj, double *val, int **cyc, int usecliques), 1924 CCtsp_bb_find_branch (char *probname, int probnum, int ncount, 1925 CCdatagroup *dat, int *ptour, double *upperbound, 1926 CCtsp_lpcuts *pool, CCtsp_branchobj **b, int usecliques, 1927 int *foundtour, int *besttour), 1928 CCtsp_check_integral (CCtsp_lp *lp, double *val, int **cyc, int *yesno), 1929 CCtsp_find_branch_edge (CCtsp_lp *lp, int *n0, int *n1, double *val, 1930 int **cyc, int branchtype), 1931 CCtsp_find_branch_cliques (CCtsp_lp *lp, int nwant, int *ngot, 1932 CCtsp_lpclique **bcliques, double **bval), 1933 CCtsp_execute_branch (CCtsp_lp *lp, CCtsp_branchobj *b), 1934 CCtsp_execute_unbranch (CCtsp_lp *lp, CClpbasis *basis), 1935 CCtsp_splitprob (CCtsp_lp *lp, CCtsp_branchobj *b, int child0, int child1), 1936 CCtsp_bb_splitprob (char *probname, int probnum, int ncount, 1937 CCdatagroup *dat, int *ptour, double initial_ub, CCtsp_lpcuts *pool, 1938 CCtsp_branchobj *b, int child0, int child1, double *val0, 1939 double *val1, int *prune0, int *prune1), 1940 CCtsp_dumptour (int ncount, CCdatagroup *dat, int *perm, char *probname, 1941 int *tour), 1942 CCtsp_add_branchhistory_to_lp (CCtsp_lp *lp), 1943 CCtsp_easy_dfs_brancher (CCtsp_lp *lp, CCtsp_cutselect *sel, int depth, 1944 double *upbound, int *bbcount, int usecliques, int *besttour), 1945 CCtsp_bfs_brancher (char *probname, int id, double lowerbound, 1946 CCtsp_cutselect *sel, double *upbound, int *bbcount, int usecliques, 1947 CCdatagroup *mydat, int *ptour, CCtsp_lpcuts *pool, int ncount, 1948 int *besttour), 1949 CCtsp_do_interactive_branch (CCtsp_lp *lp), 1950 CCtsp_inspect_full_edges (CCtsp_lp *lp), 1951 CCtsp_read_probfile (CCtsp_lp *lp, char *fname, int ncount), 1952 CCtsp_read_probfile_id (CCtsp_lp *lp, char *fname, int id, int ncount), 1953 CCtsp_write_probfile_sav (CCtsp_lp *lp), 1954 CCtsp_write_probfile_id (CCtsp_lp *lp), 1955 CCtsp_dump_x (CCtsp_lp *lp, char *fname), 1956 CCtsp_exact_price (CCtsp_lp *lp, CCbigguy *bound, int phase1), 1957 CCtsp_edge_elimination (CCtsp_lp *lp), 1958 CCtsp_exact_dual (CCtsp_lp *lp), 1959 CCtsp_verify_infeasible_lp (CCtsp_lp *lp, int *yesno), 1960 CCtsp_verify_lp_prune (CCtsp_lp *lp, int *yesno), 1961 CCtsp_tighten_lpcut_in (CCtsp_lpgraph *g, CCtsp_lpcut_in *c, 1962 double *x, CCtsp_lpcut_in *d, CCtsp_tighten_info *stats, 1963 double *pimprove), 1964 CCtsp_tighten_lpcut (CCtsp_lpgraph *g, CCtsp_lpclique *cliques, 1965 CCtsp_lpcut *c, double *x, CCtsp_lpcut_in *d, 1966 CCtsp_tighten_info *stats, double *pimprove), 1967 CCtsp_test_pure_comb (int ncount, CCtsp_lpcut_in *c, int *yes_no, 1968 int *handle), 1969 CCtsp_test_pseudocomb (int ncount, CCtsp_lpcut_in *c, int handle, 1970 int *yes_no), 1971 CCtsp_test_teeth_disjoint (int ncount, CCtsp_lpcut_in *c, int handle, 1972 int *yes_no), 1973 CCtsp_find_pure_handle (int ncount, CCtsp_lpcut_in *c, int *handle), 1974 CCtsp_comb_to_double_decker (CCtsp_lpgraph *g, double *x, 1975 CCtsp_lpcut_in *c, CCtsp_lpcut_in **d), 1976 CCtsp_teething (CCtsp_lpgraph *g, double *x, CCtsp_lpcut_in *cut, 1977 CCtsp_lpcut_in **newcut), 1978 CCtsp_init_cutpool (int ncount, char *poolfilename, CCtsp_lpcuts **pool), 1979 CCtsp_write_cutpool (int ncount, char *poolfilename, CCtsp_lpcuts *pool), 1980 CCtsp_search_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcut_in **cuts, 1981 int *cutcount, int ncount, int ecount, int *elist, double *x), 1982 CCtsp_search_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques, 1983 int *cliquecount, int ncount, int ecount, int *elist, double *x, 1984 double maxdelta, int maxcliques, double **cliquevals), 1985 CCtsp_branch_cutpool_cliques (CCtsp_lpcuts *pool, CCtsp_lpclique **cliques, 1986 int *cliquecount, int ncount, int ecount, int *elist, double *x, 1987 int nwant, double **cliquevals), 1988 CCtsp_add_to_cutpool (CCtsp_lpcuts *pool, CCtsp_lpcuts *cuts, 1989 CCtsp_lpcut *c), 1990 CCtsp_add_to_cutpool_lpcut_in (CCtsp_lpcuts *pool, CCtsp_lpcut_in *cut), 1991 CCtsp_display_cutpool (CCtsp_lpcuts *pool), 1992 CCtsp_price_cuts (CCtsp_lpcuts *pool, int ncount, int ecount, int *elist, 1993 double *x, double *cutval), 1994 CCtsp_clique_to_array (CCtsp_lpclique *c, int **ar, int *count), 1995 CCtsp_clique_delta (CCtsp_lpgraph *g, double *x, CCtsp_lpclique *c, 1996 double *delta), 1997 CCtsp_x_greedy_tour (CCdatagroup *dat, int ncount, int ecount, int *elist, 1998 double *x, int *cyc, double *val), 1999 CCtsp_x_greedy_tour_lk (CCdatagroup *dat, int ncount, int ecount, 2000 int *elist, double *x, int *cyc, double *val); 2001 2002 void 2003 CCtsp_init_tsp_lp_struct (CCtsp_lp *lp), 2004 CCtsp_free_tsp_lp_struct (CCtsp_lp **lp), 2005 CCtsp_add_cuts_to_queue (CCtsp_lp *lp, CCtsp_lpcut_in **c), 2006 CCtsp_delete_cut_from_cutlist (CCtsp_lpcuts *cuts, int ind), 2007 CCtsp_init_lprow (CCtsp_lprow *cr), 2008 CCtsp_free_lprow (CCtsp_lprow *cr), 2009 CCtsp_unregister_cliques (CCtsp_lpcuts *cuts, CCtsp_lpcut *c), 2010 CCtsp_free_cutpool (CCtsp_lpcuts **pool), 2011 CCtsp_init_lpgraph_struct (CCtsp_lpgraph *g), 2012 CCtsp_free_lpgraph (CCtsp_lpgraph *g), 2013 CCtsp_free_lpcut_in (CCtsp_lpcut_in *c), 2014 CCtsp_free_lpclique (CCtsp_lpclique *c), 2015 CCtsp_free_bigdual (CCtsp_bigdual **d), 2016 CCtsp_init_branchobj (CCtsp_branchobj *b), 2017 CCtsp_free_branchobj (CCtsp_branchobj *b), 2018 CCtsp_print_branchhistory (CCtsp_lp *lp), 2019 CCtsp_init_tighten_info (CCtsp_tighten_info *stats), 2020 CCtsp_print_tighten_info (CCtsp_tighten_info *stats), 2021 CCtsp_mark_clique (CCtsp_lpclique *c, int *marks, int marker), 2022 CCtsp_mark_clique_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpclique *c, 2023 int *marks, int marker), 2024 CCtsp_mark_cut (CCtsp_lpcut_in *c, int *marks, int marker), 2025 CCtsp_mark_cut_and_neighbors (CCtsp_lpgraph *g, CCtsp_lpcut_in *c, 2026 int *marks, int marker), 2027 CCtsp_mark_clique_and_neighbors_double (CCtsp_lpgraph *g, CCtsp_lpclique *c, 2028 double *marks, double marker), 2029 CCtsp_is_clique_marked (CCtsp_lpclique *c, int *marks, int marker, 2030 int *yes_no), 2031 CCtsp_clique_count (CCtsp_lpclique *c, int *count); 2032 2033 2034 double 2035 CCtsp_cutprice (CCtsp_lpgraph *g, CCtsp_lpcut_in *c, double *x); 2036 2037 #else 2038 2039 int 2040 CCtsp_cutting_loop (), 2041 CCtsp_subtour_loop (), 2042 CCtsp_pricing_loop (), 2043 CCtsp_init_cutselect (), 2044 CCtsp_call_x_heuristic (), 2045 CCtsp_bb_cutting (), 2046 CCtsp_init_lp (), 2047 CCtsp_bb_init_lp (), 2048 CCtsp_get_lp_result (), 2049 CCtsp_process_cuts (), 2050 CCtsp_add_cut_to_cutlist (), 2051 CCtsp_add_cut (), 2052 CCtsp_lpcut_in_nzlist (), 2053 CCtsp_add_nzlist_to_lp (), 2054 CCtsp_add_vars_to_lp (), 2055 CCtsp_update_result (), 2056 CCtsp_infeas_recover (), 2057 CCtsp_test_cut_branch (), 2058 CCtsp_register_cliques (), 2059 CCtsp_addbad_variables (), 2060 CCtsp_eliminate_variables (), 2061 CCtsp_build_lpgraph (), 2062 CCtsp_build_lpadj (), 2063 CCtsp_add_multiple_rows (), 2064 CCtsp_delete_cut (), 2065 CCtsp_find_edge (), 2066 CCtsp_find_branch (), 2067 CCtsp_bb_find_branch (), 2068 CCtsp_check_integral (), 2069 CCtsp_find_branch_edge (), 2070 CCtsp_find_branch_cliques (), 2071 CCtsp_execute_branch (), 2072 CCtsp_execute_unbranch (), 2073 CCtsp_splitprob (), 2074 CCtsp_bb_splitprob (), 2075 CCtsp_dumptour (), 2076 CCtsp_add_branchhistory_to_lp (), 2077 CCtsp_easy_dfs_brancher (), 2078 CCtsp_bfs_brancher (), 2079 CCtsp_do_interactive_branch (), 2080 CCtsp_inspect_full_edges (), 2081 CCtsp_read_probfile (), 2082 CCtsp_read_probfile_id (), 2083 CCtsp_write_probfile_sav (), 2084 CCtsp_write_probfile_id (), 2085 CCtsp_dump_x (), 2086 CCtsp_exact_price (), 2087 CCtsp_edge_elimination (), 2088 CCtsp_exact_dual (), 2089 CCtsp_verify_infeasible_lp (), 2090 CCtsp_verify_lp_prune (), 2091 CCtsp_tighten_lpcut_in (), 2092 CCtsp_tighten_lpcut (), 2093 CCtsp_test_pure_comb (), 2094 CCtsp_test_pseudocomb (), 2095 CCtsp_test_teeth_disjoint (), 2096 CCtsp_find_pure_handle (), 2097 CCtsp_comb_to_double_decker (), 2098 CCtsp_teething (), 2099 CCtsp_init_cutpool (), 2100 CCtsp_write_cutpool (), 2101 CCtsp_search_cutpool (), 2102 CCtsp_search_cutpool_cliques (), 2103 CCtsp_branch_cutpool_cliques (), 2104 CCtsp_add_to_cutpool (), 2105 CCtsp_add_to_cutpool_lpcut_in (), 2106 CCtsp_display_cutpool (), 2107 CCtsp_price_cuts (), 2108 CCtsp_clique_to_array (), 2109 CCtsp_clique_delta (), 2110 CCtsp_x_greedy_tour (), 2111 CCtsp_x_greedy_tour_lk (); 2112 2113 void 2114 CCtsp_init_tsp_lp_struct (), 2115 CCtsp_free_tsp_lp_struct (), 2116 CCtsp_add_cuts_to_queue (), 2117 CCtsp_delete_cut_from_cutlist (), 2118 CCtsp_init_lprow (), 2119 CCtsp_free_lprow (), 2120 CCtsp_unregister_cliques (), 2121 CCtsp_free_cutpool (), 2122 CCtsp_init_lpgraph_struct (), 2123 CCtsp_free_lpgraph (), 2124 CCtsp_free_lpcut_in (), 2125 CCtsp_free_lpclique (), 2126 CCtsp_free_bigdual (), 2127 CCtsp_init_branchobj (), 2128 CCtsp_free_branchobj (), 2129 CCtsp_print_branchhistory (), 2130 CCtsp_init_tighten_info (), 2131 CCtsp_print_tighten_info (), 2132 CCtsp_mark_clique (), 2133 CCtsp_mark_clique_and_neighbors (), 2134 CCtsp_mark_cut (), 2135 CCtsp_mark_cut_and_neighbors (), 2136 CCtsp_mark_clique_and_neighbors_double (), 2137 CCtsp_is_clique_marked (), 2138 CCtsp_clique_count (); 2139 2140 2141 double 2142 CCtsp_cutprice (); 2143 2144 #endif 2145 2146 /***************************************************************************/ 2147 /* */ 2148 /* cliqhash.c */ 2149 /* */ 2150 /***************************************************************************/ 2151 2152 #ifdef CC_PROTOTYPE_ANSI 2153 2154 int 2155 CCtsp_init_cliquehash (CCtsp_lpcuts *cuts, int size), 2156 CCtsp_register_clique (CCtsp_lpcuts *cuts, CCtsp_lpclique *c); 2157 2158 void 2159 CCtsp_free_cliquehash (CCtsp_lpcuts *cuts), 2160 CCtsp_unregister_clique (CCtsp_lpcuts *cuts, int c); 2161 2162 #else 2163 2164 int 2165 CCtsp_init_cliquehash (), 2166 CCtsp_register_clique (); 2167 2168 void 2169 CCtsp_free_cliquehash (), 2170 CCtsp_unregister_clique (); 2171 2172 #endif 2173 2174 2175 2176 /***************************************************************************/ 2177 /* */ 2178 /* cutcall.c */ 2179 /* */ 2180 /***************************************************************************/ 2181 2182 typedef struct cutinfo { 2183 CC_SRKexpinfo expand; 2184 CCtsp_lpcut_in **clist; 2185 CCtsp_lpcut_in *current; 2186 int *cutcount; 2187 } cutinfo; 2188 2189 #ifdef CC_PROTOTYPE_ANSI 2190 2191 int 2192 CCtsp_connect_cuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 2193 int ecount, int *elist, double *x), 2194 CCtsp_segment_cuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 2195 int ecount, int *elist, double *x), 2196 CCtsp_exact_subtours (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, 2197 int ecount, int *elist, double *x), 2198 CCtsp_tighten_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 2199 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 2200 int *elist, double *x, double testtol, int maxcuts), 2201 CCtsp_double_decker_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 2202 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 2203 int *elist, double *x, double testtol, int maxcuts), 2204 CCtsp_teething_lp (CCtsp_lpcuts *cuts, CCtsp_tighten_info *stats, 2205 CCtsp_lpcut_in **cutsout, int *cutcount, int ncount, int ecount, 2206 int *elist, double *x, double testtol, int maxcuts), 2207 CCtsp_copy_lpcut_in (CCtsp_lpcut_in *c, CCtsp_lpcut_in *new), 2208 CCtsp_segment_to_subtour (CCtsp_lpcut_in **cut, int a, int b), 2209 CCtsp_array_to_subtour (CCtsp_lpcut_in **cut, int *ar, int acount), 2210 CCtsp_array_to_lpclique (int *ar, int acount, CCtsp_lpclique *cliq), 2211 CCtsp_seglist_to_lpclique (int nseg, int *list, CCtsp_lpclique *cliq), 2212 CCtsp_add_node_to_lpclique (CCtsp_lpclique *cin, CCtsp_lpclique *cout, 2213 int n), 2214 CCtsp_delete_node_from_lpclique (CCtsp_lpclique *cin, 2215 CCtsp_lpclique *cout, int n), 2216 CCtsp_lpcut_to_lpcut_in (CCtsp_lpcuts *cuts, CCtsp_lpcut *c, 2217 CCtsp_lpcut_in *new), 2218 CCtsp_copy_lpclique (CCtsp_lpclique *c, CCtsp_lpclique *new), 2219 CCtsp_file_cuts (char *cutfile, CCtsp_lpcut_in **cuts, int *cutcount, 2220 int ncount, int *tour), 2221 CCtsp_file_cuts_write (char *cutfile, CCtsp_lpcuts *cuts, int *tour), 2222 CCtsp_buildcut_begin (cutinfo *cuts, int init_cliquecount), 2223 CCtsp_buildcut_addclique (cutinfo *cuts, int *arr, int size, int handle); 2224 2225 void 2226 CCtsp_init_lpcut_in (CCtsp_lpcut_in *c), 2227 CCtsp_init_lpclique (CCtsp_lpclique *c), 2228 CCtsp_print_lpcut_in (CCtsp_lpcut_in *c), 2229 CCtsp_print_lpclique (CCtsp_lpclique *c), 2230 CCtsp_lpclique_compare (CCtsp_lpclique *a, CCtsp_lpclique *b, int *diff), 2231 CCtsp_buildcut_abort (cutinfo *cuts), 2232 CCtsp_buildcut_finish (cutinfo *cuts, int rhs); 2233 2234 #else 2235 2236 int 2237 CCtsp_connect_cuts (), 2238 CCtsp_segment_cuts (), 2239 CCtsp_exact_subtours (), 2240 CCtsp_tighten_lp (), 2241 CCtsp_double_decker_lp (), 2242 CCtsp_teething_lp (), 2243 CCtsp_copy_lpcut_in (), 2244 CCtsp_segment_to_subtour (), 2245 CCtsp_array_to_subtour (), 2246 CCtsp_array_to_lpclique (), 2247 CCtsp_seglist_to_lpclique (), 2248 CCtsp_add_node_to_lpclique (), 2249 CCtsp_delete_node_from_lpclique (), 2250 CCtsp_lpcut_to_lpcut_in (), 2251 CCtsp_copy_lpclique (), 2252 CCtsp_file_cuts (), 2253 CCtsp_file_cuts_write (), 2254 CCtsp_buildcut_begin (), 2255 CCtsp_buildcut_addclique (); 2256 2257 void 2258 CCtsp_init_lpcut_in (), 2259 CCtsp_init_lpclique (), 2260 CCtsp_print_lpcut_in (), 2261 CCtsp_print_lpclique (), 2262 CCtsp_lpclique_compare (), 2263 CCtsp_buildcut_abort (), 2264 CCtsp_buildcut_finish (); 2265 2266 #endif 2267 2268 2269 2270 /***************************************************************************/ 2271 /* */ 2272 /* edgemap.c */ 2273 /* */ 2274 /***************************************************************************/ 2275 2276 typedef struct CCtsp_edgeinf { 2277 int ends[2]; 2278 int val; 2279 struct CCtsp_edgeinf *next; 2280 } CCtsp_edgeinf; 2281 2282 typedef struct CCtsp_edgehash { 2283 struct CCtsp_edgeinf **table; 2284 unsigned int size; 2285 unsigned int mult; 2286 } CCtsp_edgehash; 2287 2288 2289 #ifdef CC_PROTOTYPE_ANSI 2290 2291 int 2292 CCtsp_edgehash_init (CCtsp_edgehash *h, int size), 2293 CCtsp_edgehash_add (CCtsp_edgehash *h, int end1, int end2, int val), 2294 CCtsp_edgehash_del (CCtsp_edgehash *h, int end1, int end2), 2295 CCtsp_edgehash_find (CCtsp_edgehash *h, int end1, int end2); 2296 2297 void 2298 CCtsp_edgehash_delall (CCtsp_edgehash *h), 2299 CCtsp_edgehash_free (CCtsp_edgehash *h); 2300 2301 #else 2302 2303 int 2304 CCtsp_edgehash_init (), 2305 CCtsp_edgehash_add (), 2306 CCtsp_edgehash_del (), 2307 CCtsp_edgehash_find (); 2308 2309 void 2310 CCtsp_edgehash_delall (), 2311 CCtsp_edgehash_free (); 2312 2313 #endif 2314 2315 2316 /***************************************************************************/ 2317 /* */ 2318 /* generate.c */ 2319 /* */ 2320 /***************************************************************************/ 2321 2322 #define CCtsp_PRICE_COMPLETE_GRAPH -1 2323 #define CCtsp_GEN_PRICE_EPSILON 0.0001 /* 0.0000001 */ 2324 #define CCtsp_GEN_USE_ADJ 50 /* Cutoff for using explicit adj list */ 2325 2326 #ifdef CC_PROTOTYPE_ANSI 2327 2328 void 2329 CCtsp_free_edgegenerator (CCtsp_edgegenerator *eg); 2330 2331 int 2332 CCtsp_init_edgegenerator (CCtsp_edgegenerator *eg, int ncount, 2333 CCdatagroup *dg, CCtsp_genadj *adj, int nneighbors), 2334 CCtsp_reset_edgegenerator (CCtsp_edgegenerator *eg, double *node_piest), 2335 CCtsp_generate_edges (CCtsp_edgegenerator *eg, int nwant, int *pngot, 2336 int *elist, int *elen, int *finished), 2337 CCtsp_edgelist_to_genadj (int ncount, int ecount, int *elist, int *elen, 2338 CCtsp_genadj **adj, CCtsp_genadjobj **adjobjspace); 2339 2340 #else 2341 2342 void 2343 CCtsp_free_edgegenerator (); 2344 2345 int 2346 CCtsp_init_edgegenerator (), 2347 CCtsp_reset_edgegenerator (), 2348 CCtsp_generate_edges (), 2349 CCtsp_edgelist_to_genadj (); 2350 2351 #endif 2352 2353 2354 2355 /***************************************************************************/ 2356 /* */ 2357 /* prob_io.c */ 2358 /* */ 2359 /***************************************************************************/ 2360 2361 #define CCtsp_PROB_IO_VERSION 1 2362 #define CCtsp_PROB_FILE_NAME_LEN 128 2363 2364 #define CCtsp_PROB_IO_CUTS_VERSION_BASE -1000 2365 #define CCtsp_PROB_IO_CUTS_VERSION -1001 /* Should be <= BASE (-1000) */ 2366 2367 typedef struct CCtsp_PROB_FILE { 2368 CC_SFILE *f; 2369 char name[CCtsp_PROB_FILE_NAME_LEN]; 2370 int id; 2371 int parent; 2372 double ub; 2373 double lb; 2374 CCbigguy exactlb; 2375 int nnodes; 2376 int child0; 2377 int child1; 2378 int real; /* Set to 1 when we know this is a real child */ 2379 int processed; 2380 int infeasible; 2381 struct { 2382 int dat; 2383 int edge; 2384 int fulladj; 2385 int cut; 2386 int tour; 2387 int basis; 2388 int norms; 2389 int fix; 2390 int exactdual; 2391 int history; 2392 } offsets; 2393 } CCtsp_PROB_FILE; 2394 2395 2396 #ifdef CC_PROTOTYPE_ANSI 2397 2398 CCtsp_PROB_FILE 2399 *CCtsp_prob_read (char *f, int n), 2400 *CCtsp_prob_read_name (char *f), 2401 *CCtsp_prob_write (char *f, int n), 2402 *CCtsp_prob_write_name (char *fname, char *pname); 2403 2404 int 2405 CCtsp_prob_file_delete (char *f, int n), 2406 CCtsp_prob_getname (CCtsp_PROB_FILE *p, char *name), 2407 CCtsp_prob_getid (CCtsp_PROB_FILE *p, int *id), 2408 CCtsp_prob_getparent (CCtsp_PROB_FILE *p, int *parent), 2409 CCtsp_prob_getub (CCtsp_PROB_FILE *p, double *ub), 2410 CCtsp_prob_getlb (CCtsp_PROB_FILE *p, double *lb), 2411 CCtsp_prob_getexactlb (CCtsp_PROB_FILE *p, CCbigguy *lb), 2412 CCtsp_prob_getnnodes (CCtsp_PROB_FILE *p, int *nnodes), 2413 CCtsp_prob_getchildren (CCtsp_PROB_FILE *p, int *child0, int *child1), 2414 CCtsp_prob_getreal (CCtsp_PROB_FILE *p, int *real), 2415 CCtsp_prob_getprocessed (CCtsp_PROB_FILE *p, int *processed), 2416 CCtsp_prob_getinfeasible (CCtsp_PROB_FILE *p, int *infeasible), 2417 CCtsp_prob_gettour (CCtsp_PROB_FILE *p, int **tour), 2418 CCtsp_prob_getedges (CCtsp_PROB_FILE *p, int *nedges, int **elist, 2419 int **elen), 2420 CCtsp_prob_getcuts (CCtsp_PROB_FILE *p, CC_SFILE *s, CCtsp_lpcuts *cuts), 2421 CCtsp_prob_getbasis (CCtsp_PROB_FILE *p, int *ccount, int *rcount, 2422 int **cstat, int **rstat), 2423 CCtsp_prob_getnorms (CCtsp_PROB_FILE *p, int *rcount, double **dnorm), 2424 CCtsp_prob_getfulladj (CCtsp_PROB_FILE *p, int ncount, int *fullcount, 2425 CCtsp_genadj **adj, CCtsp_genadjobj **adjspace), 2426 CCtsp_prob_getfixed (CCtsp_PROB_FILE *p, int *ecount, int **elist), 2427 CCtsp_prob_getexactdual (CCtsp_PROB_FILE *p, int ncount, 2428 CCtsp_bigdual **d), 2429 CCtsp_prob_gethistory (CCtsp_PROB_FILE *p, int *depth, 2430 CCtsp_branchobj **history), 2431 CCtsp_prob_rclose (CCtsp_PROB_FILE *p), 2432 2433 CCtsp_prob_putname (CCtsp_PROB_FILE *p, char *name), 2434 CCtsp_prob_putid (CCtsp_PROB_FILE *p, int id), 2435 CCtsp_prob_putparent (CCtsp_PROB_FILE *p, int parent), 2436 CCtsp_prob_putub (CCtsp_PROB_FILE *p, double ub), 2437 CCtsp_prob_putlb (CCtsp_PROB_FILE *p, double lb), 2438 CCtsp_prob_putexactlb (CCtsp_PROB_FILE *p, CCbigguy lb), 2439 CCtsp_prob_putnnodes (CCtsp_PROB_FILE *p, int nnodes), 2440 CCtsp_prob_putchildren (CCtsp_PROB_FILE *p, int child0, int child1), 2441 CCtsp_prob_putreal (CCtsp_PROB_FILE *p, int real), 2442 CCtsp_prob_putprocessed (CCtsp_PROB_FILE *p, int processed), 2443 CCtsp_prob_putinfeasible (CCtsp_PROB_FILE *p, int infeasible), 2444 CCtsp_prob_puttour (CCtsp_PROB_FILE *p, int *tour), 2445 CCtsp_prob_putedges (CCtsp_PROB_FILE *p, int nedges, int *elist, int *elen), 2446 CCtsp_prob_putcuts (CCtsp_PROB_FILE *p, CC_SFILE *s, CCtsp_lpcuts *cuts), 2447 CCtsp_prob_putbasis (CCtsp_PROB_FILE *p, int ccount, int rcount, int *cstat, 2448 int *rstat), 2449 CCtsp_prob_putnorms (CCtsp_PROB_FILE *p, int rcount, double *dnorm), 2450 CCtsp_prob_putfulladj (CCtsp_PROB_FILE *p, int ncount, int fullcount, 2451 CCtsp_genadj *adj), 2452 CCtsp_prob_putfixed (CCtsp_PROB_FILE *p, int ecount, int *elist), 2453 CCtsp_prob_putexactdual (CCtsp_PROB_FILE *p, CCtsp_bigdual *d, int ncount), 2454 CCtsp_prob_puthistory (CCtsp_PROB_FILE *p, int depth, 2455 CCtsp_branchobj *history), 2456 CCtsp_prob_wclose (CCtsp_PROB_FILE *p); 2457 2458 #else 2459 2460 CCtsp_PROB_FILE 2461 *CCtsp_prob_read (), 2462 *CCtsp_prob_read_name (), 2463 *CCtsp_prob_write (), 2464 *CCtsp_prob_write_name (); 2465 2466 int 2467 CCtsp_prob_file_delete (), 2468 CCtsp_prob_getname (), 2469 CCtsp_prob_getid (), 2470 CCtsp_prob_getparent (), 2471 CCtsp_prob_getub (), 2472 CCtsp_prob_getlb (), 2473 CCtsp_prob_getexactlb (), 2474 CCtsp_prob_getnnodes (), 2475 CCtsp_prob_getchildren (), 2476 CCtsp_prob_getreal (), 2477 CCtsp_prob_getprocessed (), 2478 CCtsp_prob_getinfeasible (), 2479 CCtsp_prob_gettour (), 2480 CCtsp_prob_getedges (), 2481 CCtsp_prob_getcuts (), 2482 CCtsp_prob_getbasis (), 2483 CCtsp_prob_getnorms (), 2484 CCtsp_prob_getfulladj (), 2485 CCtsp_prob_getfixed (), 2486 CCtsp_prob_getexactdual (), 2487 CCtsp_prob_gethistory (), 2488 CCtsp_prob_rclose (), 2489 2490 CCtsp_prob_putname (), 2491 CCtsp_prob_putid (), 2492 CCtsp_prob_putparent (), 2493 CCtsp_prob_putub (), 2494 CCtsp_prob_putlb (), 2495 CCtsp_prob_putexactlb (), 2496 CCtsp_prob_putnnodes (), 2497 CCtsp_prob_putchildren (), 2498 CCtsp_prob_putreal (), 2499 CCtsp_prob_putprocessed (), 2500 CCtsp_prob_putinfeasible (), 2501 CCtsp_prob_puttour (), 2502 CCtsp_prob_putedges (), 2503 CCtsp_prob_putcuts (), 2504 CCtsp_prob_putbasis (), 2505 CCtsp_prob_putnorms (), 2506 CCtsp_prob_putfulladj (), 2507 CCtsp_prob_putfixed (), 2508 CCtsp_prob_putexactdual (), 2509 CCtsp_prob_puthistory (), 2510 CCtsp_prob_wclose (); 2511 2512 #endif 2513 2514 2515 2516 /***************************************************************************/ 2517 /* */ 2518 /* qsparse.c */ 2519 /* */ 2520 /***************************************************************************/ 2521 2522 typedef struct CCtsp_qsparsegroup { 2523 CCdheap *add_queue; /* An empty heap will be maintained */ 2524 CCdheap *sub_queue; /* An empty heap will be maintained */ 2525 int *count_m1; /* The array will be maintained at 0 */ 2526 int *count_non0; /* The array will be maintained at 0 */ 2527 int *count_1; /* The array will be maintained at 0 */ 2528 int *on_add_queue; /* The array will be maintained at 0 */ 2529 int *on_sub_queue; /* The array will be maintained at 0 */ 2530 int *mults; /* The array will be maintained at 0 */ 2531 } CCtsp_qsparsegroup; 2532 2533 #ifdef CC_PROTOTYPE_ANSI 2534 2535 void 2536 CCtsp_free_qsparsify (CCtsp_qsparsegroup **pqs); 2537 int 2538 CCtsp_qsparsify (CCtsp_qsparsegroup **pqs, struct CCtsp_lpgraph *g, 2539 int *pnzlist, int *scount, struct CCtsp_sparser **slist, 2540 int *savedcount); 2541 #else 2542 2543 void 2544 CCtsp_free_qsparsify (); 2545 int 2546 CCtsp_qsparsify (); 2547 2548 #endif 2549 2550 #endif /* __TSP_H */ 2551 #ifndef __XSTUFF_H 2552 #define __XSTUFF_H 2553 2554 #ifdef CC_PROTOTYPE_ANSI 2555 2556 int 2557 Xfastcuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, int ecount, 2558 int *elist, double *x), 2559 Xslowcuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, int ecount, 2560 int *elist, double *x), 2561 Xfastsubtours (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, int ecount, 2562 int *elist, double *x), 2563 Xexactsubtours (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, int ecount, 2564 int *elist, double *x), 2565 Xcliquetrees (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, int ecount, 2566 int *elist, double *x), 2567 Xconsecutiveones (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, int ecount, 2568 int *elist, double *x, CCtsp_lpcuts *pool), 2569 Xnecklacecuts (CCtsp_lpcut_in **cuts, int *cutcount, int ncount, int ecount, 2570 int *elist, double *x, CCtsp_lpcuts *pool); 2571 2572 #else 2573 2574 int 2575 Xfastcuts (), 2576 Xslowcuts (), 2577 Xfastsubtours (), 2578 Xexactsubtours (), 2579 Xcliquetrees (), 2580 Xconsecutiveones (), 2581 Xnecklacecuts (); 2582 2583 #endif 2584 2585 #endif /* __XSTUFF_H */ 2586 #ifndef __FMATCH_H 2587 #define __FMATCH_H 2588 2589 2590 #ifdef CC_PROTOTYPE_ANSI 2591 2592 int 2593 CCfmatch_fractional_2match (int ncount, int ecount, int *elist, int *elen, 2594 CCdatagroup *dat, double *val, int *thematching, int *thedual, 2595 int *thebasis, int wantbasic); 2596 2597 #else 2598 2599 int 2600 CCfmatch_fractional_2match (); 2601 2602 #endif 2603 2604 #endif /* __FMATCH_H */ 2605 #ifndef __LINKERN_H 2606 #define __LINKERN_H 2607 2608 2609 #ifdef CC_PROTOTYPE_ANSI 2610 2611 int 2612 CClinkern_tour (int ncount, CCdatagroup *dat, int ecount, 2613 int *elist, int stallcount, int repeatcount, int *incycle, 2614 int *outcycle, double *val, int run_silently, double time_bound, 2615 double length_bound, char *saveit_name); 2616 2617 #else 2618 2619 int 2620 CClinkern_tour (); 2621 2622 #endif 2623 2624 2625 2626 /***************************************************************************/ 2627 /* */ 2628 /* Must define exactly one of: */ 2629 /* */ 2630 /* CC_LINKED_LIST_FLIPPER (flip_llX) */ 2631 /* CC_ARRAY_FLIPPER (flip_ary) */ 2632 /* CC_TWO_LEVEL_FLIPPER (flip_two) */ 2633 /* CC_SEGMENTS_FLIPPER (flip_sg1) */ 2634 /* CC_NO_UNDO_SEGMENTS_FLIPPER (flip_sg2) */ 2635 /* CC_FULL_SEGMENTS_FLIPPER (flip_sg3) */ 2636 /* CC_SPLAY_FLIPPER (flip_sp2) */ 2637 /* CC_BTREE_FLIPPER (flip_btr) */ 2638 /* */ 2639 /* NOTE: If MARK_NEIGHBORS is not defined in linkern.c, then */ 2640 /* NO_UNDO_SEGMENTS may follow a different improving sequence then */ 2641 /* the other flippers, since the next and prevs in turn () will be */ 2642 /* with respect to an out-of-date-tour. */ 2643 /* */ 2644 /***************************************************************************/ 2645 2646 2647 #define CC_TWO_LEVEL_FLIPPER 2648 /* #define BTREE_FLIPPER */ 2649 2650 #ifdef CC_LINKED_LIST_FLIPPER 2651 #define CC_EXTRA_INFO_FLIP 2652 #endif 2653 2654 #ifdef CC_ARRAY_FLIPPER 2655 #define CC_USE_FLIP_CLEANING 2656 #endif 2657 2658 #ifdef CC_TWO_LEVEL_FLIPPER 2659 #define CC_USE_FLIP_CLEANING 2660 #endif 2661 2662 #ifdef CC_NO_UNDO_SEGMENTS_FLIPPER 2663 #define CC_USE_FLIP_CLEANING 2664 #define CC_USE_QUICK_FLIPS 2665 #endif 2666 2667 #ifdef CC_FULL_SEGMENTS_FLIPPER 2668 #define CC_USE_FLIP_CLEANING 2669 #endif 2670 2671 #ifdef CC_SPLAY_FLIPPER 2672 #define CC_USE_FLIP_CLEANING 2673 #define CC_EXTRA_INFO_FLIP 2674 #endif 2675 2676 #ifdef CC_BTREE_FLIPPER 2677 #define CC_USE_FLIP_CLEANING 2678 #define CC_EXTRA_INFO_FLIP 2679 #endif 2680 2681 #ifdef CC_PROTOTYPE_ANSI 2682 2683 int 2684 CClinkern_flipper_init (int ncount, int *cyc), 2685 CClinkern_flipper_reset_perm (int ncount), 2686 CClinkern_flipper_reset_temp (int ncount), 2687 CClinkern_flipper_next (int x), 2688 CClinkern_flipper_prev (int x), 2689 CClinkern_flipper_cycle (int *x), 2690 CClinkern_flipper_sequence_burst (int x, int y, int z), 2691 CClinkern_flipper_sequence (int x, int y, int z); 2692 2693 void 2694 #ifdef CC_EXTRA_INFO_FLIP 2695 CClinkern_flipper_flip (int xprev, int x, int y, int ynext), 2696 #else 2697 CClinkern_flipper_flip (int x, int y), 2698 #endif 2699 CClinkern_flipper_flip_quick (int x, int y), 2700 CClinkern_flipper_flip_perm (int x, int y), 2701 CClinkern_flipper_sequence_burst_init (int x, int z), 2702 CClinkern_flipper_finish (void), 2703 CClinkern_flipper_free_world (void); 2704 2705 #else 2706 2707 int 2708 CClinkern_flipper_init (), 2709 CClinkern_flipper_reset_perm (), 2710 CClinkern_flipper_reset_temp (), 2711 CClinkern_flipper_next (), 2712 CClinkern_flipper_prev (), 2713 CClinkern_flipper_cycle (), 2714 CClinkern_flipper_sequence_burst (), 2715 CClinkern_flipper_sequence (); 2716 2717 void 2718 CClinkern_flipper_flip (), 2719 CClinkern_flipper_flip_quick (), 2720 CClinkern_flipper_flip_perm (), 2721 CClinkern_flipper_sequence_burst_init (), 2722 CClinkern_flipper_finish (), 2723 CClinkern_flipper_free_world (); 2724 2725 #endif 2726 2727 #endif /* __LINKERN_H */ 2728 #ifndef __MACRORUS_H 2729 #define __MACRORUS_H 2730 2731 #define CC_SWAP(a,b,t) (((t)=(a)),((a)=(b)),((b)=(t))) 2732 2733 #define CC_OURABS(a) (((a) >= 0) ? (a) : -(a)) 2734 2735 #endif /* __MACRORUS_H */ 2736