[boost] Re: [graph] bellman_ford_shortest_paths interface

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-11-12 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 Bellman-Ford 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