skumar@cbnewsh.ATT.COM (swaminathan.ravikumar) (02/10/90)
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
brahme@vlsic2.ti.com (Dan Brahme) (02/12/90)
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.
ken@aiai.ed.ac.uk (Ken Johnson) (02/12/90)
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.'
dowding@linc.cis.upenn.edu (John Dowding) (02/13/90)
In article <110154@ti-csl.csc.ti.com> brahme@vlsic2.ti.com (Dan Brahme) writes: >skumar@cbnewsh.ATT.COM (swaminathan.ravikumar) writes: > > >>I have the following facts asserted in the prolog database: . . . >Try representing trees by t(Nodename, Listofchildnodes). >which would give you >t(a,[t(b,[t(d,[]),t(e,[]),t(f,[])]), t(c, [])]) > An alternative to this is the representation used for Restriction Grammars: tree(Node, Child, Sibling) where Child is the left-most child of Node, and Sibling is the sibling to the immediate right of Node (if there is one). tree(a, tree(b, tree(d,_,tree(e,_,tree(f,_,_))), tree(c,_,_)), _) This structure may be a bit non-intuitive, but has certain advantages for some applications, in that it does not build that extra list structure, and it is cheap to dynamically grow the tree on its fringe. See the following for more details: L. Hirschman and K. Puder, "Restriction Grammar: A Prolog Implementation." in Logic Programming and its Applications, ed. D.H.D. Warren and M. VanCaneghem, 1985. John Dowding dowding@linc.cis.upenn.edu