How can I dynamically pass a condition and a method to a recursive method

Question

I want to make a method like this,

public dynamic Traverse(dynamic entity, conditions, method)
{
    foreach (var propInfo in GetTraversableProperties(entity))
    {
        if (condition) method(propInfo.GetValue(etc));
        Traverse(propInfo, condition, method);
    }
    return entity;
}

How can I do this? What is the syntax for passing the conditions and method as parameters? Also, does it make more sense to make the conditions a method and check the return value of it?

Answer 1

Your approach, and Gary's answer are both perfectly reasonable ways to reify the abstract notion of recursive traversal of a graph of objects. However, I see four potential issues. Not knowing your precise scenario, perhaps these are non-issues for you, or perhaps you should consider them:

First, suppose the graph you are traversing has extremely long paths. You are implicitly doing a depth first traversal and your method cannot be made tail recursive easily even on architectures that support tail recursion, so you run the risk of running out of call stack.

Second, you presume that the graph is acyclic; if the graph is cyclic then you certainly will run out of stack space.

Third, I don't see why the traversal algorithm returns an entity. Why isn't this method void? Or, if you are using the return as an accumulator to accumulate the value computed by the traversal, then why does the recursive step not do something with the entity returned?

Fourth, you seem to have a bad separation of concerns here. The caller is responsible for determining (1) what the root of the graph is, (2) what to do with each node. But the callee is responsible for (3) figuring out what objects to recurse on. That seems bizarre to me. The caller is providing the starting point; shouldn't the caller also have some say in how to keep on going?

I generally solve this problem as follows:

• Use an explicit stack allocated on the heap rather than using the call stack for control flow
• Track nodes I've visited before and do not re-visit them
• Have the caller determine when an object has traversable children. If the caller wishes the traversal to "bottom out" in the base case then the caller can return an empty set of children.

If I wanted an accumulator I might implement something like this sketch:

static R DepthFirstGraphAccumulate<T, R>(
    T root, 
    Func<T, IEnumerable<T>> children, 
    Func<T, R, R> accumulate)
{
    var accumulator = default(R);
    var visited = new HashSet<T>();
    var stack = new Stack<T>;
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        if (!visited.Contains(current))
        {
            visited.Add(current);
            foreach(var child in children(current))
                stack.Push(child);
            accumulator = accumulate(current, accumulator);
        }
    }
    return accumulator;
}

So, for example, if I had a graph of integers and I wished to sum the nodes reachable from a particular starting node, I'd say:

int total = DepthFirstGraphAccumulate<Node, int>(
    startNode, 
    node=>node.NeighbouringNodes, 
    (node, sum)=>node.Value + sum);

However, I'd be tempted to go even one step further on the "let's separate our concerns" path and say, hey, let's just write an abstract traverser:

static IEnumerable<T> DepthFirstGraphTraversal<T>(
    T root, 
    Func<T, IEnumerable<T>> children)
{
    var visited = new HashSet<T>();
    var stack = new Stack<T>;
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        if (!visited.Contains(current))
        {
            visited.Add(current);
            foreach(var child in children(current))
                stack.Push(child);
            yield return current;
        }
    }
}

and now if I want to do some action to every node in the graph, I just say:

foreach(var node in DepthFirstGraphTraversal<Node>(startNode, n=>n.NeighbouringNodes))
     DoSomething(node);

If I wanted to express the notion of "do something to each node that matches a condition" then I'd write:

var nodes = from node in DepthFirstGraphTraversal<Node>(startNode, n=>n.NeighbouringNodes)
            where condition(node)
            select node;
foreach(var matchingNode in nodes) DoSomething(matchingNode);