Graph traversal, part two

Last time we built an immutable structure representing a labeled directed graph, and then built a directed acyclic graph stolen from Zork: (click for larger)

The question at hand is: given a node in a finite DAG, what are all the possible traversals of edges through the graph starting from that node? We know that any traversal of a finite DAG must eventually terminate in a node that has no outgoing edge, and that there are finitely many such traversals.

Suppose we start from the Troll Room on this map; clearly if we follow the arrows we inevitably end up at the Maintenance Room. The question is: what are all the possible sequences of edges that get us from here to there? We'll represent a sequence of edges as an immutable stack, again from the NuGet package. So we'll start by adding a method to our graph type with signature:

public IEnumerable<ImmutableStack<KeyValuePair<E, N>>> AllEdgeTraversals(N start){

Let's reason recursively. What is the base case? If we are in a room with no outgoing passages, then there is exactly one path we can go on, and that's the empty path.

 var edges = Edges(start); if (edges.Count == 0) { yield return ImmutableStack<<KeyValuePair<E, N>>.Empty; }

That was easy, as the base case should be. What's the recursive case? If we know all the traversals of all the nodes that are reachable immediately from this one, then we can simply add the edges that get us to each of them to the traversals.

 // The key is the edge, the value is the node. else { foreach (var pair in edges) foreach (var path in AllEdgeTraversals(pair.Value)) yield return path.Push(pair); }

And we're done. If we then run this method on our previously-created Zork map:

 foreach (var path in map.AllEdgeTraversals("Troll Room")) { Console.WriteLine( string.Join(" ", from pair in path select pair.Key)); }

Then we get every possible traversal through this map that ends in the dead end which is the Maintenance Room:

East East East Up East North EastEast East East Up East North NorthEast East East Up Northwest East North EastEast East East Up Northwest East North NorthEast East North Northeast East North EastEast East North Northeast East North NorthEast East North Northeast Northwest East North EastEast East North Northeast Northwest East North NorthEast East North North Northeast East North EastEast East North North Northeast East North NorthEast North Northeast East North EastEast North Northeast East North North

And sure enough, those are all the possible ways to get from the Troll Room to the Maintenance Room in this DAG version of the map. Solving the "find all traversals on a cyclic graph that do not go into cycles" is a slightly trickier problem but perhaps you can see how to modify the algorithm to do so. At that point you could put the rest of the edges from the original map into the graph and see how many ways there are to leave the Troll Room and run around the Great Underground Empire without crossing your own path.

Next time: We could make this algorithm slightly more general, and in doing so, discover a surprising result.