Path: utzoo!attcan!uunet!lll-winken!lll-lcc!ames!oliveb!pyramid!prls!philabs!micomvax!zap!iros1!ouareau!tarau
From: tarau@ouareau.iro.umontreal.ca (Paul Tarau)
Newsgroups: comp.lang.prolog
Subject: Re: Minimum Spanning Tree with '=='
Keywords: minimum spanning tree, UNION-FIND
Message-ID: <545@mannix.iros1.UUCP>
Date: 16 May 88 03:17:31 GMT
References: <544@mannix.iros1.UUCP> <962@cresswell.quintus.UUCP>
Sender: news@iros1.UUCP
Reply-To: tarau@iros1.UUCP (Paul Tarau)
Organization: Universite de Montreal
Lines: 79
Posted: Sun May 15 23:17:31 1988

In the article <962@cresswell.quintus.UUCP>, ok@quintus.UUCP 
(Richard A. O'Keefe) writes:

> In article <544@mannix.iros1.UUCP>, tarau@ouareau.iro.umontreal.ca
> (Paul Tarau) presented a cunning little procedure for computing a
> minimum spanning tree.  There are some problems:
>    -	using integers as vertex labels is a bit of a pain
>    -	functor(Components,'$',NbOfVertices) is used, which is likely
>	to limit NbOfVertices to a small value (maybe ~250, but I've
>	seen otherwise nice Prologs with much lower limits)

An easy way to get rid of 'functor' and its 250 or other arbitrary limit
is to represent vertices by free variables:

% mst(NbOfVertices,Edges,MinSpanTree)
	
mst(1,_,[]):-!.		% No more vertices left
mst(N,[edge(Cost,V1-C1,V2-C2)|Es],T):-
	N>1,
	(	C1==C2->	% Both endpoints are already in the same
		T1=T,		% connected component - skip the edge
		N1 is N 	
	;	C1=C2,		% Put endpoints in the same component
		T=[edge(Cost,V1,V2)|T1],	% Take the edge
		N1 is N-1			% Count a new vertex
	),
	mst(N1,Es,T1).

:- dynamic test/1.	% necessary in Quintus Prolog to 
			% accept an unlimited number of variables
			
test(MinSpanTree):-
  mst(
      % Number of vertices
        5,
      % sorted list of edges (by cost)
        [
	  edge(10,V1,V2),edge(20,V4,V5),edge(30,V1,V4),
	  edge(40,V2,V5),edge(50,V3,V5),edge(60,V2,V3),
	  edge(70,V1,V3),edge(80,V3,V4),edge(90,V1,V5)
	],
	MinSpanTree
      ),
      numbervars(MinSpanTree,0,_). % just for a nice output

>    -	there may be many minimum spanning trees of a graph; it would
>	be nice to have a relation which can confirm that an alleged
>	mst is one.

A simple way to do it is to have a sorting algorithm which
generates alternative orderings by cost. This may be also
useful in related problems, as multiple solutions come from
multiple orderings. The procedure 'mst/3' can be seen as
just filtering this stream of solutions.

> The key hack in his code is the use of variable-variable unification
> as an implementation of the UNION-FIND problem.  For every edge in
> the input, two FINDs are done, and for every edge in the output, one
> UNION is done.
> The snag with this is that it is possible to build up variable chains
> of arbitrary length in Prolog.
> ......
> 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.

Paul Tarau