Traversing all descendants of an object

Question

I'm having problems with traversing all descendants of an object.

The 'unit' in the code below is of type Unit in my program. It has a property ChildUnits which returns a List<Unit> of the children of the unit.

I can successfully perform operations on the children. Then I check if those children have children, and if they do I can perform operations on them as well.

However, I need to check all descendants in case there is more depth than just grandchildren. I had a go with while loops in addition to the code below but it got really messy so I left it out.

This is the code I have reverted back to:

foreach (var child in unit.ChildUnits)
{
    //do something here with the child (I know it sounds dodgy).

    bool hasMoreChildren = child.ChildUnits.Count != 0;

    if(hasMoreChildren)
    {
        foreach (var descendant in child.ChildUnits)
        {
            //do something here with the descendant.
        }
    }
}

I could just go another level deep as it's relatively rare for a unit to have more depth than that. But that's not a clean solution.

I think I might need to use a graph traversal algorithm and/or recursion perhaps, but I would like some advice on how to solve this problem most efficiently.

Edit: Is it possible to do this without defining a new function/method?

You can use recursion and do the same with each child you have. — , Aug 14 '14 at 08:58
yes it's possible to do this using stack with loops instead of recursion. — , Aug 14 '14 at 09:13

score 1 · Answer 1 · 2014-08-14T09:16:51.163

Algorithm like this:

def traverse(Unit i):
       for (Unit child : i.childList):
                  // Perform your logic for child
                  traverse(child)

This will perform the same function for each child for the first node , and when applying it for i.child[j] it will perform the same function for all i.child[j].child[k] so it will perform what you want for each node and all its childs.

instead you can use stack :

stack s; 
s.push(firstNode);
while(!stack.empty()):
    t = stack.pop()
    foreach(Unit child : t):
        s.push(child)
        // Perform logic for child

Kenneth · Answer 2 · 2014-08-14T14:52:00.037

1

You can use recursion:

void processChildren(List<Unit> children)
{
    foreach (var child in children)
    {
        //do something here with the child (I know it sounds dodgy).
        processChildren(child.Children); // recursive call here
    }
}

If you don't want to define a new method, you could also roll your own stack:

var stack = new Stack<Unit>();
stack.push(firstUnit);
while( !stack.Any() ) {
    var item = stack.pop();
    //do something here with the item

    foreach(var child in item.Children)
    {
        stack.push(child);
    }
}

edited Aug 14 '14 at 14:52

answered Aug 14 '14 at 09:03

Kenneth

28,294
6
61
84

Stack class doesn't have isEmpty() method. Used the count != 0 instead. – Force444 Aug 14 '14 at 10:54
Thanks, I used `!stack.Any()` – Kenneth Aug 14 '14 at 14:52

score 1 · Accepted Answer · edited May 23 '17 at 12:29

1

Edit: Is it possible to do this without defining a new function/method?

You could use an anonymous method...which is not exactly "not defining a new method", I know :)

However, there's another issue you should take care of: Circular references... even if you dont think there will be any

Here's an implementation, without defining any new method

Action<IEnumerable<Unit>> process = null;
var processed = new HashSet<Unit>();
process = list => {
   foreach(var u in list.Where (processed.Add))
    {
        // do something here with u
        //... and then process children
        process(u.ChildUnits);
    }
};

process(myList); // do the actual processing

edited May 23 '17 at 12:29

Community

1
1

answered Aug 14 '14 at 09:11

Olivier

5,578
2
31
46

Perfect! Thanks. That question you linked to made me laugh! But in all seriousness, I will look into circular references. – Force444 Aug 14 '14 at 09:19
I think hashsets orders elements so it will not keep the same order which it's inserted ? – Aug 14 '14 at 09:22
Is the use of anonymous methods more efficient than using stack like the two other answers propose? – Force444 Aug 14 '14 at 09:22
Using an anonymous method or a stack won't make a noticeable difference and my gut feeling tells me a stack will be a bit faster because it doesn't have to push methods and arguments on the stack (the program stack I mean). This is a hinge though, I have no data to back it up. A recursion though, (either with a method or an anonymous method) could cause a StackOverflowException (if your call hierarchy gets too deep aka too many items). – Kenneth Aug 14 '14 at 09:26
@Kenneth Thank you Kenneth. If I'm almost sure that the depth will very rarely go deeper than max 4 - Should I be concerned with the possibility of a StackOverFlowException ? – Force444 Aug 14 '14 at 09:30
@mohaned no, a hashset is not ordered – Olivier Aug 14 '14 at 09:30
@D.Singh A stackoverflow may occur if your hierarchy is more thousands of levels deep – Olivier Aug 14 '14 at 09:31
And anonymous method is exactly the same as other answers... you dont see it, but the compiler generates methods behind the scene. – Olivier Aug 14 '14 at 09:35

score 0 · Answer 4 · answered Aug 14 '14 at 09:27

Another way to do this without recursion or an action/lambda, is to use a list with items to handle.

Like this.

var toDoList = new List<Unit> { unit };
while (toDoList.Any()) {
    // Get current child, and remove it from the to-do-list
    var currentChild = toDoList.First();
    toDoList.RemoveAt(0);

    // Do something with the current child.
    // ...

    // Now see, if the child has any children to handle
    if (currentChild.ChildUnits != null && currentChild.ChildUnits.Any()) {
        toDoList.AddRange(currentChild.ChildUnits);
    }
}

Traversing all descendants of an object

4 Answers4

Linked