Re: [Boost-users] Graph problem -- solvable using the Boost graph library ?

From: Jeffrey Holle (jeffreyholle_at_[hidden])
Date: 2005-12-20 18:48:13

Though I'd pipe in a way to find a path between two vertices within a tree.
This is a required step in implementing a network simplex method algorithm, 
which I've done.
Its based on Vasik Chvatal's Linear Programming book.

He has a chunk of this book on-line that describes most of the path finding 
algorithm: 
http://www.esc.auckland.ac.nz/teaching/Engsci450FC/NetworksModule/NOChapter4.pdf

The algorithm employs depth and predecessor arrays.  These need to be 
initialized from your tree.  The above mentioned pdf tells how.  I found that 
boost.graph is set up quite well to initialize them.

If your task is finding the path between a lot of vertices on a static tree, it 
could be efficiently used.  This is mainly because the paths from the target and 
from the source can be found "at the same time".

matthieu.ferrant_at_[hidden] wrote:
> 
> Hi Dmitry, Gregoire, zvrba, Aaron, Vladimir,
> 
> thanks for your answers to my question.
> 
> Gregoire, Vladimir, I initially tried using an all-pairs shortest path 
> algorithm but with a graph of 30.000 nodes or more, the distance matrix 
> is just way to large. That's why I was doing multiple Dijkstras.
> 
> Reading the other remarks, I actually ended up doing 2 dijkstras: the 
> first one from an arbitrary end-point, then looping over the distance 
> vector, selecting the end point with the largest distance value 
> associated to it. This is point is then used for a second dijkstra, 
> where I also loop over all end points to determine the other end-point. 
> Finally using the predecessor visitor, and both end points, it is easy 
> to record the full path. This I believe this somewhat boils down to what 
> Aaron wrote. Dmitry, I didn't try out your implementation, looks like it 
> might be a little faster, but what's the overhead of dijkstra vs BFS ? 
> Probably not that much in a tree.
> 
> Thanks alot for all the help so far !!
> 
> matt-
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users