Re: [BGL]: 2 desgin questions

From: Björn Lindberg (yg-boost-users_at_[hidden])
Date: 2002-10-03 09:51:25

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