Bug in BGL with num_vertices( filtered_graph )
Hello there!
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.
My system: boost 1.32.0, g++ 3.3.4, debian sarge.
My graph type is
boost::adjacency_list
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
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
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
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?
Just found it in the docs. Sorry for my blindeness, but I thought of the filtered_graph in terms of a regular graph (so no special num_vertices behaviour). I learned the hard way :-(. Maybe this exception of num_vertices should be mentioned in the description text of filtered_graph along with the reasons you lined out. Sebastian
On Dec 20, 2004, at 4:17 AM, Sebastian Weber wrote:
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?
Just found it in the docs. Sorry for my blindeness, but I thought of the filtered_graph in terms of a regular graph (so no special num_vertices behaviour). I learned the hard way :-(. Maybe this exception of num_vertices should be mentioned in the description text of filtered_graph along with the reasons you lined out.
I've added some text to the filtered_graph description stating this (with a link to the footnote), so hopefully others won't get tripped up by this in the future. Doug
participants (3)
-
Doug Gregor -
Douglas Gregor
-
Sebastian Weber