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