Re: [Boost-users] [BGL] Constantness bug in kruskal_minimum_spanning_tree

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2006-11-22 09:18:40

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