1 /**************************************************************************/
2 /*                                                                        */
3 /* EXPORTED FUNCTIONS:                                                    */
4 /*                                                                        */
5 /*    void                                                                */
6 /*        Xpancakex (Xgraph *G, double *x),                               */
7 /*        Xfreepancake (void),                                            */
8 /*        Xshrinksmallblobs (Xgraph *G, int rnum, int biggest),           */
9 /*        Xtightblobs (Xgraph *G);                                        */
10 /*                                                                        */
11 /*    int                                                                 */
12 /*        Xblobsviolated (Xgraph *G, Xcplane **list );                    */
13 /*                                                                        */
14 /**************************************************************************/
15 
16 #include "machdefs.h"
17 #include "util.h"
18 #include "Xsubtour.h"
19 
20 typedef struct pannode {
21     struct panedge **edgelist;
22     struct panedge **goodedge;
23     int degree;
24     struct vaseknode *vptr;
25 } pannode;
26 
27 typedef struct panedge {
28     double panweight;
29     pannode *ends[2];
30     int elim;
31     int tag;
32     struct vaseknode *a[2];
33     struct vaseknode *roof;
34     struct vaseknode *top;
35     struct panedge *next;
36     double rc;
37     double realrc;
38 } panedge;
39 
40 typedef struct vaseknode {
41     struct vaseknode *parent;
42     struct vaseknode *child;
43     struct vaseknode *sibling;
44     struct vaseknode *anc;
45     struct vaseknode *ptr;
46     struct vaseknode *qtr;
47     struct vaseknode *listpointer;
48     int b;
49     int d;
50     int n;
51     int tag;
52     int fringe;
53     double y;
54     double w;
55     double mult;
56     struct panedge *tree;
57     struct panedge *junk;
58     struct triomino *adj;
59     struct triomino *scan;
60 } vaseknode;
61 
62 typedef struct triomino {
63     panedge *edge;
64     vaseknode *end;
65     struct triomino *next;
66 } triomino;
67 
68 
69 static panedge **panedgespace, *panedgelist;
70 static pannode *pannodelist;
71 
72 
73 #define XPOSITIVE 1
74 
75 #define VNODEALLOC(vrequest) {                                          \
76         if (vnodestack == (vaseknode *) NULL) {                         \
77                 printf ("Ran out of vnode supply\n");                   \
78                 exit (1);                                               \
79         }                                                               \
80         vrequest = vnodestack;                                          \
81         vnodestack = vnodestack->ptr;                                   \
82     }
83 
84 #define VNODEFREE(vreturn) {                                            \
85         vreturn->ptr = vnodestack;                                      \
86         vnodestack = vreturn;                                           \
87     }
88 
89 #define TRIALLOC(trequest) {                                            \
90         trequest = tristack;                                            \
91         tristack = tristack->next;                                      \
92     }
93 
94 #define TRIFREE(treturn) {                                              \
95         treturn->next = tristack;                                       \
96         tristack = treturn;                                             \
97     }
98 
99 #define XSHORT 1000
100 #define XFEW 1
101 
102 #ifdef CC_PROTOTYPE_ANSI
103 
104 static void
105     panalloc (Xgraph *G),
106     buildpanadjlist (Xgraph *G),
107     pancakemain (Xgraph *G),
108     initpancake (Xgraph *G),
109     buildfirsttree (Xgraph *G),
110     decompositiontree (Xgraph *G),
111     initdecompositiontree (Xgraph *G),
112     drop (panedge *e, vaseknode *x),
113     throw (vaseknode *x, vaseknode *y, panedge *e),
114     trickledown (int i),
115     hookup (vaseknode *parent, vaseknode *child),
116     distribute (void),
117     initdistribute (void),
118     split (vaseknode *a),
119     bruteforce (panedge *e),
120     update (panedge *e),
121     dealwith (panedge *e, vaseknode **pa),
122     attach (panedge *e),
123     magicrc (void),
124     labeler (Xgraph *G, vaseknode *p),
125     shrinkblob (Xgraph *G, vaseknode *v);
126 
127 static int
128     ssblob (Xgraph *G, vaseknode *v, int rnum, int biggest, int *shrunk);
129 
130 static double
131     min2 (panedge **elist),
132     findbound (void),
133     blnode (Xgraph *G, Xcplane **list, vaseknode *v, int *hit),
134     tblob (Xgraph *G, vaseknode *v, int *count);
135 
136 static vaseknode
137     *anc (vaseknode *v),
138     *vsmall (Xgraph *G, vaseknode *p),
139     *newcomp (vaseknode *v, double w);
140 
141 #else
142 
143 static void
144     panalloc (),
145     buildpanadjlist (),
146     pancakemain (),
147     initpancake (),
148     buildfirsttree (),
149     decompositiontree (),
150     initdecompositiontree (),
151     drop (),
152     throw (),
153     trickledown (),
154     hookup (),
155     distribute (),
156     initdistribute (),
157     split (),
158     bruteforce (),
159     update (),
160     dealwith (),
161     attach (),
162     magicrc (),
163     labeler (),
164     shrinkblob ();
165 
166 static int
167     ssblob ();
168 
169 static double
170     min2 (),
171     findbound (),
172     blnode (),
173     tblob ();
174 
175 static vaseknode
176     *anc (),
177     *vsmall (),
178     *newcomp ();
179 
180 #endif
181 
182 #ifdef  DEBUG
183 #ifdef CC_PROTOTYPE_ANSI
184 static void
185     dumpwork (void),
186     dumpdecompositiontree (Xgraph *G),
187     dumpvaseknodes (Xgraph *G, vaseknode *pv),
188     printvaseknode (vaseknode *v);
189 #else
190 static void
191     dumpdecompositiontree (),
192     dumpwork (),
193     dumpvaseknodes (),
194     printvaseknode ();
195 #endif
196 #endif /* DEBUG */
197 
198 #define XMAGICNODE 0
199 
200 static int step = 0;
201 static vaseknode *root;
202 static vaseknode *vpannodes = (vaseknode *) NULL, *vnodehit;
203 static vaseknode *head, *tail;
204 static vaseknode *vnodestack = (vaseknode *) NULL;
205 static triomino *trisupply, *tristack;
206 static panedge *work;
207 static panedge **vheap;
208 static int vheapend = 0;
209 static int componentcount = 0;
210 
211 
212 #ifdef CC_PROTOTYPE_ANSI
Xpancakex(Xgraph * G,double * x)213 void Xpancakex (Xgraph *G, double *x)
214 #else
215 void Xpancakex (G, x)
216 Xgraph *G;
217 double *x;
218 #endif
219 {
220     double *dp;
221     int i;
222     panedge *pm;
223 
224     panalloc (G);
225     Xloadx (G, x);
226 
227     for (i = G->nedges, pm = panedgelist, dp = x; i; i--, pm++)
228         pm->panweight = -(*dp++);
229 
230     pancakemain (G);
231 }
232 
233 #ifdef CC_PROTOTYPE_ANSI
panalloc(Xgraph * G)234 static void panalloc (Xgraph *G)
235 #else
236 static void panalloc (G)
237 Xgraph *G;
238 #endif
239 {
240     int i;
241     Xedge *pe;
242     panedge *pa;
243 
244     pannodelist = CC_SAFE_MALLOC (G->nnodes + 1000, pannode);
245     panedgelist = CC_SAFE_MALLOC (G->nedges + 1000, panedge);
246     if (!pannodelist || !panedgelist) {
247         fprintf (stderr, "out of memory in panalloc\n");
248         exit (1);
249     }
250 
251     for (i = G->nedges, pa = panedgelist, pe = G->edgelist; i;
252                                                        i--, pa++, pe++) {
253         pa->ends[0] = pannodelist + (pe->ends[0] - G->nodelist);
254         pa->ends[1] = pannodelist + (pe->ends[1] - G->nodelist);
255     }
256 
257     buildpanadjlist (G);
258 }
259 
260 
261 #ifdef CC_PROTOTYPE_ANSI
buildpanadjlist(Xgraph * G)262 static void buildpanadjlist (Xgraph *G)
263 #else
264 static void buildpanadjlist (G)
265 Xgraph *G;
266 #endif
267 {
268     int i, *degrees, *pint;
269     pannode *pv;
270     panedge *pa, **edgespace;
271     Xedge *pe;
272 
273     edgespace = CC_SAFE_MALLOC (G->nnodes + (G->nedges * 2) + 1000, panedge *);
274     degrees = CC_SAFE_MALLOC (G->nnodes + 1000, int);
275     if (!edgespace || !degrees) {
276         fprintf (stderr, "out of memory in buildpadadjlist\n");
277         exit (1);
278     }
279     panedgespace = edgespace;
280 
281     for (i = 0, pint = degrees; i < G->nnodes; i++)
282         *pint++ = 0;
283 
284     for (i = 0, pe = G->edgelist; i < G->nedges; i++, pe++) {
285         degrees[pe->ends[0] - G->nodelist]++;
286         degrees[pe->ends[1] - G->nodelist]++;
287     }
288 
289     for (i = 0, pint = degrees, pv = pannodelist; i < G->nnodes;
290          i++, pint++, pv++) {
291         if (*pint) {
292             pv->edgelist = pv->goodedge = edgespace;
293             edgespace += *pint + 1;
294         } else
295             pv->edgelist = pv->goodedge = (panedge **) NULL;
296     }
297 
298     for (i = 0, pa = panedgelist; i < G->nedges; i++, pa++) {
299         *(pa->ends[0]->goodedge++) = pa;
300         *(pa->ends[1]->goodedge++) = pa;
301     }
302 
303     for (i = 0, pv = pannodelist; i < G->nnodes; i++, pv++)
304         *(pv->goodedge) = (panedge *) NULL;
305 
306     CC_FREE (degrees, int);
307 }
308 
309 #ifdef CC_PROTOTYPE_ANSI
pancakemain(Xgraph * G)310 static void pancakemain (Xgraph *G)
311 #else
312 static void pancakemain (G)
313 Xgraph *G;
314 #endif
315 {
316     initpancake (G);
317     buildfirsttree (G);
318     findbound ();
319     /* printf ("decompositiontree: %lf\n", findbound ()); */
320 }
321 
322 #ifdef CC_PROTOTYPE_ANSI
initpancake(Xgraph * G)323 static void initpancake (Xgraph *G)
324 #else
325 static void initpancake (G)
326 Xgraph *G;
327 #endif
328 {
329     int i;
330     pannode *pn;
331     vaseknode *pv;
332     triomino *pt;
333 
334     vpannodes = CC_SAFE_MALLOC ((2 * G->nnodes) - 1 + 1000, vaseknode);
335     if (!vpannodes) {
336         fprintf (stderr, "out of memory in initpancake\n");
337         exit (1);
338     }
339 
340     for (i = G->nnodes, pn = pannodelist, pv = vpannodes; i; i--, pn++, pv++) {
341         pv->parent = (vaseknode *) NULL;
342         pv->child = (vaseknode *) NULL;
343         pv->sibling = (vaseknode *) NULL;
344         pv->adj = (triomino *) NULL;
345         pv->n = 0;
346         pv->b = 1;
347         pv->anc = pv;
348         pv->junk = (panedge *) NULL;
349         pv->w = XBIGNEG;
350         pv->y = 0.0;
351         pn->vptr = pv;
352     }
353 
354     vnodestack = vpannodes + G->nnodes;
355     for (i = G->nnodes - 2, pv = vnodestack; i; i--, pv++)
356         pv->ptr = pv + 1;
357     pv->ptr = (vaseknode *) NULL;
358 
359     trisupply = CC_SAFE_MALLOC (2 * G->nedges + 1000, triomino);
360     if (!trisupply) {
361         fprintf (stderr, "out of memory in initpancake\n");
362         exit (1);
363     }
364 
365     tristack = trisupply;
366     for (i = 2 * G->nedges - 1, pt = tristack; i; i--, pt++)
367         pt->next = pt + 1;
368 
369     VNODEALLOC (head);
370 }
371 
372 #ifdef CC_PROTOTYPE_ANSI
Xfreepancake(void)373 void Xfreepancake (void)
374 #else
375 void Xfreepancake ()
376 #endif
377 {
378     CC_FREE (vpannodes, vaseknode);
379     CC_FREE (trisupply, triomino);
380     CC_FREE (vheap, panedge *);
381     CC_FREE (pannodelist, pannode);
382     CC_FREE (panedgelist, panedge);
383     CC_FREE (panedgespace, panedge *);
384 }
385 
386 #ifdef CC_PROTOTYPE_ANSI
buildfirsttree(Xgraph * G)387 static void buildfirsttree (Xgraph *G)
388 #else
389 static void buildfirsttree (G)
390 Xgraph *G;
391 #endif
392 {
393     vaseknode *p;
394     double parw;
395     vaseknode *q;
396 
397     decompositiontree (G);
398     distribute ();
399 
400 
401     head->ptr = tail = root;
402     p = head;
403     do {
404         p = p->ptr;
405         parw = p->w;
406         for (q = p->child; q != (vaseknode *) NULL; q = q->sibling) {
407             q->mult = parw - q->w;
408             if (q->child != (vaseknode *) NULL) {
409                 tail->ptr = q;
410                 tail = q;
411             }
412         }
413     } while (p != tail);
414     root->mult = -root->w;
415 
416     magicrc ();
417 }
418 
419 #ifdef CC_PROTOTYPE_ANSI
decompositiontree(Xgraph * G)420 static void decompositiontree (Xgraph *G)
421 #else
422 static void decompositiontree (G)
423 Xgraph *G;
424 #endif
425 {
426     panedge *e;
427     int i;
428     double w, ub;
429     vaseknode *x, *y;
430 
431     initdecompositiontree (G);
432 
433     for (componentcount = G->nnodes - 2; componentcount;) {
434         for (;;) {
435             e = *vheap;
436             *vheap = vheap[vheapend--];
437             trickledown (0);
438             x = anc (e->ends[0]->vptr);
439             y = anc (e->ends[1]->vptr);
440             if (x != y)
441                 break;
442             drop (e, x);
443         }
444 
445         w = e->panweight;
446         throw (x, y, e);
447 
448         ub = w + 0.01;
449 
450         while (vheapend >= 0 && (e = *vheap)->panweight < ub) {
451             *vheap = vheap[vheapend--];
452             trickledown (0);
453             x = anc (e->ends[0]->vptr);
454             y = anc (e->ends[1]->vptr);
455             if (x != y)
456                 throw (x, y, e);
457             else
458                 drop (e, x);
459         }
460 
461         for (; vnodehit != (vaseknode *) NULL; vnodehit = vnodehit->ptr)
462             if (vnodehit->n)
463                 root = newcomp (vnodehit, w);
464     }
465     i = vheapend + 1;
466     while (i)
467         drop (vheap[--i], root);
468 }
469 
470 #ifdef CC_PROTOTYPE_ANSI
initdecompositiontree(Xgraph * G)471 static void initdecompositiontree (Xgraph *G)
472 #else
473 static void initdecompositiontree (G)
474 Xgraph *G;
475 #endif
476 {
477     int i;
478     panedge *pe, **ph;
479     pannode *pm;
480 
481     vnodehit = (vaseknode *) NULL;
482     work = (panedge *) NULL;
483 
484     for (i = G->nedges, pe = panedgelist; i; i--, pe++)
485         pe->tag = XFALSE;
486 
487     vheap = CC_SAFE_MALLOC (G->nedges + 1000, panedge *);
488     if (!vheap) {
489         fprintf (stderr, "out of memory in initdecompositiontree\n");
490         exit (1);
491     }
492 
493     pm = pannodelist + XMAGICNODE;
494     for (i = G->nedges, pe = panedgelist, ph = vheap; i; i--, pe++)
495         if (pe->ends[0] != pm && pe->ends[1] != pm)
496             *(ph++) = pe;
497         else
498             pe->rc = pe->panweight;
499 
500     vheapend = (ph - vheap) - 1;
501     for (i = vheapend / 2; i >= 0; i--)
502         trickledown (i);
503 }
504 
505 #ifdef CC_PROTOTYPE_ANSI
drop(panedge * e,vaseknode * x)506 static void drop (panedge *e, vaseknode *x)
507 #else
508 static void drop (e, x)
509 panedge *e;
510 vaseknode *x;
511 #endif
512 {
513     e->a[0] = e->ends[0]->vptr;
514     e->a[1] = e->ends[1]->vptr;
515     e->roof = x;
516     e->rc = XPOSITIVE;
517     e->next = work;
518     work = e;
519 }
520 
521 #ifdef  DEBUG
522 #ifdef CC_PROTOTYPE_ANSI
dumpwork(void)523 static void dumpwork (void)
524 #else
525 static void dumpwork ()
526 #endif
527 {
528     panedge *pe;
529 
530     printf ("WORK: ");
531     for (pe = work; pe != (panedge *) NULL; pe = pe->next)
532         printf ("(%d, %d) -> ", pe->ends[0] - pannodelist,
533                 pe->ends[1] - pannodelist);
534     printf ("NULL\n");
535     fflush (stdout);
536 }
537 #endif /* DEBUG */
538 
539 
540 #ifdef  DEBUG
541 #ifdef CC_PROTOTYPE_ANSI
dumpdecompositiontree(Xgraph * G)542 static void dumpdecompositiontree (Xgraph *G)
543 #else
544 static void dumpdecompositiontree (G)
545 Xgraph *G;
546 #endif
547 {
548     int i;
549     pannode *pn;
550 
551     printf ("Nodes of the decomposition tree:\n");
552     for (i = 0, pn = pannodelist; i < G->nnodes; i++, pn++)
553         if (pn != pannodelist + XMAGICNODE)
554             dumpvaseknodes (G, pn->vptr);
555     printf ("\n");
556     fflush (stdout);
557 }
558 #endif /* DEBUG */
559 
560 #ifdef  DEBUG
561 #ifdef CC_PROTOTYPE_ANSI
dumpvaseknodes(Xgraph * G,vaseknode * pv)562 static void dumpvaseknodes (Xgraph *G, vaseknode *pv)
563 #else
564 static void dumpvaseknodes (G, pv)
565 Xgraph *G;
566 vaseknode *pv;
567 #endif
568 {
569     /* dump vaseknodes whose smallest real pannode is v */
570 
571     vaseknode *p;
572 
573     for (p = pv->parent; p != (vaseknode *) NULL && vsmall (G, p) == pv;
574                                                        p = p->parent) {
575         printf ("Node %d: ", p - vpannodes);
576         printvaseknode (p);
577         printf ("\n");
578     }
579     fflush (stdout);
580 }
581 #endif /* DEBUG */
582 
583 #ifdef CC_PROTOTYPE_ANSI
vsmall(Xgraph * G,vaseknode * p)584 static vaseknode *vsmall (Xgraph *G, vaseknode *p)
585 #else
586 static vaseknode *vsmall (G, p)
587 Xgraph *G;
588 vaseknode *p;
589 #endif
590 {
591     vaseknode *p1, *p2, *psmall = vpannodes + G->nnodes;
592 
593     if (p->child == (vaseknode *) NULL)
594         return p;
595     for (p1 = p->child; p1 != (vaseknode *) NULL; p1 = p1->sibling)
596         if ((p2 = vsmall (G, p1)) < psmall)
597             psmall = p2;
598     return psmall;
599 }
600 
601 #ifdef  DEBUG
602 #ifdef CC_PROTOTYPE_ANSI
printvaseknode(vaseknode * p)603 static void printvaseknode (vaseknode *p)
604 #else
605 static void printvaseknode (p)
606 vaseknode *p;
607 #endif
608 {
609     vaseknode *p1;
610     panedge *pe;
611 
612     if (p->child != (vaseknode *) NULL) {
613         for (p1 = p->child; p1 != (vaseknode *) NULL; p1 = p1->sibling)
614             printf ("%d ", p1 - vpannodes);
615     } else
616         printf ("%d ", p - vpannodes);
617     printf ("mult: %f ", p->mult);
618     printf ("parent: %d ", p->parent - vpannodes);
619     printf ("depth: %d ", p->d);
620     printf ("b: %d ", p->b);
621     printf ("junk: ");
622     for (pe = p->junk; pe != (panedge *) NULL; pe = pe->next)
623         printf ("(%d, %d) ", pe->ends[0] - pannodelist,
624                 pe->ends[1] - pannodelist);
625     fflush (stdout);
626 }
627 #endif /* DEBUG */
628 
629 #ifdef CC_PROTOTYPE_ANSI
throw(vaseknode * x,vaseknode * y,panedge * e)630 static void throw (vaseknode *x, vaseknode *y, panedge *e)
631 #else
632 static void throw (x, y, e)
633 vaseknode *x, *y;
634 panedge *e;
635 #endif
636 {
637     e->a[0] = x;
638     e->a[1] = y;
639 
640     e->rc = 0.0;
641     attach (e);
642 
643     if (!(x->n)) {
644         x->n = 1;
645         x->ptr = vnodehit;
646         vnodehit = x;
647     }
648     if (!(y->n)) {
649         y->n = 1;
650         y->ptr = vnodehit;
651         vnodehit = y;
652     }
653     e->next = work;
654     work = e;
655 }
656 
657 #ifdef CC_PROTOTYPE_ANSI
anc(vaseknode * v)658 static vaseknode *anc (vaseknode *v)
659 #else
660 static vaseknode *anc (v)
661 vaseknode *v;
662 #endif
663 {
664     vaseknode *hand, *va;
665 
666     hand = v;
667     while (hand != hand->anc)
668         hand = hand->anc;
669 
670     va = hand;
671     for (hand = v; hand != va; hand = hand->anc)
672         hand->anc = va;
673 
674     return va;
675 }
676 
677 #ifdef CC_PROTOTYPE_ANSI
trickledown(int i)678 static void trickledown (int i)
679 #else
680 static void trickledown (i)
681 int i;
682 #endif
683 {
684     panedge *memo;
685     int k, minchild;
686 
687     memo = vheap[i];
688 
689     while ((k = (2 * i) + 2) <= vheapend) {
690         minchild = (vheap[k - 1]->panweight <= vheap[k]->panweight ? k - 1 : k);
691 
692         if (memo->panweight > vheap[minchild]->panweight) {
693             vheap[i] = vheap[minchild];
694             i = minchild;
695         } else {
696             vheap[i] = memo;
697             return;
698         }
699     }
700     if (k - 1 == vheapend && memo->panweight > vheap[vheapend]->panweight) {
701         vheap[i] = vheap[vheapend];
702         i = vheapend;
703     }
704     vheap[i] = memo;
705 }
706 
707 #ifdef CC_PROTOTYPE_ANSI
newcomp(vaseknode * v,double w)708 static vaseknode *newcomp (vaseknode *v, double w)
709 #else
710 static vaseknode *newcomp (v, w)
711 vaseknode *v;
712 double w;
713 #endif
714 {
715     vaseknode *new, *stack;
716     triomino *t;
717 
718     VNODEALLOC (new);
719     new->parent = (vaseknode *) NULL;
720     new->child = (vaseknode *) NULL;
721     new->sibling = (vaseknode *) NULL;
722     new->anc = new;
723     new->n = 0;
724     new->b = 0;
725     new->w = w;
726     new->adj = (triomino *) NULL;
727     new->junk = (panedge *) NULL;
728     new->tag = XFALSE;
729 
730     hookup (new, v);
731     v->qtr = (vaseknode *) NULL;
732 
733     do {
734         stack = v->qtr;
735         for (t = v->adj; t != (triomino *) NULL; t = t->next) {
736             t->edge->roof = new;
737             v = t->end;
738             if (v->n) {
739                 v->qtr = stack;
740                 stack = v;
741                 hookup (new, v);
742                 componentcount--;
743             }
744         }
745     } while ((v = stack) != (vaseknode *) NULL);
746 
747     return new;
748 }
749 
750 #ifdef CC_PROTOTYPE_ANSI
hookup(vaseknode * parent,vaseknode * child)751 static void hookup (vaseknode *parent, vaseknode *child)
752 #else
753 static void hookup (parent, child)
754 vaseknode *parent, *child;
755 #endif
756 {
757     child->n = 0;
758     child->parent = parent;
759     child->anc = parent;
760     child->sibling = parent->child;
761     parent->child = child;
762 }
763 
764 #ifdef CC_PROTOTYPE_ANSI
distribute(void)765 static void distribute (void)
766 #else
767 static void distribute ()
768 #endif
769 {
770     vaseknode *active;
771     panedge *e, *f;
772 
773     initdistribute ();
774     active = (vaseknode *) NULL;
775     root->n = 0;
776 
777     for (e = work, work = (panedge *) NULL; e != (panedge *) NULL; e = f) {
778         f = e->next;
779         e->top = root;
780         dealwith (e, &active);
781     }
782 
783     while (work) {
784         for (; active != (vaseknode *) NULL; active = active->ptr)
785             if (active->n < XFEW)
786                 active->n = -1;
787             else {
788                 active->n = 0;
789                 split (active);
790             }
791         for (e = work, work = (panedge *) NULL; e != (panedge *) NULL;
792                                                                     e = f) {
793             f = e->next;
794             if (e->top->n >= 0) {
795                 update (e);
796                 dealwith (e, &active);
797             } else
798                 bruteforce (e);
799         }
800         step = step / 2;
801     }
802 }
803 
804 #ifdef CC_PROTOTYPE_ANSI
initdistribute(void)805 static void initdistribute (void)
806 #else
807 static void initdistribute ()
808 #endif
809 {
810     vaseknode *stack, *finger, *x;
811     int maxd, twice, d;
812 
813     maxd = 0;
814 
815     root->d = 0;
816     root->ptr = (vaseknode *) NULL;
817 
818     for (finger = root; finger != (vaseknode *) NULL; finger = stack) {
819         stack = finger->ptr;
820         finger->anc = root;
821         if ((x = finger->child) != (vaseknode *) NULL) {
822             d = finger->d + 1;
823             do {
824                 x->d = d;
825                 x->ptr = stack;
826                 stack = x;
827                 x = x->sibling;
828             } while (x != (vaseknode *) NULL);
829             if (d > maxd)
830                 maxd = d;
831         }
832     }
833     step = 1;
834     twice = 2;
835     while (twice < maxd) {
836         step = twice;
837         twice = step + step;
838     }
839 }
840 
841 #ifdef CC_PROTOTYPE_ANSI
split(vaseknode * a)842 static void split (vaseknode *a)
843 #else
844 static void split (a)
845 vaseknode *a;
846 #endif
847 {
848     int mid, bot;
849     vaseknode *stack, *hand, *foot, *memo, *x;
850 
851     mid = step + a->d;
852     bot = step + mid;
853 
854     a->qtr = (vaseknode *) NULL;
855     for (hand = a; hand != (vaseknode *) NULL; hand = stack) {
856         stack = hand->qtr;
857         if (hand->d == mid) {
858             memo = hand->qtr;
859             hand->qtr = (vaseknode *) NULL;
860             for (foot = hand; foot != (vaseknode *) NULL; foot = stack) {
861                 stack = foot->qtr;
862                 foot->anc = hand;
863                 if (foot->d != bot) {
864                     for (x = foot->child; x != (vaseknode *) NULL;
865                          x = x->sibling) {
866                         x->qtr = stack;
867                         stack = x;
868                     }
869                 }
870             }
871             hand->qtr = memo;
872         } else
873             for (x = hand->child; x != (vaseknode *) NULL; x = x->sibling) {
874                 x->qtr = stack;
875                 stack = x;
876             }
877     }
878 }
879 
880 #ifdef CC_PROTOTYPE_ANSI
bruteforce(panedge * e)881 static void bruteforce (panedge *e)
882 #else
883 static void bruteforce (e)
884 panedge *e;
885 #endif
886 {
887     vaseknode *x, *y, *nx, *ny;
888     int dx, dy;
889 
890     x = e->a[0];
891     y = e->a[1];
892 
893     if (x == y) {
894         printf ("Tough luck Pal 1.\n");
895         exit (1);
896     }
897     dx = x->d;
898     dy = y->d;
899 
900     while (dx > dy) {
901         x = x->parent;
902         dx--;
903     }
904     if (x == y) {
905         printf ("Tough luck Pal 2.\n");
906         exit (1);
907     }
908     while (dy > dx) {
909         y = y->parent;
910         dy--;
911     }
912     if (x == y) {
913         printf ("Tough luck Pal 3.\n");
914         exit (1);
915     }
916     nx = x->parent;
917     ny = y->parent;
918     while (nx != ny) {
919         x = nx;
920         y = ny;
921         nx = x->parent;
922         ny = y->parent;
923     }
924 
925     e->a[0] = x;
926     e->a[1] = y;
927 
928     e->roof = nx;
929     /* if (e->rc > 0.0) { e->next = nx->junk; nx->junk = e; } else { e->tag =
930      * XFALSE; attach (e); } */
931     e->next = nx->junk;
932     nx->junk = e;
933 }
934 
935 #ifdef CC_PROTOTYPE_ANSI
update(panedge * e)936 static void update (panedge *e)
937 #else
938 static void update (e)
939 panedge *e;
940 #endif
941 {
942     vaseknode *x, *y, *v;
943 
944     x = e->a[0]->anc;
945     y = e->a[1]->anc;
946     v = e->top;
947 
948     if (x == v) {
949         if (y != v)
950             e->a[1] = y;
951     } else if (y == v)
952         e->a[0] = x;
953     else if (x != y) {
954         e->a[0] = x;
955         e->a[1] = y;
956     } else {
957         e->top = x;
958         if (x->d > e->roof->d)
959             e->roof = x;
960     }
961 }
962 
963 #ifdef CC_PROTOTYPE_ANSI
dealwith(panedge * e,vaseknode ** pa)964 static void dealwith (panedge *e, vaseknode **pa)
965 #else
966 static void dealwith (e, pa)
967 panedge *e;
968 vaseknode **pa;
969 #endif
970 {
971     if ((e->roof->d) - (e->a[0]->d) < XSHORT &&
972         (e->roof->d) - (e->a[1]->d) < XSHORT)
973         bruteforce (e);
974     else {
975         e->next = work;
976         work = e;
977         if (!e->top->n) {
978             e->top->ptr = *pa;
979             *pa = e->top;
980         }
981         (e->top->n)++;
982     }
983 }
984 
985 #ifdef CC_PROTOTYPE_ANSI
attach(panedge * e)986 static void attach (panedge *e)
987 #else
988 static void attach (e)
989 panedge *e;
990 #endif
991 {
992     triomino *cell;
993 
994     TRIALLOC (cell);
995     cell->edge = e;
996     cell->end = e->a[1];
997     cell->next = e->a[0]->adj;
998     e->a[0]->adj = cell;
999 
1000     TRIALLOC (cell);
1001     cell->edge = e;
1002     cell->end = e->a[0];
1003     cell->next = e->a[1]->adj;
1004     e->a[1]->adj = cell;
1005 }
1006 
1007 #ifdef CC_PROTOTYPE_ANSI
magicrc(void)1008 static void magicrc (void)
1009 #else
1010 static void magicrc ()
1011 #endif
1012 {
1013     double a;
1014     panedge **pee, *pe;
1015 
1016     a = min2 ((pannodelist + XMAGICNODE)->edgelist);
1017 
1018     for (pee = (pannodelist + XMAGICNODE)->edgelist;
1019                 (pe = *pee) != (panedge *) NULL; pee++)
1020         pe->rc -= a;
1021 
1022     (pannodelist + XMAGICNODE)->vptr->y += a;
1023 }
1024 
1025 #ifdef CC_PROTOTYPE_ANSI
min2(panedge ** elist)1026 static double min2 (panedge **elist)
1027 #else
1028 static double min2 (elist)
1029 panedge **elist;
1030 #endif
1031 {
1032     double minweight, minweight2, td;
1033     panedge *e;
1034 
1035     if (elist == (panedge **) NULL || elist[0] == (panedge *) NULL ||
1036                                       elist[1] == (panedge *) NULL) {
1037         fprintf (stderr, "Vertex has degree < two\n");
1038         exit (1);
1039     }
1040     minweight = elist[0]->rc;
1041     minweight2 = elist[1]->rc;
1042     if (minweight > minweight2) {
1043         SWAP (minweight, minweight2, td);
1044     }
1045     for (elist += 2; (e = *elist) != (panedge *) NULL; elist++) {
1046         if (e->rc < minweight2) {
1047             minweight2 = e->rc;
1048             if (minweight > minweight2) {
1049                 SWAP (minweight, minweight2, td);
1050             }
1051         }
1052     }
1053     return minweight2;
1054 }
1055 
1056 #ifdef CC_PROTOTYPE_ANSI
findbound(void)1057 static double findbound (void)
1058 #else
1059 static double findbound ()
1060 #endif
1061 {
1062     vaseknode *p, *q, *stack;
1063     triomino *tri;
1064     panedge **pee, *pe;
1065     double tree_bound = 0.0;
1066     double star_bound = 0.0;
1067     double edge_bound = 0.0;
1068 
1069     root->ptr = (vaseknode *) NULL;
1070     root->n = 1;
1071     root->b = 0;
1072 
1073 
1074     for (p = stack = root; p; p = stack) {
1075         if (p->n) {
1076             p->n = 0;
1077             q = p->child;
1078             if (q)
1079                 for (; q; q = q->sibling) {
1080                     q->ptr = stack;
1081                     stack = q;
1082                     q->n = 1;
1083                     q->b = 0;
1084                 }
1085             else {
1086                 stack = p->ptr;
1087                 (p->parent->b)++;
1088                 star_bound += p->y;
1089             }
1090             for (tri = p->adj; tri; tri = tri->next)
1091                 edge_bound += tri->edge->rc;
1092         } else {
1093             stack = p->ptr;
1094             if (stack)
1095                 (p->parent->b) += p->b;
1096             tree_bound -= (p->mult) * ((p->b) - 1);
1097         }
1098     }
1099     star_bound *= 2.0;
1100     edge_bound /= 2.0;
1101 
1102     for (pee = ((pannodelist + XMAGICNODE)->edgelist);
1103                  (pe = *pee) != (panedge *) NULL; pee++)
1104         if (pe->rc < 0.0)
1105             edge_bound += pe->rc;
1106     star_bound += (pannodelist + XMAGICNODE)->vptr->y * 2;
1107 
1108     return tree_bound + star_bound + edge_bound;
1109 }
1110 
1111 #ifdef CC_PROTOTYPE_ANSI
Xblobsviolated(Xgraph * G,Xcplane ** list)1112 int Xblobsviolated (Xgraph *G, Xcplane **list)
1113 #else
1114 int Xblobsviolated (G, list)
1115 Xgraph *G;
1116 Xcplane **list;
1117 #endif
1118 {
1119     int hit = 0;
1120 
1121     blnode (G, list, root, &hit);
1122     return hit;
1123 }
1124 
1125 #ifdef CC_PROTOTYPE_ANSI
blnode(Xgraph * G,Xcplane ** list,vaseknode * v,int * hit)1126 static double blnode (Xgraph *G, Xcplane **list, vaseknode *v, int *hit)
1127 #else
1128 static double blnode (G, list, v, hit)
1129 Xgraph *G;
1130 Xcplane **list;
1131 vaseknode *v;
1132 int *hit;
1133 #endif
1134 {
1135     double w = 0.0;
1136     double t;
1137     panedge *e;
1138     vaseknode *c;
1139 
1140     if (!v->child)
1141         return 0.0;
1142     else {
1143         for (e = v->junk; e; e = e->next)
1144             w += (G->edgelist + (e - panedgelist))->x;
1145         for (c = v->child; c; c = c->sibling)
1146             w += blnode (G, list, c, hit);
1147         t = v->b;
1148         if (w > t - 1.0 + XCUTTOLERANCE) {
1149             G->magicnum++;
1150             labeler (G, v);
1151             if (Xcutchecksout (G, G->magicnum)) {
1152                 Xloadcplane_cut (G, list, G->magicnum);
1153                 (*hit)++;
1154             } else {
1155                 printf ("BAD BLOB");
1156                 fflush (stdout);
1157             }
1158         }
1159         return w;
1160     }
1161 }
1162 
1163 #ifdef CC_PROTOTYPE_ANSI
labeler(Xgraph * G,vaseknode * p)1164 static void labeler (Xgraph *G, vaseknode *p)
1165 #else
1166 static void labeler (G, p)
1167 Xgraph *G;
1168 vaseknode *p;
1169 #endif
1170 {
1171     vaseknode *c;
1172 
1173     if (!p->child)
1174         (G->nodelist + (p - vpannodes))->magiclabel = G->magicnum;
1175     else
1176         for (c = p->child; c; c = c->sibling)
1177             labeler (G, c);
1178 }
1179 
1180 #ifdef CC_PROTOTYPE_ANSI
Xshrinksmallblobs(Xgraph * G,int rnum,int biggest)1181 void Xshrinksmallblobs (Xgraph *G, int rnum, int biggest)
1182 #else
1183 void Xshrinksmallblobs (G, rnum, biggest)
1184 Xgraph *G;
1185 int rnum;
1186 int biggest;
1187 #endif
1188 {
1189     int shrunk = 0;
1190 
1191     ssblob (G, root, rnum, biggest, &shrunk);
1192 }
1193 
1194 #ifdef CC_PROTOTYPE_ANSI
ssblob(Xgraph * G,vaseknode * v,int rnum,int biggest,int * shrunk)1195 static int ssblob (Xgraph *G, vaseknode *v, int rnum, int biggest, int *shrunk)
1196 #else
1197 static int ssblob (G, v, rnum, biggest, shrunk)
1198 Xgraph *G;
1199 vaseknode *v;
1200 int rnum;
1201 int biggest;
1202 int *shrunk;
1203 #endif
1204 {
1205     int count = 0;
1206     vaseknode *c;
1207     static int s = 0;
1208 
1209     if (v->b < 3)
1210         return 0;
1211     else {
1212         for (c = v->child; c; c = c->sibling)
1213             count += ssblob (G, c, rnum, biggest, shrunk);
1214         if (count)
1215             return count;
1216         else {
1217             if (v->tag) {
1218                 if (v->b <= biggest &&
1219                     (!rnum || (++s) % 2)) {
1220                     shrinkblob (G, v);
1221                     (*shrunk)++;
1222                 }
1223                 return 1;
1224             } else
1225                 return 0;
1226         }
1227     }
1228 }
1229 
1230 #ifdef CC_PROTOTYPE_ANSI
shrinkblob(Xgraph * G,vaseknode * v)1231 static void shrinkblob (Xgraph *G, vaseknode *v)
1232 #else
1233 static void shrinkblob (G, v)
1234 Xgraph *G;
1235 vaseknode *v;
1236 #endif
1237 {
1238     Xnode *first, *pn;
1239 
1240     G->magicnum++;
1241     labeler (G, v);
1242     first = G->pseudonodelist->next;
1243     while (first->magiclabel != G->magicnum)
1244         first = first->next;
1245     for (pn = first->next; pn; pn = pn->next)
1246         if (pn->magiclabel == G->magicnum)
1247             Xsimpleshrink (G, first, pn);
1248 }
1249 
1250 #ifdef CC_PROTOTYPE_ANSI
Xtightblobs(Xgraph * G)1251 void Xtightblobs (Xgraph *G)
1252 #else
1253 void Xtightblobs (G)
1254 Xgraph *G;
1255 #endif
1256 {
1257     int count = 0;
1258 
1259     tblob (G, root, &count);
1260     printf ("Number tight blobs: %d\n", count);
1261 }
1262 
1263 #ifdef CC_PROTOTYPE_ANSI
tblob(Xgraph * G,vaseknode * v,int * count)1264 static double tblob (Xgraph *G, vaseknode *v, int *count)
1265 #else
1266 static double tblob (G, v, count)
1267 Xgraph *G;
1268 vaseknode *v;
1269 int *count;
1270 #endif
1271 {
1272     double w = 0.0;
1273     double t;
1274     panedge *e;
1275     vaseknode *c;
1276 
1277     if (v->b < 3)
1278         return 0.0;
1279     else {
1280         for (e = v->junk; e; e = e->next)
1281             w += (G->edgelist + (e - panedgelist))->x;
1282         for (c = v->child; c; c = c->sibling)
1283             w += tblob (G, c, count);
1284         t = v->b;
1285         if (w > t - 1.0 - XEPSILON) {
1286             v->tag = 1;
1287             (*count)++;
1288         } else
1289             v->tag = 0;
1290         return w;
1291     }
1292 }
1293 
1294