Boost logo

Boost :

Subject: Re: [boost] [graph] strange behaviour of relax
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-10-23 09:03:44

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

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:

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at