Traversal algorithms using generics, generic constraints (where), and Action delegates
Posted by Roy Triesscheijn on February 10th, 2011
As many of you I enjoy solving a very complex problem, however sometimes it’s finding new ways todo simple things that really excites me! This happened again today, I was working on a simple Depth-First-Search traversal algorithm when it suddenly doomed to me that I was duplicating a lot of code because I had to do DFS multiple times, with the only difference the action to take at each node.
Pondering about this for a few minutes and I thought about using a delegate as a sort of method pointer to tell the DFS algorithm what action to take for each node. I wrote a quick delegate and named it Action, but then I remembered that C# has the built in Action
With these techniques in mind I quickly wrote the following code:
public void DFS<T>(T node, Action<T> action) where T : IHasChildren<T>
{
Stack<T> stack = new Stack<T>();
action(node);
stack.PushMany<T>(node.Children);
while (stack.Count > 0)
{
T n = stack.Pop();
action(n);
stack.PushMany<T>(n.Children);
}
}
public interface IHasChildren<T>
{
List<T> Children;
}
This way you can use DFS on any type of node as long as it implements IHasChildren, and you can use any Action
Edit:
Stack.PushMany is my own extension method that allows a list to be put on a stack (just a simple for each).
February 11th, 2011 at 6:14 AM
1. You have a tiny amount of duplicate code here as well, you can just to stack.Push(node) before the loop
2. There is a pattern like IHasChildren already, it’s called IEnumerable; the code would be even more generic if you replaced List with IEnumerable or (perhaps even better) provided an additional Func for getting the list of nodes from node. That way you’ll be able to use the algorithm without adapting the data structure (i.e. use it on XmlNode?). Requiring the nodes themselves to be enumerables is probably too restrictive, but that’s a possibility as well.
February 11th, 2011 at 8:34 AM
Hey Arseny,
Good comments! The reason I used the IHasChildren interface and not IEnumberable is because IEnumerable usually means that the item “is” a list-like-structure, while in this case it means that the item “has” a list like structure, for example throwing in a List (which is IEnumerable) would give very weird results. Adding a Func<> to extract child items from the node is a very smart move though!
February 11th, 2011 at 4:31 PM
public static IEnumerable DFS(ITreeNode root)
{
yield return root;
foreach (ITreeNode node in root)
{
foreach (ITreeNode var in DFS(node))
{
yield return var;
}
}
}
public interface ITreeNode : IEnumerable
{
}
This might be an interesting experiment. I don’t know if yield generates any garbage and I don’t know what the performance hit of the yield statement is, but I do know using delegates can be pretty costly in terms of performance. Also, you needlessly iterate over a collection multiple times (first PushMany, then the while) while creating a stack (garbage!) which is technically not needed in my solution.
February 11th, 2011 at 4:40 PM
Btw, I would personally prefer adding the depth first method to the base class for scene graph items. Seems a bit neater and you have more flexibility in terms of return types and need to implement interfaces and things like that. Don’t make things too generic when it’s not necessary.
public class TestTreeNode
{
private List children;
public IEnumerable depthFirst()
{
yield return this;
foreach (TestTreeNode child in children)
{
foreach (TestTreeNode var in child.depthFirst())
{
yield return var;
}
}
}
}
February 11th, 2011 at 7:40 PM
Kan het echt niet volgen, heb het aan Laurens gevraagd maar hij snapt er ook niets van
February 11th, 2011 at 8:44 PM
Mart:
I dont iterate multiple times. First I push all the childs at the stack, then I iterate all these childs, and push the childs-childs on the stack
.
As for using yield like that, hmm interesting I wonder if that would work, and if it would be faster or slower.
February 12th, 2011 at 3:04 PM
[...] Traversal algorithms using generics, generic constraints (where), and Action delegates [...]