Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C# XML Recursive Trees
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
 
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);
            }
}
 
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 13:06pm
Edited 23-Jun-11 10:52am
v3
Comments
Firo Atrum Ventus at 22-Jun-11 21:49pm
   
Can you please explain more about your "POT" and "POP"?
Like, The rules in assigning their values?
Mesrop Simonian at 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.
2irfanshaikh at 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 at 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.
Rate this: bad
good
Please Sign up or sign in to vote.

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
  Permalink  
Comments
Mesrop Simonian at 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 at 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 at 23-Jun-11 18:15pm
   
single root node that is the parent of everything.
TRK3 at 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 at 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 at 23-Jun-11 18:42pm
   
MainBranch I meant to say
TRK3 at 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 at 23-Jun-11 18:41pm
   
Main Branch I meant to say
Rate this: bad
good
Please Sign up or sign in to vote.

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.
  Permalink  
v3
Comments
Mesrop Simonian at 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 at 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 at 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 at 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 at 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 at 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 at 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 at 24-Jun-11 13:09pm
   
Now that definitely looks like it would work. I'm going to try it now.
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 3

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.
  Permalink  
v3
Comments
Mesrop Simonian at 24-Jun-11 13:08pm
   
the SetNewTotal method always returns 0s... also, isn't total at some point supposed to be assigned the value of r?
BobJanova at 24-Jun-11 17:17pm
   
Whoops, you are correct. That's what I get for writing in a hurry at work ;). Will update the solution.

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

  Print Answers RSS
0 Maciej Los 310
1 OriginalGriff 295
2 Afzaal Ahmad Zeeshan 224
3 Sergey Alexandrovich Kryukov 195
4 BillWoodruff 160
0 OriginalGriff 6,499
1 Sergey Alexandrovich Kryukov 6,048
2 DamithSL 5,193
3 Manas Bhardwaj 4,657
4 Maciej Los 4,120


Advertise | Privacy | Mobile
Web03 | 2.8.1411022.1 | Last Updated 24 Jun 2011
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100