LINQ to Graph

As promised in my previous, I now provides some details about an example I gave during my talk at SoCal Code Camp titled “LINQ to Objects A-Z”. In this blog, I will discuss LINQ to Graph.

LINQ to object has a large number of functions to query IEnumerable<T>. What if we are dealing with a hierarchy? It turns out LINQ can flatten one-level-down hierarchies with one of the SelectMany methods. For deeper hierarchies, we need to do either the depth-first-search (DFS) or the breath-first-search (BFS). In this post, I will provide generic implementations of BFS and DFS. These functions return an IEnumerable<T> that can subsequently processed with LINQ.

With DFS, we need to recursively place exposed nodes on a stack and search each node until nothing left on the stack. With BFS, we use a queue instead of a stack to store unsearched nodes. The implementation of DFS is relatively simple as recursive function calls already provide a stack implicitly. The following code snippets show the DFS implementation.

The DFS function accept the three arguments. The first argument is the starting node. The second argument getInners is a lambda function that returns the child inner nodes of a parent node. The third argument is a lambda function that returns the leaf nodes of a parent node.

The following code snippets demonstrate using DFS to search a direction for files recursively. We pass the path of the starting directory as the first argument. We use Directory.EnumerateDirectories to implement the getInners function and use Directory.EnumerateFiles to implement the getLeafs function.

The implementation of BFS is longer. We need to implement a queue explicitly. Two helper functions are defined to help managing the queue. The BFS function can be used in place of DFS in the recursive problem; only the order of the outputs will change.

The source code of this blog could be found at http://skylinq.codeplex.com. In future blogs, I will continue discussing application of LINQ in combinatorial problems.