[graph] bellman_ford_shortest_paths interface
Hi, 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. 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. 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 - Volodya
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
On Nov 11, 2004, at 1:47 PM, Doug Gregor wrote:
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. Doug
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
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
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
On Nov 15, 2004, at 11:02 AM, Vladimir Prus wrote:
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.
Correct.
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.
Sorry; yes, this is an efficient implementation of the above.
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.
I don't know of a real example. If we can dispatch cleanly to provide both functionality types, I don't see a problem with having both versions. Unfortunately, the common case (VertexAndEdgeListGraph) has the stranger syntax, and we're stuck with that until we move everything into namespace boost::graph. Doug
participants (2)
-
Doug Gregor -
Vladimir Prus