help with node height in a tree 
Author Message
 help with node height in a tree

I have a tree with a bunch of edges (here are a few):
edge(amy0,betty1).
edge(amy0,barbara2).
edge(betty1,chad5).

and some rules:
leaf(X) :- \+ edge(X,_).
child(X,Y) :- edge(Y,X).

I'm trying to recursively define the height of a node as:
zero if the node is a leaf (has no children, no edge(X,_). )
1 + the max of the heights of all of its children otherwise.

I can get the base case easily:
height(H,X) :- leaf(X), H=0.

But when I try to do the recursive part... how do I handle the multiple
children?  I don't know in advance how many there are.

height(H,X) :- child(Z,X),             /* get all the children of X */
                      maxheight(H1,Z),   /* set H1 to the max height of all
children */
                      H = 1 + H1.

Should that be [Z] to make it be a list?  Or is it automatically a list?  I
notice if I put child(Z,amy0), write(Z). in a program, I only get the first
one.  At the prompt, of course, I can use ; to get the rest of them.

maxheight(H1,[]) :- H1=0.

maxheight(H1,[H|T]) :-
   maxheight(H2,H),
   maxheight(H3,T),
   H1 = max(H2,H3).

Am I even close?  I'm getting so confused.  I'm going to go try to figure
out what information trace. is giving me.

--
Wendy in Chandler, AZ



Tue, 11 May 2004 10:01:14 GMT  
 help with node height in a tree

Quote:

>height(H,X) :- child(Z,X),             /* get all the children of X */
>                      maxheight(H1,Z),   /* set H1 to the max height of all
>children */
>                      H = 1 + H1.

>Should that be [Z] to make it be a list?  Or is it automatically a list?

To get a list of all the children, you'll need to use one of Prolog's
all-solutions predicates: findall/3, setof/3, or bagof/3.

--

The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.



Tue, 11 May 2004 14:26:33 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Help: TREEs, NODEs, and COLLECTIONs

2. Changing an individual nodes height on a BWidget .

3. Height-balanced tree, source code wanted.

4. Binary tree height predicate?

5. Tree nodes and CwWidget

6. ActiveX tree control's wiat event does not abort after nodes are added

7. Building Tree for list of nodes in level order

8. <tree-node> in DUIM

9. NODE tree introspection

10. random node in tree

11. Internal Nodes of an XOR tree

12. Internal nodes of an XOR tree

 

 
Powered by phpBB® Forum Software