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

Subject: Re: [boost] [graph] dijkstra pull request ping
From: alex (alexhighviz_at_[hidden])
Date: 2015-10-22 16:55:52

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

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

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.