A very similar conversation came up in the chatterbox a few weeks ago.
in reply to Graph traversal--shortest path?
Someone asked about Graph::BFS and linked to Six Degrees via Shortest Path ?. I did some research on this problem, and was able to solve a variant of the problem porkpilot describes by using simple accesses to Graph::Base methods.
In the process of exploring Graph::BFS I found that its biggest problem was its poor documentation -- I couldn't figure out how it worked without reading all the code, and I didn't have the energy.