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-27 16:45:15

On Fri, Oct 23, 2015 at 12:49 PM alex <alexhighviz_at_[hidden]> wrote:

> > Note that in the pseudo code discovery of a vertex happens only if the
> new
> > distance is less than the old distance.
>
> No, the pseudo code is based on the implied precondition that all distances
> are infinity. And on that condition the pseudo code and the actual code are
> equivalent.
>

I don't believe in "implied" assumptions. A comment in the pseudo code says:

"

*This loop is not run in dijkstra_shortest_paths_no_init"*
I think that there are strictly two cases, one in which the loop is run and
the other in which it is not. When the loop is run, the algorithm can be
optimized in the way you have described previously (i.e., the check for
improvement of distance may be removed when a vertex is white).

> Note that this implied precondition is also reflected in the description of
> post-conditions on the same page:
>
> "Dijkstra's algorithm finds all the shortest paths from the source vertex
> to
> every other vertex"
>

That sentence continues with "by" and the rest of the paragraph which
specifies what is actually supposed to hapen.

> "Upon completion of the algorithm, the edges (p[u],u) for all u in V are in
> the tree"
>

That just says what the tree is.

> "If p[u] = u then u is either the source vertex or a vertex that is not
> reachable from the source"
>

That is probably tough. With the no_init version one can have vertices
without a parent that are still reachable from source. I would not take
this as restricting the possible values of the distance map in the no_init
version. I think that by specifying a custom distance map, one can
basically modify what is reachable and what is not.

> "The shortest path weight is the sum of the edge weights along the shortest
> path"
>

That is still true, modulo the meaning of the word reachable.

> "At the end of the algorithm, vertices reachable from the source vertex
> will
> have been colored black. All other vertices will still be white"
>

Again, modulo reachable.

> None of these are upheld for a distance map with arbitrary values.
>

They mostly are, except that one can make some vertices unreachable. I
think that all the post-conditions you have listed here are not strong
enough to forbid arbitrary values in the distance map for the no_init
version of the algorithm. I myself would assume by reading the pseudo code
and the documentation that there is nothing preventing me from using the
no_init version of the algorithm along with a custom distance map to
control traversal. I think that forbidding custom distance map at this
point would not be backward compatible, but it would also be
counterproductive, as there is really not a good reason to do so. If
anything, the documentation should be made more unambiguous on the point of
what are the possible inputs for the distance map.

> >
> > If we would go with the ideas you describe, the code would not work for
> > arbitrary distance map. There are 2 cases:
> >
> > 1) All values in the distance map are inf (or are implicitly inf).
> > 2) User provides a distance map with arbitrary values and they must be
> > respected per pseudo code.
> >
>
> I disagree, I don't think case 2 is a valid case for Dijkstra's shortest
> paths. At the moment using it like that gives inconsistent results. I don't
> think the purpose of the no_init version is to allow arbitrary distance
> values.
>

OK, so here we disagree. I think that this is precisely the reason for the
no_init version. Why would we need it otherwise? Besides, I think that
there is no reason to forbid such a usage, and this is similar to providing
a preinitialized color map to BFS. The documentation is quite clear to what
the algorithm actually does, and the pseudo code is not broken by allowing
arbitrary distance maps as inputs. I don't see a compelling reason to
forbid controlling the behavior of the algorithm by providing a custom
distance map. On the other hand, if there was more voices from the users
that would want to eliminate such a use, we could do that, but I am not
sure how this improves the library. I do agree though that the
documentation of the no_init features could be improved.

> > As far as I understand, you want to do something specific for case 1)
> where we
> > do not need to do the check in the pseudo code because we know it will
> always
> > be true, right? If we did so, we need to have code that also works for
> case 2).
> > Right now we just have the code for case 2) and it also works for case
> 1).
> Let me
> > know if I misunderstood something.
> >
>
> If you mean Piotr's patch, yes you understood correct. If you mean the
> current Boost version: you misunderstood, this is just for case 1.
>

This point would depend on what decision we make on the discussion above.
If we allow arbitrary distance maps, then we would two versions of code to
provide the optimization you propose.

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