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

Subject: Re: [boost] [graph] dijkstra pull request ping
From: alex (alexhighviz_at_[hidden])
Date: 2015-10-21 07:26:29

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