1 /**************************************************************************/
2 /* */
3 /* EXPORTED FUNCTION: */
4 /* int necklaces(Xcplane **, double *) */
5 /* */
6 /**************************************************************************/
7
8 #include "machdefs.h"
9 #include "util.h"
10 #include "Xsubtour.h"
11 #include "Xpq.h"
12 #include "Xnecklac.h"
13
14 #ifdef CC_PROTOTYPE_ANSI
15
16 static void
17 cliquelist_free (Xclique *),
18 necklace_build_neckedges (double *),
19 necklace_build_necklaces (PQ_node *),
20 necklace_build_neckadj (void),
21 necklace_destroy_neckadj (void),
22 label_necklaces (PQ_node *),
23 label_necklaces_work (PQ_node *),
24 label_necklace (PQ_node *),
25 label_edges (PQ_node *, PQ_node *, int),
26 lift_ends (PQ_node *, PQ_node *),
27 lift_edges (PQ_node *, PQ_node *),
28 dump_necklaces (void),
29 dump_necklace_work (PQ_node *),
30 free_equation (Xeqn *),
31 compute_toroots (PQ_node *),
32 free_toroots (PQ_node *),
33 eqn_addto (Xeqn *, Xeqn *),
34 dump_intptr_list (Xintptr *),
35 collect_neck_tooth_leaf (PQ_node *, int, int, Xnodeptr **),
36 collect_neck_tooth_work (PQ_node *, int, int, Xnodeptr **, PQ_node *),
37 binsys_init (bin_system *, int),
38 binsys_elim (bin_system *, Xeqn *),
39 binsys_random_solution (bin_system *),
40 binsys_eval_pivot (bin_system *, Xeqn *),
41 binsys_pop_sparse (bin_system *),
42 binsys_free_system (bin_system *),
43 ds_makeset (PQ_node *);
44
45 static int
46 necklace_cuts (double *, Xcplane **, PQ_node *),
47 neckedge_compare (const void *, const void *),
48 count_necklaces (PQ_node *),
49 find_node_label (PQ_node *),
50 necklace_crunch_cuts (PQ_node *, Xcplane **),
51 necklace_add_edge_to_sys (Xneckedge *, bin_system *),
52 necklace_try_solutions (bin_system *, PQ_node *, Xcplane **, Xintptrptr **),
53 find_label (Xintptr *, int),
54 intptr_list_size (Xintptr *),
55 intptrlist_equal (Xintptr *, Xintptr *),
56 find_solution (Xintptr *, Xintptrptr *),
57 necklace_checkout_solution (Xintptr *, PQ_node *, Xcplane **),
58 count_labeled_children (PQ_node *),
59 check_realization (PQ_node *, int, PQ_node **, PQ_node **),
60 collect_necklace_label (PQ_node *),
61 binsys_add_dense (bin_system *, Xeqn *),
62 binsys_add_sparse (bin_system *, Xeqn *),
63 binsys_force_zero (bin_system *, int);
64
65 static PQ_node
66 *init_elems (PQ_node *elems),
67 *necklace_build_cuttree (double *),
68 *necklace_build_spantree (void),
69 *ds_find (PQ_node *),
70 *ds_link (PQ_node *, PQ_node *);
71
72 static Xeqn
73 *necklace_edge_to_eqn (Xneckedge *);
74
75 static Xintptr
76 *intptr_add (Xintptr *, Xintptr *),
77 *intptr_add_destruc (Xintptr *, Xintptr *),
78 *intptr_addto (Xintptr *, Xintptr *),
79 *intptr_copy (Xintptr *),
80 *binsys_random_minimal_solution (bin_system *),
81 *binsys_list_solution (bin_system *);
82
83 static Xnodeptr
84 *collect_necklace_tooth (PQ_node *, PQ_node *, PQ_node *, PQ_node *),
85 *collect_necklace_handle (void);
86
87 static int
88 add_clique_to_PQtree (Xclique *c, PQ_node *elems);
89 static PQ_node
90 *clique_to_PQlist (Xclique *c, PQ_node *elems);
91 static int
92 find_intptr_list (Xintptr *p, int n);
93
94 #else
95
96 static void
97 cliquelist_free (),
98 necklace_build_neckedges (),
99 necklace_build_necklaces (),
100 necklace_build_neckadj (),
101 necklace_destroy_neckadj (),
102 label_necklaces (),
103 label_necklaces_work (),
104 label_necklace (),
105 label_edges (),
106 lift_ends (),
107 lift_edges (),
108 dump_necklaces (),
109 dump_necklace_work (),
110 free_equation (),
111 compute_toroots (),
112 free_toroots (),
113 eqn_addto (),
114 dump_intptr_list (),
115 collect_neck_tooth_leaf (),
116 collect_neck_tooth_work (),
117 binsys_init (),
118 binsys_elim (),
119 binsys_random_solution (),
120 binsys_eval_pivot (),
121 binsys_pop_sparse (),
122 binsys_free_system (),
123 ds_makeset ();
124
125 static int
126 necklace_cuts (),
127 neckedge_compare (),
128 count_necklaces (),
129 find_node_label (),
130 necklace_crunch_cuts (),
131 necklace_add_edge_to_sys (),
132 necklace_try_solutions (),
133 find_label (),
134 intptr_list_size (),
135 intptrlist_equal (),
136 find_solution (),
137 necklace_checkout_solution (),
138 count_labeled_children (),
139 check_realization (),
140 collect_necklace_label (),
141 binsys_add_dense (),
142 binsys_add_sparse (),
143 binsys_force_zero ();
144
145 static PQ_node
146 *init_elems (),
147 *necklace_build_cuttree (),
148 *necklace_build_spantree (),
149 *ds_find (),
150 *ds_link ();
151
152 static Xeqn
153 *necklace_edge_to_eqn ();
154
155 static Xintptr
156 *intptr_add (),
157 *intptr_add_destruc (),
158 *intptr_addto (),
159 *intptr_copy (),
160 *binsys_random_minimal_solution (),
161 *binsys_list_solution ();
162
163 static Xnodeptr
164 *collect_necklace_tooth (),
165 *collect_necklace_handle ();
166
167 static int
168 add_clique_to_PQtree ();
169 static PQ_node
170 *clique_to_PQlist ();
171 static int
172 find_intptr_list ();
173
174
175 #endif
176
177 #define NECK_ENUM_CUTOFF 5
178 #define NECK_ENUM_NTRIES 50
179 #define NECK_NEXTTRY(x) (((x)*2)/3)
180
181 static int verbose = 0;
182 static int nnecklaces;
183 static PQ_node **necklist;
184 static Xneckedge *neckedgelist;
185 static int nneckedges;
186 static PQ_node *necknodelist;
187 static int magicneckedgenum = 0;
188 static Xgraph *G;
189
190 static Xclique *cliquelist = (Xclique *) NULL;
191 static int ncliques = 0;
192
193 #ifdef CC_PROTOTYPE_ANSI
Xnecklaces(Xgraph * Gin,Xcplane ** list,double * x)194 int Xnecklaces (Xgraph *Gin, Xcplane **list, double *x)
195 #else
196 int Xnecklaces (Gin, list, x)
197 Xgraph *Gin;
198 Xcplane **list;
199 double *x;
200 #endif
201 {
202 double szeit;
203 PQ_node *pqroot;
204 int k;
205
206 G = Gin;
207
208 szeit = CCutil_zeit ();
209
210 printf ("CALLED NECKLACE ... (%d, %d)\n", G->nnodes, G->nedges);
211 fflush (stdout);
212
213 pqroot = necklace_build_cuttree (x);
214
215 if (!pqroot) {
216 return 0;
217 }
218
219 k = necklace_cuts (x, list, pqroot);
220
221 /*
222 for (c = *list; c; c = c->next)
223 if (c->handles)
224 printcliquetree (c->handles, c->teeth);
225 else
226 printchvatalcomb (c->handle, c->teeth);
227 */
228
229
230 XPQ_free_all (pqroot, 1);
231 CC_FREE (necknodelist, PQ_node);
232
233 printf ("Time in Necklace: %2f\n", CCutil_zeit () - szeit);
234 fflush (stdout);
235
236 return k;
237 }
238
239 #ifdef CC_PROTOTYPE_ANSI
necklace_cuts(double * x,Xcplane ** list,PQ_node * pqroot)240 static int necklace_cuts (double *x, Xcplane **list, PQ_node *pqroot)
241 #else
242 static int necklace_cuts (x, list, pqroot)
243 double *x;
244 Xcplane **list;
245 PQ_node *pqroot;
246 #endif
247 {
248 PQ_node *spanroot;
249 int k;
250
251 necklace_build_neckedges (x);
252
253 necklace_build_necklaces (pqroot);
254
255 necklace_build_neckadj ();
256
257 spanroot = necklace_build_spantree ();
258
259 if (!spanroot) {
260 necklace_destroy_neckadj ();
261 CC_FREE (necklist, PQ_node *);
262 CC_FREE (neckedgelist, Xneckedge);
263 return 0;
264 }
265
266 spanroot->toroot = (Xintptr *) NULL;
267 compute_toroots (spanroot);
268
269 k = necklace_crunch_cuts (pqroot, list);
270
271 free_toroots (spanroot);
272 necklace_destroy_neckadj ();
273 CC_FREE (necklist, PQ_node *);
274 CC_FREE (neckedgelist, Xneckedge);
275
276 return k;
277 }
278
279 #ifdef CC_PROTOTYPE_ANSI
necklace_build_cuttree(double * x)280 static PQ_node *necklace_build_cuttree (double *x)
281 #else
282 static PQ_node *necklace_build_cuttree (x)
283 double *x;
284 #endif
285 {
286 int i;
287 Xclique *cnext;
288 PQ_node *token_elem;
289 double szeit;
290
291 for (i=0; i<G->nedges; i++) {
292 G->edgelist[i].x = x[i];
293 }
294 cliquelist = (Xclique *) NULL;
295 ncliques = 0;
296 szeit = CCutil_zeit ();
297 Xall_tightcuts (G, &cliquelist, &ncliques);
298 printf ("Found %d tight cliques in %.2f seconds\n", ncliques,
299 CCutil_zeit () - szeit);
300
301 necknodelist = CC_SAFE_MALLOC (G->nnodes, PQ_node);
302 if (!necknodelist) {
303 fprintf (stderr, "out of memory in necklace\n");
304 exit (1);
305 }
306
307 token_elem = init_elems (necknodelist);
308
309 while (cliquelist) {
310 cnext = cliquelist->next;
311 if (!add_clique_to_PQtree (cliquelist, necknodelist)) {
312 XPQ_free_all (token_elem, 1);
313 CC_FREE (necknodelist, PQ_node);
314 cliquelist_free (cliquelist);
315 printf ("ZZZ Necklace bailout\n");
316 fflush (stdout);
317 return (PQ_node *) NULL;
318 }
319 Xintptr_list_free (cliquelist->nodes);
320 Xcliquefree (cliquelist);
321 cliquelist = cnext;
322 }
323 return XPQ_find_root (token_elem);
324 }
325
326 #ifdef CC_PROTOTYPE_ANSI
cliquelist_free(Xclique * c)327 static void cliquelist_free (Xclique *c)
328 #else
329 static void cliquelist_free (c)
330 Xclique *c;
331 #endif
332 {
333 Xclique *cnext;
334
335 while (c) {
336 cnext = c->next;
337 Xintptr_list_free (c->nodes);
338 Xcliquefree (c);
339 c = cnext;
340 }
341 }
342
343 #ifdef CC_PROTOTYPE_ANSI
neckedge_compare(const void * a,const void * b)344 static int neckedge_compare (const void *a, const void *b)
345 #else
346 static int neckedge_compare (a, b)
347 const void *a;
348 const void *b;
349 #endif
350 {
351 if (((const Xneckedge *) a)->x < ((const Xneckedge *) b)->x) {
352 return 1;
353 } else if (((const Xneckedge *) a)->x > ((const Xneckedge *) b)->x) {
354 return -1;
355 } else {
356 return 0;
357 }
358 }
359
360 #ifdef CC_PROTOTYPE_ANSI
necklace_build_neckedges(double * x)361 static void necklace_build_neckedges (double *x)
362 #else
363 static void necklace_build_neckedges (x)
364 double *x;
365 #endif
366 {
367 int i;
368
369 for (i=0; i<G->nnodes; i++) {
370 necknodelist[i].adj = (Xneckedgeptr *) NULL;
371 necknodelist[i].magiclabel = 0;
372 }
373
374 neckedgelist = CC_SAFE_MALLOC (G->nedges, Xneckedge);
375 if (!neckedgelist) {
376 fprintf (stderr, "out of memory in necklace\n");
377 exit (1);
378 }
379 for (i=0, nneckedges = 0; i<G->nedges; i++) {
380 if (x[i] > 0.0) {
381 neckedgelist[nneckedges].x = x[i];
382 neckedgelist[nneckedges].ends[0] = necknodelist + (G->edgelist[i].ends[0] - G->nodelist);
383 neckedgelist[nneckedges].ends[1] = necknodelist + (G->edgelist[i].ends[1] - G->nodelist);
384 neckedgelist[nneckedges].magiclabel = 0;
385 nneckedges++;
386 }
387 }
388 qsort ((char *) neckedgelist, nneckedges, sizeof (Xneckedge), neckedge_compare);
389 }
390
391 #ifdef CC_PROTOTYPE_ANSI
necklace_build_necklaces(PQ_node * pqroot)392 static void necklace_build_necklaces (PQ_node *pqroot)
393 #else
394 static void necklace_build_necklaces (pqroot)
395 PQ_node *pqroot;
396 #endif
397 {
398 int neckspace;
399
400 neckspace = count_necklaces (pqroot);
401
402 necklist = CC_SAFE_MALLOC (neckspace, PQ_node *);
403 if (!necklist) {
404 fprintf (stderr, "out of memory in necklace\n");
405 exit (1);
406 }
407 nnecklaces = 0;
408
409 label_necklaces (pqroot);
410
411 if (nnecklaces != neckspace) {
412 fprintf (stderr, "ZZZ NECKLACE COUNTS WRONG (%d != %d)\n",neckspace, nnecklaces);
413 }
414
415 printf ("%d necklaces found, ",nnecklaces);
416 fflush (stdout);
417
418 if (verbose) {
419 printf ("Necklaces:\n");
420 dump_necklaces ();
421 }
422 }
423
424 #ifdef CC_PROTOTYPE_ANSI
necklace_build_neckadj(void)425 static void necklace_build_neckadj (void)
426 #else
427 static void necklace_build_neckadj ()
428 #endif
429 {
430 int i;
431
432 for (i=0; i<nneckedges; i++) {
433 Xadd_neckedgeptr (&neckedgelist[i].ends[0]->adj, &neckedgelist[i]);
434 Xadd_neckedgeptr (&neckedgelist[i].ends[1]->adj, &neckedgelist[i]);
435 }
436 }
437
438 #ifdef CC_PROTOTYPE_ANSI
necklace_destroy_neckadj(void)439 static void necklace_destroy_neckadj (void)
440 #else
441 static void necklace_destroy_neckadj ()
442 #endif
443 {
444 int i;
445
446 for (i=0; i<G->nnodes; i++) {
447 Xneckedgeptr_list_free (necknodelist[i].adj);
448 necknodelist[i].adj = (Xneckedgeptr *) NULL;
449 }
450 }
451
452 #ifdef CC_PROTOTYPE_ANSI
count_necklaces(PQ_node * x)453 static int count_necklaces (PQ_node *x)
454 #else
455 static int count_necklaces (x)
456 PQ_node *x;
457 #endif
458 {
459 int cnt = 0;
460 PQ_node *z, *zprev, *znext;
461 int childcount = 0;
462
463 PQ_set_FOREACH (x->children_set, z, children_elem, zprev, znext) {
464 cnt += count_necklaces (z);
465 childcount++;
466 }
467 if (x->type == Q_NODE || (x->type == P_NODE && childcount == 2)) {
468 cnt++;
469 }
470 return cnt;
471 }
472
473 #ifdef CC_PROTOTYPE_ANSI
label_necklaces(PQ_node * pqroot)474 static void label_necklaces (PQ_node *pqroot)
475 #else
476 static void label_necklaces (pqroot)
477 PQ_node *pqroot;
478 #endif
479 {
480 int i;
481
482 for (i=0; i<nneckedges; i++) {
483 neckedgelist[i].cends[0] = neckedgelist[i].ends[0];
484 neckedgelist[i].cends[1] = neckedgelist[i].ends[1];
485 neckedgelist[i].necklabel = -1;
486 }
487
488 necklace_build_neckadj ();
489
490 label_necklaces_work (pqroot);
491 /* label_necklaces_work destroys neckadj except for pqroot and magicnode */
492 Xneckedgeptr_list_free (pqroot->adj);
493 pqroot->adj = (Xneckedgeptr *) NULL;
494 Xneckedgeptr_list_free (necknodelist[MAGICNODE].adj);
495 necknodelist[MAGICNODE].adj = (Xneckedgeptr *) NULL;
496
497 assert (nnecklaces < G->nnodes);
498 }
499
500 #ifdef CC_PROTOTYPE_ANSI
label_necklaces_work(PQ_node * n)501 static void label_necklaces_work (PQ_node *n)
502 #else
503 static void label_necklaces_work (n)
504 PQ_node *n;
505 #endif
506 {
507 PQ_node *z;
508 PQ_node *zprev;
509 PQ_node *znext;
510 int cnt;
511
512 cnt = 0;
513 PQ_set_FOREACH (n->children_set, z, children_elem, zprev, znext) {
514 cnt++;
515 label_necklaces_work (z);
516 }
517 n->children_set.size = cnt;
518
519 label_necklace (n);
520 }
521
522 #ifdef CC_PROTOTYPE_ANSI
label_necklace(PQ_node * n)523 static void label_necklace (PQ_node *n)
524 #else
525 static void label_necklace (n)
526 PQ_node *n;
527 #endif
528 {
529 PQ_node *a, *b, *c;
530
531 if (n->type == Q_NODE || (n->type == P_NODE && PQ_set_SIZE (n->children_set) == 2)) {
532 a = PQ_set_LEFT_ELEM (n->children_set);
533 assert (a);
534 b = a->children_elem.ptr1;
535 if (!b) {
536 b = a->children_elem.ptr2;
537 }
538 assert (b);
539
540 necklist[nnecklaces] = n;
541 label_edges (a, b, nnecklaces);
542 nnecklaces++;
543 }
544
545 if (n->type != LEAF_NODE) {
546 PQ_set_FOREACH (n->children_set, a, children_elem, b, c) {
547 lift_ends (a, n);
548 }
549
550 n->adj = (Xneckedgeptr *) NULL;
551 PQ_set_FOREACH (n->children_set, a, children_elem, b, c) {
552 lift_edges (a, n);
553 }
554 }
555 }
556
557 #ifdef CC_PROTOTYPE_ANSI
label_edges(PQ_node * a,PQ_node * b,int n)558 static void label_edges (PQ_node *a, PQ_node *b, int n)
559 #else
560 static void label_edges (a, b, n)
561 PQ_node *a;
562 PQ_node *b;
563 int n;
564 #endif
565 {
566 Xneckedgeptr *p;
567
568 for (p = a->adj; p; p = p->next) {
569 assert (p->this->cends[0] == a || p->this->cends[1] == a);
570 if (p->this->cends[0] == b || p->this->cends[1] == b) {
571 p->this->necklabel = n;
572 }
573 }
574 }
575
576 #ifdef CC_PROTOTYPE_ANSI
lift_ends(PQ_node * a,PQ_node * n)577 static void lift_ends (PQ_node *a, PQ_node *n)
578 #else
579 static void lift_ends (a, n)
580 PQ_node *a;
581 PQ_node *n;
582 #endif
583 {
584 Xneckedgeptr *p;
585
586 for (p = a->adj; p; p = p->next) {
587 if (p->this->cends[0] == a) {
588 p->this->cends[0] = n;
589 } else {
590 assert (p->this->cends[1] == a);
591 p->this->cends[1] = n;
592 }
593 }
594 }
595
596 #ifdef CC_PROTOTYPE_ANSI
lift_edges(PQ_node * a,PQ_node * n)597 static void lift_edges (PQ_node *a, PQ_node *n)
598 #else
599 static void lift_edges (a, n)
600 PQ_node *a;
601 PQ_node *n;
602 #endif
603 {
604 Xneckedgeptr *p, *pnext;
605
606 for (p = a->adj; p; p = pnext) {
607 pnext = p->next;
608 if (p->this->cends[0] != n || p->this->cends[1] != n) {
609 assert (p->this->cends[0] == n || p->this->cends[1] == n);
610 p->next = n->adj;
611 n->adj = p;
612 } else {
613 Xneckedgeptrfree (p);
614 }
615 }
616 a->adj = (Xneckedgeptr *) NULL;
617 }
618
619 #ifdef CC_PROTOTYPE_ANSI
dump_necklaces(void)620 static void dump_necklaces (void)
621 #else
622 static void dump_necklaces ()
623 #endif
624 {
625 int i;
626 PQ_node *z, *znext, *zprev;
627 int j;
628
629 for (i=0; i<nnecklaces; i++) {
630 printf ("%d:",i);
631 PQ_set_FOREACH (necklist[i]->children_set, z, children_elem, zprev, znext) {
632 if (z->type == Q_NODE || (z->type == P_NODE && PQ_set_SIZE (z->children_set) == 2)) {
633 j = find_node_label (z);
634 printf (" %d",j);
635 } else if (z->type == LEAF_NODE) {
636 printf (" n%d",z->number);
637 } else {
638 printf (" (");
639 dump_necklace_work (z);
640 printf (")");
641 }
642 }
643 printf ("\n");
644 }
645 }
646
647 #ifdef CC_PROTOTYPE_ANSI
dump_necklace_work(PQ_node * x)648 static void dump_necklace_work (PQ_node *x)
649 #else
650 static void dump_necklace_work (x)
651 PQ_node *x;
652 #endif
653 {
654 PQ_node *z, *zprev, *znext;
655 if (x->type == Q_NODE || (x->type == P_NODE && PQ_set_SIZE (x->children_set) == 2)) {
656 printf ("%d ",find_node_label (x));
657 } else if (x->type == LEAF_NODE) {
658 printf ("n%d ",x->number);
659 } else {
660 PQ_set_FOREACH (x->children_set, z, children_elem, zprev, znext) {
661 dump_necklace_work (z);
662 }
663 }
664 }
665
666 #ifdef CC_PROTOTYPE_ANSI
find_node_label(PQ_node * z)667 static int find_node_label (PQ_node *z)
668 #else
669 static int find_node_label (z)
670 PQ_node *z;
671 #endif
672 {
673 int i;
674
675 for (i=0; i<nnecklaces; i++) {
676 if (necklist[i] == z) {
677 return i;
678 }
679 }
680 return -1;
681 }
682
683 #ifdef CC_PROTOTYPE_ANSI
necklace_build_spantree(void)684 static PQ_node *necklace_build_spantree (void)
685 #else
686 static PQ_node *necklace_build_spantree ()
687 #endif
688 {
689 int i;
690 int k;
691 PQ_node *front, *back, *new;
692 Xneckedge *e;
693 Xneckedgeptr *it;
694 PQ_node *root;
695 int cnt;
696
697 for (i=0; i<G->nnodes; i++) {
698 ds_makeset (&necknodelist[i]);
699 }
700 for (i=0; i<nneckedges; i++) {
701 neckedgelist[i].inspanning = 0;
702 }
703
704 for (i=0, k=G->nnodes-1; k && i < nneckedges; i++) {
705 if (ds_find (neckedgelist[i].ends[0]) != ds_find (neckedgelist[i].ends[1])) {
706 ds_link (ds_find (neckedgelist[i].ends[0]), ds_find (neckedgelist[i].ends[1]));
707 neckedgelist[i].inspanning = 1;
708 k--;
709 }
710 }
711 if (k) {
712 return (PQ_node *) NULL;
713 }
714
715 /* this is a bit clumsy; first we build the spanning tree, then we do
716 a breadth-first search through it to root it */
717
718 G->magicnum++;
719 root = &necknodelist[0];
720 cnt = 0;
721
722 front = root;
723 front->magiclabel = G->magicnum;
724 cnt++;
725 front->entered = (Xneckedge *) NULL;
726 front->next = (PQ_node *) NULL;
727 back = front;
728
729 while (front) {
730 for (it = front->adj; it; it = it->next) {
731 e = it->this;
732 if (e->inspanning) {
733 new = (e->ends[0] == front) ? e->ends[1] : e->ends[0];
734 if (new->magiclabel != G->magicnum) {
735 new->magiclabel = G->magicnum;
736 cnt++;
737 new->entered = e;
738 back->next = new;
739 back = new;
740 back->next = (PQ_node *) NULL;
741 }
742 }
743 }
744 front = front->next;
745 }
746 if (cnt < G->nnodes) {
747 printf ("ZZZ !!!!LOST THE SPANNING TREE!!!!\n");
748 fflush (stdout);
749 return (PQ_node *) NULL;
750 }
751 return root;
752 }
753
754 #ifdef CC_PROTOTYPE_ANSI
necklace_crunch_cuts(PQ_node * pqroot,Xcplane ** list)755 static int necklace_crunch_cuts (PQ_node *pqroot, Xcplane **list)
756 #else
757 static int necklace_crunch_cuts (pqroot, list)
758 PQ_node *pqroot;
759 Xcplane **list;
760 #endif
761 {
762 bin_system necksys;
763 Xeqn *oneseqn;
764 int i;
765 Xintptr *tmp;
766 int tried;
767 Xintptrptr *found;
768 int k;
769 int trynext;
770 int v;
771
772 binsys_init (&necksys, nnecklaces);
773
774 for (i=0; i<nneckedges; i++) {
775 neckedgelist[i].insystem = neckedgelist[i].inspanning;
776 }
777
778 oneseqn = Xeqnalloc ();
779 oneseqn->lhs = (Xintptr *) NULL;
780 for (i = nnecklaces-1; i>=0; i--) {
781 tmp = Xintptralloc ();
782 tmp->this = i;
783 tmp->next = oneseqn->lhs;
784 oneseqn->lhs = tmp;
785 }
786 oneseqn->rhs = 1;
787
788 if (binsys_add_dense (&necksys, oneseqn) != 1) {
789 fprintf (stderr, "ZZZ ODDNESS CONSTRAINT FAILED\n");
790 }
791 printf ("1"); fflush (stdout);
792
793 found = (Xintptrptr *) NULL;
794 k = 0;
795 trynext = NECK_NEXTTRY (nnecklaces);
796
797 tried = 0;
798 for (i=0; i<nneckedges && necksys.nfreevars > NECK_ENUM_CUTOFF; i++) {
799 if (!neckedgelist[i].inspanning) {
800 v = necklace_add_edge_to_sys (&neckedgelist[i], &necksys);
801 if (v == 1) {
802 neckedgelist[i].insystem = 1;
803 printf ("+"); fflush (stdout);
804 tried = 0;
805 if (necksys.nfreevars <= trynext) {
806 printf (" (%.2f:%d)",neckedgelist[i].x,necksys.nfreevars);
807 fflush (stdout);
808 k += necklace_try_solutions (&necksys, pqroot, list, &found);
809 printf ("\n"); fflush (stdout);
810 tried = 1;
811 trynext = NECK_NEXTTRY (trynext);
812 }
813 } else if (v == 0) {
814 neckedgelist[i].insystem = 1;
815 printf ("."); fflush (stdout);
816 } else {
817 printf ("-"); fflush (stdout);
818 }
819 }
820 }
821 if (!tried) {
822 printf (" (%.2f:%d)",neckedgelist[i-1].x,necksys.nfreevars);
823 fflush (stdout);
824 k += necklace_try_solutions (&necksys, pqroot, list, &found);
825 printf ("\n"); fflush (stdout);
826 }
827
828 Xintptrptr_list_freeall (found);
829 binsys_free_system (&necksys);
830 return k;
831 }
832
833 #ifdef CC_PROTOTYPE_ANSI
necklace_edge_to_eqn(Xneckedge * e)834 static Xeqn *necklace_edge_to_eqn (Xneckedge *e)
835 #else
836 static Xeqn *necklace_edge_to_eqn (e)
837 Xneckedge *e;
838 #endif
839 {
840 Xeqn *neweqn;
841 Xintptr *tmp;
842
843 neweqn = Xeqnalloc ();
844 neweqn->lhs = intptr_add (e->ends[0]->toroot, e->ends[1]->toroot);
845 if (e->necklabel != -1) {
846 tmp = Xintptralloc ();
847 tmp->this = e->necklabel;
848 tmp->next = (Xintptr *) NULL;
849 neweqn->lhs = intptr_add_destruc (neweqn->lhs, tmp);
850 }
851 neweqn->rhs = 0;
852 return neweqn;
853 }
854
855 #ifdef CC_PROTOTYPE_ANSI
necklace_add_edge_to_sys(Xneckedge * e,bin_system * s)856 static int necklace_add_edge_to_sys (Xneckedge *e, bin_system *s)
857 #else
858 static int necklace_add_edge_to_sys (e, s)
859 Xneckedge *e;
860 bin_system *s;
861 #endif
862 {
863 Xeqn *neweqn;
864
865 neweqn = necklace_edge_to_eqn (e);
866 return binsys_add_sparse (s, neweqn);
867 }
868
869 #ifdef CC_PROTOTYPE_ANSI
necklace_try_solutions(bin_system * necksys,PQ_node * pqroot,Xcplane ** list,Xintptrptr ** found)870 static int necklace_try_solutions (bin_system *necksys, PQ_node *pqroot, Xcplane **list, Xintptrptr **found)
871 #else
872 static int necklace_try_solutions (necksys, pqroot, list, found)
873 bin_system *necksys;
874 PQ_node *pqroot;
875 Xcplane **list;
876 Xintptrptr **found;
877 #endif
878 {
879 int i;
880 int k = 0;
881 Xintptr *sollst;
882 Xintptrptr *new;
883
884 for (i=0; i<NECK_ENUM_NTRIES; i++) {
885 sollst = binsys_random_minimal_solution (necksys);
886 if (intptr_list_size (sollst) >= 3 &&
887 !find_solution (sollst, *found)) {
888 new = Xintptrptralloc ();
889 new->this = sollst;
890 new->next = *found;
891 *found = new;
892 k += necklace_checkout_solution (sollst, pqroot, list);
893 } else {
894 Xintptr_list_free (sollst);
895 }
896 }
897 return k;
898 }
899
900 #ifdef CC_PROTOTYPE_ANSI
free_equation(Xeqn * sys)901 static void free_equation (Xeqn *sys)
902 #else
903 static void free_equation (sys)
904 Xeqn *sys;
905 #endif
906 {
907 Xintptr_list_free (sys->lhs);
908 Xeqnfree (sys);
909 }
910
911 #ifdef CC_PROTOTYPE_ANSI
compute_toroots(PQ_node * n)912 static void compute_toroots (PQ_node *n)
913 #else
914 static void compute_toroots (n)
915 PQ_node *n;
916 #endif
917 {
918 Xneckedgeptr *ep;
919 Xneckedge *e;
920 PQ_node *m;
921 Xintptr tmp;
922
923 for (ep = n->adj; ep; ep=ep->next) {
924 if (ep->this->inspanning) {
925 e = ep->this;
926 m = (e->ends[0] == n) ? e->ends[1] : e->ends[0];
927 if (m->entered == e) {
928 if (e->necklabel != -1) {
929 tmp.this = e->necklabel;
930 tmp.next = (Xintptr *) NULL;
931 m->toroot = intptr_add (n->toroot, &tmp);
932 } else {
933 m->toroot = intptr_copy (n->toroot);
934 }
935 compute_toroots (m);
936 }
937 }
938 }
939 }
940
941 #ifdef CC_PROTOTYPE_ANSI
free_toroots(PQ_node * n)942 static void free_toroots (PQ_node *n)
943 #else
944 static void free_toroots (n)
945 PQ_node *n;
946 #endif
947 {
948 Xneckedgeptr *ep;
949 Xneckedge *e;
950 PQ_node *m;
951
952 for (ep = n->adj; ep; ep=ep->next) {
953 if (ep->this->inspanning) {
954 e = ep->this;
955 m = (e->ends[0] == n) ? e->ends[1] : e->ends[0];
956 if (m->entered == e) {
957 free_toroots (m);
958 }
959 }
960 }
961 Xintptr_list_free (n->toroot);
962 n->toroot = (Xintptr *) NULL;
963 }
964
965 #ifdef CC_PROTOTYPE_ANSI
intptr_add(Xintptr * a,Xintptr * b)966 static Xintptr *intptr_add (Xintptr *a, Xintptr *b)
967 #else
968 static Xintptr *intptr_add (a, b)
969 Xintptr *a;
970 Xintptr *b;
971 #endif
972 {
973 Xintptr *sum;
974 Xintptr **sumend;
975
976 sum = (Xintptr *) NULL;
977 sumend = ∑
978
979 while (a && b) {
980 if (a->this == b->this) {
981 a = a->next;
982 b = b->next;
983 } else if (a->this < b->this) {
984 *sumend = Xintptralloc ();
985 (*sumend)->this = a->this;
986 sumend = & (*sumend)->next;
987 a = a->next;
988 } else {
989 assert (a->this > b->this);
990 *sumend = Xintptralloc ();
991 (*sumend)->this = b->this;
992 sumend = & (*sumend)->next;
993 b = b->next;
994 }
995 }
996 if (a) {
997 *sumend = intptr_copy (a);
998 } else if (b) {
999 *sumend = intptr_copy (b);
1000 } else {
1001 *sumend = (Xintptr *) NULL;
1002 }
1003 return sum;
1004 }
1005
1006 #ifdef CC_PROTOTYPE_ANSI
intptr_add_destruc(Xintptr * a,Xintptr * b)1007 static Xintptr *intptr_add_destruc (Xintptr *a, Xintptr *b)
1008 #else
1009 static Xintptr *intptr_add_destruc (a, b)
1010 Xintptr *a;
1011 Xintptr *b;
1012 #endif
1013 {
1014 Xintptr *sum;
1015 Xintptr **sumend;
1016 Xintptr *tnext;
1017
1018 sum = (Xintptr *) NULL;
1019 sumend = ∑
1020
1021 while (a && b) {
1022 if (a->this == b->this) {
1023 tnext = a->next;
1024 Xintptrfree (a);
1025 a = tnext;
1026 tnext = b->next;
1027 Xintptrfree (b);
1028 b = tnext;
1029 } else if (a->this < b->this) {
1030 *sumend = a;
1031 sumend = &a->next;
1032 a = a->next;
1033 } else {
1034 assert (a->this > b->this);
1035 *sumend = b;
1036 sumend = &b->next;
1037 b = b->next;
1038 }
1039 }
1040 if (a) {
1041 *sumend = a;
1042 } else if (b) {
1043 *sumend = b;
1044 } else {
1045 *sumend = (Xintptr *) NULL;
1046 }
1047 return sum;
1048 }
1049
1050 /* destroys a, but leaves b alone */
1051 #ifdef CC_PROTOTYPE_ANSI
intptr_addto(Xintptr * a,Xintptr * b)1052 static Xintptr *intptr_addto (Xintptr *a, Xintptr *b)
1053 #else
1054 static Xintptr *intptr_addto (a, b)
1055 Xintptr *a;
1056 Xintptr *b;
1057 #endif
1058 {
1059 Xintptr *sum;
1060 Xintptr **sumend;
1061 Xintptr *tnext;
1062
1063 sum = (Xintptr *) NULL;
1064 sumend = ∑
1065
1066 while (a && b) {
1067 if (a->this == b->this) {
1068 tnext = a->next;
1069 Xintptrfree (a);
1070 a = tnext;
1071 b = b->next;
1072 } else if (a->this < b->this) {
1073 *sumend = a;
1074 sumend = &a->next;
1075 a = a->next;
1076 } else {
1077 assert (a->this > b->this);
1078 *sumend = Xintptralloc ();
1079 (*sumend)->this = b->this;
1080 sumend = & (*sumend)->next;
1081 b = b->next;
1082 }
1083 }
1084 if (a) {
1085 *sumend = a;
1086 } else if (b) {
1087 *sumend = intptr_copy (b);
1088 } else {
1089 *sumend = (Xintptr *) NULL;
1090 }
1091 return sum;
1092 }
1093
1094 #ifdef CC_PROTOTYPE_ANSI
intptr_copy(Xintptr * a)1095 static Xintptr *intptr_copy (Xintptr *a)
1096 #else
1097 static Xintptr *intptr_copy (a)
1098 Xintptr *a;
1099 #endif
1100 {
1101 Xintptr *sum;
1102 Xintptr **sumend;
1103
1104 sum = (Xintptr *) NULL;
1105 sumend = ∑
1106
1107 while (a) {
1108 *sumend = Xintptralloc ();
1109 (*sumend)->this = a->this;
1110 sumend = & (*sumend)->next;
1111 a = a->next;
1112 }
1113 *sumend = (Xintptr *) NULL;
1114 return sum;
1115 }
1116
1117 #ifdef CC_PROTOTYPE_ANSI
eqn_addto(Xeqn * a,Xeqn * b)1118 static void eqn_addto (Xeqn *a, Xeqn *b)
1119 #else
1120 static void eqn_addto (a, b)
1121 Xeqn *a;
1122 Xeqn *b;
1123 #endif
1124 {
1125 a->lhs = intptr_addto (a->lhs, b->lhs);
1126 a->rhs ^= b->rhs;
1127 }
1128
1129 #ifdef CC_PROTOTYPE_ANSI
dump_intptr_list(Xintptr * p)1130 static void dump_intptr_list (Xintptr *p)
1131 #else
1132 static void dump_intptr_list (p)
1133 Xintptr *p;
1134 #endif
1135 {
1136 if (p) {
1137 printf ("%d",p->this);
1138 p = p->next;
1139 }
1140 while (p) {
1141 printf (" %d",p->this);
1142 p = p->next;
1143 }
1144 fflush (stdout);
1145 }
1146
1147 #ifdef CC_PROTOTYPE_ANSI
find_label(Xintptr * e,int label)1148 static int find_label (Xintptr *e, int label)
1149 #else
1150 static int find_label (e, label)
1151 Xintptr *e;
1152 int label;
1153 #endif
1154 {
1155 while (e) {
1156 if (e->this == label) return 1;
1157 if (e->this > label) return 0;
1158 e = e->next;
1159 }
1160 return 0;
1161 }
1162
1163 #ifdef CC_PROTOTYPE_ANSI
intptr_list_size(Xintptr * p)1164 static int intptr_list_size (Xintptr *p)
1165 #else
1166 static int intptr_list_size (p)
1167 Xintptr *p;
1168 #endif
1169 {
1170 int i;
1171
1172 for (i=0; p; p = p->next) {
1173 i++;
1174 }
1175 return i;
1176 }
1177
1178 #ifdef CC_PROTOTYPE_ANSI
intptrlist_equal(Xintptr * a,Xintptr * b)1179 static int intptrlist_equal (Xintptr *a, Xintptr *b)
1180 #else
1181 static int intptrlist_equal (a, b)
1182 Xintptr *a;
1183 Xintptr *b;
1184 #endif
1185 {
1186 while (a && b) {
1187 if (a->this != b->this) {
1188 return 0;
1189 }
1190 a = a->next;
1191 b = b->next;
1192 }
1193 return (a == b);
1194 }
1195
1196 #ifdef CC_PROTOTYPE_ANSI
find_solution(Xintptr * sollst,Xintptrptr * found)1197 static int find_solution (Xintptr *sollst, Xintptrptr *found)
1198 #else
1199 static int find_solution (sollst, found)
1200 Xintptr *sollst;
1201 Xintptrptr *found;
1202 #endif
1203 {
1204 while (found) {
1205 if (intptrlist_equal (sollst, found->this)) {
1206 return 1;
1207 }
1208 found = found->next;
1209 }
1210 return 0;
1211 }
1212
1213 #ifdef CC_PROTOTYPE_ANSI
necklace_checkout_solution(Xintptr * sollst,PQ_node * pqroot,Xcplane ** list)1214 static int necklace_checkout_solution (Xintptr *sollst, PQ_node *pqroot, Xcplane **list)
1215 #else
1216 static int necklace_checkout_solution (sollst, pqroot, list)
1217 Xintptr *sollst;
1218 PQ_node *pqroot;
1219 Xcplane **list;
1220 #endif
1221 {
1222 int cnt;
1223 Xintptr *p;
1224 PQ_node *lefthalf, *righthalf;
1225 Xnodeptrptr *teeth;
1226 Xnodeptrptr *handles;
1227 Xnodeptrptr *npp;
1228 int test;
1229
1230 if (verbose) {
1231 printf ("New minimal solution: ");
1232 dump_intptr_list (sollst);
1233 printf ("\n");
1234 fflush (stdout);
1235 } else {
1236 printf (".");
1237 fflush (stdout);
1238 }
1239
1240 G->magicnum++;
1241 for (p = sollst, cnt = 0; p; p = p->next) {
1242 cnt++;
1243 necklist[p->this]->magiclabel = G->magicnum;
1244 }
1245
1246 if (count_labeled_children (pqroot) != cnt) {
1247 fprintf (stderr, "Lost some labels\n");
1248 exit (1);
1249 }
1250
1251 for (p = sollst; p; p = p->next) {
1252 if (!check_realization (necklist[p->this], cnt, &lefthalf, &righthalf)) {
1253 if (verbose) {
1254 printf ("Unrealizable!!\n");
1255 }
1256 return 0;
1257 }
1258 }
1259 if (verbose) {
1260 printf ("Realizable\n");
1261 } else {
1262 printf ("+");
1263 fflush (stdout);
1264 }
1265
1266 magicneckedgenum++;
1267
1268 teeth = (Xnodeptrptr *) NULL;
1269 for (p = sollst; p; p = p->next) {
1270 if (!check_realization (necklist[p->this], cnt, &lefthalf, &righthalf)) {
1271 fprintf (stderr, "ZZZ Whoops, necklace broke\n");
1272 exit (1);
1273 }
1274 npp = Xnodeptrptralloc ();
1275 npp->this = collect_necklace_tooth (lefthalf, righthalf, necklist[p->this], pqroot);
1276 npp->next = teeth;
1277 teeth = npp;
1278 }
1279 handles = Xnodeptrptralloc ();
1280 handles->next = (Xnodeptrptr *) NULL;
1281 handles->this = collect_necklace_handle ();
1282
1283 if (!Xcliquefluff (G, &handles, &teeth)) {
1284 printf ("ZZZ NECKLACE DE FLUFFED TO 0\n");
1285 fflush (stdout);
1286 return 0;
1287 }
1288
1289 test = Xloadcplane (list, (Xnodeptr *) NULL, handles, teeth, 0);
1290 if (!test) {
1291 Xfreeteeth (handles);
1292 Xfreeteeth (teeth);
1293 printf ("-");
1294 fflush (stdout);
1295 } else {
1296 printf ("YES ");
1297 fflush (stdout);
1298 }
1299
1300 return test;
1301 }
1302
1303 #ifdef CC_PROTOTYPE_ANSI
count_labeled_children(PQ_node * x)1304 static int count_labeled_children (PQ_node *x)
1305 #else
1306 static int count_labeled_children (x)
1307 PQ_node *x;
1308 #endif
1309 {
1310 int cnt = 0;
1311 PQ_node *z, *zprev, *znext;
1312
1313 PQ_set_FOREACH (x->children_set, z, children_elem, zprev, znext) {
1314 cnt += count_labeled_children (z);
1315 }
1316 if (x->magiclabel == G->magicnum) {
1317 cnt++;
1318 }
1319 x->labeled_children_count = cnt;
1320 return cnt;
1321 }
1322
1323 #ifdef CC_PROTOTYPE_ANSI
check_realization(PQ_node * x,int fullcnt,PQ_node ** lefthalf,PQ_node ** righthalf)1324 static int check_realization (PQ_node *x, int fullcnt, PQ_node **lefthalf, PQ_node **righthalf)
1325 #else
1326 static int check_realization (x, fullcnt, lefthalf, righthalf)
1327 PQ_node *x;
1328 int fullcnt;
1329 PQ_node **lefthalf;
1330 PQ_node **righthalf;
1331 #endif
1332 {
1333 PQ_node *z, *zprev, *znext;
1334
1335 PQ_set_FOREACH (x->children_set, z, children_elem, zprev, znext) {
1336 if (zprev && z->labeled_children_count == 0 && zprev->labeled_children_count == 0) {
1337 *lefthalf = zprev;
1338 *righthalf = z;
1339 return 1;
1340 }
1341 }
1342 if (x->labeled_children_count == fullcnt) {
1343 if (PQ_set_RIGHT_ELEM (x->children_set)->labeled_children_count == 0) {
1344 *lefthalf = PQ_set_RIGHT_ELEM (x->children_set);
1345 *righthalf = (PQ_node *) NULL;
1346 return 1;
1347 }
1348 if (PQ_set_LEFT_ELEM (x->children_set)->labeled_children_count == 0) {
1349 *lefthalf = PQ_set_LEFT_ELEM (x->children_set);
1350 *righthalf = (PQ_node *) NULL;
1351 return 1;
1352 }
1353 }
1354 return 0;
1355 }
1356
1357 #ifdef CC_PROTOTYPE_ANSI
collect_necklace_tooth(PQ_node * lefthalf,PQ_node * righthalf,PQ_node * x,PQ_node * pqroot)1358 static Xnodeptr *collect_necklace_tooth (PQ_node *lefthalf, PQ_node *righthalf, PQ_node *x, PQ_node *pqroot)
1359 #else
1360 static Xnodeptr *collect_necklace_tooth (lefthalf, righthalf, x, pqroot)
1361 PQ_node *lefthalf;
1362 PQ_node *righthalf;
1363 PQ_node *x;
1364 PQ_node *pqroot;
1365 #endif
1366 {
1367 Xnodeptr *tooth;
1368
1369 tooth = (Xnodeptr *) NULL;
1370
1371 if (!lefthalf) {
1372 lefthalf = righthalf;
1373 righthalf = (PQ_node *) NULL;
1374 }
1375 G->magicnum++;
1376 collect_neck_tooth_work (lefthalf, 0, G->magicnum, &tooth, (PQ_node *) NULL);
1377 if (righthalf) {
1378 collect_neck_tooth_work (righthalf, 1, G->magicnum, &tooth, (PQ_node *) NULL);
1379 } else {
1380 collect_neck_tooth_work (pqroot, 1, G->magicnum, &tooth, x);
1381 collect_neck_tooth_leaf (&necknodelist[MAGICNODE], 1, G->magicnum, &tooth);
1382 }
1383 return tooth;
1384 }
1385
1386 #ifdef CC_PROTOTYPE_ANSI
collect_neck_tooth_leaf(PQ_node * x,int mode,int label,Xnodeptr ** list)1387 static void collect_neck_tooth_leaf (PQ_node *x, int mode, int label, Xnodeptr **list)
1388 #else
1389 static void collect_neck_tooth_leaf (x, mode, label, list)
1390 PQ_node *x;
1391 int mode;
1392 int label;
1393 Xnodeptr **list;
1394 #endif
1395 {
1396 Xnodeptr *np;
1397 Xneckedgeptr *ep;
1398 PQ_node *y;
1399
1400 np = Xnodeptralloc ();
1401 np->this = G->nodelist + x->number;
1402 np->next = *list;
1403 *list = np;
1404 if (mode == 0) {
1405 x->magiclabel = label;
1406 } else {
1407 for (ep = x->adj; ep; ep = ep->next) {
1408 y = ep->this->ends[0];
1409 if (y == x) y = ep->this->ends[1];
1410 if (y->magiclabel == label) {
1411 ep->this->magiclabel = magicneckedgenum;
1412 }
1413 }
1414 }
1415 }
1416
1417 #ifdef CC_PROTOTYPE_ANSI
collect_neck_tooth_work(PQ_node * x,int mode,int label,Xnodeptr ** list,PQ_node * avoid)1418 static void collect_neck_tooth_work (PQ_node *x, int mode, int label, Xnodeptr **list, PQ_node *avoid)
1419 #else
1420 static void collect_neck_tooth_work (x, mode, label, list, avoid)
1421 PQ_node *x;
1422 int mode;
1423 int label;
1424 Xnodeptr **list;
1425 PQ_node *avoid;
1426 #endif
1427 {
1428 PQ_node *z, *zprev, *znext;
1429
1430 if (x == avoid) return;
1431 if (x->type == LEAF_NODE) {
1432 collect_neck_tooth_leaf (x, mode, label, list);
1433 } else {
1434 PQ_set_FOREACH (x->children_set, z, children_elem, zprev, znext) {
1435 collect_neck_tooth_work (z, mode, label, list, avoid);
1436 }
1437 }
1438 }
1439
1440 #ifdef CC_PROTOTYPE_ANSI
collect_necklace_handle(void)1441 static Xnodeptr *collect_necklace_handle (void)
1442 #else
1443 static Xnodeptr *collect_necklace_handle ()
1444 #endif
1445 {
1446 Xnodeptr *handle;
1447 int cnt;
1448 Xnodeptr *np;
1449 int i;
1450
1451 G->magicnum++;
1452 cnt = collect_necklace_label (necknodelist);
1453 handle = (Xnodeptr *) NULL;
1454 if (cnt*2 < G->nnodes) {
1455 for (i=0; i<G->nnodes; i++) {
1456 if (necknodelist[i].magiclabel == G->magicnum) {
1457 np = Xnodeptralloc ();
1458 np->this = &(G->nodelist[i]);
1459 np->next = handle;
1460 handle = np;
1461 }
1462 }
1463 } else {
1464 for (i=0; i<G->nnodes; i++) {
1465 if (necknodelist[i].magiclabel != G->magicnum) {
1466 np = Xnodeptralloc ();
1467 np->this = &(G->nodelist[i]);
1468 np->next = handle;
1469 handle = np;
1470 }
1471 }
1472 }
1473 return handle;
1474 }
1475
1476 #ifdef CC_PROTOTYPE_ANSI
collect_necklace_label(PQ_node * x)1477 static int collect_necklace_label (PQ_node *x)
1478 #else
1479 static int collect_necklace_label (x)
1480 PQ_node *x;
1481 #endif
1482 {
1483 int cnt;
1484 Xneckedgeptr *ep;
1485 PQ_node *y;
1486
1487 x->magiclabel = G->magicnum;
1488 cnt = 1;
1489
1490 for (ep = x->adj; ep; ep = ep->next) {
1491 if (ep->this->magiclabel != magicneckedgenum && ep->this->insystem) {
1492 y = ep->this->ends[0];
1493 if (y == x) y = ep->this->ends[1];
1494 if (y->magiclabel != G->magicnum) {
1495 cnt += collect_necklace_label (y);
1496 }
1497 }
1498 }
1499 return cnt;
1500 }
1501
1502 #ifdef CC_PROTOTYPE_ANSI
binsys_init(bin_system * s,int nvars)1503 static void binsys_init (bin_system *s, int nvars)
1504 #else
1505 static void binsys_init (s, nvars)
1506 bin_system *s;
1507 int nvars;
1508 #endif
1509 {
1510 int i;
1511
1512 s->vars = CC_SAFE_MALLOC (nvars, bin_var);
1513 if (!s->vars) {
1514 fprintf (stderr, "out of memory in necklace\n");
1515 exit (1);
1516 }
1517
1518 for (i=0; i<nnecklaces; i++) {
1519 s->vars[i].elim = (Xeqn *) NULL;
1520 s->vars[i].value = VALUE_UNKNOWN;
1521 s->vars[i].fixed = 0;
1522 }
1523
1524 s->sparselist = (Xeqn *) NULL;
1525 s->denseeqn = (Xeqn *) NULL;
1526 s->nvars = nvars;
1527 s->nfreevars = nvars;
1528 }
1529
1530 #ifdef CC_PROTOTYPE_ANSI
binsys_add_dense(bin_system * s,Xeqn * e)1531 static int binsys_add_dense (bin_system *s, Xeqn *e)
1532 #else
1533 static int binsys_add_dense (s, e)
1534 bin_system *s;
1535 Xeqn *e;
1536 #endif
1537 {
1538 assert (s->denseeqn == (Xeqn *) NULL);
1539 binsys_elim (s, e);
1540 if (e->lhs == (Xintptr *) NULL) {
1541 if (e->rhs == 0) {
1542 Xeqnfree (e);
1543 return 0;
1544 } else {
1545 Xeqnfree (e);
1546 return -1;
1547 }
1548 }
1549 s->denseeqn = e;
1550 e->next = (Xeqn *) NULL;
1551 s->nfreevars--;
1552 return 1;
1553 }
1554
1555 #ifdef CC_PROTOTYPE_ANSI
binsys_add_sparse(bin_system * s,Xeqn * e)1556 static int binsys_add_sparse (bin_system *s, Xeqn *e)
1557 #else
1558 static int binsys_add_sparse (s, e)
1559 bin_system *s;
1560 Xeqn *e;
1561 #endif
1562 {
1563 binsys_elim (s, e);
1564
1565 if (!e->lhs) {
1566 if (e->rhs == 0) {
1567 free_equation (e);
1568 return 0;
1569 } else {
1570 free_equation (e);
1571 return -1;
1572 }
1573 }
1574 if (s->denseeqn && intptrlist_equal (e->lhs, s->denseeqn->lhs)) {
1575 if (e->rhs == s->denseeqn->rhs) {
1576 free_equation (e);
1577 return 0;
1578 } else {
1579 free_equation (e);
1580 return -1;
1581 }
1582 }
1583 e->pivot = e->lhs->this;
1584 s->vars[e->pivot].elim = e;
1585 if (s->denseeqn && find_label (s->denseeqn->lhs, e->pivot)) {
1586 eqn_addto (s->denseeqn, e);
1587 assert (s->denseeqn->lhs);
1588 e->hitdense = 1;
1589 } else {
1590 e->hitdense = 0;
1591 }
1592 e->next = s->sparselist;
1593 s->sparselist = e;
1594 s->nfreevars--;
1595
1596 return 1;
1597 }
1598
1599 #ifdef CC_PROTOTYPE_ANSI
binsys_elim(bin_system * s,Xeqn * e)1600 static void binsys_elim (bin_system *s, Xeqn *e)
1601 #else
1602 static void binsys_elim (s, e)
1603 bin_system *s;
1604 Xeqn *e;
1605 #endif
1606 {
1607 Xintptr **p;
1608 Xintptr *q;
1609 Xeqn *f;
1610
1611 p = &e->lhs;
1612 while ((q = *p) != (Xintptr *) NULL) {
1613 if ((f = s->vars[q->this].elim) != (Xeqn *) NULL) {
1614 if (f->lhs && f->lhs->this == q->this) {
1615 eqn_addto (e, f);
1616 } else {
1617 eqn_addto (e, f);
1618 p = &e->lhs;
1619 }
1620 } else {
1621 p = & (*p)->next;
1622 }
1623 }
1624 }
1625
1626 #ifdef CC_PROTOTYPE_ANSI
binsys_random_minimal_solution(bin_system * s)1627 static Xintptr *binsys_random_minimal_solution (bin_system *s)
1628 #else
1629 static Xintptr *binsys_random_minimal_solution (s)
1630 bin_system *s;
1631 #endif
1632 {
1633 Xintptr *sollst;
1634 int nadded;
1635 int i;
1636
1637 for (i=0; i<s->nvars; i++) {
1638 s->vars[i].fixed = 0;
1639 }
1640
1641 nadded = 0;
1642 while (s->nfreevars) {
1643 binsys_random_solution (s);
1644 for (i=0; i<s->nvars; i++) {
1645 if (s->vars[i].value == 0 && !s->vars[i].fixed) {
1646 s->vars[i].fixed = 1;
1647 if (binsys_force_zero (s, i) == 1) {
1648 nadded++;
1649 }
1650 }
1651 }
1652 }
1653 binsys_random_solution (s);
1654 sollst = binsys_list_solution (s);
1655 for (i=0; i<nadded; i++) {
1656 binsys_pop_sparse (s);
1657 }
1658 return sollst;
1659 }
1660
1661 #ifdef CC_PROTOTYPE_ANSI
binsys_random_solution(bin_system * s)1662 static void binsys_random_solution (bin_system *s)
1663 #else
1664 static void binsys_random_solution (s)
1665 bin_system *s;
1666 #endif
1667 {
1668 Xeqn *e;
1669 int i;
1670
1671 for (i=0; i<s->nvars; i++) {
1672 if (s->vars[i].elim) {
1673 s->vars[i].value = VALUE_UNKNOWN;
1674 } else {
1675 s->vars[i].value = (CCutil_lprand () & 1);
1676 }
1677 }
1678 if (s->denseeqn && s->denseeqn->lhs) {
1679 s->denseeqn->pivot = s->denseeqn->lhs->this;
1680 binsys_eval_pivot (s, s->denseeqn);
1681 }
1682 for (e = s->sparselist; e; e = e->next) {
1683 binsys_eval_pivot (s, e);
1684 }
1685 }
1686
1687 #ifdef CC_PROTOTYPE_ANSI
binsys_eval_pivot(bin_system * s,Xeqn * e)1688 static void binsys_eval_pivot (bin_system *s, Xeqn *e)
1689 #else
1690 static void binsys_eval_pivot (s, e)
1691 bin_system *s;
1692 Xeqn *e;
1693 #endif
1694 {
1695 int val;
1696 Xintptr *p;
1697
1698 val = e->rhs;
1699 for (p = e->lhs; p; p = p->next) {
1700 if (p->this != e->pivot) {
1701 assert (s->vars[p->this].value != VALUE_UNKNOWN);
1702 val ^= s->vars[p->this].value;
1703 }
1704 }
1705 s->vars[e->pivot].value = val;
1706 }
1707
1708 #ifdef CC_PROTOTYPE_ANSI
binsys_force_zero(bin_system * s,int v)1709 static int binsys_force_zero (bin_system *s, int v)
1710 #else
1711 static int binsys_force_zero (s, v)
1712 bin_system *s;
1713 int v;
1714 #endif
1715 {
1716 Xeqn *e = Xeqnalloc ();
1717 Xintptr *p;
1718
1719 e->rhs = 0;
1720 p = Xintptralloc ();
1721 p->this = v;
1722 p->next = (Xintptr *) NULL;
1723 e->lhs = p;
1724
1725 return binsys_add_sparse (s, e);
1726 }
1727
1728 #ifdef CC_PROTOTYPE_ANSI
binsys_pop_sparse(bin_system * s)1729 static void binsys_pop_sparse (bin_system *s)
1730 #else
1731 static void binsys_pop_sparse (s)
1732 bin_system *s;
1733 #endif
1734 {
1735 Xeqn *e;
1736
1737 e = s->sparselist;
1738 s->sparselist = e->next;
1739 s->vars[e->pivot].elim = (Xeqn *) NULL;
1740 if (e->hitdense && s->denseeqn) {
1741 eqn_addto (s->denseeqn, e);
1742 }
1743 s->nfreevars++;
1744 free_equation (e);
1745 }
1746
1747 #ifdef CC_PROTOTYPE_ANSI
binsys_list_solution(bin_system * s)1748 static Xintptr *binsys_list_solution (bin_system *s)
1749 #else
1750 static Xintptr *binsys_list_solution (s)
1751 bin_system *s;
1752 #endif
1753 {
1754 Xintptr *lst;
1755 Xintptr **lstend;
1756 Xintptr *new;
1757 int i;
1758
1759 lst = (Xintptr *) NULL;
1760 lstend = &lst;
1761 for (i=0; i<s->nvars; i++) {
1762 if (s->vars[i].value == 1) {
1763 new = Xintptralloc ();
1764 new->this = i;
1765 *lstend = new;
1766 lstend = &new->next;
1767 }
1768 }
1769 *lstend = (Xintptr *) NULL;
1770 return lst;
1771 }
1772
1773 #ifdef CC_PROTOTYPE_ANSI
binsys_free_system(bin_system * s)1774 static void binsys_free_system (bin_system *s)
1775 #else
1776 static void binsys_free_system (s)
1777 bin_system *s;
1778 #endif
1779 {
1780 Xeqn *e, *enext;
1781
1782 CC_FREE (s->vars, bin_var);
1783
1784 for (e = s->sparselist; e; e = enext) {
1785 enext = e->next;
1786 free_equation (e);
1787 }
1788 if (s->denseeqn) {
1789 free_equation (s->denseeqn);
1790 }
1791
1792 s->vars = (bin_var *) NULL;
1793 s->sparselist = (Xeqn *) NULL;
1794 s->denseeqn = (Xeqn *) NULL;
1795 s->nvars = 0;
1796 s->nfreevars = 0;
1797 }
1798
1799 /* disjoint sets ala Tarjan (from Data Structures and Network Algorithms
1800 by Robert Tarjan) */
1801
1802 #ifdef CC_PROTOTYPE_ANSI
ds_makeset(PQ_node * v)1803 static void ds_makeset (PQ_node *v)
1804 #else
1805 static void ds_makeset (v)
1806 PQ_node *v;
1807 #endif
1808 {
1809 v->setinfo.parent = v;
1810 v->setinfo.rank = 0;
1811 }
1812
1813 #ifdef CC_PROTOTYPE_ANSI
ds_find(PQ_node * v)1814 static PQ_node *ds_find (PQ_node *v)
1815 #else
1816 static PQ_node *ds_find (v)
1817 PQ_node *v;
1818 #endif
1819 {
1820 PQ_node *p = v->setinfo.parent;
1821
1822 return v == p ? v : (v->setinfo.parent = ds_find (p));
1823 }
1824
1825 #ifdef CC_PROTOTYPE_ANSI
ds_link(PQ_node * x,PQ_node * y)1826 static PQ_node *ds_link (PQ_node *x, PQ_node *y)
1827 #else
1828 static PQ_node *ds_link (x, y)
1829 PQ_node *x;
1830 PQ_node *y;
1831 #endif
1832 {
1833 PQ_node *t;
1834 if (x->setinfo.rank > y->setinfo.rank) {
1835 SWAP (x,y,t);
1836 } else if (x->setinfo.rank == y->setinfo.rank) {
1837 y->setinfo.rank++;
1838 }
1839 x->setinfo.parent = y;
1840 return y;
1841 }
1842
1843 #ifdef CC_PROTOTYPE_ANSI
init_elems(PQ_node * elems)1844 static PQ_node *init_elems (PQ_node *elems)
1845 #else
1846 static PQ_node *init_elems (elems)
1847 PQ_node *elems;
1848 #endif
1849 {
1850 int i;
1851 PQ_node *token;
1852
1853 for (i = 0, token = (PQ_node *) NULL; i < G->nnodes; i++) {
1854 if (i != MAGICNODE) {
1855 elems[i].next = token;
1856 token = &elems[i];
1857 }
1858 elems[i].number = i;
1859 }
1860
1861 XPQ_init_tree (token);
1862 return token;
1863 }
1864
1865 #ifdef CC_PROTOTYPE_ANSI
add_clique_to_PQtree(Xclique * c,PQ_node * elems)1866 static int add_clique_to_PQtree (Xclique *c, PQ_node *elems)
1867 #else
1868 static int add_clique_to_PQtree (c, elems)
1869 Xclique *c;
1870 PQ_node *elems;
1871 #endif
1872 {
1873 PQ_node *cut;
1874
1875 cut = clique_to_PQlist (c, elems);
1876 return (XPQ_process (cut) != (PQ_node *) NULL);
1877 }
1878
1879 #ifdef CC_PROTOTYPE_ANSI
clique_to_PQlist(Xclique * c,PQ_node * elems)1880 static PQ_node *clique_to_PQlist (Xclique *c, PQ_node *elems)
1881 #else
1882 static PQ_node *clique_to_PQlist (c, elems)
1883 Xclique *c;
1884 PQ_node *elems;
1885 #endif
1886 {
1887 Xintptr *p;
1888 PQ_node *cut;
1889 int n;
1890
1891 if (find_intptr_list (c->nodes, MAGICNODE)) {
1892 G->magicnum++;
1893 for (p = c->nodes; p; p = p->next) {
1894 G->nodelist[p->this].magiclabel = G->magicnum;
1895 }
1896 for (n = 1, cut = (PQ_node *) NULL; n < G->nnodes; n++) {
1897 if (G->nodelist[n].magiclabel != G->magicnum) {
1898 elems[n].next = cut;
1899 cut = &elems[n];
1900 }
1901 }
1902 } else {
1903 for (cut = (PQ_node *) NULL, p = c->nodes; p; p = p->next) {
1904 n = p->this;
1905 elems[n].next = cut;
1906 cut = &elems[n];
1907 }
1908 }
1909 return cut;
1910 }
1911
1912
1913
1914 #ifdef CC_PROTOTYPE_ANSI
find_intptr_list(Xintptr * p,int n)1915 static int find_intptr_list (Xintptr *p, int n)
1916 #else
1917 static int find_intptr_list (p, n)
1918 Xintptr *p;
1919 int n;
1920 #endif
1921 {
1922 while (p) {
1923 if (p->this == n)
1924 return 1;
1925 p = p->next;
1926 }
1927 return 0;
1928 }
1929
1930
1931