[Graph] Dijkstra algorithms checks edge weight is positive: loss of generality ?
Hello, I'm not very familiar yet with all boost::graph internals, but there is something that bothers me: I use a special weight_map (cost functions of my own), providing my own distance_combine. So WeightMap::value_type is CostFunction and DistanceMap::value_type is float The dijkstra algorithm checks if an edge has a positive weight ( boost/graph/dijkstra_shortest_paths.hpp lines 121 & 122 with version 1.36.0). However, it uses the distance_compare parameters where "argument types that match the value type of the DistanceMap property map" So it tries to compare my cost function against a float (which of course is not possible). Of course this test garanties the optimality of the algorithm, but it restricts the use to have the weight_map and the distance_map of the same type. Did I miss how to use custom weight_maps, or is it some special case that wasn't thought of ? For now I just commented out the check Thank you ! PS: a more general optimality condition is (sufficient, but I'm not sure if it's necessary) : the combine function has to be non decreasing : for a node u, and edge e = (u,v), the distance_map d and the weight map w distance_compare(d[u], distance_combine(d[u], w[e]) ) has to be true
I use a special weight_map (cost functions of my own), providing my own distance_combine. So WeightMap::value_type is CostFunction
I think that your WeightMap should return the result of your CostFunction, not the function itself. I'm not familiar with the graph library, though, so I don't know if that's easy to do.
The dijkstra algorithm checks if an edge has a positive weight (boost/graph/dijkstra_shortest_paths.hpp lines 121 & 122 with version 1.36.0). .... For now I just commented out the check
Dijkstra's algorithm only works correctly with non-negative edge weights, so some sort of check is necessary.
PS: a more general optimality condition is (sufficient, but I'm not sure if it's necessary) : the combine function has to be non decreasing : for a node u, and edge e = (u,v), the distance_map d and the weight map w distance_compare(d[u], distance_combine(d[u], w[e]) ) has to be true
This should be sufficient in general, and again, some sort of check is necessary.
I think that your WeightMap should return the result of your CostFunction, not the function itself. I'm not familiar with the graph library, though, so I don't know if that's easy to do. The result of the cost function depends on the distance I believe this is meant to be done with the parameter named distance_combine (the documentation states that the distance_map and weight_map do not need to be of the same type). And it works in my case. I have : struct Combine_distance{ float operator()(float distance, FunctionPtr f) const{ return (*f)(distance); } };
The weight map value type is FunctionPtr, and I call dijkstra with : boost::dijkstra_shortest_paths(cg, start_idx, boost::predecessor_map(&p[0]) .distance_map(&d[0]) .weight_map(get(&Edge_property::length, cg)) .distance_combine(Combine_distance()) ); But of course I have to comment out the check.
Dijkstra's algorithm only works correctly with non-negative edge weights, so some sort of check is necessary. Not exactly. If the arcs have constant weights, then yes. If you have dynamic weights, it's not that simple.
PS: a more general optimality condition is (sufficient, but I'm not sure if it's necessary) : the combine function has to be non decreasing : for a node u, and edge e = (u,v), the distance_map d and the weight map w distance_compare(d[u], distance_combine(d[u], w[e]) ) has to be true
This should be sufficient in general, and again, some sort of check is necessary. Of course a check is needed, but should be more flexible with the condition I gave on the first mail. It should rather happen when en edge is relaxed By default distance_compare is < and distance combine is + So my condition would be : d[u] < d[u] + w[e] that is equivalent to w[e] > 0, so edge weight has to be positive.
I think that your WeightMap should return the result of your
CostFunction, not the function itself. I'm not familiar with the graph library, though, so I don't know if that's easy to do.
The result of the cost function depends on the distance I believe this is meant to be done with the parameter named distance_combine
Well, that's something I didn't consider. I'm sure you're right. Now I'm just being curious. If your cost function is the same for every edge, you could move the real work of the cost function to the combine method. (If it varies between graphs, you could make the function pointer a member of the struct.) The weight_map could then return some other value that the cost function uses (or ignores). (the documentation states that the distance_map and weight_map do not need
to be of the same type).
Since I just read it, I feel I should correct that. http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/dijkstra_shortest_paths.... The last sentence describing weight_map says that they should be the same type. However, I think that condition could (and should) be relaxed. As for the discussion of the edge-checking condition, every description of Dijkstra's algorithm that I've read says that it only guarantees a correct answer when edges have non-negative weights. Really, we can generalize that to "compare(d[u], combine(d[u], w[e])) must be true," as you stated. I don't know how to do that with this library, since examine_edge considers the edge, but not the distance. I suspect that it will require interface changes, though they may be minor. Again, I'm not familiar with the library, only with the algorithm.
Well, that's something I didn't consider. I'm sure you're right. Now I'm just being curious. If your cost function is the same for every edge, you could move the real work of the cost function to the combine method. (If it varies between graphs, you could make the function pointer a member of the struct.) The weight_map could then return some other value that the cost function uses (or ignores).
Maybe I should explain what I'm doing ;) I work on multimodal transportation (combining diffrent means of transport): the time you spend for taking the bus depends on the time you arrive at the bus stop (waiting time) the time you spend on a road edge depends on the time of the day (rush hour or not) And of course the time depends on the path you took before. Thus you can't precalculate the weight (and every edge has a different cost function). A possible work arround would be a operator()<(float) { return true;} to my cost functions.
(the documentation states that the distance_map and weight_map do not need to be of the same type).
Since I just read it, I feel I should correct that. http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/dijkstra_shortest_paths.... The last sentence describing weight_map says that they should be the same type. However, I think that condition could (and should) be relaxed.
Urg, sorry! Indeed it's quite clear... I thought about (on the same page): "The CombineFunction type must be a model of Binary Function. The first argument type of the binary function must match the value type of the DistanceMap property map and the second argument type must match the value type of the WeightMap property map" so I assumed they can be different.
As for the discussion of the edge-checking condition, every description of Dijkstra's algorithm that I've read says that it only guarantees a correct answer when edges have non-negative weights. Really, we can generalize that to "compare(d[u], combine(d[u], w[e])) must be true," as you stated. I don't know how to do that with this library, since examine_edge considers the edge, but not the distance. I suspect that it will require interface changes, though they may be minor. Again, I'm not familiar with the library, only with the algorithm.
The following patch could do it (but it changes a more general function relax, so I'm not sure of the implications on other algorithms) diff /usr/include/boost/graph/dijkstra_shortest_paths.hpp /usr/include/boost/graph_old/dijkstra_shortest_paths.hpp 120a121,122
if (m_compare(get(m_weight, e), m_zero)) throw negative_edge();
diff /usr/include/boost/graph/relax.hpp /usr/include/boost/graph_old/relax.hpp
16d15
< #include
Now I'm just being curious. If your cost function is the same for
every edge, you could move the real work of the cost function to the combine method. (If it varies between graphs, you could make the function pointer a member of the struct.) The weight_map could then return some other value that the cost function uses (or ignores).
I work on multimodal transportation (combining diffrent means of transport): the time you spend for taking the bus depends on the time you arrive at the bus stop (waiting time) the time you spend on a road edge depends on the time of the day (rush hour or not) And of course the time depends on the path you took before. Thus you can't precalculate the weight (and every edge has a different cost function).
Cool, I wondered what the application was. Now it makes sense. I figured that your edges would have different cost functions, but thought I should mention it anyway.
(the documentation states that the distance_map and weight_map do not need to be of the same type).
Since I just read it, I feel I should correct that.
http://www.boost.org/doc/libs/
1_36_0/libs/graph/doc/dijkstra_shortest_paths.html http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/dijkstra_shortest_paths....
The last sentence describing weight_map says that they should be the
same type. However, I think that condition could (and should) be relaxed. http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/dijkstra_shortest_paths....
Urg, sorry! Indeed it's quite clear... I thought about (on the same page): "The CombineFunction type must be a model of Binary Function. The first argument type of the binary function must match the value type of the DistanceMap property map and the second argument type must match the value type of the WeightMap property map" so I assumed they can be different.
That does imply that they can be different...I'd say one or both of those statements needs to change.
As for the discussion of the edge-checking condition, every description
of Dijkstra's algorithm that I've read says that it only guarantees a correct answer when edges have non-negative weights. Really, we can generalize that to "compare(d[u], combine(d[u], w[e])) must be true," as you stated. I don't know how to do that with this library, since examine_edge considers the edge, but not the distance. I suspect that it will require interface changes, though they may be minor. Again, I'm not familiar with the library, only with the algorithm.
The following patch could do it (but it changes a more general function relax, so I'm not sure of the implications on other algorithms)
diff /usr/include/boost/graph/dijkstra_shortest_paths.hpp /usr/include/boost/graph_old/dijkstra_shortest_paths.hpp 120a121,122
if (m_compare(get(m_weight, e), m_zero)) throw negative_edge();
diff /usr/include/boost/graph/relax.hpp /usr/include/boost/graph_old/relax.hpp 16d15 < #include
53,55d51 < if ( compare(combine(d_u, w_e), d_u) ) { < throw negative_edge(); < }
Well, the Bellman-Ford algorithm includes the same header, and so probably uses the same function. Since it works with negative edges (but not negative cycles), this patch isn't the way to go. Do you think I should contact the dev mailing list in order to get
an opinion more of the internals ?
Since nobody else is weighing in on this discussion, and all my knowledge of the graph library was learned in the last 24 hours, I'd say yes. Be sure to mention the discrepancy in the documentation about value types. This is just wishful thinking on my part, but I wonder if the distance could be incorporated into the edge descriptor, or the vertex descriptor? I imagine that would require even more changes, but it would allow weight_map to calculate the edge weight, and examine_edge could stay as-is.
participants (2)
-
Dave Steenburgh -
Tristram Gräbener