Path: utzoo!attcan!uunet!mcsun!ukc!edcastle!aiai!ken
From: ken@aiai.ed.ac.uk (Ken Johnson)
Newsgroups: comp.lang.prolog
Subject: Re: prolog tree building question
Keywords: m-way trees
Message-ID: <1731@skye.ed.ac.uk>
Date: 12 Feb 90 11:09:59 GMT
Reply-To: ken@aiai.UUCP (Ken Johnson)
Followup-To: comp.lang.prolog
Organization: AIAI, University of Edinburgh, Scotland
Lines: 44

In article <8052@cbnewsh.ATT.COM> skumar@cbnewsh.ATT.COM (swaminathan.ravikumar) writes:

>I have the following facts asserted in the prolog database:
>
>	linked(a, b).
>	linked(a, c).
>	linked(b, d).
>	linked(b, e).
>	linked(b, f).
>
>and I want to construct an "m-way" tree strcuture as follows:

tree(Start,t(Start,Tree)) :-
	setof(Endpoint,linked(Start,Endpoint),Set),
	expand_set(Set,[],Tree).

tree(Leaf,[Leaf]) :-
	\+ linked(Leaf,_).

expand_set([],So_far,So_far).

expand_set([H|T],So_far,Tree) :-
	tree(H,Subtree),
	expand_set(T,[Subtree|So_far],Tree).

% ------------------------

The invocation
  tree(a,T)
gives
  T = t(a,[[c],t(b,[[f],[e],[d]])]).

(that is: t/2 has as its arg1 a node and as its arg2 a list of the trees
which succeed that node.)

Note this is not necessarily a better representation of the tree than
the original series of linked/2 clauses, which is a perfectly good
representation in the Prolog idiom. 

-- 
Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN
E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 212
`I have read your article, Mr Johnson, and I am no wiser now than when I
started'.  -- `Possibly not, sir, but far better informed.'