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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-11-15 11:02:12

Doug Gregor wrote:

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

You'd need to make property map return +inf when property on any other
vertex is accessed, then.

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

Is this for implementation of the above? Else I don't understand what you
mean.

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

Yes, it's more viable. However, it's still not clear for me why you would
prefer having no list of vertices and using hash_map. Given that
Bellman-Ford visits all vertices except for isolated one, hash_map won't be
better either in memory usage or run time.

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

May I again ask you if you have a real example? It still feels bad to
optimize for generic case which might be never needed. It might be possible
to provide fully generic version with a slightly different name or use a
special parameter, or something, without complicating interface for the
common case.

- Volodya