|laziness, impatience, and hubris
Short Circuiting DFS Graph Traversalby Limbic~Region (Chancellor)
|on Oct 29, 2010 at 00:54 UTC
Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:
In this node, neversaint asks how to find all paths between two nodes in a graph. The example graph is not weighted and since we are only interested in paths and not costs, this doesn't come into play. While the example graph is directed, I don't believe it matters.
Graph appears to have a method but it is unclear to me if it only finds all the shortest paths or all paths (I haven't tested). The straight forward approach is a depth first search (DFS). My question is if it is possible to efficiently short-circuit the search.
I have provided a short circuiting solution though I am not positive it is correct (limited test set). I also don't know if it is very efficient (optimizing for run time). The basic idea is this: At each node, a handful of conditions can apply.
Since Y is in a path considered dead, I can short circuit if my path has an R, X and T in any order. I have only tested this hypothesis on two graphs. If this is not a safe assumption, please provide an example that disproves it and also offer any suggestions for short circuiting that you know to be viable.
Now assuming you have made it this far, the problem is that Y may be part of many completed paths. In order to determine if I can short circuit, I have to go through all of them until I find a match or reach the end. Depending on a number of factors (the graph, order of traversal, end points, etc), it can be more expensive keeping track of completed paths then just enumerating all of them. The thing that bothers me is that when more than one completed path share a single non-end point node in common then if one fails they all fail. Unfortunately, I haven't figured out how to group them together this way and still loop over all of them. Can you think of a way to do this more efficiently or do you know of an entirely different approach that is more efficient?
Cheers - L~R