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