dsf.c

   1 /*
   2  * dsf.c: some functions to handle a disjoint set forest,
   3  * which is a data structure useful in any solver which has to
   4  * worry about avoiding closed loops.
   5  */
   6
   7 #include <assert.h>
   8 #include <string.h>
   9
  10 #include "puzzles.h"
  11
  12 void print_dsf(int *dsf, int size)
  13 {
  14     int *printed_elements = snewn(size, int);
  15     int *equal_elements = snewn(size, int);
  16     int *inverse_elements = snewn(size, int);
  17     int printed_count = 0, equal_count, inverse_count;
  18     int i, n, inverse;
  19
  20     memset(printed_elements, -1, sizeof(int) * size);
  21
  22     while (1) {
  23         equal_count = 0;
  24         inverse_count = 0;
  25         for (i = 0; i < size; ++i) {
  26             if (!memchr(printed_elements, i, sizeof(int) * size))
  27                 break;
  28         }
  29         if (i == size)
  30             goto done;
  31
  32         i = dsf_canonify(dsf, i);
  33
  34         for (n = 0; n < size; ++n) {
  35             if (edsf_canonify(dsf, n, &inverse) == i) {
  36                if (inverse)
  37                    inverse_elements[inverse_count++] = n;
  38                else
  39                    equal_elements[equal_count++] = n;
  40             }
  41         }
  42
  43         for (n = 0; n < equal_count; ++n) {
  44             fprintf(stderr, "%d ", equal_elements[n]);
  45             printed_elements[printed_count++] = equal_elements[n];
  46         }
  47         if (inverse_count) {
  48             fprintf(stderr, "!= ");
  49             for (n = 0; n < inverse_count; ++n) {
  50                 fprintf(stderr, "%d ", inverse_elements[n]);
  51                 printed_elements[printed_count++] = inverse_elements[n];
  52             }
  53         }
  54         fprintf(stderr, "\n");
  55     }
  56 done:
  57
  58     sfree(printed_elements);
  59     sfree(equal_elements);
  60     sfree(inverse_elements);
  61 }
  62
  63 int *snew_dsf(int size)
  64 {
  65     int i;
  66     int *ret;
  67
  68     ret = snewn(size, int);
  69     for (i = 0; i < size; i++) {
  70         /* Bottom bit of each element of this array stores whether that element
  71          * is opposite to its parent, which starts off as false */
  72         ret[i] = i << 1;
  73     }
  74
  75     /*print_dsf(ret, size); */
  76
  77     return ret;
  78 }
  79
  80 int dsf_canonify(int *dsf, int index)
  81 {
  82     return edsf_canonify(dsf, index, NULL);
  83 }
  84
  85 void dsf_merge(int *dsf, int v1, int v2)
  86 {
  87     edsf_merge(dsf, v1, v2, FALSE);
  88 }
  89
  90 int edsf_canonify(int *dsf, int index, int *inverse_return)
  91 {
  92     int start_index = index, canonical_index;
  93     int inverse = 0;
  94
  95 /*    fprintf(stderr, "dsf = %p\n", dsf); */
  96 /*    fprintf(stderr, "Canonify %2d\n", index); */
  97
  98     assert(index >= 0);
  99
 100     /* Find the index of the canonical element of the 'equivalence class' of
 101      * which start_index is a member, and figure out whether start_index is the
 102      * same as or inverse to that. */
 103     while ((dsf[index] >> 1) != index) {
 104         inverse ^= (dsf[index] & 1);
 105         index = dsf[index] >> 1;
 106 /*        fprintf(stderr, "index = %2d, ", index); */
 107 /*        fprintf(stderr, "inverse = %d\n", inverse); */
 108     }
 109     canonical_index = index;
 110
 111     if (inverse_return)
 112         *inverse_return = inverse;
 113
 114     /* Update every member of this 'equivalence class' to point directly at the
 115      * canonical member. */
 116     index = start_index;
 117     while (index != canonical_index) {
 118         int nextindex = dsf[index] >> 1;
 119         int nextinverse = inverse ^ (dsf[index] & 1);
 120         dsf[index] = (canonical_index << 1) | inverse;
 121         inverse = nextinverse;
 122         index = nextindex;
 123     }
 124
 125     assert(inverse == 0);
 126
 127 /*    fprintf(stderr, "Return %2d\n", index); */
 128
 129     return index;
 130 }
 131
 132 void edsf_merge(int *dsf, int v1, int v2, int inverse)
 133 {
 134     int i1, i2;
 135
 136 /*    fprintf(stderr, "dsf = %p\n", dsf); */
 137 /*    fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */
 138
 139     v1 = edsf_canonify(dsf, v1, &i1);
 140     inverse ^= i1;
 141     v2 = edsf_canonify(dsf, v2, &i2);
 142     inverse ^= i2;
 143
 144 /*    fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */
 145
 146     if (v1 == v2)
 147         assert(!inverse);
 148     else
 149         dsf[v2] = (v1 << 1) | !!inverse;
 150
 151     v2 = edsf_canonify(dsf, v2, &i2);
 152     assert(v2 == v1);
 153     assert(i2 == inverse);
 154
 155 /*    fprintf(stderr, "dsf[%2d] = %2d\n", v2, dsf[v2]); */
 156 }