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

Subject: Re: [boost] [graph] dijkstra pull request ping
From: Tim Keitt (tkeitt_at_[hidden])
Date: 2015-10-21 09:57:31

http://www.keittlab.org/

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

> >Dear all, this mail concerns this pull request:
> >
> >https://github.com/boostorg/graph/pull/13
> >
> >which is currently over one year long. Maybe, the idea of the patch is
> >unclear or needs some additional discussion.
>
> I think it does.
>
> The idea of your patch is to be able to specify a maximum distance for each
> node. As long as the graph distance is above that maximum distance the node
> does not get added to the queue. I can see that is useful, but it is not
> Dijkstra's algorithm. Could you just make your own function
> dijkstra_with_max_node_distance() or something like that?
>

That would be my suggestion as well.

THK

> >
> >The patch solves the problem which arises when using no_init version on
> >dijkstra algorithm and passing a custom distance_map.
> >This algorithm is implemented as call to BFS, which is very unfortunate
> >since it is not BFS.
> >Maybe BFS could be seen as special case of dijkstra with custom priority
> >queue but not the other way around.
>
> 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.
>
> >The current implementation introduces some inefficiencies, which are
> >described in the pull request's comment.
> >
> >I've created very short and direct patch which makes the implementation
> >straight forward.
>
> It does not really seem short as it is duplicating most of the BFS code.
>
> >Additionally, the unit test is added to check mentioned efficiency gain.
>
> It is efficient for another problem than Dijkstra's.
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>