Re: [Boost-users] [BGL] DistanceMatrix type for johnson_all_pairs_shortest_paths

Subject: Re: [Boost-users] [BGL] DistanceMatrix type for johnson_all_pairs_shortest_paths
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-09-09 10:41:50

On Wed, 9 Sep 2009, Ralf Goertz wrote:

> Hi,
>
> I spent a lot of time to figure out what the problem was. But the reason
> why there is a problem is still not clear.
>
> I modified the johnson_all_pairs_shortest_paths example program to allow
> for non-constant graphs. The example prog contained
>
> std::vector < int >d(V, (std::numeric_limits < int >::max)());
> int D[V][V];
> johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0]));
>
> with V being const int whose value is known at compile time. In my
> program this is obviously not the case, therefore I defined
>
> const int V(num_vertices(g));
> std::vector < int >d(V, (std::numeric_limits < int >::max)());
> int D[V][V];
> johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0]));
>
> But this didn't compile, I got the error
>
> error: no matching function for call
> to ‘johnson_all_pairs_shortest_paths(Graph&, int [(long int)V][(long
> int)V], boost::bgl_named_params<int*, boost::vertex_distance_t,
> boost::no_property>)’

I do not know how GCC handles the types of run-time sized arrays, which 
are compiler-specific in C++.

> However, it is possible to access elements of D as D[i][j], even if V
> isn't known at compile time. This is (according to what I read at
> http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/BasicMatrix.html )
> the only constrained for D. Substituting
>
> int D[V][V]
>
> with
>
> vector<vector<int> > D(V,vector<int>(V))
>
> solves the problem, but still why is there a problem in the first place?

It looks like the type of D in your array case is something unusual that 
cannot have a reference formed to it or somehow cannot be deduced as a 
template argument.  I would recommend the vector solution you posted since 
that is portable.

-- Jeremiah Willcock