Percentages and trees

Question

Hi, I have an unordered tree. Each node represents a task that can be done (1), not done (0) or have children tasks.

For example:

1
-1.1
-1.2
--1.2.1
--1.2.2
-1.3
2
3
-3.1
4
-4.1
--4.1.1
5

Suppose that the leaves 1.2.1, 3.1 and 5 are done

1
-1.1
-1.2
--1.2.1*
--1.2.2
-1.3
2
3
-3.1*
4
-4.1
--4.1.1
5*

I want to calculate the percentage of completeness of each node. The leaves are easily calculated with 0% or 100%, but how to compute all the others?

At the moment, I walk the tree from the leaves on and each node is calculated based on the percentage of completeness of the children. For example:

1      50%
-1.1*  100%
-1.2   0%
2      0%
3      33%
-3.1*  100%
-3.2   0%
-3.3   0%

Now, more children are added to 1.2 (that is no more a leaf but becomes a node). If the children are "not done", 1.2 is always 0% and so 1 is 50%, but I would like 1 to be less then 50%, as, descending into his children and grand-children the number of tasks to be completed in order for it to the done 100% is greater!

1       50%
-1.1*   100%
-1.2    0%
--1.2.1 0%
--1.2.2 0%
2       0%
3       33%
-3.1*   100%
-3.2    0%
-3.3    0%

What is the best way to calculate this? Thanks

Answer 1

you could try with a post order visit (pseudocode):

postorder(node) {

    foreach(child : children) {
        postorder(child)
        node.visited++

        if (child.completed == 1) {
           node.completed++        
        }
    }

    print("%d%%", (node.completed / node.visited) * 100)
}

Answer 2

You can define the %done as total (sub)nodes done divided by total (sub) nodes. Counting only the leaves.

In this case:

       1  (1/2 = 50%)
      / \
   1.1*  1.2

Adding the extra nodes:

       1  (1/3 = 33%)
      / \
   1.1*  1.2 (0/2 = 0%)
         / \
    1.2.1   1.2.2

If that is not enough, you can add a weight to each task and calculate the completed weight divided by the total weight.

Answer 3

For any node, % done = # of descendant leaves done / total # of descendant leaves

Where:

number of descendant leaves = sum(childrens' # of descendant leaves)

Answer 4

This depends on the weight you want to give to each level. If I were you I would choose the first method that you mentioned (i.e. put the same weight on items on the same level) so 1 with 50% would look right to me and the difference of having more nodes would be seen by a slower increase of 'done' percentage for 1.2 node.

To get a node to affect more distant ancestors you could calculate the ancestor percentage as an average of all the leafs in its subtree (that would give 33% completion for task 1), but this doesn't seem quite right to me. It all depends on how you really want to represent the data - I don't think there's a 'right' way of doing it.

Answer 5

I think the percentage of each node is the average value of it's children (not sub-children) percentages.

For example

 1_per = (1.1_per + 1.2_per) / 2
 3_per = (3.1_per + 3.2_per + 3.3_per) / 3