Subject: Re: How to construct a tree from a given structure and elements

From: [email-masked] (Uwe Lesta)
Date: Sat, 09 Dec 2000 20:17:22 +0100

First of all I like to thanks Richard A. O'Keefe for his help.
I esteem his direct and clear remarks.

Also i like to excuse me for my incomplete question which
generates misunderstanding.

So let me try a second time to describe the problem.

The header of this thread leads to the goal

    % construct a tree from a given structure and elements
    construct_tree(+tree_structure, +tree_elements, -tree).

which might be called from

	build_tree(T):-
		build_tree_structure_from_tree_struct(TS),
		build_tree_elements_from_material(E),
		construct_tree(TS, E, T).

where tree_structure describes a schema what a valid tree is and
tree_elements is a bag of elements which must be in the result tree.

the definition of the tree structure is given in the facts of 

         % tree_struct(child_name, parent_name, max_posible_childs).
         tree_struct(node1, root, 2).
         tree_struct(node2a, node1, 5).
         tree_struct(node2b, node1, 8).
         tree_struct(node3a, node2a, 2).
         tree_struct(node3b, node2a, 1).
         tree_struct(node3a, node2b, 2).
         tree_struct(node3c, node2b, 10).
         % ...

     root
     |
     +--node1
        |
        +--node2a
        |  |
        |  +--node3a
        |  |
        |  +--node3b
        |
        +--node2b
           |
           +--node3a
           |
           |--node3c
 
> (it is not a tree, because node3a appears twice in it),

I can't agree, but please correct me if the definition of tree says
that all nodes must have different names and tell me whats the right
name for this kind of graph.

Independent of this point I see that i miss some information here how to
build a tree.

Let's see what i have / not have on the second parameter tree_elements

% material(node_name, amount_of_nodes).
material(node3a, 7).
material(node3c, 30).
material(node2b, 6).

 1) I have 6 nodes of the type 'node2b' each of it can have 10 childs of
node3c 
    or 2 childs of node3a. So if i fit it together one node3a is left.

 2) I have to create a node 'node2a' to put one 'node3a' into the tree

 3) I have to create a node1 and a root node

	that results in the following output:

     root
     |
     +--node1
        |
        +--node2a
        |  |
        |  +--node3a
        |
        +--node2b
        |  |
        |  +--node3c
        |  +--node3c
        |  +-- % up to 10 node3c
        |
        +--node2b
        |  |
        |  +--node3c
        |  +--node3c
        |  +-- % up to 10 node3c
        |
        +--node2b
        |  |
        |  +--node3c
        |  +--node3c
        |  +-- % up to 10 node3c
        |
        +--node2b
        |  |
        |  +--node3a
        |  +--node3a
        |
        +--node2b
        |  |
        |  +--node3a
        |  +--node3a
        |
        +--node2b
           |
           +--node3a
           +--node3a

Lets see what shall happens if i add the node properties and
interpret it as constraints.

% node_points(node_name, green_points(max_allowed, amount),
red_points(max_allowed, amount)).
node_points(node1,  green_points(50, 0), red_points(30,0)).
node_points(node2a, green_points(20, 1), red_points(10,2)).
node_points(node2b, green_points(20, 2), red_points(10,5)).
node_points(node3a, green_points(8, 4),  red_points(2,1)).
node_points(node3b, green_points(8, 8),  red_points(2,1)).
node_points(node3c, green_points(8, 1),  red_points(2,0)).

the summary of green_points for node1 is greater than 50 so i
must add a second node1. 
(I add the condition for the summary of green and red points in
brackets)

     root
     |
     +--node1(41 =< 50, 18 =< 30)
     |  |
     |  +--node2a(4+1 =< 20, 1+2 =< 10)
     |  |  |
     |  |  +--node3a(4,1)
     |  |
     |  +--node2b(10+2 =< 20, 0+5 =< 10)
     |  |  |
     |  |  +--node3c(1,0)
     |  |  +--node3c(1,0)
     |  |  +-- % up to 10 node3c
     |  |
     |  +--node2b(10+2 =< 20, 0+5 =< 10)
     |  |  |
     |  |  +--node3c(1,0)
     |  |  +--node3c(1,0)
     |  |  +-- % up to 10 node3c
     |  |
     |  +--node2b(10+2 =< 20, 0+5 =< 10)
     |     |
     |     +--node3c(1,0)
     |     +--node3c(1,0)
     |     +-- % up to 10 node3c
     |    
     +--node1(30 =< 50, 21 =< 30)
        |
        +--node2b(8+2 =< 20, 2+5 =< 10)
        |  |
        |  +--node3a(4,1)
        |  +--node3a(4,1)
        |
        +--node2b(8+2 =< 20, 2+5 =< 10)
        |  |
        |  +--node3a(4,1)
        |  +--node3a(4,1)
        |
        +--node2b(8+2 =< 20, 2+5 =< 10)
           |
           +--node3a(4,1)
           +--node3a(4,1)

Finaly I like to build a weight balanced tree considering
these constraints.

node_weight(_, 1).
/*
% node_weight might be changed to 
node_weight(N, NW):-
	node_points(N, green_points(_, GP), red_points(_,RP)),
	NW is GP + RP.
*/

I hope the problem is much clearer now.

I wish you a nice weekend and looking for your advises.

-- 

Regards

Uwe
[email-masked]