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”:

Lattice

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 Down
Left Left Down Left Down
Left Left Down Down Left
Left Down Left Left Down
Left Down Left Down Left
Left Down Down Left Left
Down Left Left Left Down
Down Left Left Down Left
Down Left Down Left Left
Down 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):

graph

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.

7 thoughts on “Graph traversal, part three

  1. I’m having trouble following the second lattice. Specifically, the pattern I’m seeing breaks in the edges from (5, 1) to (4, 0) and (5, 2) to (4, 1). They have values 1 and 2, but should they both be 4? If that’s the case, I see what’s going on here.

    In any case, mind blown! Not only am I surprised that this connection exists, I’m surprised that I didn’t expect you to make some sort of connection.

    • Whoops! Those edges are wrong. I’ll fix it. Thanks for the note.

      I’m always happy to blow my reader’s minds, but this one was somewhat foreshadowed. This post was inspired by a comment to the previous series that noted that the recursive algorithm was essentially exploring a tree of possibilities. What I’ve done here is made the control flow graph of the combination algorithms into actual graphs, and then traversed them.

      • Yeah, I remembered that comment when I went over the parallels between the two.

        I also flashed back to my undergrad graph algorithms class, where we talked about polynomial-time transformations between problems like boolean satisfiablity and graph coloring. The transformation from finding subsets to traversing dags is apparently pretty straightforward!

      • This graph reminds me somewhat of some puzzles by Dudney (late 1800s) related to enumerating paths. I think he used a few forms, one of which might have matched the “combinations” one above; the one I particularly remember, had to do with enumerating the ways of spelling “WAS IT A RAT I SAW” on a letter grid.

  2. I was just fiddling around with something similar the other day. If you change the orientation of your infinite lattice, it’s clear that it’s Pascal’s triangle. The path interpretation provides a nice proof for the additive formula that can be used to generate it.

    • (You don’t have to change the orientation; I just mean that Pascal’s triangle is always drawn with a different orientation.)

  3. Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1732

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