Graph traversal, part three

Last time we made a little recursive algorithm to walk around a directed acyclic graph, or DAG. I made that algorithm a member of the graph class, but did you notice something about it? It did not access any private member of the class. Rather, it only used the public interface to do its work. What information do we need to find all the traversals of a DAG starting from a given node? Only the set of edges which come off that node, which we could determine from a delegate! We could in fact have written this algorithm as the following static method:

public static IEnumerable<ImmutableStack<KeyValuePair<E,N>>> AllEdgeTraversals<E, N>( N start, Func<N, IReadOnlyDictionary<E, N>> getEdges){ var edges = getEdges(start); if (edges.Count == 0) { yield return ImmutableStack<KeyValuePair<E, N>>.Empty; } else { foreach (var pair in edges) foreach (var path in AllEdgeTraversals(pair.Value, getEdges)) yield return path.Push(pair); }}

We don't need a monolithic, precomputed graph data structure at all. We can compute the edge set of a given node on demand, as it were.

Of course we can use this static method with our graph structure easily enough:

foreach (var path in AllEdgeTraversals("Troll Room", n => map.Edges(n))) Console.WriteLine(string.Join(" ", from pair in path select pair.Key));

And we get the same result as before.

Here's a graph that I am interested in exploring. The nodes are the points on the two-dimensional lattice of non-negative integers. Each node has zero, one or two edges that point to a neighbouring node, and the labels are either "Left" or "Down":

This is an infinite graph, and so we cannot really represent it in our immutable graph structure easily. But that's OK; every traversal on the graph is finite because they all eventually get to (0,0), and we can create new nodes and edges as needed:

Func<Tuple<int, int>, IReadOnlyDictionary<string, Tuple<int, int>>> getEdges = latticePoint =>{ var edges = ImmutableDictionary<string, Tuple<int, int>>.Empty; if (latticePoint.Item1 > 0 { edges = edges.Add( "Left", Tuple.Create(latticePoint.Item1 - 1, latticePoint.Item2)); } if (latticePoint.Item2 > 0) { edges = edges.Add( "Down", Tuple.Create(latticePoint.Item1, latticePoint.Item2 - 1)); } return edges;};

What are all the traversals from (3, 2) to (0, 0)?

foreach (var path in AllEdgeTraversals(Tuple.Create(3, 2), getEdges)) Console.WriteLine(string.Join(" ", from pair in path select pair.Key));

Run that and we get

Left Left Left Down DownLeft Left Down Left DownLeft Left Down Down LeftLeft Down Left Left DownLeft Down Left Down LeftLeft Down Down Left LeftDown Left Left Left DownDown Left Left Down LeftDown Left Down Left LeftDown Down Left Left Left

Wait a minute" that looks suspiciously familiar. If we replaced the lefts with "true" and the downs with "false"" oh my goodness, I've accidentally and totally not on purpose solved the "enumerate all bit sequences of size n that have exactly k true bits" problem again, which in turn gives us a solution to the "enumerate all the combinations of k elements from an n-element sequence" problem. Enumerating the traversals on this graph starting at (k, n-k) is exactly the same as enumerating all the sequences of n bits with exactly k true bits.

Is that ever weird!

Finally, one more. Recall that we also solved the "enumerate the combinations of k items from a sequence of n" by solving the problem "enumerate the sets of size k drawn from the integers 0 through n-1". We can solve that problem by enumerating all the traversals of this graph starting from (n, k):

Doing so is left as an exercise. Do you see the connection between these recursive graph traversal algorithms and the equivalent recursive combination algorithms from the previous series?

Next time: we'll look at another problem involving paths on a DAG.