C# Need a Recursive Function for Analyzing % of Total and % of Parent at Branch Level

Question

4.00/5 (2 votes)

See more:

Hi everyone,

I have a hierarchical tree that can have an unspecified number of branches. You add children to parents then parents to their parents and so on. Everything then gets added onto the main branch. Something like this:

MyTree t = new MyTree();
            Branch topBranch = new Branch();
            Branch B1 = new Branch(topBranch);
            Branch B2 = new Branch(topBranch);
            Branch B3 = new Branch(topBranch);
            Branch B4 = new Branch(topBranch);
            Branch B11 = new Branch(B1);
            Branch B21 = new Branch(B2);
            Branch B211 = new Branch(B21);
            Branch B31 = new Branch(B3);
            Branch B41 = new Branch(B4);
            B1.Children.Add(B11);
            B2.Children.Add(B21);
            B21.Children.Add(B211);
            B3.Children.Add(B31);
            B4.Children.Add(B41);
            topBranch.Children.Add(B1);
            topBranch.Children.Add(B2);
            topBranch.Children.Add(B3);
            topBranch.Children.Add(B4);
            t.MainBranch = topBranch;
            return t;

I need to create two functions within MyTree that will assign values to POT and POP attributes of each tree. POT - Percent of Total, POP - Percent of Parent.

I am thinking I probably need to make these functions recursive, however, I have a problem in the function below
CORRECTION HERE:

- when I do

foreach (Branch b in this.Children)

, it starts going down the hierarchy - but then I need it to come back up in order to process the siblings. I need help figuring out that part. So Branch 1.1 has a sub branch 1.1.1, but it also has a sibling - Branch 1.2, which has a sub branch 1.2.1. These methods will only process 1.1 and 1.1.1

C#

private void evaluatePOT(Branch Branch, int runningTotal)
        {
            if (Branch.POT == 0)
            {
                runningTotal += 1;

                foreach (Branch br in Branch.Children)
                {
                    evaluatePOT(br, runningTotal);
                }
                Branch.POT = (double)runningTotal / this.TotalNumberOfBranches * 100;
            }
            else
            //get sibling
            {
                Branch sibling = this.getSibling(Branch);
                if (sibling == null)
                    //if sibling is null then get parent
                    sibling = Branch.Parent;

                evaluatePOT(sibling, runningTotal);
            }
}

C#

private void evaluatePOP(Branch Branch)
        {
            if (Branch != null)
            {
                int totalOtherChildren = 1;

                if (Branch.Parent != null)
                    foreach (Branch B in Branch.Parent.Children)
                        if (B.Guid != Branch.Guid)
                            totalOtherChildren += 1;

                Branch.POP = (double)1 / totalOtherChildren * 100;
                foreach (Branch b in Branch.Children)
                    evaluatePOP(b);
            }
        }

Posted 22-Jun-11 12:06pm

Mesrop Simonian

Updated 23-Jun-11 9:52am

v3

Add a Solution

Comments

Firo Atrum Ventus 22-Jun-11 21:49pm

Can you please explain more about your "POT" and "POP"?
Like, The rules in assigning their values?

Mesrop Simonian 23-Jun-11 15:54pm

% of total equals The current branch + all of its children / total * 100, % of Parent is same with regards to the parent only instead of the big total.

[no name] 23-Jun-11 1:03am

If your data is in SQL Server you can use CTE query to do Recursive calculation.

I suppose the link given below will be helpful to you:
http://msdn.microsoft.com/en-us/library/ms186243.aspx

Mesrop Simonian 23-Jun-11 15:55pm

thanks, but my tree is built inside the code itself, although subsequently it will be in the database... but right now, i need it to work without a backend.

3 solutions

Solution 1

It's pretty simple: the runningTotal is passed to the routine by value, not buy reference. So when you make changes to it, they are not reflected back up the tree.
For example:

void Change (int i)
   {
   Console.WriteLine(i);
   if (i < 3)
      {
      i++;
      Change(i);
      Console.WriteLine("After Change: " + i.ToString());
      }
   }

If you call Change with zero, you will get:

