Jeremy Siek wrote:

Hi Bjorn,

On Wed, 2 Oct 2002, [iso-8859-1] Björn Lindberg wrote: [snip] yg-boo> 1) Why is a lot of the function arguments made by value rather than yg-boo> reference? As an example, consider the BFS algorithm, where the yg-boo> documentation states that [snip]

One of the usage scenarios that we wanted to support with the algorithms was creating visitor objects on the fly, within the argument list of the call to the graph algorithm. In this situation, the visitor object is a temporary object. Now there is a truly unfortunate rule in the C++ std that says a temporary cannot be bound to a non-const reference parameter. So we had to decide whether we wanted to support this kind of usage and go with call-by-value, or not and go with call-by-reference. We chose call-by-value, following in the footsteps of the STL (which passes functors by value).

Ah yes, I forgot about that rule. I was thinking that since the temporary is in scope for the whole expression, this would still work. I forgot that it won't for non-const references.

yg-boo> 2) Non-constness. It seems impossible to use BGL together with yg-boo> code that is "const-correct". If, for instance, I have a function yg-boo> implementing some kind of examining algorithm on a graph (so the yg-boo> graph is passed to it as const), and this algorithm uses yg-boo> breadth_first_search with a visitor that doesn't modify the graph, yg-boo> it still can't be const when passed to breadth_first_search. This yg-boo> only leaves the options of either (i) casting away constness in yg-boo> the call, which is bad because it could introduce bugs later on, yg-boo> or (ii) leaving out const altogether which is not good either. yg-boo> yg-boo> Maybe I've just misunderstood something and this is possible, or yg-boo> perhaps it is impossible to implement BGL in this way?

If you look at the docs for BFS, you'll see that one version takes the graph non-const, and the other takes the graph as a const reference. The reason is that BFS modifies the color map during the search. The version of the algorithm that takes the graph non-const may be getting the color map from the graph, as an internal property map, so in this case BFS is modifying the graph in some sense. The version of BFS that takes the graph as a const reference has a separate parameter for the color map.

I suggest that you use the non-named template parameter version that takes the graph by const reference.

I see. To be honest, I find the BFS docs to be somewhat confusing. For instance I haven't been able to find what bgl_named_params is. So I've looked at examples, and my BFS invocations typically look something like this boost::breadth_first_search(tree, root(tree), boost::visitor(visitor)); I've been looking at bgl_named_params just now, but I can't really figure out how to use it. I guess I'm already using it with the line above, but I just copied the use of visitor(...) from an example, I can't say that I know what it does. Speaking of visitors, I find that I often want my visitors to store or access data for every vertex in the graph. This leads me to use property maps (or just plain old std::vectors) a lot. Is creating a property map an expensive operation? How about access, is it done in O(1) time? It seems the best idiom here is to pass a property map to the visitor's constructor, letting the visitor keep a reference to it, so that it is available for the visitor methods, eg discover_vertex(...). It would be more elegant to hide the visitor's functionality a bit more, but the only way I can see to do that is by letting discover_vertex(...) create the property map on every call, which is possible since it is passed the graph as an argument. This seems far too expensive though. Björn