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)

zorkmap

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 East
East East East Up East North North
East East East Up Northwest East North East
East East East Up Northwest East North North
East East North Northeast East North East
East East North Northeast East North North
East East North Northeast Northwest East North East
East East North Northeast Northwest East North North
East East North North Northeast East North East
East East North North Northeast East North North
East North Northeast East North East
East 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.

12 thoughts on “Graph traversal, part two

  1. Very interesting, but isn’t this tailored towards DAGs with just one “dead end”?

    I came up with a slightly more general solution (hope thats no spoiler on what you plan for the next post šŸ˜‰ ), based on generating all paths starting at a specific node and then filtering for the wanted “finish node”:
    https://github.com/RaphMad/GraphTraversal/blob/master/GraphTraversal/Graph/GraphExtensions.cs

    The idea is pretty much the same, except that all intermediate paths are also generated (to allow for any “finish” node) and I sticked to iterator blocks instead of using a stack.

    • The algorithm I give finds all the traversals from a given node no matter how many “finish nodes” there are; the fact that there is only one will come in handy in a future episode.

      • Ah I get it, the problem you tackled is:

        “Given a directed acyclic graph (DAG), what are all the possible edge traversals through that graph starting from a particular node?”

        It is just a coincidence based on the structure of the graph that this also answers “What are the paths from Troll Room to Maintenance room”.

  2. Pingback: Graph traversal, part one | Fabulous adventures in coding

    • Indeed, though I already discussed that problem in my series on the A* algorithm a few years back. The system I’ve set up here does not easily allow the edge labels to be weights because they must be unique.

      • Could edges be used as weights if duplicates were resolved by simply adding a small “adjustment” either when a collision was detected, or else preemptively (e.g. if weights will be positive integers less than one billion, and there will be no more than four billion nodes, give each node an `Int64` “weight” which is equal to the desired weight plus a node index)?

        • That could be done, but sounds a bit clunky to me. I’d rather keep the edge labels as Eric has designed them, and add supplemental properties to the edges (such as “distance” and “speed limit”). It all really depends on the use-case, as Zork doesn’t require either.

        • An index pair would work though I would prefer the pair “weight, guid” and now you can have as many edges between nodes as you want with whatever weights you want. But like I said in the previous episode, if I were trying to solve the problem of traversal of a weighted graph then I would choose a different data structure in the first place.

  3. Pingback: Dew Drop – November 3, 2014 (#1890) | Morning Dew

  4. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1729

  5. Pingback: Graph traversal, part three | Fabulous adventures in coding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s