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-23 09:32:44

On Thu, Oct 22, 2015 at 4:56 PM alex <alexhighviz_at_[hidden]> wrote:

> > > > What do you mean by not evaluating decreased? Then we use decreased
> > > > to check which visitor function we should call, so I am not sure if
> > > > one
> > > could
> > > get rid
> > > > of that without having two versions of the code (one for the
> "classical"
> > > version,
> > > > and one for an arbitrary distance map).
> > > >
> > >
> > > Sorry I am not clear. Yes, I do think that you should get rid of the
> > > redundant check. And, yes that would mean that if you want the
> > > arbitrary distance map, you should have two versions.
> > >
> >
> > I would  only agree with that if we could demonstrate that there is a
> statistically
> > significant performance advantage of doing so. Looking at the code, I am
> > skeptical that this check has much or any impact on performance on most
> > modern platforms. Do you have any evidence that shows there would be a
> > benefit to having two versions of the code?
> >
>
> There are the following advantages:
>
> 1. you avoid one unnecessary check for each vertex
> 2. you do not need to initialize values in the distance map
> 3. you do not need to specify an "inf" value for distance
>
> (1) and (2) should bring some performance gain, but it is so little that I
> did not notice it and did not feel the urge to measure it. I don't think
> performance is a good reason to take out the redundant check.
>

The check only becomes redundant if there are two versions of the code, one
for dijkstra_shortest_paths_no_init and one for dijkstra_shortest_paths.
The code that covers dijkstra_shortest_paths_no_init automatically covers
dijkstra_shortest_paths. There is an advantage to it, and if one would
provide separate code for the two, there should be a compelling reason. In
my opinion, in this case the reason should be performance. Otherwise, why
do this?

> (2) and (3) however make the algorithm simpler and cleaner to use. It
> becomes easier / possible to apply the method when there is no good value
> for "inf". I do think that is a good reason to take out the redundant
> check.
>

Yes, I agree with you that it makes *one version* of the algorithm cleaner,
but we have to make a decision that we want to provide that version in the
first place. I think that providing an elegant version at the cost of two
different implementations is actually additional complexity.

> If you take out the redundant checks in the relax function, you no longer
> need to use boost::closed_plus and can do with std::plus. Again, to me that
> makes the function simpler and cleaner. But that is a separate issue,
> because you can do that whether you make two separate functions or not.
>

True, agreed. Still, the same as above: do we want to have two
implementations instead of one?