Path: utzoo!attcan!uunet!lll-winken!lll-tis!mordor!sri-spam!sri-unix!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Minimum Spanning Tree with '=='
Keywords: minimum spanning tree, UNION-FIND
Message-ID: <998@cresswell.quintus.UUCP>
Date: 19 May 88 19:10:37 GMT
References: <544@mannix.iros1.UUCP> <962@cresswell.quintus.UUCP> <545@mannix.iros1.UUCP>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 37

In article <545@mannix.iros1.UUCP>, tarau@ouareau.iro.umontreal.ca (Paul Tarau) writes:
> In the article <962@cresswell.quintus.UUCP>, ok@quintus.UUCP 
> (Richard A. O'Keefe) writes:
> > Any Prolog implementors out there using a nontrivial UNION-FIND for
> > managing variable-variable unification?
> 
> The UNION-FIND problem can be solved for variable-variable unification
> (at implementation language level) by making a tree instead of a
> chain of variable references.
> 
> There are two operations:
> - weight balancing (by maintaining the size of the tree)
> - path compression (by making each variable on a path point to the root).
> 
> As explained in R.Sidgewick, Algorithms, Adison-Wesley, 1983, p.402-405
> this is an almost O(E) operation for a structure with E edges.
> 
> At a first look the necessary WAM hacking seems minimal,
> as only the 'unify_variable Yn' instruction is involved.
> 

(1) That's Sedgewick with two "e"s and one "i";
    there is now a second edition of the book;
    Tarjan's papers are, I think, clearer.
    There is also Rem's algorithm, which is very pretty.

(2) The data-structures required for the nearly-linear UNION-FIND are
    non-trivial, and would dramatically increase the space needed for
    variables.

(3) It is not the case that only unify_variable_Yn would be involved.
    To start with, because the data structure would change, every
    dereferencing operation would be affected (and would become slower).
    Further, backtracking would have to undo the UNIONs, so trailing
    and failing would be affected.

(4) We return to the question: are there any Prolog implementors out there
    who have thought it worthwhile to use a non-trivial UNION-FIND?