Re: [Boost-users] Looking for a book on graph algorithms

Subject: Re: [Boost-users] Looking for a book on graph algorithms
From: Nick Edmonds (ngedmond_at_[hidden])
Date: 2009-01-23 16:39:07

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_at_[hidden]>  
> 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 Sutton
> andrew.n.sutton_at_[hidden]
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users