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