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