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.
12 /*void print_dsf(int *dsf, int size)
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;
20 memset(printed_elements, -1, sizeof(int) * size);
25 for (i = 0; i < size; ++i) {
26 if (!memchr(printed_elements, i, sizeof(int) * size))
32 i = dsf_canonify(dsf, i);
34 for (n = 0; n < size; ++n) {
35 if (edsf_canonify(dsf, n, &inverse) == i) {
37 inverse_elements[inverse_count++] = n;
39 equal_elements[equal_count++] = n;
43 for (n = 0; n < equal_count; ++n) {
44 fprintf(stderr, "%d ", equal_elements[n]);
45 printed_elements[printed_count++] = equal_elements[n];
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];
54 fprintf(stderr, "\n");
58 sfree(printed_elements);
59 sfree(equal_elements);
60 sfree(inverse_elements);
63 void dsf_init(int *dsf, int size)
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. */
76 int *snew_dsf(int size)
80 ret = snewn(size, int);
83 /*print_dsf(ret, size); */
88 int dsf_canonify(int *dsf, int index)
90 return edsf_canonify(dsf, index, NULL);
93 void dsf_merge(int *dsf, int v1, int v2)
95 edsf_merge(dsf, v1, v2, FALSE);
98 int dsf_size(int *dsf, int index) {
99 return dsf[dsf_canonify(dsf, index)] >> 2;
102 int edsf_canonify(int *dsf, int index, int *inverse_return)
104 int start_index = index, canonical_index;
107 /* fprintf(stderr, "dsf = %p\n", dsf); */
108 /* fprintf(stderr, "Canonify %2d\n", index); */
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); */
121 canonical_index = index;
124 *inverse_return = inverse;
126 /* Update every member of this 'equivalence class' to point directly at the
127 * canonical member. */
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;
137 assert(inverse == 0);
139 /* fprintf(stderr, "Return %2d\n", index); */
144 void edsf_merge(int *dsf, int v1, int v2, int inverse)
148 /* fprintf(stderr, "dsf = %p\n", dsf); */
149 /* fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */
151 v1 = edsf_canonify(dsf, v1, &i1);
154 v2 = edsf_canonify(dsf, v2, &i2);
158 /* fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */
163 assert(inverse == 0 || inverse == 1);
164 if ((dsf[v2] >> 2) > (dsf[v1] >> 2)) {
169 dsf[v1] += (dsf[v2] >> 2) << 2;
170 dsf[v2] = (v1 << 2) | !!inverse;
173 v2 = edsf_canonify(dsf, v2, &i2);
175 assert(i2 == inverse);
177 /* fprintf(stderr, "dsf[%2d] = %2d\n", v2, dsf[v2]); */