Re: [boost] [graph] dijkstra pull request ping

Subject: Re: [boost] [graph] dijkstra pull request ping
From: Marcin Zalewski (marcin.zalewski_at_[hidden])
Date: 2015-10-21 16:15:30

On Wed, Oct 21, 2015 at 11:33 AM alex <alexhighviz_at_[hidden]> wrote:

> >  I can see that is useful, but it is not
> >> Dijkstra's algorithm.
> >>
> >
> >Could you give the reference to the "real" Dijkstra algorithm? We are
> >talking about implementation detail which was
> >not concerned at all in the original Dijkstra paper.
>
> Dijkstra (1959) A Note on Two Problems in Connexion with Graphs:
>
> "If the node R belongs to set C, it is added to set B "
>
> Boost:
>
> if (v_color == Color::white()) {
>       put(color, v, Color::gray());
>
> Patch:
>
> if(decreased) {
>   if (v_color == Color::white()) {
>     put(color, v, Color::gray());
>
> Now, I know that in the classical usage 'decreased' is always true, so
> there
> is no change in behaviour. I also know that the way that Boost implements
> Dijkstra, it evaluates 'decreased' anyway despite knowing beforehand it
> must
> be true. So you are not proposing to change behaviour or to make the
> function less efficient. But, I think BGL shouldn't evaluate 'decreased' to
> begin with (https://svn.boost.org/trac/boost/ticket/7387).
>

The edge has to be relaxed, so we get decreased for free anyway, right?
What do you mean by not evaluating decreased? Then we use decreased to
check which visitor function we should call, so I am not sure if one could
get rid of that without having two versions of the code (one for the
"classical" version, and one for an arbitrary distance map).

> > Note, that standard
> >dijkstra call with default distance map works
> >exactly the same with or without my patch. IMHO, the current conception
> >(without my patch) is caused only by using BFS abstraction.
> >Try to modify my code to achieve previous functionality and you find it
> >really awkward.
>
> I think one solution would be to use a visitor with a reference to the
> queue
> and to a map indicating precalculated nodes.
>
> You could then use the edge_relaxed() callback with
> void edge_relaxed(G& , E& e)
> {
>    Vertev t = target(e);
>   if( get(is_precalculated, t ) {
>     queue.push(t)
>     put(is_precalculated, t, false);
> }
>
> To use this you would need to initialize the color_map such that the color
> for precalculated nodes is gray.
>

This sounds a bit complicated overall.