0
1
2
3
After Change: 3
After Change: 2
After Change: 1

Because after each Change returns, the value if i is reset.
Either return the new value of runningTotal when you exit evaluatePOT, or make it a ref parameter

Posted 22-Jun-11 21:27pm

OriginalGriff

Comments

Mesrop Simonian 23-Jun-11 15:46pm

Thanks for the answer, but I completely screwed up the question. Maybe you'll be up for this challenge as well - the problem isn't that children of children are not being processed, they are. The problem is coming back up in the hierarchy and navigating to siblings, so that ALL branches end up getting processed through the method. Because right now it goes down the list as long as children have children, but then it stops, so if the main branch had 2 subbranches, only the children of the first sub branch are visited, then the execution ends. Sorry for the confusion, I myself wasn't sure exactly why the calculations were wrong.

TRK3 23-Jun-11 16:59pm

Do you have a single root node that is the parent of everything, or do you have several nodes at the top that are "siblings" but have no parent.

If the latter is the case, note that evaluatePOT only traverses either the children or the siblings, but not both, so if the initial node that you call it with has both children and siblings, only the children get evaluated.

Mesrop Simonian 23-Jun-11 18:15pm

single root node that is the parent of everything.

TRK3 23-Jun-11 18:24pm

Are you calling evaluatePOT() on the single root node?

