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

Subject: Re: [boost] [graph] dijkstra pull request ping
From: alex (alexhighviz_at_[hidden])
Date: 2015-10-21 11:33:22

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

> 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 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).
>
To me it looks like a good abstraction with a bad name.