CODEWITHSUNDEEP
c#algorithmrecursiongraph-algorithmtraversal
Force444
Force444

Reputation: 3381

Traversing all descendants of an object

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?

Upvotes: 0

Views: 1178

Answers (4)

Kenneth
Kenneth

Reputation: 28737

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);
    }
}

Upvotes: 1

Olivier
Olivier

Reputation: 5688

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

Upvotes: 1

Maarten
Maarten

Reputation: 22945

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);
    }
}

Upvotes: 0

user1935024
user1935024

Reputation:

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

Upvotes: 1

Related Questions