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 int *snew_dsf(int size
)
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 */
75 /*print_dsf(ret, size); */
80 int dsf_canonify(int *dsf
, int index
)
82 return edsf_canonify(dsf
, index
, NULL
);
85 void dsf_merge(int *dsf
, int v1
, int v2
)
87 edsf_merge(dsf
, v1
, v2
, FALSE
);
90 int edsf_canonify(int *dsf
, int index
, int *inverse_return
)
92 int start_index
= index
, canonical_index
;
95 /* fprintf(stderr, "dsf = %p\n", dsf); */
96 /* fprintf(stderr, "Canonify %2d\n", index); */
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); */
109 canonical_index
= index
;
112 *inverse_return
= inverse
;
114 /* Update every member of this 'equivalence class' to point directly at the
115 * canonical member. */
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
;
125 assert(inverse
== 0);
127 /* fprintf(stderr, "Return %2d\n", index); */
132 void edsf_merge(int *dsf
, int v1
, int v2
, int inverse
)
136 /* fprintf(stderr, "dsf = %p\n", dsf); */
137 /* fprintf(stderr, "Merge [%2d,%2d], %d\n", v1, v2, inverse); */
139 v1
= edsf_canonify(dsf
, v1
, &i1
);
141 v2
= edsf_canonify(dsf
, v2
, &i2
);
144 /* fprintf(stderr, "Doing [%2d,%2d], %d\n", v1, v2, inverse); */
149 dsf
[v2
] = (v1
<< 1) | !!inverse
;
151 v2
= edsf_canonify(dsf
, v2
, &i2
);
153 assert(i2
== inverse
);
155 /* fprintf(stderr, "dsf[%2d] = %2d\n", v2, dsf[v2]); */