Re: [Boost-users] Bug in BGL with num_vertices( filtered_graph )

From: Douglas Gregor (dgregor_at_[hidden])
Date: 2004-12-19 14:35:13

On Dec 19, 2004, at 12:55 PM, Sebastian Weber wrote:
> I don't see the trouble in renumbering the vertices if there is 
> already a vertex_index-property. It should be possible to build up a 
> map which provides a mapping from filtered vertex index number to real 
> vertex index number. This could also speed up operations (like a loop 
> over all vertices) on filtered graphs, since the vertice predicate 
> would no longer be necessary to check, wheather a vertice is in the 
> set of the filtered vertices or not.

Well, you can't mutate the underlying vertex_index, so you'd need to 
build your own vertex_index mapping. That's doable, but it would have 
to be updated every time the predicate changes. It would have to be an 
option: we can't change the semantics of filtered_graph this way, 
because it is now a very light-weight adaptor but it would become 
significantly heavier if we start dealing with vertex and edge index 
mappings and require stable predicates.

>> more real terms, if we made the change to num_vertices(G) then most 
>> algorithm invocations would start failing because they rely on vertex 
>> indices :(
>
> ... a hint in the docs would be nice. I haven't found any.

The filtered_graph docs for num_vertices say that it returns the number 
of vertices in the underlying graph, and has a footnote giving the 
rationale/explanation that I repeated here. What more information could 
we give here?

        Doug