Boost logo

Boost :

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

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.


Boost list run by bdawes at, gregod at, cpdaniel at, john at