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