Path: utzoo!utgpu!water!watmath!clyde!bellcore!faline!thumper!ulysses!andante!princeton!udel!rochester!cornell!uw-beaver!teknowledge-vaxc!sri-unix!quintus!ok
From: ok@quintus.UUCP
Newsgroups: comp.lang.prolog
Subject: Re: Minimum Spanning Tree with '=='
Keywords: minimum spanning tree, connected components, logical variable
Message-ID: <962@cresswell.quintus.UUCP>
Date: 13 May 88 01:46:57 GMT
References: <12534@tut.cis.ohio-state.edu> <544@mannix.iros1.UUCP>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 33
Posted: Thu May 12 21:46:57 1988

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)
    -	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.

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.  You have to try rather hard, but you
can do it.  For example, to build a chain of length 5,

	_ = ''(A,B,C,D,E,F),	% A @< B @< ... @< F
	E = F,
	...
	A = B,

This gives us a chain F->E->...->B->A having five links.  Letting V be
the number of vertices in the graph, and E be the number of edges, it
is thus possible for the UNIONs and FINDs to take O(V.(E+V)) time.
This is a pretty unlikely worst case, but this behaviour _has_ been
observed in a benchmark.  There are methods which could be used to
reduce this worst case, but they'd push the constant factor up.  Any
Prolog implementors out there using a nontrivial UNION-FIND for
managing variable-variable unification?