I'm assuming you've already checked CLR and Aho, Hopcroft, and Ullman? They don't solve the specific problems you mention but are a always good starting point.
If you really want up-to-date algorithms, I disagree with Andrew, Conference/Journal papers are exactly where you should look. If you're looking for things like girth, diameter, etc. the Infovis community might have some useful resources as they're always interested in properties of networks. There are a lot of books on graph algorithms out there but I haven't found most of them particularly useful. When I look at implementing new algorithms in the Parallel BGL I check the above resources, plus Ja Ja (An Introduction to Parallel Algorithms), then head straight for conferences/journal publications.
With regards to finding all paths from v to u, you can modify the BGL's implementation of Dijkstra's algorithm to relax equal-weight edges fairly simply (or you could just check for equal weight edges on non-tree-edge which makes figuring out when to terminate easier). Then if you make all edges have weight 0 (just replace your edge weight property map with one that always returns 0) all paths will be equal weight and you'll be able to identify all paths from v to u.
Cheers,
Nick
On Jan 23, 2009, at 12:27 PM, Andrew Sutton wrote:
On Fri, Jan 23, 2009 at 12:15 PM, Roger House
<rhouse@sonic.net> wrote:
I'm looking for a good book on graph algorithms, perhaps something a bit different than the usual introductory book.
For example, I would like an algorithm for finding all paths from vertex v to vertex u, not necessarily the shortest
one or the longest one. Also, algorithms for determining the girth, diameter, and other properties of graphs are of
interest. Or perhaps I should be looking at journal papers? Any pointers will be appreciated.
I'm not sure about books on graph algorithms, and (in my experience) journal papers on graph algorithms aren't generally geared towards implementers.
There are algorithms in sandbox/SOC/2007/graphs that compute girth, diameter, and several other measures. They were supposed to be integrated into the trunk pending a mini-review, but it never happened. I may try to decouple from them the SoC changes to the library and add them to the trunk, but I probably won't have time for a while.
andrew.n.sutton@gmail.com
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users