1 #ifndef __XSUBTOUR_H 2 #define __XSUBTOUR_H 3 4 #include "Xcutpool.h" 5 6 #define XFALSE 0 7 #define XEPSILON .0001 8 #define XCUTTOLERANCE .01 9 #define XBLOTOLERANCE .01 10 #define XCUTTWO (2.0-XCUTTOLERANCE) 11 #define XCUTNUM 150 12 #define XMAXWEIGHT 1e30 13 #define XBIGNEG -10000000000.0 14 #define SWAP(x,y,temp) (temp = x, x = y, y = temp) 15 #define OTHEREND(e,n) (e->ends[0] == n ? e->ends[1] : e->ends[0]) 16 #define OTHERCURRENTEND(e,n) ((e)->cends[0] == (n) ? (e)->cends[1] : (e)->cends[0]) 17 18 typedef struct Xedge { 19 struct Xnode *ends[2]; 20 struct Xnode *cends[2]; 21 struct Xnode *splitter; 22 int weight; 23 double x; 24 double rc; 25 double flow; 26 int stay; 27 int elim; 28 int weak; 29 int hold; 30 int fixed; 31 int magiclabel; 32 struct Xedge *next; 33 } Xedge; 34 35 typedef struct Xextraedge { 36 int ends[2]; 37 int weight; 38 int elim; 39 } Xextraedge; 40 41 typedef struct Xextralink { 42 int ends[2]; 43 int weight; 44 struct Xextralink *next; 45 } Xextralink; 46 47 typedef struct Xedgeptr { 48 struct Xedge *this; 49 struct Xedgeptr *next; 50 } Xedgeptr; 51 52 typedef struct Xedgeset { 53 struct Xedgeptr *head; 54 struct Xedgeptr *tail; 55 } Xedgeset; 56 57 typedef struct Xnodeset { 58 struct Xnodeptr *head; 59 struct Xnodeptr *tail; 60 } Xnodeset; 61 62 typedef struct Xnode { 63 Xedgeset adj; 64 Xedgeset cadj; 65 Xnodeset base; 66 int degree; 67 int magiclabel; 68 int stacklabel; 69 int pseudonumber; 70 double excess; 71 int flowlabel; 72 Xedgeptr *current; 73 int active; 74 struct Xnode *next, *prev; 75 struct Xnode *snext; 76 struct Xnode *tnext; /* Only use locally */ 77 Xedge *pe; 78 struct Xclink *cuts; 79 struct Xblink *blossoms; 80 int mark; 81 int Tmark; 82 int rand1; 83 int rand2; 84 } Xnode; 85 86 typedef struct Xnodeptr { 87 struct Xnode *this; 88 struct Xnodeptr *next; 89 } Xnodeptr; 90 91 typedef struct Xnodeptrptr { 92 struct Xnodeptr *this; 93 struct Xnodeptrptr *next; 94 } Xnodeptrptr; 95 96 typedef struct Xclink { 97 int cut; 98 struct Xclink *next; 99 } Xclink; 100 101 typedef struct Xblink { 102 int cut; 103 char handle; 104 int tooth; 105 struct Xblink *next; 106 } Xblink; 107 108 typedef struct Xconstraint { 109 int sort; 110 struct Xnodeptr *teeth; 111 int rhs; 112 } Xconstraint; 113 114 typedef struct Xcplane { 115 unsigned long val; 116 struct Xnodeptr *handle; 117 struct Xnodeptrptr *handles; 118 struct Xnodeptrptr *teeth; 119 struct Xcplane *next; 120 } Xcplane; 121 122 typedef struct Xiplane { 123 struct Xintptr *handle; 124 struct Xintptrptr *handles; 125 struct Xintptrptr *teeth; 126 struct Xiplane *next; 127 } Xiplane; 128 129 typedef struct Xcuttree_node { 130 struct Xcuttree_node *parent; 131 struct Xcuttree_node *sibling; 132 struct Xcuttree_node *child; 133 double cutval; 134 int ndescendants; 135 Xnode *special; 136 Xnodeset nlist; 137 Xnode *pseudonode; 138 struct Xcuttree_node *next; 139 } Xcuttree_node; 140 141 typedef struct Xintptr { 142 int this; 143 struct Xintptr *next; 144 } Xintptr; 145 146 typedef struct Xintptrptr { 147 Xintptr *this; 148 struct Xintptrptr *next; 149 } Xintptrptr; 150 151 typedef struct Xblock { 152 Xnodeptr *members; 153 struct Xcutnodeptr *cutnodes; 154 struct Xblockptr *neighbors; 155 Xedgeptr *one; 156 double weight; 157 double x; 158 int mark; 159 } Xblock; 160 161 typedef struct Xblockptr { 162 struct Xblockptr *next; 163 struct Xblock *this; 164 double hood_weight; 165 } Xblockptr; 166 167 typedef struct Xcutnode { 168 Xnode *name; 169 Xblockptr *blocks; 170 int mark; 171 } Xcutnode; 172 173 typedef struct Xcutnodeptr { 174 struct Xcutnode *this; 175 struct Xcutnodeptr *next; 176 } Xcutnodeptr; 177 178 typedef struct Xcombhash { 179 unsigned long val; 180 struct Xcombhash *next; 181 } Xcombhash; 182 183 typedef struct Xclique { 184 double slack; 185 Xintptr *nodes; 186 struct Xclique *next; 187 struct Xclique *prev; 188 } Xclique; 189 190 typedef struct Xgraph { 191 int nnodes; 192 Xnode *nodelist; 193 int nedges; 194 Xedge *edgelist; 195 Xnode *pseudonodelist; 196 Xedge *pseudoedgelist; 197 int npseudonodes; 198 int magicnum; 199 int stacknum; 200 int magicedgenum; 201 } Xgraph; 202 203 #ifdef CC_PROTOTYPE_ANSI 204 205 /* adjacency.c */ 206 207 void 208 Xbuildpanadjlist (void), 209 Xbuildmatadjlist (void); 210 211 /* allcuts.c */ 212 213 void 214 Xall_tightcuts (Xgraph *Gin, Xclique **cliquelistin, int *ncliquesin); 215 216 /* Xblock.c */ 217 218 void 219 Xlocalshrink_a (Xgraph *G, int component), 220 Xlocalshrink_b (Xgraph *G, int component), 221 Xlocalshrink_c (Xgraph *G, int component), 222 Xadd_tooth (Xnode *t, Xnodeptr **list); 223 224 int 225 Xblockcombs (Xgraph *G, Xcplane **cplanelist, double *x), 226 Xlocalcombs (Xgraph *G, Xcplane **cplanelist, double *x), 227 Xglobalcombs (Xgraph *G, Xcplane **cplanelist, double *x), 228 XTmark_components (Xgraph *G), 229 Xbasiccliques (Xgraph *G, Xcplane **list, double *x), 230 Xsearchbasiccliques (Xgraph *G, Xcplane **list, int pseudo, double *x), 231 Xbasicclique (Xgraph *G, Xcplane **list, double *x, Xblock *bigtooth), 232 Xmarktooth (Xedge *e, Xnodeptr **list), 233 Xmarktoothend (Xnode *n, Xnodeptr **list), 234 Xrepeat_1_shrink (Xgraph *G, Xnode *n, Xedge *e); 235 236 Xedge 237 *Xcurrentedge (Xnode *n1, Xnode *n2); 238 239 240 /* Xblocheck.c */ 241 242 int 243 Xexactblossoms_run (Xgraph *G, Xcplane **list, double *x), 244 Xexactblossomcheck (Xgraph *G, Xcplane **list, int pseudo, double *x), 245 Xolaf (Xgraph *G, int choice); 246 247 248 /* Xclique.c */ 249 250 int 251 Xcliquetree (Xgraph *G, Xcplane **list, double *x), 252 Xcliquetree_work (Xgraph *G, Xcplane **list, int pseudo, double *x, 253 int type_of_grow); 254 255 256 /* Xcuthash.c */ 257 258 void 259 Xinit_hash_values (Xgraph *G); 260 261 unsigned long 262 Xcut_hash_value (Xnodeptr *h), 263 Xcomb_hash_value (Xnodeptr *h, Xnodeptrptr *t), 264 Xclique_hash_value (Xnodeptrptr *h, Xnodeptrptr *t); 265 266 267 /* Xblobs.c */ 268 269 void 270 Xpancakex (Xgraph *G, double *x), 271 Xfreepancake (void), 272 Xshrinksmallblobs (Xgraph *G, int rnum, int biggest), 273 Xtightblobs (Xgraph *G); 274 275 int 276 Xblobsviolated (Xgraph *G, Xcplane **list ); 277 278 279 /* Xcclean.c */ 280 281 void 282 Xcleancomb (Xgraph *G, Xnodeptr **handle, Xnodeptrptr **teeth, 283 int *nteeth, double *x); 284 int 285 Xcheckcomb (Xgraph *G, Xnodeptr *handle, Xnodeptrptr *teeth), 286 Xcliquefluff (Xgraph *G, Xnodeptrptr **handles, Xnodeptrptr **teeth), 287 Xtemp_combfluff (Xgraph *G, Xnodeptr **handle, Xnodeptrptr **teeth), 288 Xcombfluff (Xgraph *G, Xnodeptrptr **handles, Xnodeptrptr **teeth, 289 int cliquetest), 290 Xhistok (unsigned int *hist), 291 Xtemp_combcheck (Xgraph *G, Xnodeptr *handle, Xnodeptrptr *teeth), 292 Xcheckclique (Xgraph *G, Xnodeptrptr *handles, Xnodeptrptr *teeth); 293 294 /* Xcutload.c */ 295 296 void 297 Xcliquetree_slack_rhs_flow (Xgraph *G, Xnodeptrptr *handles, 298 Xnodeptrptr *teeth, double *x, double *slack, double *rhs), 299 Xfreecplanelist (Xcplane **list); 300 301 int 302 Xcutchecksout (Xgraph *G, int x), 303 Xtemp_doblossom (Xgraph *G, Xcplane **cplanelist, Xnodeptr *handle, 304 Xedgeptr *teeth), 305 Xviolated_clique_flow (Xgraph *G, Xnodeptrptr *handles, Xnodeptrptr *teeth, 306 double *x), 307 Xloadcplane (Xcplane **list, Xnodeptr *h, Xnodeptrptr *H, 308 Xnodeptrptr *t, int countcheck), 309 Xloadcplane_cut (Xgraph *G, Xcplane **list, int num); 310 311 312 /* Xcuts.c */ 313 314 int 315 Xolaf_combs (Xgraph *G, Xcplane **list, double *x), 316 Xblobcuts (Xgraph *G, Xcplane **list, double *x); 317 318 int 319 Xreallyfaststuff (Xcplane **, double *, double *), 320 Xfaststuff (Xcplane **, double *, double *), 321 Xmediumstuff (Xcplane **, double *, double *), 322 Xslowstuff (Xcplane **, double *, double *), 323 Xreallyslowstuff (Xcplane **, double *, double *), 324 Xall_run_olaf (Xcplane **, double *), 325 Xheuristiccutcheck (Xcplane **, double *); 326 327 /* Xcututil.c */ 328 329 void 330 Xfreecplanestruct (Xcplane *c), 331 Xfreeiplanestruct (Xiplane *c), 332 Xcplane_to_iplane (Xgraph *G, Xcplane *c, Xiplane **ipl), 333 Xiplane_to_cplane (Xgraph *G, Xiplane *c, Xcplane **cpl), 334 Xportablecut_to_cplane (Xgraph *G, Xportablecut *p, Xcplane **cpl), 335 Xportablecut_to_handles_and_teeth (Xgraph *G, Xportablecut *p, 336 Xnodeptrptr **handles, Xnodeptrptr **teeth), 337 Xportablecut_to_iplane (Xportablecut *p, Xiplane **ipl), 338 Xiplane_to_portablecut (Xiplane *c, Xportablecut *p), 339 Xfreeteeth (Xnodeptrptr *teeth), 340 Xprintchvatalcomb (Xgraph *G, Xnodeptr *h, Xnodeptrptr *t), 341 Xprintcliquetree (Xgraph *G, Xnodeptrptr *h, Xnodeptrptr *t), 342 Xdumpchvatalcomb (FILE *out, Xintptr *h, Xintptrptr *t), 343 Xdumpcliquetree (FILE *out, Xintptrptr *h, Xintptrptr *t); 344 345 int 346 Xslackclique (Xgraph *G, Xnodeptrptr *handles, Xnodeptrptr *teeth, 347 double *slack), 348 Xinduced_edges_flow (Xgraph *G, Xnodeptr *set); 349 350 351 /* Xflow.c */ 352 353 double 354 Xflow (Xgraph *G, Xnode *, Xnode *, double); 355 356 int 357 Xmincut (Xgraph *G, Xnode *, Xnode *, double, double *, int *), 358 Xexactcutcheck (Xgraph *G, Xcplane **list, double *x), 359 Xrunconnectcuts (Xgraph *G, Xcplane **, double *); 360 361 362 /* Xgomhu.c */ 363 364 Xcuttree_node 365 *Xgomory_hu (Xgraph *G); 366 367 void 368 Xcuttree_free (Xcuttree_node *n); 369 370 /* necklace.c */ 371 372 int 373 Xnecklaces (Xgraph *Gin, Xcplane **, double *); 374 375 /* newkids.c */ 376 377 int 378 Xnewkids (Xgraph *Gin, double *x, Xcplane **list); 379 380 /* Xourallo.c */ 381 382 Xblink *Xblinkalloc (void); 383 Xblockptr *Xblockptralloc (void); 384 Xclink *Xclinkalloc (void); 385 Xclique *Xcliquealloc (void); 386 Xcombhash *Xcombhashalloc (void); 387 Xcplane *Xcplanealloc (void); 388 Xcutnodeptr *Xcutnodeptralloc (void); 389 Xcuttree_node *Xcuttree_nodealloc (void); 390 Xedge *Xedgealloc (void); 391 Xedgeptr *Xedgeptralloc (void); 392 Xintptr *Xintptralloc (void); 393 Xintptrptr *Xintptrptralloc (void); 394 void Xadd_intptrptr (Xintptrptr **, Xintptr *); 395 Xiplane *Xiplanealloc (void); 396 Xnode *Xnodealloc (void); 397 Xnodeptr *Xnodeptralloc (void); 398 Xnodeptrptr *Xnodeptrptralloc (void); 399 void Xadd_edgeptr (Xedgeptr **, Xedge *); 400 void Xadd_extralink (Xextralink **, int, int, int); 401 void Xadd_nodeptr (Xnodeptr **, Xnode *); 402 void Xadd_nodeptrptr (Xnodeptrptr **, Xnodeptr *); 403 void Xblinkfree (Xblink *); 404 void Xblockptrfree (Xblockptr *); 405 void Xclinkfree (Xclink *); 406 void Xcliquefree (Xclique *); 407 void Xcombhashfree (Xcombhash *); 408 void Xcplane_list_free (Xcplane *); 409 void Xcplanefree (Xcplane *); 410 void Xcutnodeptrfree (Xcutnodeptr *); 411 void Xcuttree_nodefree (Xcuttree_node *); 412 void Xedgefree (Xedge *); 413 void Xedge_list_free (Xedge *); 414 void Xedgeptr_list_free (Xedgeptr *); 415 void Xedgeptrfree (Xedgeptr *); 416 void Xextralink_list_free (Xextralink *); 417 void Xinitialize_ouralloc (void); 418 void Xintptr_list_free (Xintptr *); 419 void Xintptrfree (Xintptr *); 420 void Xintptrptr_list_free (Xintptrptr *); 421 void Xintptrptr_list_freeall(Xintptrptr *); 422 void Xintptrptrfree (Xintptrptr *); 423 void Xiplane_list_free (Xiplane *); 424 void Xiplanefree (Xiplane *); 425 void Xnodefree (Xnode *); 426 void Xnodeptr_list_free (Xnodeptr *); 427 void Xnodeptrfree (Xnodeptr *); 428 void Xnodeptrptr_list_free (Xnodeptrptr *); 429 void Xnodeptrptrfree (Xnodeptrptr *); 430 void Xunion_nodeptr (Xgraph *G, Xnodeptr *, Xnodeptr *, Xnodeptr **); 431 432 433 /* Xshrink.c */ 434 435 void 436 Xbuildpseudonodelist (Xgraph *G, int all), 437 Xbuildpseudonodenumbers (Xgraph *G), 438 Xdestroypseudonodelist (Xgraph *G), 439 Xdumppseudograph (Xgraph *G), 440 Xdumppseudograph_edgelist (Xgraph *G), 441 Xsimpleshrink (Xgraph *G, Xnode *, Xnode *), 442 Xrebuildcadj (Xgraph *G); 443 444 int 445 Xshrinkprocess (Xgraph *G, Xcplane **), 446 Xheavy_edge_cuts (Xgraph *G, Xcplane **list, double *x); 447 448 449 /* Xgraph.c */ 450 451 void 452 Xfreegraph (Xgraph *G), 453 Xloadx (Xgraph *G, double *x); 454 455 int 456 Xbuildgraph (Xgraph *G, int ncount, int ecount, int *elist, int *elen); 457 458 /* Xstuff.c */ 459 460 int 461 Xsearch_cutpool_for_slack_cliques (Xgraph *G, double maxslack, 462 int request, int *kcount, Xportableclique **klist, int ecount, 463 int *elist, double *x); 464 465 #else 466 467 /* adjacency.c */ 468 469 void 470 Xbuildpanadjlist (), 471 Xbuildmatadjlist (); 472 473 /* allcuts.c */ 474 475 void 476 Xall_tightcuts (); 477 478 /* Xblock.c */ 479 480 void 481 Xlocalshrink_a (), 482 Xlocalshrink_b (), 483 Xlocalshrink_c (), 484 Xadd_tooth (); 485 486 int 487 Xblockcombs (), 488 Xlocalcombs (), 489 Xglobalcombs (), 490 XTmark_components (), 491 Xbasiccliques (), 492 Xsearchbasiccliques (), 493 Xbasicclique (), 494 Xmarktooth (), 495 Xmarktoothend (), 496 Xrepeat_1_shrink (); 497 498 Xedge 499 *Xcurrentedge (); 500 501 502 /* Xblocheck.c */ 503 504 int 505 Xexactblossoms_run (), 506 Xexactblossomcheck (), 507 Xolaf (); 508 509 510 /* Xclique.c */ 511 512 int 513 Xcliquetree (), 514 Xcliquetree_work (); 515 516 517 /* Xcuthash.c */ 518 519 void 520 Xinit_hash_values (); 521 522 unsigned long 523 Xcut_hash_value (), 524 Xcomb_hash_value (), 525 Xclique_hash_value (); 526 527 528 /* Xblobs.c */ 529 530 void 531 Xpancakex (), 532 Xfreepancake (), 533 Xshrinksmallblobs (), 534 Xtightblobs (); 535 536 int 537 Xblobsviolated (); 538 539 540 /* Xcclean.c */ 541 542 void 543 Xcleancomb (); 544 int 545 Xcheckcomb (), 546 Xcliquefluff (), 547 Xtemp_combfluff (), 548 Xcombfluff (), 549 Xhistok (), 550 Xtemp_combcheck (), 551 Xcheckclique (); 552 553 /* Xcutload.c */ 554 555 void 556 Xcliquetree_slack_rhs_flow (), 557 Xfreecplanelist (); 558 559 int 560 Xcutchecksout (), 561 Xtemp_doblossom (), 562 Xviolated_clique_flow (), 563 Xloadcplane (), 564 Xloadcplane_cut (); 565 566 567 /* Xcuts.c */ 568 569 int 570 Xolaf_combs (), 571 Xblobcuts (); 572 573 int 574 Xreallyfaststuff (), 575 Xfaststuff (), 576 Xmediumstuff (), 577 Xslowstuff (), 578 Xreallyslowstuff (), 579 Xall_run_olaf (), 580 Xheuristiccutcheck (); 581 582 /* Xcututil.c */ 583 584 void 585 Xfreecplanestruct (), 586 Xfreeiplanestruct (), 587 Xcplane_to_iplane (), 588 Xiplane_to_cplane (), 589 Xportablecut_to_cplane (), 590 Xportablecut_to_handles_and_teeth (), 591 Xportablecut_to_iplane (), 592 Xiplane_to_portablecut (), 593 Xfreeteeth (), 594 Xprintchvatalcomb (), 595 Xprintcliquetree (), 596 Xdumpchvatalcomb (), 597 Xdumpcliquetree (); 598 599 int 600 Xslackclique (), 601 Xinduced_edges_flow (); 602 603 604 /* Xflow.c */ 605 606 double 607 Xflow (); 608 609 int 610 Xmincut (), 611 Xexactcutcheck (), 612 Xrunconnectcuts (); 613 614 615 /* Xgomhu.c */ 616 617 Xcuttree_node 618 *Xgomory_hu (); 619 620 void 621 Xcuttree_free (); 622 623 /* necklace.c */ 624 625 int 626 Xnecklaces (); 627 628 /* newkids.c */ 629 630 int 631 Xnewkids (); 632 633 /* Xourallo.c */ 634 635 Xblink *Xblinkalloc (); 636 Xblockptr *Xblockptralloc (); 637 Xclink *Xclinkalloc (); 638 Xclique *Xcliquealloc (); 639 Xcombhash *Xcombhashalloc (); 640 Xcplane *Xcplanealloc (); 641 Xcutnodeptr *Xcutnodeptralloc (); 642 Xcuttree_node *Xcuttree_nodealloc (); 643 Xedge *Xedgealloc (); 644 Xedgeptr *Xedgeptralloc (); 645 Xintptr *Xintptralloc (); 646 Xintptrptr *Xintptrptralloc (); 647 void Xadd_intptrptr (); 648 Xiplane *Xiplanealloc (); 649 Xnode *Xnodealloc (); 650 Xnodeptr *Xnodeptralloc (); 651 Xnodeptrptr *Xnodeptrptralloc (); 652 void Xadd_edgeptr (); 653 void Xadd_extralink (); 654 void Xadd_nodeptr (); 655 void Xadd_nodeptrptr (); 656 void Xblinkfree (); 657 void Xblockptrfree (); 658 void Xclinkfree (); 659 void Xcliquefree (); 660 void Xcombhashfree (); 661 void Xcplane_list_free (); 662 void Xcplanefree (); 663 void Xcutnodeptrfree (); 664 void Xcuttree_nodefree (); 665 void Xedgefree (); 666 void Xedge_list_free (); 667 void Xedgeptr_list_free (); 668 void Xedgeptrfree (); 669 void Xextralink_list_free (); 670 void Xinitialize_ouralloc (); 671 void Xintptr_list_free (); 672 void Xintptrfree (); 673 void Xintptrptr_list_free (); 674 void Xintptrptr_list_freeall(); 675 void Xintptrptrfree (); 676 void Xiplane_list_free (); 677 void Xiplanefree (); 678 void Xnodefree (); 679 void Xnodeptr_list_free (); 680 void Xnodeptrfree (); 681 void Xnodeptrptr_list_free (); 682 void Xnodeptrptrfree (); 683 void Xunion_nodeptr (); 684 685 686 /* Xshrink.c */ 687 688 void 689 Xbuildpseudonodelist (), 690 Xbuildpseudonodenumbers (), 691 Xdestroypseudonodelist (), 692 Xdumppseudograph (), 693 Xdumppseudograph_edgelist (), 694 Xsimpleshrink (), 695 Xrebuildcadj (); 696 697 int 698 Xshrinkprocess (), 699 Xheavy_edge_cuts (); 700 701 702 /* Xgraph.c */ 703 704 void 705 Xfreegraph (), 706 Xloadx (); 707 708 int 709 Xbuildgraph (); 710 711 /* Xstuff.c */ 712 713 int 714 Xsearch_cutpool_for_slack_cliques (); 715 716 #endif 717 #endif /* __XSUBTOUR_H */ 718 719