Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!wuarchive!decwrl!sun-barr!newstop!texsun!smunews!ti-csl!vlsic2!brahme
From: brahme@vlsic2.ti.com (Dan Brahme)
Newsgroups: comp.lang.prolog
Subject: Re: prolog tree building question
Keywords: m-way trees
Message-ID: <110154@ti-csl.csc.ti.com>
Date: 11 Feb 90 23:39:13 GMT
References: <8052@cbnewsh.ATT.COM>
Sender: news@ti-csl.csc.ti.com
Organization: Texas Instruments Inc, SPDC Operations, Dallas, TX
Lines: 108

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:

>		a
>		|
>	     -------
>	     |     |
>	     b     c
>	     |
>           -----	   
>	   | | |
>	   d e f

>I would appreciate any suggestions or pointers to reference
>materials on doing this.

>Thanks.

>-- ravi
>skumar@hocus.att.com

Try representing trees by t(Nodename, Listofchildnodes).
which would give you 
t(a,[t(b,[t(d,[]),t(e,[]),t(f,[])]), t(c, [])])

However if your database is a set of links then you have to write a
program to get this tree. 
------------------------

One way to write this is:

tree(T) :- 
   grow_downtree(_A, T0),
   grow_uptree(T0, T).

grow_downtree(A, t(A, Ts)) :- 
   down_links(A, Bs),
   grow_downtrees(Bs, Ts).
   
down_links(A, Bs) :- bagof(B, (functor(L, l, 2), arg(1, L, A), arg(2, L, B),
                               call(L)), Bs).

grow_downtrees([], []).
grow_downtrees([A1|A2], [T1|T2]) :-
   grow_downtree(A1, T1),
   grow_downtrees(A2, T2).

grow_uptree(t(A, T), Tree) :- 
   l(B, A) -->
   (down_links(B, A, As),
    grow_downtrees(As, Ts),
    grow_uptree(t(B, [t(A, T)|Ts])))
  ; Tree = t(A, T).

down_links(A, B, Bs) :- 
    bagof( B1, (functor(L, l, 2), arg(1, L, A), arg(2, L, B1),
                call(L), B1 <> B), Bs).


-------------------------------------------------------------


If you write this program in the Lisp or C style
the prolog version may turn out to be much
slower than the lisp or C version. By lisp or C style I mean something
like what we have below:

tree(T) :- get_links(Ls), transform(Ls, T).

get_links(Links) :- bagof(Link, (functor(Link, l, 2), call(Link)), Links).

transform([Link_orSubtree|Forest], Tree) :- 
   insert(Link_or_Subtree, Forest, NewForest),
     NewForest = [Tree] --> true
   ; transform(NewForest, Tree).
transform([], _Tree).

insert(l(A, B), [l(A0, A)|FR], [t(A0, [t(A, t(B, []))])|FR]).
insert(l(A, B), [l(B, B0)|FR], [t(A, [t(B, t(B0, []))])|FR]).
insert(t(A, T), [Tree|FR], [NewTree|FR]) :- merge(t(A, T), Tree, NewTree).
insert(Link_or_Subtree, [F1|FR], [F1|NewFR]) :- 
    insert(Link_or_Subtree, FR, NewFR).
insert(_L, [], []).
    
I have omitted merge(T1, T2, T) which basically merges
T1 and T2 if possible (that is they share a
node) otherwise it fails. 

---------------------------------------------------

Dan brahme

PS: One of the differences in the prolog versus Lisp/C like versions
is that former uses backtracking extensively whereas the latter has
no backtracking. In fact you could transform most of the clauses to lisp conds.
Also I have'nt compiled this code (thus there may be errors in the
use of bagof (i.e., free variables, use of quantifier) 
so check a manual before using it.