From 07682b793f616607202800f0bf9f573dc3656b29 Mon Sep 17 00:00:00 2001 From: simon Date: Sun, 27 Dec 2009 10:01:11 +0000 Subject: [PATCH] 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. git-svn-id: svn://svn.tartarus.org/sgt/puzzles@8792 cda61777-01e9-0310-a592-d414129be87e --- dsf.c | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) 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; -- 2.11.0