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:46:04

On Wed, Oct 21, 2015 at 9:23 AM Piotr Wygocki <vwygos_at_[hidden]> wrote:

> Dear Alex,
>
> Thank you for your feedback!
>
>   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. 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.
>

We should probably use the pseudo code in the documentation:

http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/dijkstra_shortest_paths.html

The pseudo code seems to support your assertion that a vertex should not be
discovered if relaxation was not successful. So it seems that the actual
implementation is not in agreement with the documentation. Do you agree
with that characterization of the issue? If so, your patch does take care
of the issue, but we should make sure that this is the best way to go.

> > This does not seem a real problem. The BFS function is well suited to
> > Dijkstra's algorithm, perhaps the only problem is that its name is not
> fully
> > appropriate.
>
> It is important to make proper abstractions. As I previously said BFS could
> be expressed as Dijkstra with custom  priority queue
> implemented as FIFO. It does not work the other way around. Dijkstra is NOT
> a special kind of BFS. Implementation happens to be similar, which was used
> in this case (which is bad IMO).
>

I think that the perspective here was to reuse breadth_first_visit as a
traversal pattern rather than as a BFS. However, as you rightly noted, that
fails for the reason that when a white vertex is uncovered, it is
unconditionally inserted into the queue. I've been staring at the code
trying to come up with a workaround while keeping breadth_first_visit, but
it quickly becomes inelegant and defeats the purpose. I think that unless
we make some modifications to breadth_first_search, we may have to go with
your patch. The only thing I am not sure of is this:

https://github.com/boostorg/graph/pull/13/files#diff-55abe8912b7c5c01b7be025e60b92c78R252

This branch seems to be for testing purposes only to avoid using a relaxed
heap, no? In any case, commenting out this if statement should probably be
a separate patch with a separate explanation anyway.

Does anyone have any ideas on whether there are better solutions than
Piotr's patch?

> Regards,
>
> Piotr
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>