Because if you are, it looks to me like the whole tree is being traversed, but you are only getting the results for the single branch (as per OriginalGriff's solution).

However, you are setting branch.POT when you visit that branch -- but you don't know the full total until you've visited all the branches. So you are using an incomplete value of runningTotal when you set POT. You'll need to traverse the whole tree once to get the total before you can set POT in each branch.

Mesrop Simonian 23-Jun-11 18:41pm

I'm calling it in the Tree object's MainRoot property's set method, so it's supposed to scan all the roots contained within MainRoot and assign the POT and POP properties for each root.

Mesrop Simonian 23-Jun-11 18:42pm

MainBranch I meant to say

TRK3 23-Jun-11 18:45pm

See my edited reply above -- you answered my reply while I was fixing mine.

The problem is that you are setting POT using an incomplete value for the total.

Mesrop Simonian 23-Jun-11 18:41pm

Main Branch I meant to say

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

TRK3 · Accepted Answer · 2011-06-23T11:21:00

Solution 2

See my reply in Solution 1 for why root level siblings are not getting traversed.

I think a better way to do this, would be to have a member variable called TotalNumberOfChildren.

When you create a branch, TotalNumberOfChildren is set to zero.

Add a member function:

void IncrementChildren(int number_added) { 
    TotalNumberOfChildren += number_added;
    if (this.parent)
       parent.IncrementChildren(number_added);
}

In the Add(Branch b) function, call IncrementChildren(b.TotalNumberOfChildren + 1) when you add a child.

(If you implement removeChild() you'll have to implement DecrementChildren() similarly.)

Doing it that way, the TotalNumberOfChildren field will be valid at all times.

Then if you need POP, it's just:

float POP() {
   if (this.parent) {
      // POP is total of my children + 1 (self) divided by parent's total.
      return (this.TotalNumberOfChildren + 1) * 100.0 /
                         this.parent.TotalNumberOfChildren;
   } else {
      return 100.0;  // or Inf or whatever makes sense for POP of the root.
   }
}

And of course, POT is just:

(this.TotalOfChildren + 1) * 100.0 / root.TotalOfChildren

Depending on how you want to use POT, child nodes can traverse all the parent pointers to get to root in order to report POT, or the caller who wants to know POT can be required to have access to root and do the calculation himself given TotalOfChildren.

Posted 23-Jun-11 11:21am

TRK3

Updated 23-Jun-11 12:25pm

v3

Comments

Mesrop Simonian 23-Jun-11 18:14pm

This solution unfortunately won't work because root.TotalOfChildren cannot be evaluated without recursive calls. When a branch is added, total number of children is incremented only by 1. However, the added branch may have a number of children of its own (say 10), which should be accounted for in the POT evaluation. In this case, the calculated POT for the main branch that contains the entire tree will be 1 (me) + 1 (my children) over 12 (total number of branches) = 16%, which is incorrect if all 10 children are part of the parent's child. The right solution must come out to 12/12 * 100 = 100%. I really don't think this problem will be solvable without recursive calls to the evaluation methods both for POT as well as POP.

TRK3 23-Jun-11 18:22pm

Really? How silly of me.

See my improved solution above.

Of course it can't be solved without recursion -- it's just a matter of deciding where and when to do the recursion.

My proposed solution does the recursion up the parent link when you add, as opposed to doing the recursion down all the children links when you want to calculate POT and POP. Depending on your usage pattern one or the other method is going to be preferrable.

Mesrop Simonian 23-Jun-11 18:49pm

Bottom up vs top-down doesn't matter I think. The question is the ability to do horizontal navigation as well - we got the up/down we need the left/right, so instead of a depth-first search, it needs to be a breadth-first search, but in that case I don't know how to ensure that every single branch in the structure will be visited.

TRK3 23-Jun-11 18:59pm

I don't see why you need to do breadth-first vs. depth-first. For any given node, don't you just need to know the total of all children below that, and the total of all children?

You can count them either depth first, or breadth-first you'll get the same answer.

Of course if you go bottom-up, there isn't any breadth-first / depth-first decision to make -- there is only one up.

That's an advantage of my proposal, you don't have to loop over all children and/or siblings and recurse down them -- just go up the parent links updating the TotalOfChildren. And if you were worried about stack depth, you could always implement that as a loop over the parent links, and update the TotalOfChildren value directly, so that you aren't actually using recursion at all (but the recursive implementation is clearer).

Mesrop Simonian 23-Jun-11 19:36pm

Absolutely. You may be on to something here, because I think you have a partial solution for POP, but POT is still a different issue. I compared the edited solution to the previous version and I only saw differences in the IncrementChildren section. So this IncrementChildren method, I assume, is on branch level, not tree level. If so, where are POP and POT? Branch level or tree level? POP can be branch level and this solution might work, but POT cannot, because "root" is not known at branch level (out of scope). And if that's the case the solution is not implementable. Do you see why?

TRK3 23-Jun-11 20:07pm

Actually root is known at branch level. Every branch knows it's parent, so you can recurse on parent to get root. In other words:

Branch::Root() {
if (this.parent == NULL)
return this;
else
return this.parent.root();
}

Or walk the parent link a loop if you want to avoid recursion.

So POT becomes:

(this.TotalOfChildren + 1) * 100.0 / this.root().TotalOfChildren

If that's efficient enough for what you are doing, your done. My solution for POP is complete, and with the addition of root(), POT is complete as well.

TRK3 23-Jun-11 20:27pm

If for efficiency reasons you don't want to recurse to find root everytime you want POT, then you have a choice:

a) The caller will have to know about root and supply total as an additional argument to POT (not an unreasonable design decision).

b) When you are done adding to the tree you'll have to traverse the whole tree and set POT when the total of the tree is known.

Mesrop Simonian 24-Jun-11 13:09pm

Now that definitely looks like it would work. I'm going to try it now.

BobJanova · Accepted Answer · 2011-06-24T00:13:00

I think this is easiest in two passes (which has been alluded to in previous answers), a precalculation pass where the totals for each node are recorded (which must traverse the whole tree), and a calculation pass where the branch's value is compared to the parent or root.

class Branch {
 int total;
 List<Branch> children; 
 Branch parent;
 
 Branch Root { 
  get { 
   Branch b = this;
   while(b.parent != null) b = b.parent;
   return b;
  }
 }

 int SetNewTotal() {
  // Precalculation pass. Traverses the tree (similar to recursion)
  int r = 1;
  foreach(Branch cb in children) r += cb.SetNewTotal();
  return total = r;
 }

 float POP { get { return total * 1f / parent.total; } }
 float POT { get { return total * 1f / Root.total; } } 
}

Whenever you modify the tree you should call rootNode.SetNewTotal to repair all the total values.

C# Need a Recursive Function for Analyzing % of Total and % of Parent at Branch Level

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0

Existing Members

...or Join us