matroid-finder.c

   1 #include <errno.h>
   2 #include <fcntl.h>
   3 #include <limits.h>
   4 #include <locale.h>
   5 #include <stddef.h>
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9 #include <sys/mman.h>
  10 #include <sys/stat.h>
  11 #include <unistd.h>
  12 #include <wchar.h>
  13 #include <wctype.h>
  14
  15 #define STR2(x) #x
  16 #define STR(x) STR2(x)
  17
  18 #define L(x) __FILE__ ":" STR(__LINE__) ": " x
  19 #define SGN(x, y) (((x) < (y)) ? -1 : ((x) > (y) ? 1 : 0))
  20 #define UNUSED(x) (void) (sizeof(x))
  21
  22 #define BOUNDARY_NODE ((node *) 0)
  23 #define NODE_NAME(n) ((n) ? ((n)->name) : ("BOUNDARY"))
  24 #define NODE_COLOR(n) ((n) ? ((n)->c) : (C_BOUNDARY))
  25
  26 typedef enum { C_BLACK, C_WHITE, C_BOUNDARY } color;
  27 typedef enum { D_LEFT, D_RIGHT } dir;
  28 typedef enum { R_AWAY, R_TO } relative_dir;
  29 typedef struct {
  30         /* */
  31         char *name;
  32         size_t name_len;
  33         color c;
  34         char check_res;
  35 } node;
  36 typedef struct {
  37         /* */
  38         node *l;
  39         node *r;
  40         dir d;
  41         unsigned int fix_depth;
  42 } edge;
  43 typedef struct {
  44         /* */
  45         size_t nodes_num;
  46         node *nodes;
  47         size_t edges_num;
  48         edge *edges;
  49 } graph;
  50
  51 static int
  52 add_new_node(graph *g,
  53              color c,
  54              const char *s,
  55              size_t n)
  56 {
  57         void *newmem = 0;
  58         char *sd;
  59         int ret = -1;
  60         size_t j = 0;
  61         const char *p;
  62
  63         if (n > INT_MAX / 2) {
  64                 fprintf(stderr, "Absurdly long node name\n");
  65                 goto cleanup;
  66         }
  67
  68         if (!strncmp(s, "BOUNDARY", n) &&
  69             n == 8) {
  70                 fprintf(stderr, "The node name `BOUNDARY' is forbidden\n");
  71                 goto cleanup;
  72         }
  73
  74         for (p = s; p < s + n; ++p) {
  75                 if (*p == '[' ||
  76                     *p == ']' ||
  77                     *p == '(' ||
  78                     *p == ')') {
  79                         fprintf(stderr,
  80                                 "Node names are not allowed to contain `[', "
  81                                 "`]', `(', or `)'");
  82                         goto cleanup;
  83                 }
  84         }
  85
  86         for (j = 0; j < g->nodes_num; ++j) {
  87                 if (!strncmp(s, g->nodes[j].name, n) &&
  88                     g->nodes[j].name_len == n) {
  89                         fprintf(stderr, "Duplicate node %s\n",
  90                                 g->nodes[j].name);
  91                         goto cleanup;
  92                 }
  93         }
  94
  95         if (!(newmem = realloc(g->nodes, (g->nodes_num + 1) *
  96                                sizeof *g->nodes))) {
  97                 perror(L("realloc"));
  98                 goto cleanup;
  99         }
 100
 101         if (!(sd = strndup(s, n + 1))) {
 102                 perror(L("strndup"));
 103                 goto cleanup;
 104         }
 105
 106         sd[n] = '\0';
 107         g->nodes = newmem;
 108         g->nodes[g->nodes_num] = (node) { .name = sd, .name_len = n, .c = c };
 109         newmem = sd = 0;
 110         g->nodes_num++;
 111         ret = 0;
 112 cleanup:
 113         free(newmem);
 114         free(sd);
 115
 116         return ret;
 117 }
 118
 119 static int
 120 add_new_edge(graph *g,
 121              const char *s1,
 122              size_t n1,
 123              const char *s2,
 124              size_t n2)
 125 {
 126         void *newmem = 0;
 127         edge *e = 0;
 128         node *v1 = 0;
 129         node *v2 = 0;
 130         int ret = -1;
 131         size_t j = 0;
 132
 133         if (n1 > INT_MAX / 2 ||
 134             n2 > INT_MAX / 2) {
 135                 fprintf(stderr, "Absurdly long node name\n");
 136                 goto cleanup;
 137         }
 138
 139         for (j = 0; j < g->nodes_num; ++j) {
 140                 if (!strncmp(s1, g->nodes[j].name, n1) &&
 141                     g->nodes[j].name_len == n1) {
 142                         v1 = &g->nodes[j];
 143                         break;
 144                 }
 145         }
 146
 147         for (j = 0; j < g->nodes_num; ++j) {
 148                 if (!strncmp(s2, g->nodes[j].name, n2) &&
 149                     g->nodes[j].name_len == n2) {
 150                         v2 = &g->nodes[j];
 151                         break;
 152                 }
 153         }
 154
 155         if (!v1) {
 156                 if (strncmp(s1, "BOUNDARY", n1) ||
 157                     n1 != 8) {
 158                         fprintf(stderr, "Unknown node `%.*s'\n", (int) n1, s1);
 159                         goto cleanup;
 160                 }
 161         }
 162
 163         if (!v2) {
 164                 if (strncmp(s2, "BOUNDARY", n2) ||
 165                     n2 != 8) {
 166                         fprintf(stderr, "Unknown node `%.*s'\n", (int) n2, s2);
 167                         goto cleanup;
 168                 }
 169         }
 170
 171         if (v1 == v2) {
 172                 fprintf(stderr, "Illegal node (%s, %s)\n", NODE_NAME(v1),
 173                         NODE_NAME(v2));
 174                 goto cleanup;
 175         }
 176
 177         for (j = 0; j < g->edges_num; ++j) {
 178                 e = &g->edges[j];
 179
 180                 if ((e->l == v1 &&
 181                      e->r == v2) ||
 182                     (e->l == v2 &&
 183                      e->r == v1)) {
 184                         fprintf(stderr, "Duplicate edge (%s, %s)\n", NODE_NAME(
 185                                         e->l), NODE_NAME(e->r));
 186                         goto cleanup;
 187                 }
 188         }
 189
 190         if (!(newmem = realloc(g->edges, (g->edges_num + 1) *
 191                                sizeof *g->edges))) {
 192                 perror(L("realloc"));
 193                 goto cleanup;
 194         }
 195
 196         g->edges = newmem;
 197         g->edges[g->edges_num] = (edge) { .l = v1, .r = v2, .fix_depth = -1 };
 198         newmem = 0;
 199         g->edges_num++;
 200         ret = 0;
 201 cleanup:
 202         free(newmem);
 203
 204         return ret;
 205 }
 206
 207 /*
 208  * Order edges first by their left component, then by their right
 209  * component. This ensures that the edges representing boundary nodes
 210  * are always first.
 211  */
 212 static int
 213 comp_edge(const void *a,
 214           const void *b)
 215 {
 216         edge *pa = (edge *) a;
 217         edge *pb = (edge *) b;
 218         int d = 0;
 219
 220         if (!pa->l &&
 221             pb->l) {
 222                 return -1;
 223         }
 224
 225         if (pa->l &&
 226             !pb->l) {
 227                 return 1;
 228         }
 229
 230         if (pa->l &&
 231             pb->l) {
 232                 d = strcmp(pa->l->name, pb->l->name);
 233
 234                 if (d) {
 235                         return d;
 236                 }
 237         }
 238
 239         return strcmp(pa->r->name, pb->r->name);
 240 }
 241
 242 /*
 243  * Returns the address of the first byte of a non-whitespace character
 244  * beyond s, or 0 on error, or terminus on exhaustion.
 245  */
 246 static const char *
 247 next_wchar_of_certain_type(const char *s,
 248                            const char *terminus,
 249                            char want_whitespace)
 250 {
 251         const char *p = s;
 252         mbstate_t ps = { 0 };
 253         size_t e = 0;
 254         wchar_t wc = 0;
 255
 256         if (s == terminus) {
 257                 return 0;
 258         }
 259
 260         while (p < terminus) {
 261                 switch ((e = mbrtowc(&wc, p, (terminus - p) + 1, &ps))) {
 262                 case (size_t) -1:
 263                 case (size_t) -2:
 264                         perror(L("mbrtowc"));
 265
 266                         return 0;
 267                         break;
 268                 case 0:
 269
 270                         return 0;
 271                         break;
 272                 default:
 273
 274                         if ((!!want_whitespace == !!iswspace(wc)) &&
 275                             p != s) {
 276                                 return p;
 277                         }
 278                 }
 279
 280                 p += e;
 281         }
 282
 283         return terminus;
 284 }
 285
 286 static int
 287 read_file(const char *path,
 288           graph *g)
 289 {
 290         int fd = 0;
 291         int ret = -1;
 292         char *contents = 0;
 293         const char *contents_end = 0;
 294         const char *p = 0;
 295         const char *q = 0;
 296         const char *r = 0;
 297         const char *s = 0;
 298         const char *t = 0;
 299         struct stat sb;
 300         size_t length = 0;
 301
 302         if ((fd = open(path, O_RDONLY)) < 0) {
 303                 perror(L("open"));
 304                 goto cleanup;
 305         }
 306
 307         if (fstat(fd, &sb) < 0) {
 308                 perror(L("fstat"));
 309                 goto cleanup;
 310         }
 311
 312         length = sb.st_size;
 313
 314         if (length < 4) {
 315                 fprintf(stderr, "File is not well-formed\n");
 316                 goto cleanup;
 317         }
 318
 319         if ((contents = mmap(0, length, PROT_READ, MAP_PRIVATE, fd, 0)) ==
 320             MAP_FAILED) {
 321                 perror("mmap");
 322                 goto cleanup;
 323         }
 324
 325         contents_end = contents + (length - 1);
 326
 327         if (!(p = memchr(contents, '[', length)) ||
 328             strncmp(p, "[W]", 3)) {
 329                 fprintf(stderr, "File does not contain `[W]' marker\n");
 330                 goto cleanup;
 331         }
 332
 333         q = p + 3;
 334         r = memchr(q, '[', contents_end - q);
 335
 336         if (!r ||
 337             strncmp(r, "[B]", 3)) {
 338                 fprintf(stderr, "File does not contain `[B]' marker\n");
 339                 goto cleanup;
 340         }
 341
 342         p = next_wchar_of_certain_type(q, r, 0);
 343         q = next_wchar_of_certain_type(p, r, 1);
 344
 345         while (q &&
 346                q <= r) {
 347                 if (p != q) {
 348                         if (add_new_node(g, C_WHITE, p, q - p) < 0) {
 349                                 goto cleanup;
 350                         }
 351                 }
 352
 353                 p = next_wchar_of_certain_type(q, contents_end, 0);
 354                 q = next_wchar_of_certain_type(p, contents_end, 1);
 355         }
 356
 357         p = r + 3;
 358         r = memchr(p, '[', contents_end - q);
 359
 360         if (!r ||
 361             strncmp(r, "[E]", 3)) {
 362                 fprintf(stderr, "File does not contain `[E]' marker\n");
 363                 goto cleanup;
 364         }
 365
 366         p = next_wchar_of_certain_type(p, r, 0);
 367         q = next_wchar_of_certain_type(p, r, 1);
 368
 369         while (q &&
 370                q <= r) {
 371                 if (p != q) {
 372                         if (add_new_node(g, C_BLACK, p, q - p) < 0) {
 373                                 goto cleanup;
 374                         }
 375                 }
 376
 377                 p = next_wchar_of_certain_type(q, contents_end, 0);
 378                 q = next_wchar_of_certain_type(p, contents_end, 1);
 379         }
 380
 381         s = r;
 382
 383         while (1) {
 384                 if (!(p = memchr(s, '(', contents_end - s))) {
 385                         break;
 386                 }
 387
 388                 if (!(p = next_wchar_of_certain_type(p, contents_end, 0))) {
 389                         break;
 390                 }
 391
 392                 if (!(q = next_wchar_of_certain_type(p, contents_end, 1))) {
 393                         break;
 394                 }
 395
 396                 if (!(r = next_wchar_of_certain_type(q, contents_end, 0))) {
 397                         break;
 398                 }
 399
 400                 if (!(s = next_wchar_of_certain_type(r, contents_end, 1))) {
 401                         break;
 402                 }
 403
 404                 if (!(t = memchr(r, ')', contents_end - r))) {
 405                         break;
 406                 }
 407
 408                 s = (s < t) ? s : t;
 409
 410                 if (add_new_edge(g, p, q - p, r, s - r) < 0) {
 411                         goto cleanup;
 412                 }
 413         }
 414
 415         ret = 0;
 416 cleanup:
 417
 418         if (fd) {
 419                 close(fd);
 420         }
 421
 422         if (contents) {
 423                 munmap(contents, length);
 424         }
 425
 426         return ret;
 427 }
 428
 429 /*
 430  * Modify graph g so that all edges containing v point away from (to)
 431  * node v when away==1 (0), except the specified exception edge. If a
 432  * contradiction is encountered, *proven_wrong is set. If anything is
 433  * done, *changed is set.
 434  */
 435 static void
 436 ensure_all_pointing_right_dir(graph *g,
 437                               node *v,
 438                               relative_dir rd,
 439                               unsigned int depth,
 440                               edge *except,
 441                               char *changed,
 442                               char *proven_wrong)
 443 {
 444         size_t j;
 445         edge *e;
 446
 447         if (!g ||
 448             !v ||
 449             *proven_wrong) {
 450                 return;
 451         }
 452
 453         for (j = 0; j < g->edges_num; ++j) {
 454                 if ((e = &g->edges[j]) == except) {
 455                         continue;
 456                 }
 457
 458                 if (e->l == v) {
 459                         if (e->fix_depth <= depth &&
 460                             e->d == (rd == R_AWAY ? D_LEFT : D_RIGHT)) {
 461                                 *proven_wrong = 1;
 462
 463                                 return;
 464                         }
 465
 466                         if (e->fix_depth > depth) {
 467                                 *changed = 1;
 468                                 e->fix_depth = depth;
 469                                 e->d = (rd == R_AWAY ? D_RIGHT : D_LEFT);
 470                         }
 471                 } else if (e->r == v) {
 472                         if (e->fix_depth <= depth &&
 473                             e->d == (rd == R_AWAY ? D_RIGHT : D_LEFT)) {
 474                                 *proven_wrong = 1;
 475
 476                                 return;
 477                         }
 478
 479                         if (e->fix_depth > depth) {
 480                                 *changed = 1;
 481                                 e->fix_depth = depth;
 482                                 e->d = (rd == R_AWAY ? D_LEFT : D_RIGHT);
 483                         }
 484                 }
 485         }
 486 }
 487
 488 /*
 489  * Check graph g to ensure that there is at least one edge containing
 490  * v which is able to be set to point away from (to) node v when
 491  * away==1 (0). If none is found, *proven_wrong is set. If exactly one
 492  * is found, it is fixed with the appropriate depth and *changed is
 493  * set.
 494  */
 495 static void
 496 ensure_one_left_to_point_right(graph *g,
 497                                node *v,
 498                                relative_dir rd,
 499                                unsigned int depth,
 500                                char *changed,
 501                                char *proven_wrong)
 502 {
 503         size_t j;
 504         edge *e = 0;
 505         edge *candidate = 0;
 506
 507         if (!g ||
 508             !v ||
 509             *proven_wrong) {
 510                 return;
 511         }
 512
 513         for (j = 0; j < g->edges_num; ++j) {
 514                 e = &g->edges[j];
 515
 516                 if (e->fix_depth <= depth) {
 517                         if (!(e->l == v &&
 518                               e->d == (rd == R_AWAY ? D_RIGHT : D_LEFT)) &&
 519                             !(e->r == v &&
 520                               e->d == (rd == R_AWAY ? D_LEFT : D_RIGHT))) {
 521                                 /*
 522                                  * Ignore fixed nodes that don't have
 523                                  * right orientation and endpoint
 524                                  */
 525                                 continue;
 526                         }
 527
 528                         /*
 529                          * We don't just have a candidate, we have an
 530                          * actual fixed edge. Don't bother checking
 531                          * for the error case of two edges, or
 532                          * forcibly setting all other edges to the
 533                          * right direction, those actions are handled
 534                          * in ensure_all_pointing_right_dir().
 535                          */
 536                         return;
 537                 } else if (e->l == v ||
 538                            e->r == v) {
 539                         if (candidate) {
 540
 541                                 /*
 542                                  * There are multiple candidates, so
 543                                  * we can't set anything
 544                                  */
 545                                 return;
 546                         }
 547
 548                         candidate = e;
 549                 }
 550         }
 551
 552         if (!candidate) {
 553                 /*
 554                  * There's nothing that could save us - this
 555                  * configuration is impossible.
 556                  */
 557                 *proven_wrong = 1;
 558
 559                 return;
 560         }
 561
 562         *changed = 1;
 563         candidate->fix_depth = depth;
 564
 565         if ((candidate->l == v &&
 566              rd == R_AWAY) ||
 567             (candidate->r == v &&
 568              rd == R_TO)) {
 569                 candidate->d = D_RIGHT;
 570         } else {
 571                 candidate->d = D_LEFT;
 572         }
 573 }
 574
 575 static void
 576 update_for_newly_fixed_edge(graph *g,
 577                             edge *e,
 578                             unsigned int depth,
 579                             char *changed,
 580                             char *proven_wrong)
 581 {
 582         if (!g ||
 583             !e) {
 584                 return;
 585         }
 586
 587         switch (e->d) {
 588         case D_LEFT:
 589
 590                 switch (NODE_COLOR(e->l)) {
 591                 case C_WHITE:
 592                         ensure_all_pointing_right_dir(g, e->l, R_AWAY, depth, e,
 593                                                       changed, proven_wrong);
 594                         break;
 595                 case C_BLACK:
 596                         ensure_one_left_to_point_right(g, e->l, R_AWAY, depth,
 597                                                        changed, proven_wrong);
 598                         break;
 599                 default:
 600                         break;
 601                 }
 602
 603                 if (*proven_wrong) {
 604                         return;
 605                 }
 606
 607                 switch (NODE_COLOR(e->r)) {
 608                 case C_WHITE:
 609                         ensure_one_left_to_point_right(g, e->r, R_TO, depth,
 610                                                        changed, proven_wrong);
 611                         break;
 612                 case C_BLACK:
 613                         ensure_all_pointing_right_dir(g, e->r, R_TO, depth, e,
 614                                                       changed, proven_wrong);
 615                         break;
 616                 default:
 617                         break;
 618                 }
 619
 620                 break;
 621         case D_RIGHT:
 622
 623                 switch (NODE_COLOR(e->l)) {
 624                 case C_WHITE:
 625                         ensure_one_left_to_point_right(g, e->l, R_TO, depth,
 626                                                        changed, proven_wrong);
 627                         break;
 628                 case C_BLACK:
 629                         ensure_all_pointing_right_dir(g, e->l, R_TO, depth, e,
 630                                                       changed, proven_wrong);
 631                         break;
 632                 default:
 633                         break;
 634                 }
 635
 636                 if (*proven_wrong) {
 637                         return;
 638                 }
 639
 640                 switch (NODE_COLOR(e->r)) {
 641                 case C_WHITE:
 642                         ensure_all_pointing_right_dir(g, e->r, R_AWAY, depth, e,
 643                                                       changed, proven_wrong);
 644                         break;
 645                 case C_BLACK:
 646                         ensure_one_left_to_point_right(g, e->r, 1, depth,
 647                                                        changed, proven_wrong);
 648                         break;
 649                 default:
 650                         break;
 651                 }
 652
 653                 break;
 654         }
 655 }
 656
 657 /*
 658  * Repeatedly call update_for_newly_fixed_edge on all edges of a given
 659  * depth, possibly fixing more choices of edge directions at that
 660  * depth.
 661  */
 662 static void
 663 update_to_fixed_point(graph *g,
 664                       unsigned int depth,
 665                       char *broken,
 666                       char allow_scan_below_depth)
 667 {
 668         char changed = 1;
 669         edge *e = 0;
 670         size_t j;
 671
 672         while (changed &&
 673                !*broken) {
 674                 changed = 0;
 675
 676                 for (j = 0; j < g->edges_num; ++j) {
 677                         e = &g->edges[j];
 678
 679                         if (e->fix_depth == depth ||
 680                             (allow_scan_below_depth &&
 681                              e->fix_depth <= depth)) {
 682                                 update_for_newly_fixed_edge(g, e, depth,
 683                                                             &changed, broken);
 684                         }
 685                 }
 686         }
 687 }
 688
 689 int
 690 admits_perfect_orientation(graph *g,
 691                            unsigned int depth)
 692 {
 693         edge *e;
 694         edge *chosen_to_fix = 0;
 695         char broken = 0;
 696         size_t j = 0;
 697
 698         if (depth >= (unsigned int) -3) {
 699                 fprintf(stderr, "Absurd depth encountered - bailing\n");
 700
 701                 return 0;
 702         }
 703
 704         for (j = 0; j < g->edges_num; ++j) {
 705                 e = &g->edges[j];
 706
 707                 if (e->fix_depth > depth) {
 708                         /*
 709                          * In the case that some edges were tested
 710                          * before for other configurations, we wish to
 711                          * avoid the situation in which such a branch
 712                          * was tested at depth depth+1, and is not
 713                          * selected as the unfixed branch here. For
 714                          * then it would, in any speculation arising
 715                          * from this position, magically appear to be
 716                          * fixed, when it really should not be.
 717                          */
 718                         e->fix_depth = (unsigned int) -1;
 719                         chosen_to_fix = e;
 720                 }
 721         }
 722
 723         if (chosen_to_fix) {
 724                 chosen_to_fix->d = D_LEFT;
 725
 726                 /*
 727                  * We start out at depth + 2 so that, if this doesn't
 728                  * work out, the ramifications will be nicely hidden
 729                  * by moving to only depth + 1 in the next step
 730                  */
 731                 chosen_to_fix->fix_depth = depth + 2;
 732                 update_to_fixed_point(g, depth + 2, &broken, 0);
 733
 734                 if (!broken &&
 735                     admits_perfect_orientation(g, depth + 2)) {
 736                         return 1;
 737                 }
 738
 739                 /*
 740                  * Evidently setting that direction to LEFT resulted
 741                  * in a contradiction. So we may freely set it to
 742                  * RIGHT. We could really set the depth to `depth'
 743                  * here, but that doesn't really gain anything.
 744                  */
 745                 chosen_to_fix->d = D_RIGHT;
 746                 chosen_to_fix->fix_depth = depth + 1;
 747                 broken = 0;
 748                 update_to_fixed_point(g, depth + 1, &broken, 0);
 749
 750                 if (!broken &&
 751                     admits_perfect_orientation(g, depth + 1)) {
 752                         return 1;
 753                 }
 754
 755                 /*
 756                  * There was a choice we could make, and each choice
 757                  * led to a contradiction.
 758                  */
 759                 return 0;
 760         }
 761
 762         /*
 763          * At this point, there's nothing we may choose. Just check
 764          * whether our choices made sense.
 765          */
 766         for (j = 0; j < g->nodes_num; ++j) {
 767                 g->nodes[j].check_res = 0;
 768         }
 769
 770         for (j = 0; j < g->edges_num; ++j) {
 771                 e = &g->edges[j];
 772
 773                 switch (e->d) {
 774                 case D_LEFT:
 775
 776                         if (e->l &&
 777                             e->l->c == C_WHITE) {
 778                                 broken = broken ||
 779                                          e->l->check_res;
 780                                 e->l->check_res = 1;
 781                         }
 782
 783                         if (e->r &&
 784                             e->r->c == C_BLACK) {
 785                                 broken = broken ||
 786                                          e->r->check_res;
 787                                 e->r->check_res = 1;
 788                         }
 789
 790                         break;
 791                 case D_RIGHT:
 792
 793                         if (e->l &&
 794                             e->l->c == C_BLACK) {
 795                                 broken = broken ||
 796                                          e->l->check_res;
 797                                 e->l->check_res = 1;
 798                         }
 799
 800                         if (e->r &&
 801                             e->r->c == C_WHITE) {
 802                                 broken = broken ||
 803                                          e->r->check_res;
 804                                 e->r->check_res = 1;
 805                         }
 806
 807                         break;
 808                 }
 809
 810                 if (broken) {
 811                         break;
 812                 }
 813         }
 814
 815         for (j = 0; j < g->nodes_num; ++j) {
 816                 broken = broken ||
 817                          !g->nodes[j].check_res;
 818         }
 819
 820         return !broken;
 821 }
 822
 823 /*** REIMPLEMENTATION LINE ***/
 824 int
 825 main(int argc,
 826      char **argv)
 827 {
 828         graph g = { 0 };
 829         char broken = 0;
 830         edge *e = 0;
 831         node *t = 0;
 832         size_t j = 0;
 833         size_t num_edge_nodes = 0;
 834
 835         setlocale(LC_ALL, "");
 836
 837         if (argc != 2) {
 838                 printf("Usage: %s INPUT_FILE\n", argv[0]);
 839
 840                 return 1;
 841         }
 842
 843         if (read_file(argv[1], &g) < 0) {
 844                 return 1;
 845         }
 846
 847         /* Tidy up the edges */
 848         for (j = 0; j < g.edges_num; ++j) {
 849                 e = &g.edges[j];
 850
 851                 if (!e->r) {
 852                         t = e->l;
 853                         e->l = e->r;
 854                         e->r = t;
 855                 } else if (e->l &&
 856                            e->r &&
 857                            strcmp(e->l->name, e->r->name) > 0) {
 858                         t = e->l;
 859                         e->l = e->r;
 860                         e->r = t;
 861                 }
 862         }
 863
 864         qsort(g.edges, g.edges_num, sizeof *g.edges, comp_edge);
 865
 866         /*
 867          * Now all the border nodes (the 0s) are at the front - how
 868          * many are there? While we're here, fix the boundary edges as
 869          * LEFT at initial depth 0.
 870          */
 871         for (j = 0; j < g.edges_num; ++j) {
 872                 e = &g.edges[j];
 873
 874                 if (!e->l) {
 875                         num_edge_nodes++;
 876                         e->fix_depth = 0;
 877                         e->d = D_LEFT;
 878                 } else {
 879                         e->fix_depth = (unsigned int) -1;
 880                 }
 881         }
 882
 883         /*
 884          * Count upwards through the possible start source/sink
 885          * configurations, in binary
 886          */
 887         do {
 888                 for (j = num_edge_nodes; j < g.edges_num; ++j) {
 889                         g.edges[j].fix_depth = (unsigned int) -1;
 890                 }
 891
 892                 broken = 0;
 893                 update_to_fixed_point(&g, 0, &broken, 1);
 894
 895                 if (!broken &&
 896                     admits_perfect_orientation(&g, 1)) {
 897                         printf("{ ");
 898
 899                         for (j = 0; j < num_edge_nodes; ++j) {
 900                                 if (g.edges[j].d == D_LEFT) {
 901                                         printf("%s ", NODE_NAME(g.edges[j].r));
 902                                 }
 903                         }
 904
 905                         printf("}\n");
 906                 }
 907
 908                 if (g.edges[0].d == D_LEFT) {
 909                         g.edges[0].d = D_RIGHT;
 910                 } else {
 911                         j = 0;
 912
 913                         while (j < num_edge_nodes) {
 914                                 if (g.edges[j].d == D_RIGHT) {
 915                                         g.edges[j].d = D_LEFT;
 916                                 } else {
 917                                         g.edges[j].d = D_RIGHT;
 918                                         break;
 919                                 }
 920
 921                                 j++;
 922                         }
 923
 924                         if (j >= num_edge_nodes) {
 925                                 /* Must have tried all configurations */
 926                                 break;
 927                         }
 928                 }
 929         } while (1);
 930
 931         free(g.edges);
 932
 933         for (j = 0; j < g.nodes_num; ++j) {
 934                 free(g.nodes[j].name);
 935         }
 936
 937         free(g.nodes);
 938
 939         return 0;
 940 }