Re: [boost] Re: [graph] bellman_ford_shortest_paths interface

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-11-12 13:48:39

On Nov 12, 2004, at 2:27 AM, Vladimir Prus wrote:

> 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

You can store information within the vertices and have only the names 
of a few of the vertices to start from. For the properties, you keep a 
global counter: each time you run the algorithm, you increment the 
counter, thereby telling all vertices that their values are out of 
date.

> (I'd don't think using
> std::map for distance map is viable for performance reasons).

What about a hash table? That's efficient enough to be viable.
>
> 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.

Then we are essentially lowering the algorithm by placing on more 
requirements. It is a common use case to have a VertexAndEdgeListGraph, 
but it isn't the only use case.

        Doug