Re: [Boost-Users] [bgl] breadth_first_search for shortest paths (fwd)

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2002-10-31 16:34:52

Hi Joel,

On Thu, 31 Oct 2002, Joel Young wrote:
yg-boo> Dear Jeremy, et al,
yg-boo>
yg-boo> I am trying to implement a shortest paths algorithm on
yg-boo> a directed graph.
yg-boo>
yg-boo> As I have unit edge weights, I would rather use breadth_first_search
yg-boo> rather than dijkstra.

Righto.

yg-boo>
yg-boo> // Is this a good candidate for addition?

Sure.

yg-boo> The problem is that on_start_vertex does not seem to be
yg-boo> implemented for breadth_first_search, but it is for depth_first.
yg-boo> For dijkstra, the start node seems to be automaticly zeroed.  I
yg-boo> guess I could mod
yg-boo>
yg-boo> Am I missing something really obvious here or is there an
yg-boo> inconsistency across the algorithms?
yg-boo>
yg-boo> Shouldn't on_start_vertex be used for all of the graph algorithms?

Well, if you use breadth_first_visit instead, then you can do the
initialization of the vertices yourself, as is done in dijkstra.

However, you have a point. It would be more consistent to have
on_start_vertex implemented for breadth_first_search. Do you feel up to
doing the patch?

yg-boo> Also, I can't seem to find documentation on neighbor_bfs.hpp

Yeah, that's on the to-do list.

Cheers,
Jeremy

----------------------------------------------------------------------
 Jeremy Siek                          http://php.indiana.edu/~jsiek/
 Ph.D. Student, Indiana Univ. B'ton   email: jsiek_at_[hidden]
 C++ Booster (http://www.boost.org)   office phone: [phone]
----------------------------------------------------------------------