1 /**************************************************************************/
2 /* */
3 /* EXPORTED FUNCTIONS: */
4 /* */
5 /* void */
6 /* cleancomb (); */
7 /* */
8 /* int */
9 /* checkcomb (), */
10 /* cliquefluff (), */
11 /* temp_combfluff (), */
12 /* combfluff (), */
13 /* histok (), */
14 /* checkclique (); */
15 /* */
16 /**************************************************************************/
17
18 #include "machdefs.h"
19 #include "util.h"
20 #include "Xsubtour.h"
21
22
23 #ifdef CC_PROTOTYPE_ANSI
24
25 static void
26 complement_nodeptrlist (Xgraph *G, Xnodeptr *list, Xnodeptr **new),
27 get_smaller_cliquetree (Xgraph *G, Xnodeptrptr **newhandles,
28 Xnodeptrptr **newteeth, Xnodeptrptr *handles, Xnodeptrptr *teeth,
29 Xnodeptr *specialhandle),
30 clean_handle (Xgraph *G, Xnodeptr **handle, Xnodeptrptr **teeth,
31 int *nteeth, int *degree, double *x),
32 clean_stretch (Xgraph *G, Xnode *a, Xnode *b, Xnodeptr **toss,
33 Xnodeptr **tooth, int *degree, double *x),
34 clean_tooth (Xgraph *G, Xnodeptr *handle, Xnodeptr *tooth,
35 Xnodeptr **newtooth, double *x, int *degree),
36 process_clean_tooth_node (Xgraph *G, Xnode *n, double *x, int *degree,
37 Xnodeptr **toss),
38 clean_handle_connect_dfs (Xgraph *G, Xnode *n, double *x, int k);
39
40 static int
41 checkclique_work (Xgraph *G, Xnodeptrptr *handles, Xnodeptrptr *teeth,
42 int flipped),
43 check_for_intersecting_teeth (Xgraph *G, Xnodeptr *handle,
44 Xnodeptrptr *teeth),
45 setmarks (Xgraph *G, int *vec, Xnodeptr *p, int from, int to),
46 check_cavity (Xgraph *G, Xnodeptr *p, int *vec),
47 verify_13 (Xgraph *G, Xnodeptrptr *handles, Xnodeptrptr *teeth),
48 clean_handle_connect (Xgraph *G, Xnodeptr *handle, double *x);
49
50 #else
51
52 static void
53 complement_nodeptrlist (),
54 get_smaller_cliquetree (),
55 clean_handle (),
56 clean_stretch (),
57 clean_tooth (),
58 process_clean_tooth_node (),
59 clean_handle_connect_dfs ();
60
61 static int
62 checkclique_work (),
63 check_for_intersecting_teeth (),
64 setmarks (),
65 check_cavity (),
66 verify_13 (),
67 clean_handle_connect ();
68
69 #endif
70
71
72 #ifdef CC_PROTOTYPE_ANSI
Xcheckcomb(Xgraph * G,Xnodeptr * handle,Xnodeptrptr * teeth)73 int Xcheckcomb (Xgraph *G, Xnodeptr *handle, Xnodeptrptr *teeth)
74 #else
75 int Xcheckcomb (G, handle, teeth)
76 Xgraph *G;
77 Xnodeptr *handle;
78 Xnodeptrptr *teeth;
79 #endif
80 {
81 int nteeth, count, in, out;
82 Xnodeptr *np;
83 Xnodeptrptr *ntp;
84
85 for (nteeth = 0, ntp = teeth; ntp; ntp = ntp->next)
86 nteeth++;
87 if (nteeth % 2 == 0) {
88 return 0;
89 }
90 G->magicnum++;
91 for (count = 0, np = handle; np; np = np->next, count++)
92 np->this->magiclabel = G->magicnum;
93
94 if (count < 3) {
95 return 0;
96 }
97 for (count = 0, ntp = teeth; count < nteeth; ntp = ntp->next, count++) {
98 in = out = 0;
99 for (np = ntp->this; np; np = np->next)
100 if (np->this->magiclabel == G->magicnum)
101 in = 1;
102 else
103 out = 1;
104 if (!in || !out) {
105 return 0;
106 }
107 }
108 return 1;
109 }
110
111 #ifdef CC_PROTOTYPE_ANSI
Xcliquefluff(Xgraph * G,Xnodeptrptr ** handles,Xnodeptrptr ** teeth)112 int Xcliquefluff (Xgraph *G, Xnodeptrptr **handles, Xnodeptrptr **teeth)
113 #else
114 int Xcliquefluff (G, handles, teeth)
115 Xgraph *G;
116 Xnodeptrptr **handles, **teeth;
117 #endif
118 {
119 /* Returns 1 if new clique-tree is loaded in handles and teeth */
120 /* Returns 0 if clique-tree should be killed, wiping out the cut. */
121
122 int nteeth, nhandles, nonpendant, hit, hit1, hit2, cavity;
123 Xnodeptrptr *ntp, *mtp;
124 Xnodeptrptr *nonpendant_teeth, *pendant_teeth;
125 Xnodeptrptr *handle1_teeth, *handle2_teeth;
126 Xnodeptrptr *handle1, *handle2;
127 Xnodeptr *np;
128
129 for (nhandles = 0, ntp = *handles; ntp; ntp = ntp->next)
130 nhandles++;
131 for (nteeth = 0, ntp = *teeth; ntp; ntp = ntp->next)
132 nteeth++;
133
134 if (nhandles == 1)
135 return Xcombfluff (G, handles, teeth, 0);
136
137 if (nteeth % 2 == 0 || nteeth < 3 || nhandles != 2) {
138 Xfreeteeth (*teeth);
139 Xfreeteeth (*handles);
140 /* printf ("FF Wrong Number of Handles or Teeth\n"); */
141 return 0;
142 }
143 /* COLLECT NONPENDANT TEETH */
144
145 nonpendant_teeth = (Xnodeptrptr *) NULL;
146 pendant_teeth = (Xnodeptrptr *) NULL;
147 nonpendant = 0;
148 for (ntp = *teeth; ntp; ntp = ntp->next) {
149 G->magicnum++;
150 for (np = ntp->this; np; np = np->next)
151 np->this->magiclabel = G->magicnum;
152 for (mtp = *handles, hit = 0; mtp && hit < 2; mtp = mtp->next)
153 for (np = mtp->this; np; np = np->next)
154 if (np->this->magiclabel == G->magicnum) {
155 hit++;
156 break;
157 }
158 if (hit >= 2) {
159 nonpendant++;
160 Xadd_nodeptrptr (&nonpendant_teeth, ntp->this);
161 } else
162 Xadd_nodeptrptr (&pendant_teeth, ntp->this);
163 }
164
165 if (nonpendant != 1) {
166 Xnodeptrptr_list_free (nonpendant_teeth);
167 Xnodeptrptr_list_free (pendant_teeth);
168 Xfreeteeth (*teeth);
169 Xfreeteeth (*handles);
170 return 0;
171 }
172 /* DO NOT ALLOW NONPENDANT TEETH TO MEET ANY OTHER TEETH */
173
174 G->magicnum++;
175 for (ntp = pendant_teeth; ntp; ntp = ntp->next)
176 for (np = ntp->this; np; np = np->next)
177 np->this->magiclabel = G->magicnum;
178 for (ntp = nonpendant_teeth; ntp; ntp = ntp->next)
179 for (np = ntp->this; np; np = np->next)
180 if (np->this->magiclabel == G->magicnum) {
181 Xnodeptrptr_list_free (nonpendant_teeth);
182 Xnodeptrptr_list_free (pendant_teeth);
183 Xfreeteeth (*teeth);
184 Xfreeteeth (*handles);
185 /* printf ("FF Nonpendant Teeth Meet\n"); */
186 return 0;
187 } else
188 np->this->magiclabel = G->magicnum;
189
190 /* DIVIDE THE NONPENDANT TEETH AMONGST THE TWO HANDLES */
191
192 G->magicnum++;
193 handle1 = (Xnodeptrptr *) NULL;
194 Xadd_nodeptrptr (&handle1, (*handles)->this);
195 handle1_teeth = (Xnodeptrptr *) NULL;
196 for (np = handle1->this; np; np = np->next)
197 np->this->magiclabel = G->magicnum;
198 for (ntp = pendant_teeth; ntp; ntp = ntp->next)
199 for (np = ntp->this; np; np = np->next)
200 if (np->this->magiclabel == G->magicnum) {
201 Xadd_nodeptrptr (&handle1_teeth, ntp->this);
202 break;
203 }
204 G->magicnum++;
205 handle2 = (Xnodeptrptr *) NULL;
206 Xadd_nodeptrptr (&handle2, (*handles)->next->this);
207 handle2_teeth = (Xnodeptrptr *) NULL;
208 for (np = handle2->this; np; np = np->next)
209 np->this->magiclabel = G->magicnum;
210 for (ntp = pendant_teeth; ntp; ntp = ntp->next)
211 for (np = ntp->this; np; np = np->next)
212 if (np->this->magiclabel == G->magicnum) {
213 Xadd_nodeptrptr (&handle2_teeth, ntp->this);
214 break;
215 }
216 /* WE NO LONGER NEED THE ORIGINAL HANDLE & TEETH LISTS */
217
218 Xnodeptrptr_list_free (*handles);
219 Xnodeptrptr_list_free (*teeth);
220 Xnodeptrptr_list_free (pendant_teeth);
221
222 /* DON'T ALLOW ANY TOOTH TO MEET A TOOTH HITTING THE OTHER HANDLE */
223
224 G->magicnum++;
225 for (ntp = handle1_teeth; ntp; ntp = ntp->next)
226 for (np = ntp->this; np; np = np->next)
227 np->this->magiclabel = G->magicnum;
228 for (ntp = handle2_teeth; ntp; ntp = ntp->next)
229 for (np = ntp->this; np; np = np->next)
230 if (np->this->magiclabel == G->magicnum) {
231 Xfreeteeth (handle1_teeth);
232 Xfreeteeth (handle2_teeth);
233 Xfreeteeth (handle1);
234 Xfreeteeth (handle2);
235 Xfreeteeth (nonpendant_teeth);
236 /* printf ("FF Cross Teeth Meet\n"); */
237 return 0;
238 }
239
240 /* USE THE COMB CODE TO CLEAN THE TEETH MEETING EACH HANDLE */
241
242 if (!Xcombfluff (G, &handle1, &handle1_teeth, 1)) {
243 Xfreeteeth (handle2);
244 Xfreeteeth (handle2_teeth);
245 Xfreeteeth (nonpendant_teeth);
246 /* printf ("FF Comb Fluff of First Handle Failed\n"); */
247 return 0;
248 } else if (!Xcombfluff (G, &handle2, &handle2_teeth, 1)) {
249 Xfreeteeth (handle1);
250 Xfreeteeth (handle1_teeth);
251 Xfreeteeth (nonpendant_teeth);
252 /* printf ("FF Comb Fluff of Second Handle Failed\n"); */
253 return 0;
254 }
255 if (!handle1 || !handle2 || !handle1_teeth || !handle2_teeth) {
256 /* printf ("OH OH IN FLUFF\n"); */
257 return 0;
258 }
259
260 /* CHECK THAT NEW HANDLES DO NOT MEET */
261
262 G->magicnum++;
263 for (np = handle1->this; np; np = np->next)
264 np->this->magiclabel = G->magicnum;
265 G->magicnum++;
266 for (np = handle2->this; np; np = np->next)
267 if (np->this->magiclabel == G->magicnum - 1) {
268 Xfreeteeth (handle1);
269 Xfreeteeth (handle2);
270 Xfreeteeth (handle1_teeth);
271 Xfreeteeth (handle2_teeth);
272 Xfreeteeth (nonpendant_teeth);
273 /* printf ("FF New Handles Meet\n"); */
274 return 0;
275 } else
276 np->this->magiclabel = G->magicnum;
277
278 /* CHECK THAT NONPENDANT TOOTH HAS A CAVITY */
279
280 for (np = nonpendant_teeth->this, hit1 = 0, hit2 = 0, cavity = 0; np;
281 np = np->next) {
282 if (np->this->magiclabel == G->magicnum - 1)
283 hit1++;
284 else if (np->this->magiclabel == G->magicnum)
285 hit2++;
286 else
287 cavity++;
288 }
289
290 if (!hit1 || !hit2 || !cavity) {
291 Xfreeteeth (handle1);
292 Xfreeteeth (handle2);
293 Xfreeteeth (handle1_teeth);
294 Xfreeteeth (handle2_teeth);
295 Xfreeteeth (nonpendant_teeth);
296 /* printf ("FF Nonpendant Tooth No Longer Has a Cavity\n"); */
297 return 0;
298 }
299
300 /* PUT THE NEW CLIQUE TREE TOGETHER */
301
302 handle1->next = handle2;
303 *handles = handle1;
304
305 ntp = handle1_teeth;
306 while (ntp->next)
307 ntp = ntp->next;
308 if (!ntp) {
309 /* printf ("OH OH 2 IN FLUFF\n"); */
310 return 0;
311 }
312 ntp->next = handle2_teeth;
313 nonpendant_teeth->next = handle1_teeth;
314 *teeth = nonpendant_teeth;
315
316 return 1;
317 }
318
319 #ifdef CC_PROTOTYPE_ANSI
Xtemp_combfluff(Xgraph * G,Xnodeptr ** handle,Xnodeptrptr ** teeth)320 int Xtemp_combfluff (Xgraph *G, Xnodeptr **handle, Xnodeptrptr **teeth)
321 #else
322 int Xtemp_combfluff (G, handle, teeth)
323 Xgraph *G;
324 Xnodeptr **handle;
325 Xnodeptrptr **teeth;
326 #endif
327 {
328 Xnodeptrptr *temphandle;
329
330 temphandle = (Xnodeptrptr *) NULL;
331 Xadd_nodeptrptr (&temphandle, *handle);
332 if (!Xcliquefluff (G, &temphandle, teeth)) {
333 return 0;
334 } else {
335 *handle = temphandle->this;
336 Xnodeptrptrfree (temphandle);
337 return 1;
338 }
339 }
340
341 #ifdef CC_PROTOTYPE_ANSI
Xtemp_combcheck(Xgraph * G,Xnodeptr * handle,Xnodeptrptr * teeth)342 int Xtemp_combcheck (Xgraph *G, Xnodeptr *handle, Xnodeptrptr *teeth)
343 #else
344 int Xtemp_combcheck (G, handle, teeth)
345 Xgraph *G;
346 Xnodeptr *handle;
347 Xnodeptrptr *teeth;
348 #endif
349 {
350 int rval;
351 Xnodeptrptr *temphandle;
352
353 temphandle = (Xnodeptrptr *) NULL;
354 Xadd_nodeptrptr (&temphandle, handle);
355
356 rval = Xcheckclique (G, temphandle, teeth);
357 Xnodeptrptrfree (temphandle);
358 return rval;
359 }
360
361 #define SET_NOTEST -2
362
363 #ifdef CC_PROTOTYPE_ANSI
Xcombfluff(Xgraph * G,Xnodeptrptr ** handles,Xnodeptrptr ** teeth,int cliquetest)364 int Xcombfluff (Xgraph *G, Xnodeptrptr **handles, Xnodeptrptr **teeth,
365 int cliquetest)
366 #else
367 int Xcombfluff (G, handles, teeth, cliquetest)
368 Xgraph *G;
369 Xnodeptrptr **handles;
370 Xnodeptrptr **teeth;
371 int cliquetest;
372 #endif
373 {
374 int *in_hand;
375 int *in_tooth;
376 int i, j;
377 int nhand;
378 int nteeth;
379 int newteeth;
380 Xnodeptr **teeth_array;
381 Xnodeptr *p;
382 Xnodeptrptr *np;
383 int v;
384
385 for (np = *handles, nhand = 0; np; np = np->next)
386 nhand++;
387 for (np = *teeth, nteeth = 0; np; np = np->next)
388 nteeth++;
389 if (nhand != 1) {
390 /*
391 printf ("FF Fluff Comb called with more (or less) than one handle\n");
392 */
393 Xfreeteeth (*handles);
394 Xfreeteeth (*teeth);
395 return 0;
396 }
397 if (nteeth == 3 && !cliquetest) {
398 if (verify_13 (G, *handles, *teeth)) {
399 return 1;
400 } else {
401 for (np = *handles; np; np = np->next) {
402 Xnodeptr_list_free (np->this);
403 }
404 for (np = *teeth; np; np = np->next) {
405 Xnodeptr_list_free (np->this);
406 }
407 Xnodeptrptr_list_free (*handles);
408 Xnodeptrptr_list_free (*teeth);
409 *handles = (Xnodeptrptr *) NULL;
410 *teeth = (Xnodeptrptr *) NULL;
411 /* printf ("FF Fluff Comb\n"); */
412 return 0;
413 }
414 }
415 in_hand = CC_SAFE_MALLOC (G->nnodes, int);
416 in_tooth = CC_SAFE_MALLOC (G->nnodes, int);
417 if (!in_hand || !in_tooth) {
418 fprintf (stderr, "out of memory in Xcombfluff\n");
419 exit (1);
420 }
421
422 for (i = 0; i < G->nnodes; i++) {
423 in_hand[i] = 0;
424 in_tooth[i] = -1;
425 }
426
427 if (setmarks (G, in_hand, (*handles)->this, 0, 1) != SET_NOTEST) {
428 fprintf (stderr, "A setmarks failed\n");
429 exit (1);
430 }
431 Xnodeptr_list_free ((*handles)->this);
432
433 teeth_array = CC_SAFE_MALLOC (nteeth, Xnodeptr *);
434 if (!teeth_array) {
435 fprintf (stderr, "out of memory in Xcombfluff\n");
436 exit (1);
437 }
438
439 for (np = *teeth, i = 0; np; np = np->next, i++) {
440 teeth_array[i] = np->this;
441 }
442 Xnodeptrptr_list_free (*teeth);
443
444 for (i = 0; i < nteeth; i++) {
445 v = setmarks (G, in_tooth, teeth_array[i], -1, i);
446 if (v != SET_NOTEST) {
447 j = in_tooth[v];
448 if (setmarks (G, in_tooth, teeth_array[i], i, -1) != v ||
449 setmarks (G, in_tooth, teeth_array[j], j, -1) != SET_NOTEST) {
450 fprintf (stderr, "B setmarks failed\n");
451 exit (1);
452 }
453 if (in_hand[v]) {
454 setmarks (G, in_hand, teeth_array[i], SET_NOTEST, 0);
455 setmarks (G, in_hand, teeth_array[j], SET_NOTEST, 0);
456 } else {
457 setmarks (G, in_hand, teeth_array[i], SET_NOTEST, 1);
458 setmarks (G, in_hand, teeth_array[j], SET_NOTEST, 1);
459 }
460 Xnodeptr_list_free (teeth_array[i]);
461 Xnodeptr_list_free (teeth_array[j]);
462 teeth_array[i] = (Xnodeptr *) NULL;
463 teeth_array[j] = (Xnodeptr *) NULL;
464 }
465 }
466 *teeth = (Xnodeptrptr *) NULL;
467 for (i = 0, newteeth = 0; i < nteeth; i++) {
468 if (teeth_array[i]) {
469 if (check_cavity (G, teeth_array[i], in_hand)) {
470 newteeth++;
471 Xadd_nodeptrptr (teeth, teeth_array[i]);
472 } else {
473 Xnodeptr_list_free (teeth_array[i]);
474 teeth_array[i] = (Xnodeptr *) NULL;
475 }
476 }
477 }
478
479 if (newteeth > 1 && (((!cliquetest && (newteeth & 1) == 1)) ||
480 (cliquetest && (newteeth & 1) == 0))) {
481 p = (Xnodeptr *) NULL;
482 for (i = 0; i < G->nnodes; i++) {
483 if (in_hand[i]) {
484 Xadd_nodeptr (&p, &(G->nodelist[i]));
485 }
486 }
487 *handles = (Xnodeptrptr *) NULL;
488 Xadd_nodeptrptr (handles, p);
489 CC_FREE (in_hand, int);
490 CC_FREE (in_tooth, int);
491 CC_FREE (teeth_array, Xnodeptr *);
492 return 1;
493 } else {
494 for (np = *teeth; np; np = np->next) {
495 Xnodeptr_list_free (np->this);
496 }
497 Xnodeptrptr_list_free (*teeth);
498 *teeth = (Xnodeptrptr *) NULL;
499 *handles = (Xnodeptrptr *) NULL;
500 CC_FREE (in_hand, int);
501 CC_FREE (in_tooth, int);
502 CC_FREE (teeth_array, Xnodeptr *);
503 /* printf ("FF Fluff Comb\n"); */
504 return 0;
505 }
506 }
507
508 #ifdef CC_PROTOTYPE_ANSI
setmarks(Xgraph * G,int * vec,Xnodeptr * p,int from,int to)509 static int setmarks (Xgraph *G, int *vec, Xnodeptr *p, int from, int to)
510 #else
511 static int setmarks (G, vec, p, from, to)
512 Xgraph *G;
513 int *vec;
514 Xnodeptr *p;
515 int from, to;
516 #endif
517 {
518 if (from == SET_NOTEST) {
519 while (p) {
520 vec[p->this - G->nodelist] = to;
521 p = p->next;
522 }
523 } else {
524 while (p) {
525 if (vec[p->this - G->nodelist] != from) {
526 return p->this - G->nodelist;
527 }
528 vec[p->this - G->nodelist] = to;
529 p = p->next;
530 }
531 }
532 return SET_NOTEST;
533 }
534
535 #ifdef CC_PROTOTYPE_ANSI
check_cavity(Xgraph * G,Xnodeptr * p,int * vec)536 static int check_cavity (Xgraph *G, Xnodeptr *p, int *vec)
537 #else
538 static int check_cavity (G, p, vec)
539 Xgraph *G;
540 Xnodeptr *p;
541 int *vec;
542 #endif
543 {
544 int got_hand = 0;
545 int got_cavity = 0;
546
547 while (p) {
548 if (vec[p->this - G->nodelist]) {
549 if (got_cavity)
550 return 1;
551 got_hand++;
552 } else {
553 if (got_hand)
554 return 1;
555 got_cavity++;
556 }
557 p = p->next;
558 }
559 return 0;
560 }
561
562 #define HANDLE 1
563 #define TOOTH1 2
564 #define TOOTH2 4
565 #define TOOTH3 8
566 #define NREGIONS 16
567
568 #ifdef CC_PROTOTYPE_ANSI
verify_13(Xgraph * G,Xnodeptrptr * handles,Xnodeptrptr * teeth)569 static int verify_13 (Xgraph *G, Xnodeptrptr *handles, Xnodeptrptr *teeth)
570 #else
571 static int verify_13 (G, handles, teeth)
572 Xgraph *G;
573 Xnodeptrptr *handles;
574 Xnodeptrptr *teeth;
575 #endif
576 {
577 unsigned int *node_stat;
578 unsigned int flip;
579 unsigned int hist[NREGIONS];
580 unsigned int hist2[NREGIONS];
581 int i;
582 Xnodeptr *p;
583 Xnodeptrptr *pp;
584 int nhand;
585 int nteeth;
586
587 node_stat = CC_SAFE_MALLOC (G->nnodes, unsigned int);
588 if (!node_stat) {
589 fprintf (stderr, "out of memory in verify_13\n");
590 exit (1);
591 }
592
593 for (i = 0; i < G->nnodes; i++) {
594 node_stat[i] = 0;
595 }
596 for (pp = handles, nhand = 0; pp; pp = pp->next, nhand++) {
597 for (p = pp->this; p; p = p->next) {
598 node_stat[p->this - G->nodelist] |= (1 << nhand);
599 }
600 }
601 for (pp = teeth, nteeth = 0; pp; pp = pp->next, nteeth++) {
602 for (p = pp->this; p; p = p->next) {
603 node_stat[p->this - G->nodelist] |= 1 << (nhand + nteeth);
604 }
605 }
606 if (nhand != 1 || nteeth != 3) {
607 CC_FREE (node_stat, unsigned int);
608 return 0;
609 }
610 for (i = 0; i < NREGIONS; i++) {
611 hist[i] = 0;
612 }
613 for (i = 0; i < G->nnodes; i++) {
614 hist[node_stat[i]]++;
615 }
616 for (flip = 0; flip < NREGIONS; flip++) {
617 for (i = 0; i < NREGIONS; i++) {
618 hist2[i] = hist[i ^ flip];
619 }
620 if (Xhistok (hist2)) {
621 CC_FREE (node_stat, unsigned int);
622 return 1;
623 }
624 }
625 CC_FREE (node_stat, unsigned int);
626 /* printf ("CC Verify special failed to find a good flip\n"); */
627 return 0;
628 }
629
630 #ifdef CC_PROTOTYPE_ANSI
Xhistok(unsigned int * hist)631 int Xhistok (unsigned int *hist)
632 #else
633 int Xhistok (hist)
634 unsigned int *hist;
635 #endif
636 {
637 if (!hist[TOOTH1])
638 return 0; /* tooth 1 has a cavity */
639 if (!hist[TOOTH2])
640 return 0; /* tooth 2 has a cavity */
641 if (!hist[TOOTH3])
642 return 0; /* tooth 3 has a cavity */
643 if (!hist[TOOTH1 | HANDLE])
644 return 0; /* tooth 1 intersects the handle */
645 if (!hist[TOOTH2 | HANDLE])
646 return 0; /* tooth 1 intersects the handle */
647 if (!hist[TOOTH3 | HANDLE])
648 return 0; /* tooth 1 intersects the handle */
649 if (hist[TOOTH1 | TOOTH2] ||/* Nothing else happens */
650 hist[TOOTH1 | TOOTH3] ||
651 hist[TOOTH2 | TOOTH3] ||
652 hist[TOOTH1 | TOOTH2 | TOOTH3] ||
653 hist[TOOTH1 | TOOTH2 | HANDLE] ||
654 hist[TOOTH1 | TOOTH3 | HANDLE] ||
655 hist[TOOTH2 | TOOTH3 | HANDLE] ||
656 hist[TOOTH1 | TOOTH2 | TOOTH3 | HANDLE]) {
657 return 0;
658 }
659 return 1;
660 }
661
662 #ifdef CC_PROTOTYPE_ANSI
Xcheckclique(Xgraph * G,Xnodeptrptr * handles,Xnodeptrptr * teeth)663 int Xcheckclique (Xgraph *G, Xnodeptrptr *handles, Xnodeptrptr *teeth)
664 #else
665 int Xcheckclique (G, handles, teeth)
666 Xgraph *G;
667 Xnodeptrptr *handles, *teeth;
668 #endif
669 {
670 return checkclique_work (G, handles, teeth, 0);
671 }
672
673 #ifdef CC_PROTOTYPE_ANSI
checkclique_work(Xgraph * G,Xnodeptrptr * handles,Xnodeptrptr * teeth,int flipped)674 static int checkclique_work (Xgraph *G, Xnodeptrptr *handles,
675 Xnodeptrptr *teeth, int flipped)
676 #else
677 static int checkclique_work (G, handles, teeth, flipped)
678 Xgraph *G;
679 Xnodeptrptr *handles, *teeth;
680 int flipped;
681 #endif
682 {
683 int nteeth, nhandles, nonpendant, hit, cavity, inhit;
684 Xnodeptr *np, *mp, *newtooth;
685 Xnodeptrptr *ntp, *mtp, *nonpendant_teeth, *pendant_teeth;
686 Xnodeptrptr *newhandles, *newteeth;
687 int special13, rval;
688
689 for (nteeth = 0, ntp = teeth; ntp; ntp = ntp->next)
690 nteeth++;
691 if (nteeth % 2 == 0) {
692 /* printf ("CC Even Number of Teeth: %d\n", nteeth); */
693 return 0;
694 }
695 for (nhandles = 0, ntp = handles; ntp; ntp = ntp->next)
696 nhandles++;
697
698 if (nhandles == 0) {
699 /* printf ("CC No Handles\n"); */
700 return 0;
701 }
702 if (nhandles == 1 && nteeth == 3)
703 special13 = 1;
704 else
705 special13 = 0;
706
707
708 /* EASY STUFF - Emtpy cliques, bad node numbers, etc. */
709
710 for (ntp = handles; ntp; ntp = ntp->next) {
711 if (!ntp->this) {
712 /* printf ("CC Empty Handle\n"); */
713 return 0;
714 }
715 for (hit = 0, np = ntp->this; np; np = np->next) {
716 if ((np->this - G->nodelist) < 0 ||
717 (np->this - G->nodelist) >= G->nnodes) {
718 /* printf ("CC Invalid node number in handle\n"); */
719 return 0;
720 } else
721 hit++;
722 }
723 if (hit >= G->nnodes) {
724 /* printf ("CC Handle is entire graph\n"); */
725 return 0;
726 }
727 }
728
729 for (ntp = teeth; ntp; ntp = ntp->next) {
730 if (!ntp->this) {
731 /* printf ("CC Empty Tooth\n"); */
732 return 0;
733 }
734 for (hit = 0, np = ntp->this; np; np = np->next) {
735 if ((np->this - G->nodelist) < 0 ||
736 (np->this - G->nodelist) >= G->nnodes) {
737 /* printf ("CC Invalid node number in tooth\n"); */
738 return 0;
739 } else
740 hit++;
741 }
742 if (hit >= G->nnodes) {
743 /* printf ("CC Tooth is entire graph\n"); */
744 return 0;
745 }
746 }
747
748 /* HANDLES SHOULD NEVER INTERSECT */
749
750 G->magicnum++;
751 for (ntp = handles; ntp; ntp = ntp->next)
752 for (np = ntp->this; np; np = np->next)
753 if (np->this->magiclabel == G->magicnum) {
754 if (special13)
755 return verify_13 (G, handles, teeth);
756 else {
757 /* printf ("CC Handles Meet\n"); */
758 return 0;
759 }
760 } else
761 np->this->magiclabel = G->magicnum;
762
763
764 /* INSIST THAT EVERY TOOTH HAVE A CAVITY, UNLESS WE HAVE THE 1-3 */
765 /* CASE, WHERE WE ALLOW THE INVERTED TOOTH TO HAVE NO CAVITY. */
766
767 for (ntp = teeth; ntp; ntp = ntp->next) {
768 cavity = inhit = 0;
769 for (np = ntp->this; np; np = np->next)
770 if (np->this->magiclabel != G->magicnum)
771 cavity++;
772 else
773 inhit++;
774 if (!cavity || !inhit) {
775 if (special13)
776 return verify_13 (G, handles, teeth);
777 else {
778 /* printf ("CC Tooth has no cavity\n"); */
779 return 0;
780 }
781 }
782 }
783
784 /* EVERY HANDLE HITS AN ODD NUMBER OF TEETH */
785
786 for (ntp = handles; ntp; ntp = ntp->next) {
787 G->magicnum++;
788 for (np = ntp->this; np; np = np->next)
789 np->this->magiclabel = G->magicnum;
790 for (hit = 0, mtp = teeth; mtp; mtp = mtp->next)
791 for (mp = mtp->this; mp; mp = mp->next)
792 if (mp->this->magiclabel == G->magicnum) {
793 hit++;
794 break;
795 }
796 if (hit % 2 == 0) {
797 if (special13)
798 return verify_13 (G, handles, teeth);
799 else {
800 /* printf ("CC Handle hits even num of teeth\n"); */
801 return 0;
802 }
803 }
804 }
805
806 /* TEETH IN COMBS CANNOT INTERSECT UNLESS 1-3 CASE */
807
808 if (nhandles == 1) {
809 G->magicnum++;
810 for (ntp = teeth; ntp; ntp = ntp->next) {
811 for (np = ntp->this; np; np = np->next) {
812 if (np->this->magiclabel == G->magicnum) {
813 if (special13)
814 return verify_13 (G, handles, teeth);
815 else {
816 /* printf ("CC Teeth in Comb\n"); */
817 return 0;
818 }
819 /*
820 }
821 */
822
823 } else {
824 np->this->magiclabel = G->magicnum;
825 }
826
827
828 /******************** BUG *************************************
829 SHOULD HAVE: } else {
830 np->this->magiclabel = G->magicnum;
831 }
832 **************************************************************/
833
834 }
835 }
836 return 1;
837 }
838 /* Deal with a multihandled cliquetree by finding a handle to */
839 /* delete and check that the remainder is a valid cliquetree. */
840
841
842 nonpendant_teeth = (Xnodeptrptr *) NULL;
843 pendant_teeth = (Xnodeptrptr *) NULL;
844 nonpendant = 0;
845 for (ntp = teeth; ntp; ntp = ntp->next) {
846 G->magicnum++;
847 for (np = ntp->this; np; np = np->next)
848 np->this->magiclabel = G->magicnum;
849 for (mtp = handles, hit = 0; mtp && hit < 2; mtp = mtp->next)
850 for (np = mtp->this; np; np = np->next)
851 if (np->this->magiclabel == G->magicnum) {
852 hit++;
853 break;
854 }
855 if (hit >= 2) {
856 nonpendant++;
857 Xadd_nodeptrptr (&nonpendant_teeth, ntp->this);
858 } else
859 Xadd_nodeptrptr (&pendant_teeth, ntp->this);
860 }
861
862 if (nonpendant > nhandles - 1) {
863 /*
864 printf ("CC %d handles, but %d nonpendant teeth\n",
865 nhandles, nonpendant);
866 */
867 Xnodeptrptr_list_free (nonpendant_teeth);
868 Xnodeptrptr_list_free (pendant_teeth);
869 Xprintcliquetree (G, handles, teeth);
870 return 0;
871 }
872 for (ntp = handles; ntp; ntp = ntp->next) {
873 G->magicnum++;
874 for (np = ntp->this; np; np = np->next)
875 np->this->magiclabel = G->magicnum;
876 for (mtp = nonpendant_teeth, hit = 0; mtp && hit < 2; mtp = mtp->next)
877 for (np = mtp->this; np; np = np->next)
878 if (np->this->magiclabel == G->magicnum) {
879 hit++;
880 break;
881 }
882 if (!hit) {
883 /* printf ("CC Handle meets no nonpendant tooth\n"); */
884 Xnodeptrptr_list_free (nonpendant_teeth);
885 Xnodeptrptr_list_free (pendant_teeth);
886 return 0;
887 } else if (hit == 1) {
888 if (check_for_intersecting_teeth (G, ntp->this, teeth)) {
889 get_smaller_cliquetree (G, &newhandles, &newteeth,
890 handles, teeth, ntp->this);
891 rval = checkclique_work (G, newhandles, newteeth, flipped);
892 Xnodeptrptr_list_free (nonpendant_teeth);
893 Xnodeptrptr_list_free (pendant_teeth);
894 Xnodeptrptr_list_free (newhandles);
895 Xnodeptrptr_list_free (newteeth);
896 if (!rval) {
897 printf ("CC Bad Recursion\n");
898 Xprintcliquetree (G, handles, teeth);
899 fflush (stdout);
900 }
901 return rval;
902 }
903 }
904 }
905
906 if (nhandles > 2) {
907 /* printf ("CC No good handle (%d) to reduce\n", nhandles); */
908 }
909
910 /* TRY FLIPPING THE NONPENDANT TOOTH IN TWO HANDLED CASE */
911
912 if (nhandles == 2 && !flipped) {
913 complement_nodeptrlist (G, nonpendant_teeth->this, &newtooth);
914 Xadd_nodeptrptr (&pendant_teeth, newtooth);
915 rval = checkclique_work (G, handles, pendant_teeth, 1);
916 Xnodeptr_list_free (newtooth);
917 Xnodeptrptr_list_free (nonpendant_teeth);
918 Xnodeptrptr_list_free (pendant_teeth);
919 if (rval) {
920 /* printf ("CC Needed to Flip the nonpendant tooth.\n"); */
921 } else {
922 /* printf ("CC FLIP DID NOT HELP\n"); */
923 }
924 return rval;
925 } else {
926 Xnodeptrptr_list_free (nonpendant_teeth);
927 Xnodeptrptr_list_free (pendant_teeth);
928 return 0;
929 }
930 }
931
932 #ifdef CC_PROTOTYPE_ANSI
complement_nodeptrlist(Xgraph * G,Xnodeptr * list,Xnodeptr ** new)933 static void complement_nodeptrlist (Xgraph *G, Xnodeptr *list, Xnodeptr **new)
934 #else
935 static void complement_nodeptrlist (G, list, new)
936 Xgraph *G;
937 Xnodeptr *list, **new;
938 #endif
939 {
940 Xnodeptr *np;
941 int i;
942 Xnode *n;
943
944 *new = (Xnodeptr *) NULL;
945 G->magicnum++;
946 for (np = list; np; np = np->next)
947 np->this->magiclabel = G->magicnum;
948 for (i = G->nnodes, n = G->nodelist; i; i--, n++)
949 if (n->magiclabel != G->magicnum)
950 Xadd_nodeptr (new, n);
951 }
952
953 #ifdef CC_PROTOTYPE_ANSI
get_smaller_cliquetree(Xgraph * G,Xnodeptrptr ** newhandles,Xnodeptrptr ** newteeth,Xnodeptrptr * handles,Xnodeptrptr * teeth,Xnodeptr * specialhandle)954 static void get_smaller_cliquetree (Xgraph *G, Xnodeptrptr **newhandles,
955 Xnodeptrptr **newteeth, Xnodeptrptr *handles, Xnodeptrptr *teeth,
956 Xnodeptr *specialhandle)
957 #else
958 static void get_smaller_cliquetree (G, newhandles, newteeth, handles,
959 teeth, specialhandle)
960 Xgraph *G;
961 Xnodeptrptr **newhandles, **newteeth, *handles, *teeth;
962 Xnodeptr *specialhandle;
963 #endif
964 {
965 Xnodeptrptr *ntp, *mtp;
966 Xnodeptr *np;
967 int hit;
968
969 *newhandles = (Xnodeptrptr *) NULL;
970 for (ntp = handles; ntp; ntp = ntp->next)
971 if (ntp->this != specialhandle)
972 Xadd_nodeptrptr (newhandles, ntp->this);
973 *newteeth = (Xnodeptrptr *) NULL;
974 for (ntp = teeth; ntp; ntp = ntp->next) {
975 G->magicnum++;
976 for (np = ntp->this; np; np = np->next)
977 np->this->magiclabel = G->magicnum;
978 for (mtp = *newhandles, hit = 0; mtp && !hit; mtp = mtp->next) {
979 for (np = mtp->this; np; np = np->next)
980 if (np->this->magiclabel == G->magicnum) {
981 hit++;
982 break;
983 }
984 }
985 if (hit)
986 Xadd_nodeptrptr (newteeth, ntp->this);
987 }
988 }
989
990 #ifdef CC_PROTOTYPE_ANSI
check_for_intersecting_teeth(Xgraph * G,Xnodeptr * handle,Xnodeptrptr * teeth)991 static int check_for_intersecting_teeth (Xgraph *G, Xnodeptr *handle,
992 Xnodeptrptr *teeth)
993 #else
994 static int check_for_intersecting_teeth (G, handle, teeth)
995 Xgraph *G;
996 Xnodeptr *handle;
997 Xnodeptrptr *teeth;
998 #endif
999 {
1000 Xnodeptrptr *ntp;
1001 Xnodeptr *np;
1002 Xnodeptrptr *handle_teeth;
1003
1004 G->magicnum++;
1005 for (np = handle; np; np = np->next)
1006 np->this->magiclabel = G->magicnum;
1007 handle_teeth = (Xnodeptrptr *) NULL;
1008 for (ntp = teeth; ntp; ntp = ntp->next)
1009 for (np = ntp->this; np; np = np->next)
1010 if (np->this->magiclabel == G->magicnum) {
1011 Xadd_nodeptrptr (&handle_teeth, ntp->this);
1012 break;
1013 }
1014 G->magicnum++;
1015 for (ntp = handle_teeth; ntp; ntp = ntp->next)
1016 for (np = ntp->this; np; np = np->next)
1017 if (np->this->magiclabel == G->magicnum) {
1018 Xnodeptrptr_list_free (handle_teeth);
1019 return 0;
1020 } else
1021 np->this->magiclabel = G->magicnum;
1022
1023 Xnodeptrptr_list_free (handle_teeth);
1024 return 1;
1025 }
1026
1027 #ifdef CC_PROTOTYPE_ANSI
Xcleancomb(Xgraph * G,Xnodeptr ** handle,Xnodeptrptr ** teeth,int * nteeth,double * x)1028 void Xcleancomb (Xgraph *G, Xnodeptr **handle, Xnodeptrptr **teeth,
1029 int *nteeth, double *x)
1030 #else
1031 void Xcleancomb (G, handle, teeth, nteeth, x)
1032 Xgraph *G;
1033 Xnodeptr **handle;
1034 Xnodeptrptr **teeth;
1035 int *nteeth;
1036 double *x;
1037 #endif
1038 {
1039 int *degree;
1040 Xnodeptrptr *newteeth, *ntp, *newtp;
1041
1042 /* The cleaned comb goes back into handle and teeth. */
1043
1044 if (x == (double *) NULL)
1045 return;
1046
1047 newteeth = (Xnodeptrptr *) NULL;
1048
1049 degree = CC_SAFE_MALLOC (G->nnodes, int);
1050 if (!degree) {
1051 fprintf (stderr, "out of memory in cleancomb\n");
1052 exit (1);
1053 }
1054 for (ntp = *teeth; ntp; ntp = ntp->next) {
1055 newtp = Xnodeptrptralloc ();
1056 newtp->this = (Xnodeptr *) NULL;
1057 newtp->next = newteeth;
1058 newteeth = newtp;
1059 clean_tooth (G, *handle, ntp->this, &(newtp->this), x, degree);
1060 }
1061
1062 Xfreeteeth (*teeth);
1063
1064 *teeth = newteeth;
1065
1066 clean_handle (G, handle, teeth, nteeth, degree, x);
1067
1068 CC_FREE (degree, int);
1069 }
1070
1071 #ifdef CC_PROTOTYPE_ANSI
clean_handle(Xgraph * G,Xnodeptr ** handle,Xnodeptrptr ** teeth,int * nteeth,int * degree,double * x)1072 static void clean_handle (Xgraph *G, Xnodeptr **handle, Xnodeptrptr **teeth,
1073 int *nteeth, int *degree, double *x)
1074 #else
1075 static void clean_handle (G, handle, teeth, nteeth, degree, x)
1076 Xgraph *G;
1077 Xnodeptr **handle;
1078 Xnodeptrptr **teeth;
1079 int *nteeth, *degree;
1080 double *x;
1081 #endif
1082 {
1083 Xnodeptr *np, *toss = (Xnodeptr *) NULL;
1084 Xnodeptrptr *ntp;
1085 Xnodeptr *tooth1, *tooth2, *newhandle;
1086 Xnode *n, *n1;
1087 Xedgeptr *ep;
1088 Xedge *e;
1089
1090 if (!clean_handle_connect (G, *handle, x))
1091 return;
1092
1093 G->magicnum++;
1094 for (np = *handle; np; np = np->next) {
1095 np->this->magiclabel = G->magicnum;
1096 degree[np->this - G->nodelist] = 0;
1097 }
1098 for (np = *handle; np; np = np->next) {
1099 n = np->this;
1100 for (ep = n->adj.head; ep; ep = ep->next) {
1101 e = ep->this;
1102 if (x[e - G->edgelist] > .9999 &&
1103 e->ends[0]->magiclabel == G->magicnum &&
1104 e->ends[1]->magiclabel == G->magicnum)
1105 (degree[n - G->nodelist])++;
1106 }
1107 }
1108 for (ntp = *teeth; ntp; ntp = ntp->next)
1109 for (np = ntp->this; np; np = np->next)
1110 np->this->magiclabel = G->magicnum - 1;
1111
1112 for (np = *handle; np; np = np->next) {
1113 n = np->this;
1114 if (degree[n - G->nodelist] != 2 || n->magiclabel != G->magicnum)
1115 continue;
1116 for (ep = n->adj.head; ep; ep = ep->next) {
1117 e = ep->this;
1118 n1 = OTHEREND (e, n);
1119 if (x[e - G->edgelist] > .9999 &&
1120 n1->magiclabel == G->magicnum &&
1121 degree[n1 - G->nodelist] == 2) {
1122 Xadd_nodeptr (&toss, n);
1123 Xadd_nodeptr (&toss, n1);
1124 degree[n - G->nodelist] = 0;
1125 degree[n1 - G->nodelist] = 0;
1126 clean_stretch (G, n, n1, &toss, &tooth1, degree, x);
1127 clean_stretch (G, n1, n, &toss, &tooth2, degree, x);
1128 Xadd_nodeptrptr (teeth, tooth1);
1129 Xadd_nodeptrptr (teeth, tooth2);
1130 (*nteeth) += 2;
1131 break;
1132 }
1133 }
1134 }
1135 G->magicnum++;
1136 for (np = toss; np; np = np->next)
1137 np->this->magiclabel = G->magicnum;
1138
1139 Xnodeptr_list_free (toss);
1140
1141 newhandle = (Xnodeptr *) NULL;
1142 for (np = *handle; np; np = np->next)
1143 if (np->this->magiclabel != G->magicnum)
1144 Xadd_nodeptr (&newhandle, np->this);
1145 Xnodeptr_list_free (*handle);
1146 *handle = newhandle;
1147 }
1148
1149 #ifdef CC_PROTOTYPE_ANSI
clean_stretch(Xgraph * G,Xnode * a,Xnode * b,Xnodeptr ** toss,Xnodeptr ** tooth,int * degree,double * x)1150 static void clean_stretch (Xgraph *G, Xnode *a, Xnode *b, Xnodeptr **toss,
1151 Xnodeptr **tooth, int *degree, double *x)
1152 #else
1153 static void clean_stretch (G, a, b, toss, tooth, degree, x)
1154 Xgraph *G;
1155 Xnode *a, *b;
1156 Xnodeptr **toss, **tooth;
1157 int *degree;
1158 double *x;
1159 #endif
1160 {
1161 Xnode *c;
1162 Xedgeptr *ep;
1163 Xedge *e;
1164
1165 for (ep = a->adj.head; ep; ep = ep->next) {
1166 e = ep->this;
1167 if (x[e - G->edgelist] > .9999 && ((c = OTHEREND (e, a)) != b)) {
1168 if (degree[c - G->nodelist] == 2 &&
1169 c->magiclabel == G->magicnum) {
1170 Xadd_nodeptr (toss, c);
1171 degree[c - G->nodelist] = 0;
1172 clean_stretch (G, c, a, toss, tooth, degree, x);
1173 } else {
1174 *tooth = (Xnodeptr *) NULL;
1175 Xadd_nodeptr (tooth, a);
1176 Xadd_nodeptr (tooth, c);
1177 }
1178 return;
1179 }
1180 }
1181 printf ("ERROR IN CLEAN_STRETCH\n");
1182 fflush (stdout);
1183 }
1184
1185 #ifdef CC_PROTOTYPE_ANSI
clean_tooth(Xgraph * G,Xnodeptr * handle,Xnodeptr * tooth,Xnodeptr ** newtooth,double * x,int * degree)1186 static void clean_tooth (Xgraph *G, Xnodeptr *handle, Xnodeptr *tooth,
1187 Xnodeptr **newtooth, double *x, int *degree)
1188 #else
1189 static void clean_tooth (G, handle, tooth, newtooth, x, degree)
1190 Xgraph *G;
1191 Xnodeptr *handle, *tooth, **newtooth;
1192 double *x;
1193 int *degree;
1194 #endif
1195 {
1196 Xnodeptr *np, *np1, *toss;
1197 Xnode *n;
1198 Xedgeptr *ep;
1199 Xedge *e;
1200
1201 G->magicnum++;
1202 for (np = tooth; np; np = np->next) {
1203 degree[np->this - G->nodelist] = 0;
1204 np->this->magiclabel = G->magicnum;
1205 }
1206
1207 for (np = tooth; np; np = np->next) {
1208 n = np->this;
1209 for (ep = n->adj.head; ep; ep = ep->next) {
1210 e = ep->this;
1211 if (x[e - G->edgelist] > XEPSILON &&
1212 e->ends[0]->magiclabel == e->ends[1]->magiclabel)
1213 (degree[n - G->nodelist])++;
1214 }
1215 }
1216
1217 G->magicnum++;
1218 for (np = handle; np; np = np->next) {
1219 np->this->magiclabel = G->magicnum;
1220 }
1221
1222 toss = (Xnodeptr *) NULL;
1223
1224 for (np = tooth; np; np = np->next) {
1225 n = np->this;
1226 if (n->magiclabel == G->magicnum - 1 && degree[n - G->nodelist] == 1)
1227 process_clean_tooth_node (G, n, x, degree, &toss);
1228 }
1229 G->magicnum++;
1230
1231 for (np = toss; np; np = np->next)
1232 np->this->magiclabel = G->magicnum;
1233
1234 Xnodeptr_list_free (toss);
1235
1236 *newtooth = (Xnodeptr *) NULL;
1237 for (np = tooth; np; np = np->next)
1238 if (np->this->magiclabel != G->magicnum) {
1239 np1 = Xnodeptralloc ();
1240 np1->this = np->this;
1241 np1->next = *newtooth;
1242 *newtooth = np1;
1243 }
1244 }
1245
1246 #ifdef CC_PROTOTYPE_ANSI
process_clean_tooth_node(Xgraph * G,Xnode * n,double * x,int * degree,Xnodeptr ** toss)1247 static void process_clean_tooth_node (Xgraph *G, Xnode *n, double *x,
1248 int *degree, Xnodeptr **toss)
1249 #else
1250 static void process_clean_tooth_node (G, n, x, degree, toss)
1251 Xgraph *G;
1252 Xnode *n;
1253 double *x;
1254 int *degree;
1255 Xnodeptr **toss;
1256 #endif
1257 {
1258 Xedgeptr *ep;
1259 Xedge *e;
1260 Xnodeptr *np;
1261 Xnode *n1;
1262 double t;
1263
1264 for (ep = n->adj.head; ep; ep = ep->next) {
1265 e = ep->this;
1266 t = x[e - G->edgelist];
1267 if (t > XEPSILON &&
1268 e->ends[0]->magiclabel == e->ends[1]->magiclabel) {
1269 if (t > 0.9999) {
1270 np = Xnodeptralloc ();
1271 np->this = n;
1272 np->next = *toss;
1273 *toss = np;
1274 n->magiclabel = G->magicnum - 2;
1275 n1 = OTHEREND (e, n);
1276 if (degree[n1 - G->nodelist] == 2)
1277 process_clean_tooth_node (G, n1, x, degree, toss);
1278 }
1279 return;
1280 }
1281 }
1282 return;
1283 }
1284
1285 #ifdef CC_PROTOTYPE_ANSI
clean_handle_connect(Xgraph * G,Xnodeptr * handle,double * x)1286 static int clean_handle_connect (Xgraph *G, Xnodeptr *handle, double *x)
1287 #else
1288 static int clean_handle_connect (G, handle, x)
1289 Xgraph *G;
1290 Xnodeptr *handle;
1291 double *x;
1292 #endif
1293 {
1294 Xnodeptr *np;
1295
1296 if (handle == (Xnodeptr *) NULL)
1297 return 0;
1298
1299 G->magicnum++;
1300 for (np = handle; np; np = np->next)
1301 np->this->magiclabel = G->magicnum;
1302
1303 clean_handle_connect_dfs (G, handle->this, x, G->magicnum);
1304
1305 for (np = handle; np; np = np->next)
1306 if (np->this->magiclabel == G->magicnum)
1307 return 0;
1308
1309 return 1;
1310 }
1311
1312 #ifdef CC_PROTOTYPE_ANSI
clean_handle_connect_dfs(Xgraph * G,Xnode * start,double * x,int k)1313 static void clean_handle_connect_dfs (Xgraph *G, Xnode *start, double *x, int k)
1314 #else
1315 static void clean_handle_connect_dfs (G, start, x, k)
1316 Xgraph *G;
1317 Xnode *start;
1318 double *x;
1319 int k;
1320 #endif
1321 {
1322 Xedgeptr *ep;
1323 Xedge *e;
1324 Xnode *n, *n1;
1325 Xnodeptr *next, *queue = (Xnodeptr *) NULL;
1326
1327 start->magiclabel = k - 1;
1328 Xadd_nodeptr (&queue, start);
1329
1330 while (queue) {
1331 n = queue->this;
1332 next = queue->next;
1333 Xnodeptrfree (queue);
1334 queue = next;
1335
1336 for (ep = n->adj.head; ep; ep = ep->next) {
1337 e = ep->this;
1338 if (x[e - G->edgelist] > 0.005) {
1339 n1 = OTHEREND (e, n);
1340 if (n1->magiclabel == k) {
1341 n1->magiclabel = k - 1;
1342 Xadd_nodeptr (&queue, n1);
1343 }
1344 }
1345 }
1346 }
1347 }
1348
1349