[BGL] DistanceMatrix type for johnson_all_pairs_shortest_paths
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>)’ 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? Ralf
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
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++.
That's what the problem is... I couldn't see it. You can't instantiate a template over the type of a variable length array. You can probably think of it as a local type (a struct within a function), but it probably goes beyond that. Last time I checked, calling typeid on e.g., D resulted in a compiler error. That may have been GCC 4.1, though. Didn't GCC drop them at some point? This holds for linear arrays also. One more argument against variable length arrays. Andrew Sutton andrew.n.sutton@gmail.com
Andrew Sutton wrote:
That's what the problem is... I couldn't see it. You can't instantiate a template over the type of a variable length array. You can probably think of it as a local type (a struct within a function), but it probably goes beyond that. Last time I checked, calling typeid on e.g., D resulted in a compiler error. That may have been GCC 4.1, though. Didn't GCC drop them at some point?
With gcc version 4.3.2 they still exist, and yes, you can't use typeid with nor instantiate a template over it. At least, I would have liked a more meaningful error message with the johnson_all_pairs_shortest_paths() call. Thanks for the clarification, Ralf
participants (2)
-
Andrew Sutton -
Jeremiah Willcock -
Ralf Goertz