Re: [boost] [graph] strange behaviour of relax

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