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

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)’

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