Tweak the semantics of dsf_merge() so that the canonical element of

any equivalence class is always the element with the smallest index.
This is slower (the previous behaviour, suggested by Jonas Koelker,
was to choose the new root element to maximise performance), but
still more than acceptably fast and more useful.

[originally from svn r8792]

1 files changed, 15 insertions, 1 deletions

diff --git a/dsf.c b/dsf.c
index 32179a6..f60ddc0 100644
--- 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.
+	 *
+	 * (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;