[Graph] dynamically building a graph
Hello everyone, I hope this question isn't to vague. I just looking for some general advice. 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. 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. 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. Has anyone else had these problems? Or know of a better way to build graphs dynamically? Any advice or strategies would be appreciated. Thanks, -krish
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
On 9/11/07, Douglas Gregor
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
participants (2)
-
Douglas Gregor -
Krishna Roskin