Graph traversal, part four

Let’s return now to our modified Zork graph fragment from a couple episodes back:

zorkmap

It is pretty obvious just from looking at this graph that if you start from the Troll Room and follow the arrows, there are four rooms that you must enter no matter what combination of edges you take: the East-West Passage, the Dam, the Dam Lobby and the Maintenance Room. And moreover, we’ll encounter them in that order. Let’s call these nodes “the inevitable nodes of the Troll Room”. Continue reading

About these ads

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: Continue reading

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. Continue reading

Graph traversal, part one

There are lots of topics in both practical and theoretical computer science that deal with graphs, lots of different kinds of graphs, lots of ways to represent a graph as a data structure, and lots of operations you’d want to perform on such a data structure. Like, “is this node in this graph?” or “is there any path from this node to that node in this graph?” and so on. Programming with graphs is a huge topic. In this series I want to explore a tiny subset of those topics. Specifically:

  • How can we create an immutable data structure which represents a directed graph with labels on the edges?
  • Given a directed acyclic graph (DAG), what are all the possible edge traversals through that graph starting from a particular node?

Continue reading

Producing combinations, part four

Last time I showed how to use an immutable stack of Booleans to act as flags indicating whether a particular element of a sequence should be chosen as one of the combinations of exactly k elements. A reasonable criticism of this approach is that when you have a stack containing, say, thirty flags, each of which is a managed object and contains a Boolean and a reference, then we’ve overspent by a large factor; thirty bits could fit into a single int.

Continue reading

Producing combinations, part three

All right, we have an immutable stack of Booleans and we wish to produce all such stacks of size n that have exactly k true elements. As always, a recursive algorithm has the following parts:

  • Is the problem trivial? If so, solve it.
  • Otherwise, break the problem down into one or more smaller problems, solve them recursively, and aggregate those solutions into the solution of the larger problem

Let’s start with a signature. What do we have? integers n and k. What do we want? A sequence of Boolean stacks such that the size is n, and there are k bits turned on. We therefore require that n and k both be non-negative, and that n be greater than or equal to k. Continue reading