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