BGL: filtered graph question
Hello everybody! I use the filtered_graph framework to restrict a BFS visit to a small region on my graph. BUT, I provide the starting vertex to the BFS routine by a vertice_descriptor of the underlying/unfiltered graph. Of course, this vertice descriptor matches the predicate. My code compiles fine, but I started to ask myself if this actually behaves correct? As I could not find a hint within the docs, does someone know? Greetings, Sebastian
On 4/25/06, Sebastian Weber
Hello everybody!
I use the filtered_graph framework to restrict a BFS visit to a small region on my graph. BUT, I provide the starting vertex to the BFS routine by a vertice_descriptor of the underlying/unfiltered graph. Of course, this vertice descriptor matches the predicate. My code compiles fine, but I started to ask myself if this actually behaves correct?
As I could not find a hint within the docs, does someone know?
Hi Sebastian, Yes, that should work fine. filtered_graph redefines functions like vertices, edges, adjacent_vertices, etc. so that they only return vertices/edges from the original graph that match the predicates you've provided. Once you dereference those iterators, you do get vertex/edge descriptors from the original graph. -Aaron
On the topic of filtered_graph, do any algorithms fundamentally require vertex indices to lie in [0,1,...,num_vertices), or is this needed/reccomended only when an algorithm has to allocate its own, say, color map? As noted in the documentation, such a requirement interacts badly with filtered_graph. The docs claim that "the problem is being worked on," but is it really? Daniel On Tuesday 25 April 2006 01:54, Sebastian Weber wrote:
Hello everybody!
I use the filtered_graph framework to restrict a BFS visit to a small region on my graph. BUT, I provide the starting vertex to the BFS routine by a vertice_descriptor of the underlying/unfiltered graph. Of course, this vertice descriptor matches the predicate. My code compiles fine, but I started to ask myself if this actually behaves correct?
As I could not find a hint within the docs, does someone know?
Greetings,
Sebastian
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Apr 25, 2006, at 8:14 AM, Daniel Mitchell wrote:
On the topic of filtered_graph, do any algorithms fundamentally require vertex indices to lie in [0,1,...,num_vertices), or is this needed/ reccomended only when an algorithm has to allocate its own, say, color map?
It's needed any time you create a property map that is indexed by the vertex_index values, which happens in nearly every BGL algorithm.
As noted in the documentation, such a requirement interacts badly with filtered_graph. The docs claim that "the problem is being worked on," but is it really?
Well, no, it isn't really being worked on. Every time it comes up, we just reaffirm the original decision. It's weird, but it seems to be the right answer. Doug
participants (4)
-
Aaron Windsor -
Daniel Mitchell -
Douglas Gregor -
Sebastian Weber