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

Subject: Re: [boost] [graph] strange behaviour of relax
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-10-22 16:18:56

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