Stop the analysis pass in Loopy's redraw routine from being

[sgt/puzzles] / dsf.c

diff --git a/dsf.c b/dsf.c
index 32179a6..aa22392 100644 (file)
--- a/dsf.c
+++ b/dsf.c
@@ -161,7 +161,21 @@ void edsf_merge(int *dsf, int v1, int v2, int inverse)
         assert(!inverse);
     else {
        assert(inverse == 0 || inverse == 1);
-       if ((dsf[v2] >> 2) > (dsf[v1] >> 2)) {
+       /*
+        * We always make the smaller of v1 and v2 the new canonical
+        * element. This ensures that the canonical element of any
+        * class in this structure is always the first element in
+        * it. 'Keen' depends critically on this property.
+        *
+        * (Jonas Koelker previously had this code choosing which
+        * way round to connect the trees by examining the sizes of
+        * the classes being merged, so that the root of the
+        * larger-sized class became the new root. This gives better
+        * asymptotic performance, but I've changed it to do it this
+        * way because I like having a deterministic canonical
+        * element.)
+        */
+       if (v1 > v2) {
            int v3 = v1;
            v1 = v2;
            v2 = v3;