[graph] strange behaviour of relax
Hello All, Writing special variant of dijkstra's algorithm I wanted to reuse the `relax` function (from boost/graph/relax.hpp) that is used by dijkstra_shortest_paths_no_color_map. And I've notices what I think is mismatch in behaviour between relax and dijkstra_shortest_paths_no_color_map. When the graph is not oriented, the relax function will consider decreasing distance of either target (obiously) or source. However it returns the same true in both cases, so the caller does not know which vertex was updated and the dijkstra_shortest_paths_no_color_map does not expect having to update the source at all. It shouldn't happen, but than why is that condition there? It appears to me that one or the other is wrong. But I don't know the code well enough to tell which. Regards, Jan -- Jan 'Bulb' Hudec <bulb@ucw.cz>
On Mon, 22 Oct 2012, Jan Hudec wrote:
Hello All,
Writing special variant of dijkstra's algorithm I wanted to reuse the `relax` function (from boost/graph/relax.hpp) that is used by dijkstra_shortest_paths_no_color_map. And I've notices what I think is mismatch in behaviour between relax and dijkstra_shortest_paths_no_color_map.
When the graph is not oriented, the relax function will consider decreasing distance of either target (obiously) or source. However it returns the same true in both cases, so the caller does not know which vertex was updated and the dijkstra_shortest_paths_no_color_map does not expect having to update the source at all. It shouldn't happen, but than why is that condition there?
It appears to me that one or the other is wrong. But I don't know the code well enough to tell which.
I'm not sure -- it might be because the code does not trust which direction of edge it will get traversing the incident edges of a vertex in an undirected graph, so the code allows some of them to be backwards (pointing from the target to the source). You can assume that a return of "true" from relax means that whichever vertex is opposite to the one that you are currently visiting the neighbors of is the one that has been updated. -- Jeremiah Willcock
On Oct 22 2012, Jeremiah Willcock wrote:
On Mon, 22 Oct 2012, Jan Hudec wrote:
Hello All,
Writing special variant of dijkstra's algorithm I wanted to reuse the `relax` function (from boost/graph/relax.hpp) that is used by dijkstra_shortest_paths_no_color_map. And I've notices what I think is mismatch in behaviour between relax and dijkstra_shortest_paths_no_color_map.
When the graph is not oriented, the relax function will consider decreasing distance of either target (obiously) or source. However it returns the same true in both cases, so the caller does not know which vertex was updated and the dijkstra_shortest_paths_no_color_map does not expect having to update the source at all.
The dijkstra only calls relax for cases where the d_source < d_target. Therefore if the function returns true, it is because the target was relaxed. The check on the source is redundant and I would prefer it if it were not used in the dijktra_shortest_paths algorithm. In part because this reverse check necessitates using the closed_plus instead of plain plus operator to combine distances. See also Trac: https://svn.boost.org/trac/boost/ticket/7387
It shouldn't happen, but than why is that condition there?
It appears to me that one or the other is wrong. But I don't know the code well enough to tell which.
I'm not sure -- it might be because the code does not trust which direction of edge it will get traversing the incident edges of a vertex in an undirected graph, so the code allows some of them to be backwards (pointing from the target to the source).
I assumed the reason was to be able to use one and the same relax function both for algorithms that relax either end of the edge (e.g. Bellman-Ford).
participants (3)
-
Alex Hagen-Zanker -
Jan Hudec -
Jeremiah Willcock