Your approach and Gary's answer are perfectly reasonable ways to validate the abstract concept of recursive traversal of the object graph. However, I see four potential questions. Not knowing your exact scenario, perhaps this is not a problem for you, or perhaps you should consider them:
First, suppose the graph you covered has extremely long paths. You implicitly take the first step in depth, and your method cannot be an easy recursive handhair even on architectures that support tail recursion, so you run the risk of escaping from the call stack.
Secondly, you assume that the graph is acyclic; if the graph is cyclical, then of course you end the stack space.
Thirdly, I do not understand why the traversal algorithm returns an object. Why is this method not valid? Or, if you use return as an accumulator to accumulate the value calculated by traversing, then why does the recursive step not do something with the returned object?
Fourth, you seem to have a poor separation of concerns. The caller is responsible for determining (1) what is the root of the graph, (2) what to do with each node. But the caller is responsible for (3) figuring out which objects need to be recursed. This seems strange to me. The caller provides a starting point; should the caller also talk about how to proceed?
I usually solve this problem as follows:
- Use explicit stack allocated on heap instead of using call stack for control flow
- Track sites I visited before and do not re-visit them
- Identify the caller when the object has children passing through it. If the caller wishes to bypass the lower case in the base register, the caller can return an empty set of children.
If I needed a battery, I could 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 would like to summarize the nodes reachable from a specific starting node, I would say:
int total = DepthFirstGraphAccumulate<Node, int>( startNode, node=>node.NeighbouringNodes, (node, sum)=>node.Value + sum);
However, I will be tempted to go one step further along the path “separate our concerns” and say: “Hey, just write an abstract traverse:
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 for each 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 concept of "do something for every node that matches the condition," then I would write:
var nodes = from node in DepthFirstGraphTraversal<Node>(startNode, n=>n.NeighbouringNodes) where condition(node) select node; foreach(var matchingNode in nodes) DoSomething(matchingNode);