Re: [Boost-users] [BGL]johnson_all_pairs_shortest_path algorithmdoesn't use distance_inf named parameter.

From: Peter Gerell (boost_at_[hidden])
Date: 2006-02-17 11:03:42

> Hi,
> I am had sime difficulties using the johnson_all_pairs_shortest_path 
> algorithm.
> I have a custom weight type called CostType.
> I tried calling the algorithm as follows.
>
>  johnson_all_pairs_shortest_paths(g, D, 
> distance_inf(CostType::infinity()));
>
> The result was a distance matrix with all zeros.
> The problem is the following lines from 
> johnson_all_pairs_shortest_path.hpp
>
>  DT inf = (std::numeric_limits<DT>::max)();
>  for (tie(v, v_end) = vertices(g2); v != v_end; ++v)
>    d[*v] = inf;
>
> If I specialized the numerical-limits class for CostType everything 
> started to work as expected.
>
> namespace std {
>  template<>
>  class numeric_limits<CostType> {
>  public:
>    inline static CostType min() throw() { return -CostType::infinity();}
>    inline static CostType max() throw() { return CostType::infinity(); }
>  };
> }
>
> Even if this is the good way to solve the problem, it doesn't work for 
> what I want to do.
> I'm trying to calculate the longest paths by redefining distance_inf and 
> distance_compare.
>
> Is this a bug or is it something I don't understand?
> I am using boost 1.33.1

Another problem is that a user define CombineFunction passed to the 
distance_combine parameter isn't used.
A closed_plus<DT> functor is passed to the bellman_ford_shortest_paths 
algorithm.
Same goes for the compare function. std::less<DT> is used.
It seems that the algorithms are not as generic as the documentation makes 
you believe.

When browsing the CVS-repositories I found some references to longest paths 
algorithms in some of the commit messages:
"Make relax work when we're searching for longest paths"

Thanks, Peter