It's not really what you're after, but I hope it might give some ideas (useful or not, I don't know).
How about considering a vertex as a point in space (most libraries will allow you to decorate a vertex with additonal information), then creating an edge between vertices, which will be your 'path'. You can then decorate the edge with information such as distance/maximum speed etc... Then all you need to do is use an A* path algorithm or shortest path search to get the shortest / most efficient route.... You might need a custom visitor to suit the 'weight'/'score' of how efficient the path is. I know this probably isn't of much help, but I hope it comes in useful; I've only ever used Boost.Graph (which is C++, but I believe it has a Python binding) and that was for something else -- although I do recall it had examples involving Kevin Bacon and dependency tracking etc... so a good old Google might do you some good -- ie, it's not completely related, but it might give you a few extra things to search on... All the best with the search. Jon. PS. If you do find a library, can you let me know? I'd be interested in having a play with it... -- http://mail.python.org/mailman/listinfo/python-list