Graph traversal, part four

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

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".

Actually, do we know for sure that we'll encounter them in that order? It seems plausible that the inevitable nodes come in a particular order, but naybe that's true on this graph but not true in general. I propose the following theorem: suppose a node X has two distinct inevitable nodes, Y and Z. Then either Y is an inevitable node of Z, or Z is an inevitable node of Y, but not both. And therefore, all the inevitable nodes of a particular node can be put into the unique order in which they must inevitably be visited.

It's not hard to prove this fact by considering the cases: if neither Y nor Z are inevitable nodes of each other then there must be a path that goes from A through Y and never goes through Z, which contradicts the supposition that Z is an inevitable node of A. If Y and Z are both inevitable nodes of each other then there is a cycle path, contradicting the supposition that we're in a DAG. The only remaining possibility is that exactly one is an inevitable node of the other.

Today I am interested in DAGs where there is one node that is an inevitable node of every other node in the graph. (Naturally no node can be an inevitable node of itself, as that would imply that there is a cycle in the graph.) Our little graph here is such a graph: no matter where you start, you inevitably end up in the Maintenance Room and then can go no further. Let's call such a node a "final inevitable node".

My question is: suppose we have a DAG that contains a final inevitable node. I want an algorithm that takes as its input any other node, and outputs the closest inevitable node to that node; that is, the first inevitable node that will be encountered. We know that there must be a unique first inevitable node because given any two inevitable nodes, one is after the other.

For example, the Troll Room has four inevitable nodes, the closest obviously being the East West Passage. This is not very interesting because there is only one edge out of the Troll Room! But consider the Round Room; now it is not so clear that the closest inevitable node of the Round Room is the Dam. And so on.

There are a number of ways to solve this problem; we'll consider a few ideas over the next few episodes.