Re: [Boost-users] [Graph] dynamically building a graph

From: Douglas Gregor (dgregor_at_[hidden])
Date: 2007-09-11 09:53:39

Hello Krishna,

Krishna Roskin wrote:
> I'm working on a project where I'm dynamically building a graph on the
> fly as the graph is traversed. For out_edges(...) (and other
> functions), I've been using something similar to
> shared_container_iterator to dynamically build the list of out edges.
> My target and source functions return-by-value objects that represent
> the vertices. I've also overloaded the operator[] on the graph to
> return-by-value objects with the edge and vertex properties. I use
> by-value semantics because the entire graph is never created in
> memory.
>   
Sure, that makes sense. I know that a few other BGL users have reported 
using the BGL on such "implicit" graphs.
> But my iterators and graph object don't quite fit into the rest of the
> boost graph library. For instance, filtered_graphs of my graph don't
> like that my iterators don't return references to edge_descriptors.
> I've fixed that problem by defining
>
> typedef typename Graph::edge_descriptor reference;
>
> in the iterator, i.e. reference aren't really references but
> returned-by-value objects. But this seem like treating the symptoms
> and not the cause. 
No, you've done exactly the right thing. The various iterators into the 
graph need to satisfy the MultiPassInputIterator concept, described 
(briefly) here:

    http://www.boost.org/libs/utility/MultiPassInputIterator.html

With a MultiPassInputIterator (as with an InputIterator), it's perfectly 
fine to return by-value from operator*. In this case, your "reference" 
type will be exactly the same as your "value_type", as you have done 
above. Actually, the BGL adjacency_list does this when you use "vecS" 
for the vertex storage. The vertex_iterator is actually just an instance 
of the counting_iterator template.
> And the operator[] of the filtered_graph wants to
> return references as well and so I get "returning reference to
> temporary" errors. I've gotten around this by just getting the
> vertex/edge properties from the original graph.
>   
Ah, here the BGL's model of internal vertex properties isn't permissive 
enough. It assumes that "bundled" properties (the ones accessed via 
operator[]) are always stored somewhere in memory, so one can extract a 
reference to it. This is a bug in the BGL: we should have some way to 
specify the equivalent of the iterator's "reference" type. Your 
workaround will work fine, of course.

> Has anyone else had these problems? Or know of a better way to build
> graphs dynamically? Any advice or strategies would be appreciated.
>   
I think you're on the right track.

    - Doug