
Boost : 
From: Vladimir Prus (ghost_at_[hidden])
Date: 20041112 02:27:36
Doug Gregor wrote:
> On Nov 6, 2004, at 8:57 AM, Vladimir Prus wrote:
>> after trying to use the bellman_ford_shortest_paths I think it's a
>> little bit
>> strange. First of all, user is required to initialise distance map
>> before
>> calling the algorithm. The distance to the source vertex must be set
>> to zero
>> and distances to other vertices to infinity. Why can't the algorithm
>> accept a
>> source vertex as parameter and do initialisation itself? Dijsktra
>> surely does
>> not require such initialization.
>
> I believe the intent was to make the BellmanFord algorithm require
> only an Edge List Graph and not also a Vertex List Graph. To set the
> distance map, one would need the vertices(g) function.
Do you have a practical case where this matters. How can user initialise
distance map himself without iterating over vertices (I'd don't think using
std::map for distance map is viable for performance reasons). If he can
iterate over all vertices, then the graph type can be VertexList model.
>> Is it possible to provide a version of the algorithm which
>> (1) takes just graph, without vertex number parameter
>> (2) takes start vertex, and initialises distance map itself
>
> I expect it would look like this:
>
> template <class VertexAndEdgeListGraph, class P, class T, class R>
> bool bellman_ford_shortest_paths(
> VertexAndEdgeListGraph& g,
> typename
> graph_traits<VertexAndEdgeListGraph>::vertex_descriptor source,
> const bgl_named_params<P, T, R>& params = all defaults);
>
> I'm slightly concerned that adding this overload will cause an
> ambiguity with the existing bellman_ford_shortest_paths when we have an
> adjacency list with VertexListS=vecS, but maybe we can weasel around
> that...
I would actually drop the existing overload, and provide the one above and
template <class VertexAndEdgeListGraph, class P, class T, class R>
bool bellman_ford_shortest_paths(
VertexAndEdgeListGraph& g,
typename
graph_traits<VertexAndEdgeListGraph>::vertex_descriptor source,
unsigned N,......
for special cases. This might break some code, but interface is really
better.
> One alternative would be to have:
>
> template <class VertexAndEdgeListGraph, class P, class T, class R>
> bool bellman_ford_shortest_paths(
> VertexAndEdgeListGraph& g,
> const bgl_named_params<P, T, R>& params = all defaults);
>
> Where the mandatory named parameter start_vertex(u) indicates that we
> should initialize the property maps appropriately for starting at
> vertex u, and requires a VertexAndEdgeListGraph. This is the safe
> answer, at least.
.....
> I meant "root_vertex", not "start_vertex", here. Anyway, I've
> implemented this option and checked it into CVS head.
Thanks!
 Volodya
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk