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 void dsf_init(int *dsf, int size)
  64 {
  65     int i;
  66
  67     for (i = 0; i < size; i++) dsf[i] = 6;
  68     /* Bottom bit of each element of this array stores whether that
  69      * element is opposite to its parent, which starts off as
  70      * false. Second bit of each element stores whether that element
  71      * is the root of its tree or not.  If it's not the root, the
  72      * remaining 30 bits are the parent, otherwise the remaining 30
  73      * bits are the number of elements in the tree.  */
  74 }
  75
  76 int *snew_dsf(int size)
  77 {
  78     int *ret;
  79
  80     ret = snewn(size, int);
  81     dsf_init(ret, size);
  82
  83     /*print_dsf(ret, size); */
  84
  85     return ret;
  86 }
  87
  88 int dsf_canonify(int *dsf, int index)
  89 {
  90     return edsf_canonify(dsf, index, NULL);
  91 }
  92
  93 void dsf_merge(int *dsf, int v1, int v2)
  94 {
  95     edsf_merge(dsf, v1, v2, FALSE);
  96 }
  97
  98 int dsf_size(int *dsf, int index) {
  99     return dsf[dsf_canonify(dsf, index)] >> 2;
 100 }
 101
 102 int edsf_canonify(int *dsf, int index, int *inverse_return)
 103 {
 104     int start_index = index, canonical_index;
 105     int inverse = 0;
 106
 107 /*    fprintf(stderr, "dsf = %p\n", dsf); */
 108 /*    fprintf(stderr, "Canonify %2d\n", index); */
 109
 110     assert(index >= 0);
 111
 112     /* Find the index of the canonical element of the 'equivalence class' of
 113      * which start_index is a member, and figure out whether start_index is the
 114      * same as or inverse to that. */
 115     while ((dsf[index] & 2) == 0) {
 116         inverse ^= (dsf[index] & 1);
 117         index = dsf[index] >> 2;
 118 /*        fprintf(stderr, "index = %2d, ", index); */
 119 /*        fprintf(stderr, "inverse = %d\n", inverse); */
 120     }
 121     canonical_index = index;
 122
 123     if (inverse_return)
 124         *inverse_return = inverse;
 125
 126     /* Update every member of this 'equivalence class' to point directly at the
 127      * canonical member. */
 128     index = start_index;
 129     while (index != canonical_index) {
 130         int nextindex = dsf[index] >> 2;
 131         int nextinverse = inverse ^ (dsf[index] & 1);
 132         dsf[index] = (canonical_index << 2) | inverse;
 133         inverse = nextinverse;
 134         index = nextindex;
 135     }
 136
 137     assert(inverse == 0);
 138
 139 /*    fprintf(stderr, "Return %2d\n", index); */
 140
 141     return index;
 142 }
 143
 144 void edsf_merge(int *dsf, int v1, int v2, int inverse)
 145 {
 146     int i1, i2;
 147
 148 /*    fprintf(stderr, "dsf = %p\n", dsf); */
 149 /*    fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */
 150
 151     v1 = edsf_canonify(dsf, v1, &i1);
 152     assert(dsf[v1] & 2);
 153     inverse ^= i1;
 154     v2 = edsf_canonify(dsf, v2, &i2);
 155     assert(dsf[v2] & 2);
 156     inverse ^= i2;
 157
 158 /*    fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */
 159
 160     if (v1 == v2)
 161         assert(!inverse);
 162     else {
 163         assert(inverse == 0 || inverse == 1);
 164         /*
 165          * We always make the smaller of v1 and v2 the new canonical
 166          * element. This ensures that the canonical element of any
 167          * class in this structure is always the first element in
 168          * it. 'Keen' depends critically on this property.
 169          *
 170          * (Jonas Koelker previously had this code choosing which
 171          * way round to connect the trees by examining the sizes of
 172          * the classes being merged, so that the root of the
 173          * larger-sized class became the new root. This gives better
 174          * asymptotic performance, but I've changed it to do it this
 175          * way because I like having a deterministic canonical
 176          * element.)
 177          */
 178         if (v1 > v2) {
 179             int v3 = v1;
 180             v1 = v2;
 181             v2 = v3;
 182         }
 183         dsf[v1] += (dsf[v2] >> 2) << 2;
 184         dsf[v2] = (v1 << 2) | !!inverse;
 185     }
 186
 187     v2 = edsf_canonify(dsf, v2, &i2);
 188     assert(v2 == v1);
 189     assert(i2 == inverse);
 190
 191 /*    fprintf(stderr, "dsf[%2d] = %2d\n", v2, dsf[v2]); */
 192 }