[graph] Adjacency bug after swapping undirected adjacency_list
I've stumbled upon a strange bug in the graph library. It seems that swapping an undirected adjacency_list back and forth to a copy of itself somehow causes some internal damage that becomes apparent when observing adjacenct vertices. I've attached a testcase that shows the problem. I'm using Boost 1.32 with gcc 3.4.2. Regards, Eelis #include <algorithm> #include <iterator> #include <iostream> #include <boost/graph/adjacency_list.hpp> int main () { typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> G; G g (3); add_edge(0, 1, g); add_edge(0, 2, g); G::adjacency_iterator i, j; boost::tie(i, j) = adjacent_vertices(0, g); std::copy(i, j, std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; // Prints "1 2", as it should. { // This should not alter g: G t = g; g.swap(t); g.swap(t); } boost::tie(i, j) = adjacent_vertices(0, g); std::copy(i, j, std::ostream_iterator<int>(std::cout, " ")); std::cout << std::endl; // Prints "1 2 1 2", while it should still be "1 2". }
Analysis: vec_adj_list_impl's operator= calls this->clear() followed by copy_impl(x), where x is the vec_adj_list_impl that is being assigned from. copy_impl(x) _adds_ x's vertices and edges to this->m_vertices and this->m_edges. Therefore, it would seem that clear() should clear both of those. While clear() does immediately do m_vertices.clear(), it doesn't clear m_edges directly, but instead calls clear_dispatch(edge_property_type()). There are two overloads for clear_dispatch(): one function template parameterized by the property type, and a non-template overload that accepts a reference to const no_property. While the former immediately calls m_edges.clear(), the latter does nothing (empty function body). Consequently, in graphs whose edge_property_type is no_property, the edges from 'x' mentioned above are added to the currently existing edges, while they should replace them. Since I don't know the purpose of the clear_dispatch() overload for no_property, I have no idea what the solution should be. I've also attached a simpler testcase. Regards, Eelis #include <algorithm> #include <boost/graph/adjacency_list.hpp> int main () { typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> G; G g (2); add_edge(0, 1, g); G h = g; g = h; assert(num_edges(g) == num_edges(h)); // fails }
On Feb 6, 2005, at 11:36 PM, Eelis van der Weegen wrote:
Analysis:
vec_adj_list_impl's operator= calls this->clear() followed by copy_impl(x), where x is the vec_adj_list_impl that is being assigned from. copy_impl(x) _adds_ x's vertices and edges to this->m_vertices and this->m_edges. Therefore, it would seem that clear() should clear both of those. While clear() does immediately do m_vertices.clear(), it doesn't clear m_edges directly, but instead calls clear_dispatch(edge_property_type()). There are two overloads for clear_dispatch(): one function template parameterized by the property type, and a non-template overload that accepts a reference to const no_property. While the former immediately calls m_edges.clear(), the latter does nothing (empty function body). Consequently, in graphs whose edge_property_type is no_property, the edges from 'x' mentioned above are added to the currently existing edges, while they should replace them.
Thanks for the analysis!
Since I don't know the purpose of the clear_dispatch() overload for no_property, I have no idea what the solution should be.
Once upon a time, there was an optimization in adjacency_list to handle the no_property case. It didn't work, so it was pulled out. Unfortunately, it seems that it wasn't completely removed :( I've checked in a fix. Doug
participants (2)
-
Doug Gregor -
Eelis van der Weegen