diff options
Diffstat (limited to 'apps/plugins/puzzles/src/matching.c')
-rw-r--r-- | apps/plugins/puzzles/src/matching.c | 424 |
1 files changed, 1 insertions, 423 deletions
diff --git a/apps/plugins/puzzles/src/matching.c b/apps/plugins/puzzles/src/matching.c index 9078f6c36a..aabdae0846 100644 --- a/apps/plugins/puzzles/src/matching.c +++ b/apps/plugins/puzzles/src/matching.c | |||
@@ -319,35 +319,7 @@ int matching(int nl, int nr, int **adjlists, int *adjsizes, | |||
319 | return ret; | 319 | return ret; |
320 | } | 320 | } |
321 | 321 | ||
322 | #ifdef STANDALONE_MATCHING_TEST | 322 | void matching_witness(void *scratchv, int nl, int nr, int *witness) |
323 | |||
324 | /* | ||
325 | * Diagnostic routine used in testing this algorithm. It is passed a | ||
326 | * pointer to a piece of scratch space that's just been used by | ||
327 | * matching_with_scratch, and extracts from it a labelling of the | ||
328 | * input graph that acts as a 'witness' to the maximality of the | ||
329 | * returned matching. | ||
330 | * | ||
331 | * The output parameter 'witness' should be an array of (nl+nr) | ||
332 | * integers, indexed such that witness[L] corresponds to an L-vertex (for | ||
333 | * L=0,1,...,nl-1) and witness[nl+R] corresponds to an R-vertex (for | ||
334 | * R=0,1,...,nr-1). On return, this array will assign each vertex a | ||
335 | * label which is either 0 or 1, and the following properties will | ||
336 | * hold: | ||
337 | * | ||
338 | * + all vertices not paired up by the matching are type L0 or R1 | ||
339 | * + every L0->R1 edge is used by the matching | ||
340 | * + no L1->R0 edge is used by the matching. | ||
341 | * | ||
342 | * The mere existence of such a labelling is enough to prove the | ||
343 | * maximality of the matching, because if there is any larger matching | ||
344 | * then its symmetric difference with this one must include at least | ||
345 | * one 'augmenting path', which starts at a free L-vertex and ends at | ||
346 | * a free R-vertex, traversing only unused L->R edges and only used | ||
347 | * R->L edges. But that would mean it starts at an L0, ends at an R1, | ||
348 | * and never follows an edge that can get from an 0 to a 1. | ||
349 | */ | ||
350 | static void matching_witness(void *scratchv, int nl, int nr, int *witness) | ||
351 | { | 323 | { |
352 | struct scratch *s = (struct scratch *)scratchv; | 324 | struct scratch *s = (struct scratch *)scratchv; |
353 | int i, j; | 325 | int i, j; |
@@ -357,397 +329,3 @@ static void matching_witness(void *scratchv, int nl, int nr, int *witness) | |||
357 | for (j = 0; j < nr; j++) | 329 | for (j = 0; j < nr; j++) |
358 | witness[nl + j] = s->Rlayer[j] == -1; | 330 | witness[nl + j] = s->Rlayer[j] == -1; |
359 | } | 331 | } |
360 | |||
361 | /* | ||
362 | * Standalone tool to run the matching algorithm. | ||
363 | */ | ||
364 | |||
365 | #include <string.h> | ||
366 | #include <ctype.h> | ||
367 | #include <time.h> | ||
368 | |||
369 | #include "tree234.h" | ||
370 | |||
371 | int nl, nr, count; | ||
372 | int **adjlists, *adjsizes; | ||
373 | int *adjdata, *outl, *outr, *witness; | ||
374 | void *scratch; | ||
375 | random_state *rs; | ||
376 | |||
377 | void allocate(int nl_, int nr_, int maxedges) | ||
378 | { | ||
379 | nl = nl_; | ||
380 | nr = nr_; | ||
381 | adjdata = snewn(maxedges, int); | ||
382 | adjlists = snewn(nl, int *); | ||
383 | adjsizes = snewn(nl, int); | ||
384 | outl = snewn(nl, int); | ||
385 | outr = snewn(nr, int); | ||
386 | witness = snewn(nl+nr, int); | ||
387 | scratch = smalloc(matching_scratch_size(nl, nr)); | ||
388 | } | ||
389 | |||
390 | void deallocate(void) | ||
391 | { | ||
392 | sfree(adjlists); | ||
393 | sfree(adjsizes); | ||
394 | sfree(adjdata); | ||
395 | sfree(outl); | ||
396 | sfree(outr); | ||
397 | sfree(witness); | ||
398 | sfree(scratch); | ||
399 | } | ||
400 | |||
401 | void find_and_check_matching(void) | ||
402 | { | ||
403 | int i, j, k; | ||
404 | |||
405 | count = matching_with_scratch(scratch, nl, nr, adjlists, adjsizes, | ||
406 | rs, outl, outr); | ||
407 | matching_witness(scratch, nl, nr, witness); | ||
408 | |||
409 | for (i = j = 0; i < nl; i++) { | ||
410 | if (outl[i] != -1) { | ||
411 | assert(0 <= outl[i] && outl[i] < nr); | ||
412 | assert(outr[outl[i]] == i); | ||
413 | j++; | ||
414 | |||
415 | for (k = 0; k < adjsizes[i]; k++) | ||
416 | if (adjlists[i][k] == outl[i]) | ||
417 | break; | ||
418 | assert(k < adjsizes[i]); | ||
419 | } | ||
420 | } | ||
421 | assert(j == count); | ||
422 | |||
423 | for (i = j = 0; i < nr; i++) { | ||
424 | if (outr[i] != -1) { | ||
425 | assert(0 <= outr[i] && outr[i] < nl); | ||
426 | assert(outl[outr[i]] == i); | ||
427 | j++; | ||
428 | } | ||
429 | } | ||
430 | assert(j == count); | ||
431 | |||
432 | for (i = 0; i < nl; i++) { | ||
433 | if (outl[i] == -1) | ||
434 | assert(witness[i] == 0); | ||
435 | } | ||
436 | for (i = 0; i < nr; i++) { | ||
437 | if (outr[i] == -1) | ||
438 | assert(witness[nl+i] == 1); | ||
439 | } | ||
440 | for (i = 0; i < nl; i++) { | ||
441 | for (j = 0; j < adjsizes[i]; j++) { | ||
442 | k = adjlists[i][j]; | ||
443 | |||
444 | if (outl[i] == k) | ||
445 | assert(!(witness[i] == 1 && witness[nl+k] == 0)); | ||
446 | else | ||
447 | assert(!(witness[i] == 0 && witness[nl+k] == 1)); | ||
448 | } | ||
449 | } | ||
450 | } | ||
451 | |||
452 | struct nodename { | ||
453 | const char *name; | ||
454 | int index; | ||
455 | }; | ||
456 | |||
457 | int compare_nodes(void *av, void *bv) | ||
458 | { | ||
459 | const struct nodename *a = (const struct nodename *)av; | ||
460 | const struct nodename *b = (const struct nodename *)bv; | ||
461 | return strcmp(a->name, b->name); | ||
462 | } | ||
463 | |||
464 | int node_index(tree234 *n2i, tree234 *i2n, const char *name) | ||
465 | { | ||
466 | struct nodename *nn, *nn_prev; | ||
467 | char *namedup = dupstr(name); | ||
468 | |||
469 | nn = snew(struct nodename); | ||
470 | nn->name = namedup; | ||
471 | nn->index = count234(n2i); | ||
472 | |||
473 | nn_prev = add234(n2i, nn); | ||
474 | if (nn_prev != nn) { | ||
475 | sfree(nn); | ||
476 | sfree(namedup); | ||
477 | } else { | ||
478 | addpos234(i2n, nn, nn->index); | ||
479 | } | ||
480 | |||
481 | return nn_prev->index; | ||
482 | } | ||
483 | |||
484 | struct edge { | ||
485 | int L, R; | ||
486 | }; | ||
487 | |||
488 | int compare_edges(void *av, void *bv) | ||
489 | { | ||
490 | const struct edge *a = (const struct edge *)av; | ||
491 | const struct edge *b = (const struct edge *)bv; | ||
492 | if (a->L < b->L) return -1; | ||
493 | if (a->L > b->L) return +1; | ||
494 | if (a->R < b->R) return -1; | ||
495 | if (a->R > b->R) return +1; | ||
496 | return 0; | ||
497 | } | ||
498 | |||
499 | void matching_from_user_input(FILE *fp, const char *filename) | ||
500 | { | ||
501 | tree234 *Ln2i, *Li2n, *Rn2i, *Ri2n, *edges; | ||
502 | char *line = NULL; | ||
503 | struct edge *e; | ||
504 | int i, lineno = 0; | ||
505 | int *adjptr; | ||
506 | |||
507 | Ln2i = newtree234(compare_nodes); | ||
508 | Rn2i = newtree234(compare_nodes); | ||
509 | Li2n = newtree234(NULL); | ||
510 | Ri2n = newtree234(NULL); | ||
511 | edges = newtree234(compare_edges); | ||
512 | |||
513 | while (sfree(line), lineno++, (line = fgetline(fp)) != NULL) { | ||
514 | char *p, *Lname, *Rname; | ||
515 | |||
516 | p = line; | ||
517 | while (*p && isspace((unsigned char)*p)) p++; | ||
518 | if (!*p) | ||
519 | continue; | ||
520 | |||
521 | Lname = p; | ||
522 | while (*p && !isspace((unsigned char)*p)) p++; | ||
523 | if (*p) | ||
524 | *p++ = '\0'; | ||
525 | while (*p && isspace((unsigned char)*p)) p++; | ||
526 | |||
527 | if (!*p) { | ||
528 | fprintf(stderr, "%s:%d: expected 2 words, found 1\n", | ||
529 | filename, lineno); | ||
530 | exit(1); | ||
531 | } | ||
532 | |||
533 | Rname = p; | ||
534 | while (*p && !isspace((unsigned char)*p)) p++; | ||
535 | if (*p) | ||
536 | *p++ = '\0'; | ||
537 | while (*p && isspace((unsigned char)*p)) p++; | ||
538 | |||
539 | if (*p) { | ||
540 | fprintf(stderr, "%s:%d: expected 2 words, found more\n", | ||
541 | filename, lineno); | ||
542 | exit(1); | ||
543 | } | ||
544 | |||
545 | e = snew(struct edge); | ||
546 | e->L = node_index(Ln2i, Li2n, Lname); | ||
547 | e->R = node_index(Rn2i, Ri2n, Rname); | ||
548 | if (add234(edges, e) != e) { | ||
549 | fprintf(stderr, "%s:%d: duplicate edge\n", | ||
550 | filename, lineno); | ||
551 | exit(1); | ||
552 | } | ||
553 | } | ||
554 | |||
555 | allocate(count234(Ln2i), count234(Rn2i), count234(edges)); | ||
556 | |||
557 | adjptr = adjdata; | ||
558 | for (i = 0; i < nl; i++) | ||
559 | adjlists[i] = NULL; | ||
560 | for (i = 0; (e = index234(edges, i)) != NULL; i++) { | ||
561 | if (!adjlists[e->L]) | ||
562 | adjlists[e->L] = adjptr; | ||
563 | *adjptr++ = e->R; | ||
564 | adjsizes[e->L] = adjptr - adjlists[e->L]; | ||
565 | } | ||
566 | |||
567 | find_and_check_matching(); | ||
568 | |||
569 | for (i = 0; i < nl; i++) { | ||
570 | if (outl[i] != -1) { | ||
571 | struct nodename *Lnn = index234(Li2n, i); | ||
572 | struct nodename *Rnn = index234(Ri2n, outl[i]); | ||
573 | printf("%s %s\n", Lnn->name, Rnn->name); | ||
574 | } | ||
575 | } | ||
576 | } | ||
577 | |||
578 | void test_subsets(void) | ||
579 | { | ||
580 | int b = 8; | ||
581 | int n = 1 << b; | ||
582 | int i, j, nruns, expected_size; | ||
583 | int *adjptr; | ||
584 | int *edgecounts; | ||
585 | struct stats { | ||
586 | int min, max; | ||
587 | double n, sx, sxx; | ||
588 | } *stats; | ||
589 | static const char seed[] = "fixed random seed for repeatability"; | ||
590 | |||
591 | /* | ||
592 | * Generate a graph in which every subset of [b] = {1,...,b} | ||
593 | * (represented as a b-bit integer 0 <= i < n) has an edge going | ||
594 | * to every subset obtained by removing exactly one element. | ||
595 | * | ||
596 | * This graph is the disjoint union of the corresponding graph for | ||
597 | * each layer (collection of same-sized subset) of the power set | ||
598 | * of [b]. Each of those graphs has a matching of size equal to | ||
599 | * the smaller of its vertex sets. So we expect the overall size | ||
600 | * of the output matching to be less than n by the size of the | ||
601 | * largest layer, that is, to be n - binomial(n, floor(n/2)). | ||
602 | * | ||
603 | * We run the generation repeatedly, randomising it every time, | ||
604 | * and we expect to see every possible edge appear sooner or | ||
605 | * later. | ||
606 | */ | ||
607 | |||
608 | rs = random_new(seed, strlen(seed)); | ||
609 | |||
610 | allocate(n, n, n*b); | ||
611 | adjptr = adjdata; | ||
612 | expected_size = 0; | ||
613 | for (i = 0; i < n; i++) { | ||
614 | adjlists[i] = adjptr; | ||
615 | for (j = 0; j < b; j++) { | ||
616 | if (i & (1 << j)) | ||
617 | *adjptr++ = i & ~(1 << j); | ||
618 | } | ||
619 | adjsizes[i] = adjptr - adjlists[i]; | ||
620 | if (adjsizes[i] != b/2) | ||
621 | expected_size++; | ||
622 | } | ||
623 | |||
624 | edgecounts = snewn(n*b, int); | ||
625 | for (i = 0; i < n*b; i++) | ||
626 | edgecounts[i] = 0; | ||
627 | |||
628 | stats = snewn(b, struct stats); | ||
629 | |||
630 | nruns = 0; | ||
631 | while (nruns < 10000) { | ||
632 | nruns++; | ||
633 | find_and_check_matching(); | ||
634 | assert(count == expected_size); | ||
635 | |||
636 | for (i = 0; i < n; i++) | ||
637 | for (j = 0; j < b; j++) | ||
638 | if ((i ^ outl[i]) == (1 << j)) | ||
639 | edgecounts[b*i+j]++; | ||
640 | |||
641 | if (nruns % 1000 == 0) { | ||
642 | for (i = 0; i < b; i++) { | ||
643 | struct stats *st = &stats[i]; | ||
644 | st->min = st->max = -1; | ||
645 | st->n = st->sx = st->sxx = 0; | ||
646 | } | ||
647 | |||
648 | for (i = 0; i < n; i++) { | ||
649 | int pop = 0; | ||
650 | for (j = 0; j < b; j++) | ||
651 | if (i & (1 << j)) | ||
652 | pop++; | ||
653 | pop--; | ||
654 | |||
655 | for (j = 0; j < b; j++) { | ||
656 | if (i & (1 << j)) { | ||
657 | struct stats *st = &stats[pop]; | ||
658 | int x = edgecounts[b*i+j]; | ||
659 | if (st->max == -1 || st->max < x) | ||
660 | st->max = x; | ||
661 | if (st->min == -1 || st->min > x) | ||
662 | st->min = x; | ||
663 | st->n++; | ||
664 | st->sx += x; | ||
665 | st->sxx += (double)x*x; | ||
666 | } else { | ||
667 | assert(edgecounts[b*i+j] == 0); | ||
668 | } | ||
669 | } | ||
670 | } | ||
671 | } | ||
672 | } | ||
673 | |||
674 | printf("after %d runs:\n", nruns); | ||
675 | for (j = 0; j < b; j++) { | ||
676 | struct stats *st = &stats[j]; | ||
677 | printf("edges between layers %d,%d:" | ||
678 | " min=%d max=%d mean=%f variance=%f\n", | ||
679 | j, j+1, st->min, st->max, st->sx/st->n, | ||
680 | (st->sxx - st->sx*st->sx/st->n) / st->n); | ||
681 | } | ||
682 | } | ||
683 | |||
684 | int main(int argc, char **argv) | ||
685 | { | ||
686 | static const char stdin_identifier[] = "<standard input>"; | ||
687 | const char *infile = NULL; | ||
688 | bool doing_opts = true; | ||
689 | enum { USER_INPUT, AUTOTEST } mode = USER_INPUT; | ||
690 | |||
691 | while (--argc > 0) { | ||
692 | const char *arg = *++argv; | ||
693 | |||
694 | if (doing_opts && arg[0] == '-' && arg[1]) { | ||
695 | if (!strcmp(arg, "--")) { | ||
696 | doing_opts = false; | ||
697 | } else if (!strcmp(arg, "--random")) { | ||
698 | char buf[64]; | ||
699 | int len = sprintf(buf, "%lu", (unsigned long)time(NULL)); | ||
700 | rs = random_new(buf, len); | ||
701 | } else if (!strcmp(arg, "--autotest")) { | ||
702 | mode = AUTOTEST; | ||
703 | } else { | ||
704 | fprintf(stderr, "matching: unrecognised option '%s'\n", arg); | ||
705 | return 1; | ||
706 | } | ||
707 | } else { | ||
708 | if (!infile) { | ||
709 | infile = (!strcmp(arg, "-") ? stdin_identifier : arg); | ||
710 | } else { | ||
711 | fprintf(stderr, "matching: too many arguments\n"); | ||
712 | return 1; | ||
713 | } | ||
714 | } | ||
715 | } | ||
716 | |||
717 | if (mode == USER_INPUT) { | ||
718 | FILE *fp; | ||
719 | |||
720 | if (!infile) | ||
721 | infile = stdin_identifier; | ||
722 | |||
723 | if (infile != stdin_identifier) { | ||
724 | fp = fopen(infile, "r"); | ||
725 | if (!fp) { | ||
726 | fprintf(stderr, "matching: could not open input file '%s'\n", | ||
727 | infile); | ||
728 | return 1; | ||
729 | } | ||
730 | } else { | ||
731 | fp = stdin; | ||
732 | } | ||
733 | |||
734 | matching_from_user_input(fp, infile); | ||
735 | |||
736 | if (infile != stdin_identifier) | ||
737 | fclose(fp); | ||
738 | } | ||
739 | |||
740 | if (mode == AUTOTEST) { | ||
741 | if (infile) { | ||
742 | fprintf(stderr, "matching: expected no filename argument " | ||
743 | "with --autotest\n"); | ||
744 | return 1; | ||
745 | } | ||
746 | |||
747 | test_subsets(); | ||
748 | } | ||
749 | |||
750 | return 0; | ||
751 | } | ||
752 | |||
753 | #endif /* STANDALONE_MATCHING_TEST */ | ||