On Tue, 2006-11-21 at 11:43 -0300, Fernando Cacciola wrote:
I have a graph-like data structure which supports both const and non-const vertex and edge iterators and handles, and I want to interface it to the BGL. FWIW. the iterators and handles are class types, and the const versions are different classes than the non-const ones, so removing const qualification is not the way to bind a const type to its non-const version.
The BGL concepts and algorithms were designed under the assumption that constness does not affect the traversal of graphs. That's why there are no "const_vertex_descriptor" or "const_vertex_iterator" types, for example. It was a pragmatic choice meant to avoid the duplication we see in the STL containers, which gets much worse when you have many ways of traversing the graph.
AFAICT, the proper way to address both types of iterator/handles is by specializing both graph_traits<MyGraph> and graph_traits<MyGraph const>.
... because MyGraph and MyGraph const are separate types. Yeah, this has been an issue for a lot of generic libraries, where we tend to ignore constness when we shouldn't.
The problem is that the kruskal function takes a "const Graph&" argument but it declares the internal types like this:
typedef typename graph_traits<Graph>::edge_descriptor Edge ; [snip] Unless I am missing something obvious (and I hope I am), this is a bug in the kruskal function: it should declare the working types like this:
typedef typename graph_traits<Graph const>::edge_descriptor Edge ;
Am I right? If yes, what can I do??
Yes, I think you're right. We should be consistent with our graph types... if we're working on a const Graph, get the associated types for const Graph. I see two potential solutions. The first is the solution you suggest: keep the const along with the Graph when we access its associated types. The second solution is to change the graph parameters for these algorithms from const Graph& to Graph&. This addresses another problem users have had, where they want their visitors to get a (non-const) Graph& to mutate the graph or its property maps as the algorithm runs. We've been telling them to use const_cast<>, but the right solution is to not enforce constness at all. The issue with this solution is that Graph& can't bind to non-const temporaries, so we'll need to change all of the BGL graph wrapper generators (e.g., make_reverse_graph) to return const types. Either way, we'll need to add specializations of graph_traits and property_map for "const Graph", which merely inherit their members from the non-const Graph versions: template<typename Graph> struct graph_traits<const Graph> : graph_traits<Graph> { };
Is there any "constant correct" BGL algorithm? I'm calling kruskal just as an example showing how the data structure can be interfaced to the BGL.
I imagine that nearly every BGL algorithm has this error. This is not a trivial undertaking, but it will surely improve the BGL. Cheers, Doug