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