prolog tree building question 
Author Message
 prolog tree building question

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



Wed, 29 Jul 1992 00:37:07 GMT  
 prolog tree building question

Quote:

>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


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.



Fri, 31 Jul 1992 07:39:13 GMT  
 prolog tree building question

Quote:


>>I have the following facts asserted in the prolog database:

.
.
.

Quote:
>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



Sat, 01 Aug 1992 08:12:18 GMT  
 prolog tree building question

Quote:

>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

`I have read your article, Mr Johnson, and I am no wiser now than when I
started'.  -- `Possibly not, sir, but far better informed.'



Fri, 31 Jul 1992 19:09:59 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Questions: Bushy trees in Prolog and C functions from/to Prolog

2. Need to build a tree buttom-up (parse tree)

3. Building a tree using APL...

4. Passing arguments to function: Building tree in APL

5. C4: building a relation tree?

6. Building Tree for list of nodes in level order

7. Build a tree solver...

8. ruby-htmltools, a tree-building HTML parser version 1.01

9. ruby-htmltools, a tree-building HTML parser

10. Building and traversing binary trees

11. Building a Binary Tree in Fortran 77

12. Building Modules outside of Python Source Tree

 

 
Powered by phpBB® Forum Software