Re: [boost] [graph] bellman_ford_shortest_paths interface

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-11-11 13:47:03

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. However, I agree 
that it's a bit messy to use, especially when you already have a Vertex 
List Graph.

> Another problem is that number of vertices is passed as parameter. I 
> realize
> this is more flexible (for example I can compute the maximum length of 
> all
> paths with less than N edges), but it's also confusing and dangerous. 
> I've
> just passed a wrong variable to that parameter and spend quite some 
> time
> debugging.

Same reason: getting n requires num_vertices(g), part of the Vertex 
List Graph concept.

> 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...

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.

        Doug