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

From: Krishna Roskin (krish_at_[hidden])
Date: 2007-09-13 13:07:45

On 9/11/07, Douglas Gregor <dgregor_at_[hidden]> wrote:
> 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.

I'm not surprised, it really seems like the BGL was made with that in
mind even though I realize it probably was more of a by-product of
generics.

> > 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.

That's good to know. It kind'a felt like that was cheating.

> > 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.

I wish I had more experience with BGL style programing so I could take
a stab fixing this.

> > 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.

Cool. Thanks for the reply.

-krish