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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-12-17 17:10:37

On Dec 17, 2004, at 2:26 PM, Sebastian Weber wrote:
> I think I found a bug in the BGL concerning the num_vertices function 
> applied to filtered graphs. I use the filtered graph stuff with a 
> vertice predicate. When I loop through the filtered graph with the 
> vertex_iterator, I end up with a loop over all vertices where the 
> predicate is true, just as it is supposed to be. But the function 
> num_vertices on the filtered graph does return me the number of 
> vertices of the original graph and not of the filtered graph.

It's a feature, not a bug :)

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

        Doug