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++) {
  68         /* Bottom bit of each element of this array stores whether that element
  69          * is opposite to its parent, which starts off as false */
  70         dsf[i] = i << 1;
  71     }
  72 }
  73
  74 int *snew_dsf(int size)
  75 {
  76     int *ret;
  77
  78     ret = snewn(size, int);
  79     dsf_init(ret, size);
  80
  81     /*print_dsf(ret, size); */
  82
  83     return ret;
  84 }
  85
  86 int dsf_canonify(int *dsf, int index)
  87 {
  88     return edsf_canonify(dsf, index, NULL);
  89 }
  90
  91 void dsf_merge(int *dsf, int v1, int v2)
  92 {
  93     edsf_merge(dsf, v1, v2, FALSE);
  94 }
  95
  96 int edsf_canonify(int *dsf, int index, int *inverse_return)
  97 {
  98     int start_index = index, canonical_index;
  99     int inverse = 0;
 100
 101 /*    fprintf(stderr, "dsf = %p\n", dsf); */
 102 /*    fprintf(stderr, "Canonify %2d\n", index); */
 103
 104     assert(index >= 0);
 105
 106     /* Find the index of the canonical element of the 'equivalence class' of
 107      * which start_index is a member, and figure out whether start_index is the
 108      * same as or inverse to that. */
 109     while ((dsf[index] >> 1) != index) {
 110         inverse ^= (dsf[index] & 1);
 111         index = dsf[index] >> 1;
 112 /*        fprintf(stderr, "index = %2d, ", index); */
 113 /*        fprintf(stderr, "inverse = %d\n", inverse); */
 114     }
 115     canonical_index = index;
 116
 117     if (inverse_return)
 118         *inverse_return = inverse;
 119
 120     /* Update every member of this 'equivalence class' to point directly at the
 121      * canonical member. */
 122     index = start_index;
 123     while (index != canonical_index) {
 124         int nextindex = dsf[index] >> 1;
 125         int nextinverse = inverse ^ (dsf[index] & 1);
 126         dsf[index] = (canonical_index << 1) | inverse;
 127         inverse = nextinverse;
 128         index = nextindex;
 129     }
 130
 131     assert(inverse == 0);
 132
 133 /*    fprintf(stderr, "Return %2d\n", index); */
 134
 135     return index;
 136 }
 137
 138 void edsf_merge(int *dsf, int v1, int v2, int inverse)
 139 {
 140     int i1, i2;
 141
 142 /*    fprintf(stderr, "dsf = %p\n", dsf); */
 143 /*    fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */
 144
 145     v1 = edsf_canonify(dsf, v1, &i1);
 146     inverse ^= i1;
 147     v2 = edsf_canonify(dsf, v2, &i2);
 148     inverse ^= i2;
 149
 150 /*    fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */
 151
 152     if (v1 == v2)
 153         assert(!inverse);
 154     else
 155         dsf[v2] = (v1 << 1) | !!inverse;
 156
 157     v2 = edsf_canonify(dsf, v2, &i2);
 158     assert(v2 == v1);
 159     assert(i2 == inverse);
 160
 161 /*    fprintf(stderr, "dsf[%2d] = %2d\n", v2, dsf[v2]); */
 162 }