Hi all, I'm currently trying to write a wrapper in order to use the BGL algorithms and visitors on a home-made graph class. If I'm not mistaken, this requires me to write (amongst other things) a couple functions that will return iterators over my graph edges and vertices, eg: std::pair<graph_traits<MyGraph>::out_edge_iterator, graph_traits<MyGraph>::out_edge_iterator > out_edges(graph_traits<MyGraph>::vertex_descriptor u, const MyGraph& g) and similarly in_edges(...) , vertices(...) and edges(...) functions. However, it seems that this function profile forces me to do a const_cast on g when implementing the function body since the out_edge_iterators are not const iterators, though they point to internal elements of g. I had a look at the example given in the documentation (dealing with converting LEDA graphs to the BGL), but I didn't see anything helping me on this particular issue (also, the example in the doc is a bit outdated since it uses the deprecated Boost iterator adaptors). Am I forced to rely on const_cast in these functions, or is there a way to declare my graph edges, vertices and the corresponding iterators as const in my graph_traits class ? I'm a newbie with the BGL, and more generally with this whole traits/template specialization style of programming, so please excuse me if I overlooked something obvious. Cheers.
On Tuesday 11 May 2004 08:29 am, Cyrille Damez wrote:
Am I forced to rely on const_cast in these functions, or is there a way to declare my graph edges, vertices and the corresponding iterators as const in my graph_traits class ?
The iterators won't ever need non-const access to your graph data structure. The iterators return edge or vertex descriptors, which do not have direct access to the graph data structure. Notice that every operation on descriptors includes the graph itself (which can be const or non-const)? That's what allows the constness of descriptors to be irrelevant. Granted, there are still some graph representations that might need const_casts (or something even uglier). Doug
Le Mardi 11 Mai 2004 16:50, Douglas Gregor a écrit :
The iterators won't ever need non-const access to your graph data structure. The iterators return edge or vertex descriptors, which do not have direct access to the graph data structure. Notice that every operation on descriptors includes the graph itself (which can be const or non-const)? That's what allows the constness of descriptors to be irrelevant.
So if I understood correctly, I was misunderstanding what a descriptor is supposed to be. In my particular case, the graph structure is actually a triangle mesh: the graph vertices are the mesh triangles (resp. the graph edges are mesh edges) and have non-const access to their edges (resp. the triangles that contain them). Therefore, returning non-const iterators that could in turn return descriptors was conflicting with the constness of the graph. So if I'm not mistaken, a descriptor should be something like a container for whatever additional information I am supposed to carry with my graph (here geometric data like 3D positions, normals, etc.), and shouldn't have the right to modify anything related to the graph topology. Therefore I should make all topological informations const in the vertex_descriptor and edge_descriptor classes and only enable changes to the topology through the mesh/graph object. Thanks for the explanation
On Tuesday 11 May 2004 12:27 pm, Cyrille Damez wrote:
So if I understood correctly, I was misunderstanding what a descriptor is supposed to be. In my particular case, the graph structure is actually a triangle mesh: the graph vertices are the mesh triangles (resp. the graph edges are mesh edges) and have non-const access to their edges (resp. the triangles that contain them).
Interesting.
Therefore, returning non-const iterators that could in turn return descriptors was conflicting with the constness of the graph.
This is correct.
So if I'm not mistaken, a descriptor should be something like a container for whatever additional information I am supposed to carry with my graph (here geometric data like 3D positions, normals, etc.), and shouldn't have the right to modify anything related to the graph topology. Therefore I should make all topological informations const in the vertex_descriptor and edge_descriptor classes and only enable changes to the topology through the mesh/graph object.
Descriptors are more like a key or index into a container that represents those attributes... So if all your vertices are stored into a vector, the descriptor could be the index into that vector. If your vertices were stored in an STL map, the descriptor could be the key into that map. In both cases, it's the constness of the container (vector or map) that matters, not the constness of the descriptor (key or index). Doug
Hi Cyrille, On May 11, 2004, at 7:29 AM, Cyrille Damez wrote:
Hi all,
I'm currently trying to write a wrapper in order to use the BGL algorithms and visitors on a home-made graph class. If I'm not mistaken, this requires me to write (amongst other things) a couple functions that will return iterators over my graph edges and vertices, eg:
std::pair<graph_traits<MyGraph>::out_edge_iterator, graph_traits<MyGraph>::out_edge_iterator > out_edges(graph_traits<MyGraph>::vertex_descriptor u, const MyGraph& g)
and similarly in_edges(...) , vertices(...) and edges(...) functions. However, it seems that this function profile forces me to do a const_cast on g when implementing the function body since the out_edge_iterators are not const iterators, though they point to internal elements of g.
The BGL iterators are neither const or mutable. Same for the descriptors. Instead, mutability is encoded in the property maps. So, for example, it is okay to implement out_edge_iterator using a const iterator. See the file boost/graph/vector_as_graph.hpp for an example. Look at the implementation of out_edges, and the val_out_edge_iter class. No const_cast is needed. Cheers, Jeremy _______________________________________________ Jeremy Siek <jsiek@osl.iu.edu> http://www.osl.iu.edu/~jsiek Ph.D. Student, Indiana University Bloomington Graduating in August 2004 and looking for work C++ Booster (http://www.boost.org) _______________________________________________
participants (3)
-
Cyrille Damez -
Douglas Gregor -
Jeremy Siek