Boost C++ Libraries: Ticket #371: remove_edge fails with gcc 3.4.3, likely due to libstdc++ https://svn.boost.org/trac10/ticket/371 <pre class="wiki">In certain situations a call to remove_edge fails to accomplish the removal. I believe this is dues to a problem with std::equal_range in libstdc++ in gcc 3.4.3 but until this is fixed a workaround in boost that does not use equal_range could fix this problem. The attached test program shows the problem. On line 68 removing p24 is ok but removing p12 silently fails, that is after completion the output shows 3 vertices and 3 edges remaining in the graph while it should have only 3 vertices and 2 edges left. The point of failure is the following call stack: (gdb) where #0 std::equal_range&lt;std::_List_iterator&lt;boost::detail::sei_&lt;void*, std::_List_iterator&lt;boost::list_edge&lt;void*, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt; &gt; &gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt; &gt; &gt;, boost::detail::sei_&lt;void*, std::_List_iterator&lt;boost::list_edge&lt;void*, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt; &gt; &gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt; &gt; &gt; (__first= {_M_node = 0x804f098}, __last={_M_node = 0x804f098}, __val=@0xbfffecc0) at /apps/utkej_projects/Argonne/gcc-3.4.3_inst/lib/gcc/i686-pc-linux-gnu/3.4.3/../../../../include/c++/3.4.3/bits/stl_algo.h:3814 #1 0x0804a8e9 in boost::edge_range&lt;boost::detail::adj_list_gen&lt;boost::adjacency_list&lt;boost::listS, boost::listS, boost::bidirectionalS, boost::property&lt;BoostVertexContentType, int*, boost::no_property&gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt;, boost::no_property, boost::listS&gt;, boost::listS, boost::listS, boost::bidirectionalS, boost::property&lt;BoostVertexContentType, int*, boost::no_property&gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt;, boost::no_property, boost::listS&gt;::config, boost::bidirectional_graph_helper_with_property&lt;boost::detail::adj_list_gen&lt;boost::adjacency_list&lt;boost::listS, boost::listS, boost::bidirectionalS, boost::property&lt;BoostVertexContentType, int*, boost::no_property&gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt;, boost::no_property, boost::listS&gt;, boost::listS, boost::listS, boost::bidirectionalS, boost::property&lt;BoostVertexContentType, int*, boost::no_property&gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt;, boost::no_property, boost::listS&gt;::config&gt; &gt; (u=0x804f098, v=0x804f068, g_=@0xbfffeea0) at /apps/utkej_projects/Argonne/boost_1_32_0/boost/graph/detail/adjacency_list.hpp:1485 #2 0x08049d8e in boost::bidirectional_graph_helper_with_property&lt;boost::detail::adj_list_gen&lt;boost::adjacency_list&lt;boost::listS, boost::listS, boost::bidirectionalS, boost::property&lt;BoostVertexContentType, int*, boost::no_property&gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt;, boost::no_property, boost::listS&gt;, boost::listS, boost::listS, boost::bidirectionalS, boost::property&lt;BoostVertexContentType, int*, boost::no_property&gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt;, boost::no_property, boost::listS&gt;::config&gt;::remove_edge (this=0xbfffeea0, e= {&lt;boost::detail::edge_base&lt;boost::bidirectional_tag,void*&gt;&gt; = {m_source = 0x804f098, m_target = 0x804f068}, m_eproperty = 0x804f0d8}) at /apps/utkej_projects/Argonne/boost_1_32_0/boost/graph/detail/adjacency_list.hpp:1067 #3 0x080495aa in boost::remove_edge&lt;boost::detail::edge_desc_impl&lt;boost::bidirectional_tag, void*&gt;, boost::detail::adj_list_gen&lt;boost::adjacency_list&lt;boost::listS, boost::listS, boost::bidirectionalS, boost::property&lt;BoostVertexContentType, int*, boost::no_property&gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt;, boost::no_property, boost::listS&gt;, boost::listS, boost::listS, boost::bidirectionalS, boost::property&lt;BoostVertexContentType, int*, boost::no_property&gt;, boost::property&lt;BoostEdgeContentType, int*, boost::no_property&gt;, boost::no_property, boost::listS&gt;::config&gt; (e= {&lt;boost::detail::edge_base&lt;boost::bidirectional_tag,void*&gt;&gt; = {m_source = 0x804f098, m_target = 0x804f068}, m_eproperty = 0x804f0d8}, g_=@0xbfffeea0) at /apps/utkej_projects/Argonne/boost_1_32_0/boost/graph/detail/adjacency_list.hpp:1110 #4 0x0804906a in main () at gv2.cpp:70 (gdb) Basically the problem is in stl_algo,h when __len on 3801 is initally 2 and __val in our case equals the second element and the condition on 3810 holds true. Note that for this to happen the vertices and edges in the graph need to be created in a certain order. In any case, under the above conditions we compute at 3814 __len to be 0 and __first becomes equal to __last. I.e. we don't ever look at the second element in the list which is the one we SHOULD find. 3784 template&lt;typename _ForwardIterator, typename _Tp&gt; 3785 pair&lt;_ForwardIterator, _ForwardIterator&gt; 3786 equal_range(_ForwardIterator __first, _ForwardIterator __last, 3787 const _Tp&amp; __val) 3788 { 3789 typedef typename iterator_traits&lt;_ForwardIterator&gt;::value_type 3790 _ValueType; 3791 typedef typename iterator_traits&lt;_ForwardIterator&gt;::difference_type 3792 _DistanceType; 3793 3794 // concept requirements 3795 // See comments on lower_bound. 3796 __glibcxx_function_requires(_ForwardIteratorConcept&lt;_ForwardIterator&gt;) 3797 __glibcxx_function_requires(_SameTypeConcept&lt;_Tp, _ValueType&gt;) 3798 __glibcxx_function_requires(_LessThanComparableConcept&lt;_Tp&gt;) 3799 __glibcxx_requires_partitioned(__first, __last, __val); 3800 3801 _DistanceType __len = std::distance(__first, __last); 3802 _DistanceType __half; 3803 _ForwardIterator __middle, __left, __right; 3804 3805 while (__len &gt; 0) 3806 { 3807 __half = __len &gt;&gt; 1; 3808 __middle = __first; 3809 std::advance(__middle, __half); 3810 if (*__middle &lt; __val) 3811 { 3812 __first = __middle; 3813 ++__first; 3814 __len = __len - __half - 1; 3815 } 3816 else if (__val &lt; *__middle) Subsequently the rng returns the end/end and the edge in question never gets deleted because of edge_range(source(e, g), target(e, g), g); rng.first = std::find(rng.first, rng.second, e); if (rng.first != rng.second) remove_edge(rng.first); } in graph/detail/adjacency_list.hpp unfortunately without warning. Temporarily not using equal_range should fix it. </pre> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/371 Trac 1.4.3 nobody Sat, 19 Mar 2005 07:06:01 GMT <link>https://svn.boost.org/trac10/ticket/371#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/371#comment:1</guid> <description> <pre class="wiki">Logged In: NO Actually, as I was trying to come up with an list&lt;int&gt; example for this I realized the obvious, i.e. that the whole equal_range approach only makes sense when we have a list that has been populated in the order implied by the comparison operator used on line 3810 in stl_algo.h (see above). So, I suspect the boost edge lists are not populated in that order and consequently it does not make sense to call equal_range for an unordered list (notice that in my example code I use listS, not vecS). I haven't really verified this, but now it seems to make sense. </pre> </description> <category>Ticket</category> </item> <item> <dc:creator>Douglas Gregor</dc:creator> <pubDate>Mon, 02 May 2005 15:48:02 GMT</pubDate> <title>status changed https://svn.boost.org/trac10/ticket/371#comment:2 https://svn.boost.org/trac10/ticket/371#comment:2 <ul> <li><strong>status</strong> <span class="trac-field-old">assigned</span> → <span class="trac-field-new">closed</span> </li> </ul> <pre class="wiki">Logged In: YES user_id=249098 Fixed in 1.33.0. </pre> Ticket