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

From: Sebastian Weber (sebastian.weber_at_[hidden])
Date: 2004-12-19 12:55:31

Hi!

> Actually, it was a tough decision in the design of filtered_graph. If 
> you let num_vertices(g) be the actual number of vertices after 
> filtering, it becomes an O(|V|) operation instead of an O(1) operation. 

That's clear.

> More importantly, external property maps that were based on the 
> vertex_index of the graph will cease to work, because the indices no 
> longer fall in [0, num_vertices(G)) unless you go through the 
> painstaking task of renumbering them (which is not always possible). In 

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.

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

Greetings,

Sebastian