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

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2006-11-21 09:43:20

Hi

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.

AFAICT, the proper way to address both types of iterator/handles is by 
specializing both graph_traits<MyGraph> and graph_traits<MyGraph const>.

It all works fine with my own BGL-like algorithms, but now I want to call
kruskal_minimum_spanning_tree and I can'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 ;

(and so for the vertex_descriptor, etc)

but then, lines like this:

tie(vb,ve) = vertices(G)

or this

source(e, G)

fails to compile with my graph because it attempts to bind a const 
iterator/handle to a non-const iterator/handle, which my data
structure intentionally forbids.

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

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.

TIA

Fernando Cacciola